Задача XOR

Задача XOR (исключающее ИЛИ) — классическая задача в области нейронных сетей и машинного обучения, которая иллюстрирует фундаментальное ограничение однослойного персептрона и демонстрирует необходимость использования многослойных архитектур для решения нелинейно разделимых проблем. Суть задачи заключается в построении классификатора для логической функции XOR, которая возвращает истинное значение (1), если её два бинарных входа различны, и ложное (0), если они совпадают. Задача XOR является простейшим случаем функции чётности (PARITY) для двух бит и широко используется как педагогический пример для объяснения принципов работы и ограничений нейросетей.

Постановка задачи

Даны четыре точки в двумерном пространстве признаков, соответствующие всем возможным комбинациям бинарных входов $x_1, x_2 \in \{0, 1\}$ :

$(0, 0) \rightarrow 0$
$(0, 1) \rightarrow 1$
$(1, 0) \rightarrow 1$
$(1, 1) \rightarrow 0$

Эти точки располагаются в углах единичного квадрата. Точки, принадлежащие разным классам (0 и 1), расположены по диагонали. Задача состоит в том, чтобы найти классификатор, который правильно разделит эти два класса.

Нелинейная разделимость

Ключевое свойство задачи XOR заключается в том, что она не является линейно разделимой. Это означает, что невозможно провести одну прямую линию на плоскости, которая бы разделила точки двух классов. Доказательство этого факта может быть выполнено геометрически или алгебраически. Например, любая попытка провести линию, разделяющую точки (0,0) и (1,1) от точек (0,1) и (1,0), обречена на неудачу, поскольку эти множества не являются выпуклыми и разделимыми гиперплоскостью.

Ограничения однослойного персептрона

Персептрон, предложенный Фрэнком Розенблаттом в 1957 году, представляет собой простейшую нейронную сеть, состоящую из одного слоя искусственных нейронов. Его выход для вектора признаков $\mathbf{x}$ вычисляется как $y = \sigma(w_1 x_1 + w_2 x_2 + b)$ , где $\sigma$ — ступенчатая функция активации, $w_i$ — веса, $b$ — смещение.

Решение, которое может найти персептрон, эквивалентно построению линейной разделяющей поверхности (прямой на плоскости или гиперплоскости в многомерном пространстве). Было математически доказано, что персептрон не может выучить функцию XOR, поскольку она не является линейно разделимой. Это означает, что какой бы набор весов $w_1, w_2, b$ ни был выбран, всегда найдётся по крайней мере одна точка, которая будет классифицирована неверно.

Историческое значение: «Зима ИИ»

Доказательство неспособности персептрона решить задачу XOR стало центральным аргументом в книге Марвина Минского и Сеймура Пейперта «Персептроны» (1969 год). Авторы провели строгий математический анализ возможностей и ограничений однослойных персептронов. Хотя Минский и Пейперт знали, что добавление скрытого слоя может решить проблему, они указали на отсутствие в то время эффективного алгоритма обучения для таких сетей.

Критика, прозвучавшая в книге, оказала разрушительное влияние на область исследований нейронных сетей. Финансирование этой области было резко сокращено, а интерес к нейронным сетям практически угас на долгие годы. Этот период в истории искусственного интеллекта получил название «первая зима ИИ», которая длилась примерно с 1969 по середину 1980-х годов.

Решение задачи с помощью многослойного персептрона

Проблема XOR решается с помощью добавления одного или нескольких скрытых слоёв нейронов, что приводит к созданию многослойного персептрона (MLP). Ключевая идея заключается в том, чтобы разложить нелинейную функцию XOR на комбинацию более простых, линейно разделимых функций.

Как именно работает скрытый слой? Рассмотрим архитектуру с двумя нейронами в скрытом слое и одним выходным нейроном. Каждый нейрон скрытого слоя вычисляет взвешенную сумму своих входов и пропускает её через нелинейную функцию активации (например, сигмоиду или гиперболический тангенс).

