Почему Naive Bayes не может решить XOR

Question

Я недавно начал понимать алгоритмы, связанные с обработкой естественного языка, и столкнулся с различными сайтами, которые указывают на то, что Naive Bayes не может захватить концепцию XOR. Во-первых, я не понимаю, что такое проблема XOR. Может кто-то объяснить, что проблема XOR с простым примером классификации, если это возможно.

Answer 1

Проблема XOR - это самая простая проблема, которая не является линейно разделяемой. Представьте, что у вас есть две булевы переменные X и Y, а целевое значение, которое вы хотите «предсказать», является результатом XORing двух переменных. То есть, только если один (но не другой) равен 1, вы хотите предсказать 1 как результат, а 0 в противном случае. Немного более наглядно:

Y^
1 | XOR(x=0,y=1)=1 XOR(x=1,y=1)=0 
    | 
0 | XOR(x=0,y=0)=0 XOR(x=1,y=0)=1 
    +-------------------------------> 
      0    1  X 

Как вы можете видеть, для четырех «точек» моего «сюжета» выше (X по горизонтали, Y вертикально, представьте, что запятые являются «точками», если вы хотите), вы не можете нарисовать прямую линию, которая разделяет два исхода (два 1s в верхнем левом и нижнем правом углу, а также два 0s, также в противоположных углах). Так что linear классификаторы, которые моделируют разделение классов с использованием прямых линий, не могут решить проблемы такого рода.

Теперь, что касается Наивного Байеса, он моделирует независимых событий. Учитывая только X и Y, он может моделировать распределение xs, и он может моделировать ys, но он не моделирует никакого отношения между двумя переменными. То есть, чтобы моделировать функцию XOR, классификатор должен был бы наблюдать обе переменные в то же время. Только предсказание, основанное на состоянии X без учета состояния Y (и наоборот), не может привести к правильному решению этой проблемы. Следовательно, классификатор Naive Bayes также является линейным классификатором.