Aprendizado agnóstico sobre distribuições arbitrárias

$D$ $\{0,1\}^d\times \{0,1\}$ $C$ $f:\{0,1\}^d\rightarrow\{0,1\}$ $f \in C$

e r r (f, D) = \underset{(x, y) \sim D}{Pr} [f (x) \neq y]

$err(f,D) = \Pr_{(x,y) \sim D}[f(x) \neq y]$

O P T (C, D) = min_{f \in C} e r r (f, D)

$OPT(C,D) = \min_{f \in C}\ err(f,D)$ Digamos que um algoritmo

A

$A$ aprenda agnósticamente

C

$C$ sobre qualquer distribuição, se para qualquer

D

$D$ ele puder com probabilidade

2 / 3

$2/3$ encontrar uma função

f

$f$ tal que

e r r (f, D) \leq O P T (C, D) + ϵ

$err(f,D) \leq OPT(C,D) + \epsilon$ , dado o tempo e um número de amostras de

D

$D$ que é delimitado por um polinômio em

d

$d$ e

1 / ϵ

$1/\epsilon$ .

Pergunta: Quais classes de funções $C$ são conhecidas por serem aprendidas de forma agnóstica em distribuições arbitrárias?

Nenhuma aula é muito simples! Sei que nem mesmo conjunções monótonas são aprendidas de forma agnóstica sobre distribuições arbitrárias; portanto, só estou procurando classes de funções não triviais.

reference-request machine-learning lg.learning Aaron Roth
fonte

vale ressaltar, para os não iniciados, que o aprendizado agnóstico está focado no caso quando OPT (C, D)> 0 (ou seja, você tem a classe de hipótese errada

Suresh Venkat

Bom ponto. No caso especial, quando OPT (C, D) = 0, esse é o aprendizado do PAC e é muito mais fácil. Para um aprendizado agnóstico, a garantia deve se manter, não importa o que seja OPT (C, D).

Aaron Roth

Há também o caso "PAC com ruído de classificação" em que OPT (C, D)> 0, e mesmo que você tenha a classe de hipótese correta (configuração realizável), há algum erro porque os rótulos são aleatoriamente invertidos devido ao ruído ... gostaria que os nomes das diferentes configurações fossem menos confusos.

Lev Reyzin

Isso parece aprendizagem agnóstico com um limite superior de OPT (C, D)

Suresh Venkat

Não exatamente, porque o ruído não pode ser arbitrário no modelo de classificação de ruído. Portanto, se houver algum padrão de ruído contraditório que dificulte o aprendizado (ou encontre o minimizador de risco empírico) no modelo agnóstico, isso pode não ocorrer com frequência no modelo de ruído de classificação (ou seja, cai no parâmetro delta do PAC).

Lev Reyzin

Respostas:

Se nenhuma aula é muito simples, aqui estão algumas aulas aprendidas de forma agnóstica no PAC. Em resposta aos comentários, as classes com muitas hipóteses polinomialmente são riscadas:

~~árvores de decisão de profundidade constante (e outras classes com apenas várias hipóteses)~~
~~hiperplanos em (apenas hipóteses produzindo marcações distintas) $R^2$ $O(n^2)$~~
uniões de intervalos (programação dinâmica)
paridade em alguns dos primeiros de bits (veja isto e isto ) $\log(k)\log\log(k)$ $n$
~~outras classes de hipóteses em configurações de baixa dimensão.~~

Praticamente tudo o mais é NP-Difícil de aprender (pelo menos adequadamente) de forma independente ao PAC.

O tutorial de Adam Kalai sobre aprendizado agnóstico também pode lhe interessar.

Lev Reyzin
fonte

Obrigado. Portanto, árvores de decisão de profundidade constante, hiperplanos bidimensionais (presumo que as outras configurações de baixa dimensão a que você se refere) caem na categoria de ter apenas polinomialmente muitas funções, que podem ser aprendidas por exaustão. Paridades no log (k) bits do loglog (k) e uniões de intervalos são interessantes, pois contêm muitas funções superpolinomialmente. Existem outros como estes?

Aaron Roth

Certo, embora existam infinitos hiperplanos em R ^ 2, apenas O (n ^ 2) escreveu a classificação dos pontos de dados de maneira diferente. Não conheço nenhuma outra classe interessante, mas se pensar / encontrar alguma, editarei minha resposta.

Lev Reyzin

então você quer classes de dimensão VC ilimitadas?

Suresh Venkat

dimensão VC ilimitada seria certamente interessante, mas grande finitos (para d fixa) classes já são extremamente interessante (e parecem ser raros)

Aaron Roth

@LevReyzin O link para as palestras do Kalai não está funcionando. Você poderia gentilmente consertar isso? Eu procurei na net, mas não consegui encontrar isso também.

Anirbit 03/03