Пример конкретных весов. Пусть скрытый слой состоит из двух нейронов:

Первый нейрон (назовём его $h_1$ ) настроен на распознавание ситуации, когда хотя бы один вход равен 1, но не оба одновременно (это можно сделать, задав веса $w_{11}=1, w_{12}=1$ и смещение $b_1=-0.5$ ). Тогда $h_1$ активируется (даёт выход близкий к 1) для точек (0,1) и (1,0), но не для (0,0) и (1,1). Это фактически реализует функцию OR без случая (1,1).
Второй нейрон (назовём его $h_2$ ) настроен на распознавание ситуации, когда оба входа равны 1. Веса $w_{21}=1, w_{22}=1$ и смещение $b_2=-1.5$ дают активацию, близкую к 1, только для точки (1,1). Это реализует функцию AND.

Теперь выходной нейрон комбинирует сигналы $h_1$ и $h_2$ . Если мы зададим веса $w_{out,1}=1$ , $w_{out,2}=-1$ и смещение $b_{out}=0.5$ , то выходной нейрон вычислит разность $h_1 - h_2$ , что даёт 1 для точек (0,1) и (1,0) (где $h_1=1, h_2=0$ ) и 0 для (0,0) и (1,1) (в первом случае оба 0, во втором $h_1=1, h_2=1$ и разность равна 0).

Таким образом, скрытый слой преобразует исходное пространство признаков $(x_1, x_2)$ в новое двумерное пространство $(h_1, h_2)$ , в котором точки становятся линейно разделимыми. В этом новом пространстве четыре точки располагаются следующим образом: (0,0) переходит в (0,0), (1,1) — в (1,1) (эти два класса лежат на диагонали), а (0,1) и (1,0) — в (1,0) и (0,1) соответственно. Теперь их можно разделить прямой линией. Обучение такой сети стало возможным благодаря разработке и популяризации алгоритма обратного распространения ошибки (backpropagation) в 1986 году, что положило конец «зиме ИИ» и привело к возрождению интереса к нейронным сетям.

Теорема о универсальной аппроксимации

Способность многослойных нейронных сетей решать задачу XOR является частным случаем более общего результата — теоремы о универсальной аппроксимации. Согласно этой теореме, многослойный персептрон с по крайней мере одним скрытым слоем и нелинейной функцией активации может аппроксимировать любую непрерывную функцию на компактном множестве с любой желаемой точностью. Это теоретическое обоснование делает MLP мощным инструментом для решения широкого круга задач, выходящих за рамки простой линейной классификации.

Альтернативные подходы к решению задачи XOR

Хотя многослойный персептрон является классическим решением, задача XOR может быть решена и другими методами, которые не используют нейронные сети:

Признаки высшего порядка (полиномиальные признаки). Можно вручную добавить нелинейные комбинации исходных признаков, например, перемножить $x_1$ и $x_2$ . Тогда линейный классификатор в пространстве признаков $(x_1, x_2, x_1 x_2)$ легко разделит точки, поскольку функция XOR может быть выражена как $x_1 + x_2 - 2 x_1 x_2$ . Это пример ручного инжиниринга признаков, который, однако, не масштабируется на сложные задачи.

Метод опорных векторов (SVM) с ядром. SVM с нелинейным ядром (например, RBF-ядро или полиномиальное ядро) способен решить XOR, поскольку ядро неявно отображает данные в пространство признаков более высокой размерности, где они становятся линейно разделимыми. Для XOR достаточно полиномиального ядра второй степени.

Метод k ближайших соседей (k-NN). Этот непараметрический алгоритм классификации решает XOR «естественным образом», поскольку он не строит линейной разделяющей поверхности, а основывается на голосовании ближайших соседей. Для четырех точек XOR при $k=1$ или $k=3$ классификация будет безошибочной (при условии правильного выбора метрики).

Деревья решений. Двоичное дерево решений может идеально разделить XOR, последовательно задавая вопросы о значениях признаков. Например, первое разбиение по $x_1$ , второе — по $x_2$ . Это показывает, что древовидные модели не страдают от проблемы линейной неразделимости.

