O KNN é um algoritmo de aprendizado discriminativo?

17

Parece que o KNN é um algoritmo de aprendizado discriminativo, mas não consigo encontrar fontes online que confirmem isso.

O KNN é um algoritmo de aprendizado discriminativo?

jpmuc
fonte

Respostas:

19

O KNN é um algoritmo discriminativo, pois modela a probabilidade condicional de uma amostra pertencente a uma determinada classe. Para ver isso, considere como se chega à regra de decisão dos kNNs.

Uma etiqueta de classe corresponde a um conjunto de pontos que pertencem a alguma região no espaço recurso R . Se você extrair pontos de amostra da distribuição de probabilidade real, p(x) , independentemente, então a probabilidade de extrair uma amostra dessa classe é:

P=Rp(x)dx

E se você tiver pontos? A probabilidade de que K pontos desses N pontos caiam na região R segue a distribuição binomial, P r o b ( K ) = ( NNKNR

Prob(K)=(NK)PK(1-P)N-K

Como esta distribuição tem um pico acentuado, de modo que a probabilidade pode ser aproximada pelo seu valor médio KN . Uma aproximação adicional é que a distribuição de probabilidade sobreRpermanece aproximadamente constante, de modo que se pode aproximar a integral por, P=Rp(x)dxp(x)V em queVé o volume total da região. Sob essas aproximaçõesp(x)KKNR

P=Rp(x)dxp(x)V
V .p(x)KNV

Agora, se tivéssemos várias classes, poderíamos repetir a mesma análise para cada uma, o que nos daria, ondeKké a quantidade de pontos da classekque se enquadra nessa região eNké o número total de pontos pertencentes à classeCk. AvisoΣkNk=N.

p(x|Ck)=KkNkV
KkkNkCkkNk=N

Repetindo a análise com a distribuição binomial, é fácil ver que podemos estimar o anterior .P(Ck)=NkN

Usando a regra de Bayes, que é a regra para os kNNs.

P(Ck|x)=p(x|Ck)p(Ck)p(x)=KkK
jpmuc
fonte
2
A referência não inclui nenhuma informação sobre o KNN. É o caminho certo?
bayerj
1
Eu pretendia enfatizar o que é entendido por um algoritmo discriminativo versus um generativo.
jpmuc
5

Responder por @jpmuc não parece ser preciso. Modelos generativos modelam a distribuição subjacente P (x / Ci) e depois usam o teorema de Bayes para encontrar as probabilidades posteriores. Isso é exatamente o que foi mostrado nessa resposta e conclui exatamente o oposto. : O

Para que o KNN seja um modelo generativo, poderemos gerar dados sintéticos. Parece que isso é possível quando temos alguns dados de treinamento inicial. Porém, a partir de nenhum dado de treinamento e geração de dados sintéticos não é possível. Portanto, o KNN não se encaixa muito bem com modelos generativos.

Pode-se argumentar que o KNN é um modelo discriminativo porque podemos traçar limites discriminantes para classificação, ou podemos calcular o P posterior (Ci / x). Mas tudo isso também é verdade no caso dos modelos generativos. Um verdadeiro modelo discriminativo não diz nada sobre a distribuição subjacente. Mas, no caso do KNN, sabemos muito sobre a distribuição subjacente; na verdade, estamos armazenando todo o conjunto de treinamento.

Portanto, parece que o KNN está a meio caminho entre os modelos generativo e discriminativo. Provavelmente, é por isso que o KNN não é classificado em nenhum dos modelos generativos ou discriminatórios em artigos de renome. Vamos chamá-los de modelos não paramétricos.

Binu Jasim
fonte
Eu não concordo. "Classificadores generativos aprendem um modelo da probabilidade conjunta, p (x, y), das entradas x e o rótulo y, e fazem suas previsões usando as regras de Bayes para calcular p (ylx) e, em seguida, escolhendo o rótulo mais provável y Classificadores discriminativos modelam diretamente o p (ylx) posterior, ou aprendem um mapa direto das entradas x aos rótulos das classes ". Veja "Classificadores Discriminativos vs. Geradores: Uma comparação entre regressão logística e Bayes ingênuo."
jpmuc
1

Concordo que o kNN é discriminatório. O motivo é que ele não armazena nem tenta explicitamente aprender um modelo (probabilístico) que explica os dados (ao contrário de, por exemplo, Naive Bayes).

A resposta de juampa me confunde, pois, no meu entender, um classificador generativo é aquele que tenta explicar como os dados são gerados (por exemplo, usando um modelo), e essa resposta diz que é discriminatório por esse motivo ...

Amir
fonte
1
Um modelo generativo aprende P (Ck, X), para que você possa gerar mais dados usando essa distribuição conjunta. Em contraste, um modelo discriminativo aprenderia P (Ck | X). É para isso que o @juampa aponta com o KNN.
Zhubarb
1
No momento da classificação, tanto generativo quanto discriminativo acabam usando probabilidades condicionais para fazer previsões. No entanto, os classificadores generativos aprendem a probabilidade conjunta e, segundo a regra de Bayes, calculam o condicional, enquanto, em discriminativo, um classificador calcula diretamente o condicional ou fornece uma aproximação para isso da melhor maneira possível.
Rapaio # 8/14