Эти альтернативы подчёркивают, что задача XOR является не столько «проблемой» для машинного обучения в целом, сколько иллюстрацией ограничений конкретного класса моделей (линейных классификаторов и однослойных сетей).

Современное значение

Задача XOR сохраняет своё значение и в современных исследованиях. Она используется как простой тестовый полигон для изучения:

Динамики обучения нейронных сетей с помощью стохастического градиентного спуска (SGD).
Явления переобучения и обобщения в различных архитектурах.
Анализа поведения сетей в условиях «нулевого зазора» (zero-margin), когда данные лежат непосредственно на разделяющей поверхности.

Таким образом, задача XOR, начав свой путь как демонстрация фатального недостатка ранних нейросетей, превратилась в фундаментальный учебный пример и важный инструмент для понимания принципов глубокого обучения.

См. также

Примечания

Литература

Minsky, M., & Papert, S. (1969). Perceptrons. MIT Press.
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. Nature, 323(6088), 533-536.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_XOR»

@@ Строка 1: / Строка 1: @@
-=== Задача XOR ===
+== Задача XOR ==
-'''Задача XOR''' (исключающее ИЛИ, '''eXclusive OR''') — одна из ключевых задач в области [[Машинное обучение|машинного обучения]] и [[Искусственные нейронные сети|искусственных нейронных сетей]]. Она представляет собой простую, но концептуально важную проблему [[Бинарная классификация|бинарной классификации]], которая продемонстрировала фундаментальные ограничения однослойных [[Перцептрон|перцептронов]] и сыграла ключевую роль в развитии [[Глубокое обучение|глубокого обучения]] .
+'''Задача XOR''' (исключающее ИЛИ) — классическая задача в области [[искусственные нейронные сети|нейронных сетей]] и [[машинное обучение|машинного обучения]], которая иллюстрирует фундаментальное ограничение [[персептрон|однослойного персептрона]] и демонстрирует необходимость использования [[многослойный персептрон|многослойных архитектур]] для решения нелинейно разделимых проблем. Суть задачи заключается в построении классификатора для логической функции XOR, которая возвращает истинное значение (1), если её два бинарных входа различны, и ложное (0), если они совпадают. Задача XOR является простейшим случаем функции [[четность|чётности]] (PARITY) для двух бит и широко используется как педагогический пример для объяснения принципов работы и ограничений нейросетей.
-=== Определение ===
+== Постановка задачи ==
-Задача XOR определяется [[Таблица истинности|таблицей истинности]] для двух [[Булева переменная|булевых переменных]] <math>x_1</math> и <math>x_2</math>. Функция XOR возвращает 1 (истина), если значения переменных различны, и 0 (ложь), если они совпадают .
+Даны четыре точки в двумерном пространстве признаков, соответствующие всем возможным комбинациям бинарных входов <tex>x_1, x_2 \in \{0, 1\}</tex>:
+* <tex>(0, 0) \rightarrow 0</tex>
+* <tex>(0, 1) \rightarrow 1</tex>
+* <tex>(1, 0) \rightarrow 1</tex>
+* <tex>(1, 1) \rightarrow 0</tex>
-{| class="wikitable"
+Эти точки располагаются в углах единичного квадрата. Точки, принадлежащие разным классам (0 и 1), расположены по диагонали. Задача состоит в том, чтобы найти классификатор, который правильно разделит эти два класса.
-|+ Таблица истинности для функции XOR
-|-
-! <math>x_1</math> !! <math>x_2</math> !! <math>x_1 \oplus x_2</math>
-|-
-| 0 || 0 || 0
-|-
-| 0 || 1 || 1
-|-
-| 1 || 0 || 1
-|-
-| 1 || 1 || 0
-|}
-С точки зрения машинного обучения, задача состоит в том, чтобы обучить модель правильно предсказывать выходное значение для всех четырех возможных комбинаций входных данных.
+== Нелинейная разделимость ==
-=== Свойства и значение ===
+Ключевое свойство задачи XOR заключается в том, что она не является [[линейная разделимость|линейно разделимой]]. Это означает, что невозможно провести одну прямую линию на плоскости, которая бы разделила точки двух классов. Доказательство этого факта может быть выполнено геометрически или алгебраически. Например, любая попытка провести линию, разделяющую точки (0,0) и (1,1) от точек (0,1) и (1,0), обречена на неудачу, поскольку эти множества не являются выпуклыми и разделимыми гиперплоскостью.
-Главное свойство задачи XOR, делающее её значимой для теории машинного обучения, — это '''нелинейная разделимость''' данных . Это означает, что невозможно провести единственную прямую линию ([[Гиперплоскость|гиперплоскость]] в двумерном пространстве), которая разделила бы точки с выходом 0 и 1 на плоскости .
+== Ограничения однослойного персептрона ==
-*   '''Простейшая нелинейно разделимая функция''': XOR — это самая простая [[Булева функция|булева функция]], которая не является линейно разделимой, что делает её идеальным тестом для проверки вычислительных возможностей моделей .
+[[Персептрон]], предложенный [[Фрэнк Розенблатт|Фрэнком Розенблаттом]] в 1957 году, представляет собой простейшую нейронную сеть, состоящую из одного слоя [[искусственный нейрон|искусственных нейронов]]. Его выход для вектора признаков <tex>\mathbf{x}</tex> вычисляется как <tex>y = \sigma(w_1 x_1 + w_2 x_2 + b)</tex>, где <tex>\sigma</tex> — ступенчатая функция активации, <tex>w_i</tex> — веса, <tex>b</tex> — смещение.
-*   '''Функциональная полнота''': В комбинации с другими логическими операциями, такими как [[Логическое И|AND]] и константой 1, XOR может быть использована для построения любой булевой функции, что подчеркивает её теоретическую важность в логике и вычислениях .
-*   '''Частный случай функции [[Чётность|PARITY]]''': XOR является двумерным случаем более общей задачи на четность (PARITY), которая часто используется в теории вычислительной сложности .
-=== Роль в истории нейронных сетей ===
+Решение, которое может найти персептрон, эквивалентно построению линейной разделяющей поверхности (прямой на плоскости или гиперплоскости в многомерном пространстве). Было математически доказано, что персептрон не может выучить функцию XOR, поскольку она не является линейно разделимой. Это означает, что какой бы набор весов <tex>w_1, w_2, b</tex> ни был выбран, всегда найдётся по крайней мере одна точка, которая будет классифицирована неверно.
-==== Кризис перцептрона ====
+=== Историческое значение: «Зима ИИ» ===
-В конце 1960-х годов [[Марвин Минский]] и [[Сеймур Пейперт]] в своей книге «[[Перцептроны (книга)|Перцептроны]]» представили строгое математическое доказательство того, что однослойный перцептрон не способен решить задачу XOR . Это доказательство основывалось на линейной природе решающего правила перцептрона: его выход определяется знаком взвешенной суммы входов, что всегда соответствует линейной разделяющей поверхности .
-Доказательство невозможности для однослойного перцептрона:
+Доказательство неспособности персептрона решить задачу XOR стало центральным аргументом в книге [[Марвин Минский|Марвина Минского]] и [[Сеймур Пейперт|Сеймура Пейперта]] «'''Персептроны'''» (1969 год). Авторы провели строгий математический анализ возможностей и ограничений однослойных персептронов. Хотя Минский и Пейперт знали, что добавление скрытого слоя может решить проблему, они указали на отсутствие в то время эффективного алгоритма обучения для таких сетей.
-Для классификации точек (0,0), (0,1), (1,0) и (1,1) с использованием функции шага <math>f(x) = \text{step}(w_1 x_1 + w_2 x_2 + b)</math> необходимо найти такие веса <math>w_1, w_2</math> и смещение <math>b</math>, чтобы выполнялись следующие неравенства :
-*   Для (0,0) → 0: <math>b < 0</math>
-*   Для (1,1) → 0: <math>w_1 + w_2 + b < 0</math>
-*   Для (0,1) → 1: <math>w_2 + b \ge 0</math>
-*   Для (1,0) → 1: <math>w_1 + b \ge 0</math>
-Сложение двух последних неравенств дает <math>w_1 + w_2 + 2b \ge 0</math>. Это противоречит двум первым, из которых следует <math>w_1 + w_2 + 2b < 0</math>. Таким образом, система неравенств несовместна .
+Критика, прозвучавшая в книге, оказала разрушительное влияние на область исследований нейронных сетей. Финансирование этой области было резко сокращено, а интерес к нейронным сетям практически угас на долгие годы. Этот период в истории искусственного интеллекта получил название «'''[[Зима ИИ|первая зима ИИ]]'''», которая длилась примерно с 1969 по середину 1980-х годов.
-Этот результат имел катастрофические последствия для области исследований нейронных сетей. Он продемонстрировал фундаментальные ограничения существующих на тот момент моделей и привел к так называемой «[[Зима ИИ|зиме ИИ]]» (AI Winter) — периоду значительного сокращения финансирования и интереса к нейросетевым исследованиям, который длился примерно с 1969 по 1986 год .
+== Решение задачи с помощью многослойного персептрона ==
-==== Решение и возрождение ====
+Проблема XOR решается с помощью добавления одного или нескольких '''[[скрытый слой|скрытых слоёв]]''' нейронов, что приводит к созданию '''[[многослойный персептрон|многослойного персептрона]]''' (MLP). Ключевая идея заключается в том, чтобы разложить нелинейную функцию XOR на комбинацию более простых, линейно разделимых функций.
-Ирония судьбы заключается в том, что решение задачи XOR было известно ещё до публикации Минского и Пейперта. Оно требует использования ''многослойной'' архитектуры .
-'''Ключевое решение''': задача XOR может быть решена с помощью двухслойной нейронной сети, которая вычисляет композицию более простых линейно разделимых функций . Например:
+Как именно работает скрытый слой? Рассмотрим архитектуру с двумя нейронами в скрытом слое и одним выходным нейроном. Каждый нейрон скрытого слоя вычисляет взвешенную сумму своих входов и пропускает её через нелинейную функцию активации (например, сигмоиду или гиперболический тангенс).
-<math>XOR(x_1, x_2) = OR(AND(x_1, NOT(x_2)), AND(NOT(x_1), x_2))</math>
-или, что эквивалентно,
-<math>XOR(x_1, x_2) = AND(OR(x_1, x_2), NAND(x_1, x_2))</math> .
-В нейронной сети эта композиция реализуется с помощью скрытого слоя (hidden layer). Нейроны в скрытом слое создают новое представление данных (преобразуют пространство признаков), в котором исходная задача становится линейно разделимой . Например, один нейрон может активироваться как аналог логической функции OR, а другой — как NAND. Нейрон выходного слоя, в свою очередь, комбинирует их выходы, выполняя операцию AND, что в итоге дает правильный результат XOR .
+'''Пример конкретных весов'''. Пусть скрытый слой состоит из двух нейронов:
+* Первый нейрон (назовём его <tex>h_1</tex>) настроен на распознавание ситуации, когда хотя бы один вход равен 1, но не оба одновременно (это можно сделать, задав веса <tex>w_{11}=1, w_{12}=1</tex> и смещение <tex>b_1=-0.5</tex>). Тогда <tex>h_1</tex> активируется (даёт выход близкий к 1) для точек (0,1) и (1,0), но не для (0,0) и (1,1). Это фактически реализует функцию '''OR''' без случая (1,1).
+* Второй нейрон (назовём его <tex>h_2</tex>) настроен на распознавание ситуации, когда оба входа равны 1. Веса <tex>w_{21}=1, w_{22}=1</tex> и смещение <tex>b_2=-1.5</tex> дают активацию, близкую к 1, только для точки (1,1). Это реализует функцию '''AND'''.
+Теперь выходной нейрон комбинирует сигналы <tex>h_1</tex> и <tex>h_2</tex>. Если мы зададим веса <tex>w_{out,1}=1</tex>, <tex>w_{out,2}=-1</tex> и смещение <tex>b_{out}=0.5</tex>, то выходной нейрон вычислит разность <tex>h_1 - h_2</tex>, что даёт 1 для точек (0,1) и (1,0) (где <tex>h_1=1, h_2=0</tex>) и 0 для (0,0) и (1,1) (в первом случае оба 0, во втором <tex>h_1=1, h_2=1</tex> и разность равна 0).
-Истинное возрождение интереса к нейронным сетям произошло в 1986 году, когда был популяризован [[Алгоритм обратного распространения ошибки|алгоритм обратного распространения ошибки]] (backpropagation), позволивший эффективно обучать веса в многослойных сетях и, как следствие, решать задачу XOR и гораздо более сложные проблемы .
+Таким образом, скрытый слой преобразует исходное пространство признаков <tex>(x_1, x_2)</tex> в новое двумерное пространство <tex>(h_1, h_2)</tex>, в котором точки становятся линейно разделимыми. В этом новом пространстве четыре точки располагаются следующим образом: (0,0) переходит в (0,0), (1,1) — в (1,1) (эти два класса лежат на диагонали), а (0,1) и (1,0) — в (1,0) и (0,1) соответственно. Теперь их можно разделить прямой линией. Обучение такой сети стало возможным благодаря разработке и популяризации '''[[алгоритм обратного распространения ошибки|алгоритма обратного распространения ошибки]]''' (backpropagation) в 1986 году, что положило конец «зиме ИИ» и привело к возрождению интереса к нейронным сетям.
-=== Методы решения ===
+=== Теорема о универсальной аппроксимации ===
-Современное машинное обучение предлагает множество подходов для решения задачи XOR, все они так или иначе используют нелинейность:
+Способность многослойных нейронных сетей решать задачу XOR является частным случаем более общего результата — '''[[теорема о универсальной аппроксимации|теоремы о универсальной аппроксимации]]'''. Согласно этой теореме, многослойный персептрон с по крайней мере одним скрытым слоем и нелинейной функцией активации может аппроксимировать любую непрерывную функцию на компактном множестве с любой желаемой точностью. Это теоретическое обоснование делает MLP мощным инструментом для решения широкого круга задач, выходящих за рамки простой линейной классификации.
-*   '''[[Многослойный перцептрон]] (MLP)''': Классическое решение с одним или несколькими скрытыми слоями и нелинейными [[Функция активации|функциями активации]], такими как [[Сигмоида|сигмоида]], [[ReLU|ReLU]] или [[Гиперболический тангенс|гиперболический тангенс]] .
+== Альтернативные подходы к решению задачи XOR ==
-*   '''[[Метод опорных векторов]] (SVM)''': Использование [[Ядровой метод|ядерного метода]], например, [[Полиномиальное ядро|полиномиального ядра]] второго порядка <math>K(x, x_i) = (1 + x^T x_i)^2</math>, позволяет отобразить исходные данные в более высокоразмерное пространство, где они становятся линейно разделимыми .
-*   '''[[Радиальная базисная функция]] (RBF)''': Сети на основе RBF также могут решить задачу XOR, используя нелинейное преобразование входного пространства .
-*   '''Нестандартные функции активации''': Недавние исследования показывают, что даже один нейрон с определенными функциями активации, такими как [[Growing Cosine Unit|Growing Cosine Unit]] (GCU) или [[Parametric Rectified Linear Unit|Parametric ReLU]] (PReLU) с отрицательным параметром наклона, может решить задачу XOR, демонстрируя потенциал для создания более компактных архитектур .
-=== Современное значение ===
+Хотя многослойный персептрон является классическим решением, задача XOR может быть решена и другими методами, которые не используют нейронные сети:
-Несмотря на кажущуюся простоту, задача XOR остается важным педагогическим инструментом и теоретическим эталоном . Она наглядно иллюстрирует:
+* '''Признаки высшего порядка (полиномиальные признаки)'''. Можно вручную добавить нелинейные комбинации исходных признаков, например, перемножить <tex>x_1</tex> и <tex>x_2</tex>. Тогда линейный классификатор в пространстве признаков <tex>(x_1, x_2, x_1 x_2)</tex> легко разделит точки, поскольку функция XOR может быть выражена как <tex>x_1 + x_2 - 2 x_1 x_2</tex>. Это пример ручного инжиниринга признаков, который, однако, не масштабируется на сложные задачи.
-*   Необходимость нелинейности в моделях машинного обучения для решения реальных задач.
-*   Критическую важность глубины (наличия скрытых слоев) для представления сложных функций .
-*   Мощь алгоритмов, способных автоматически изучать полезные представления данных .
-Понимание задачи XOR и истории её решения является обязательным для всех, кто изучает машинное обучение и нейронные сети, так как оно закладывает основу для понимания гораздо более сложных архитектур и алгоритмов, используемых сегодня .
+* '''Метод опорных векторов (SVM) с ядром'''. [[Метод опорных векторов|SVM]] с нелинейным ядром (например, [[радиальное базисное ядро|RBF-ядро]] или полиномиальное ядро) способен решить XOR, поскольку ядро неявно отображает данные в пространство признаков более высокой размерности, где они становятся линейно разделимыми. Для XOR достаточно полиномиального ядра второй степени.
+* '''Метод k ближайших соседей ([[k-NN]])'''. Этот непараметрический алгоритм классификации решает XOR «естественным образом», поскольку он не строит линейной разделяющей поверхности, а основывается на голосовании ближайших соседей. Для четырех точек XOR при <tex>k=1</tex> или <tex>k=3</tex> классификация будет безошибочной (при условии правильного выбора метрики).
+* '''Деревья решений'''. Двоичное [[дерево решений]] может идеально разделить XOR, последовательно задавая вопросы о значениях признаков. Например, первое разбиение по <tex>x_1</tex>, второе — по <tex>x_2</tex>. Это показывает, что древовидные модели не страдают от проблемы линейной неразделимости.
+Эти альтернативы подчёркивают, что задача XOR является не столько «проблемой» для машинного обучения в целом, сколько иллюстрацией ограничений конкретного класса моделей (линейных классификаторов и однослойных сетей).
+== Современное значение ==
+Задача XOR сохраняет своё значение и в современных исследованиях. Она используется как простой тестовый полигон для изучения:
+* Динамики обучения нейронных сетей с помощью [[стохастический градиентный спуск|стохастического градиентного спуска]] (SGD).
+* Явления [[переобучение|переобучения]] и обобщения в различных архитектурах.
+* Анализа поведения сетей в условиях «нулевого зазора» (zero-margin), когда данные лежат непосредственно на разделяющей поверхности.
+Таким образом, задача XOR, начав свой путь как демонстрация фатального недостатка ранних нейросетей, превратилась в фундаментальный учебный пример и важный инструмент для понимания принципов глубокого обучения.
+== См. также ==
+* [[Искусственный нейрон]]
+* [[Многослойный персептрон]]
+* [[Линейная разделимость]]
+* [[Алгоритм обратного распространения ошибки]]
+* [[Метод опорных векторов]]
+* [[Теорема о универсальной аппроксимации]]
+* [[Функция четности]]
+* [[Зима ИИ]]
+== Примечания ==
+<references />
+== Литература ==
+* Minsky, M., & Papert, S. (1969). ''Perceptrons''. MIT Press.
+* Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning representations by back-propagating errors. ''Nature'', 323(6088), 533-536.

Задача XOR

Материал из MachineLearning.

Текущая версия

Содержание