Теорема Новикова. 
Интеллектуальные системы

Пусть R^k — признаковое пространство, М* С R*, Mi ф 0, «= 1,2, М Р) М2 = 0. Множества М и М2 линейно отделимы (строго линейно отделимы) точно тогда, когда существуют а 6 R^k и с € К, что для любых х € М и ±2 € М2 выполнено а х 1 ^ с, а • Х2 < с (а • Х > с, а • Х2 < с).

Множества Mi, М2 С R^k строго 0-отделимы точно тогда, когда существуют, а 6 К^п, что для любых х € Mi и ±2 G М2 выполнено, а • Xi > 0, а • Х2 < 0.

Множество MCR^fc строго линейно отделимо от нуля точно тогда, когда существует a G R^fc, что для любых х 6 М выполнено а • х > 0.

Утверждение 1. Если Mi, М2 € R^k и М, = {(xj,…, х*, 1): (xi,…, х*) е М"}, i = 1,2, то Mi и М2 строго линейно отделимы тогда и только тогда, когда М и М2 строго 0-отделимы.

Доказательство. 1. Пусть М и Мг строго линейно отделимы гиперплоскостью I: а • х = с. Определим 6? R^fc+1, 6 = (ai,…, a*, — с). Тогда для всех i' 6 Mi, i' = (х, 1) выполнено Ьх' = ах—1с>0. И для всех х'? М2, х' = (х, 1) выполнено 6-х' = а • х — 1 • с < 0. То есть множества М и М2 строго 0-отделимы гиперплоскостью I' j х' 0.

2. Обратно, пусть множества М и М₂ строго 0-отделимы гиперплоскостью V: Ь х' = 0. Положим с = — 6_fc+1, a = (61,…, Тогда Mi и М2 строго линейно отделимы гиперплоскостью /: а • х = с. ?

Утверждение 2. ifc/ш Mi, М2? u M' = M |J{—х ^: Ё € А'/г}, тло М и М2 строго 0-отделимы тогда и только тогда, когЭа М' строго линейно отделимо от 0.

Доказательство. 1. Пусть М' строго линейно отделимо от 0, то есть 3aVx? М’о • х > 0. Пусть х? Mi, тогда х? М' и х a > 0, а если х? М2, то —х? М' и х • a < 0. То есть Mi и М2 строго 0-отделимы гиперплоскостью /: о • х = 0.

2. Обратно, пусть Mi и М2 строго 0-отделимы гиперплоскостью Z: a • х = 0. Тогда х • a > 0 для всех х? М'. То есть М' строго линейно отделимо от 0. ?

Пусть даны два строго линейно отделимых множества М_ь М2 С R^n₁. Пусть М' = Mi (J{—х: х? М2} и.

Тогда согласно утверждениям 1 и 2 множество М строго линейно отделимо от нуля.

Рассмотрим следующий алгоритм А, который для строго линейно отделимого от нуля множества М позволяет находить нормаль отделяющей гиперплоскости. На вход алгоритма поступает бесконечная последовательность уь$ 2,… такая, что для любого г = 1,2,… выполнено у*? М. Эта последовательность называется обучающей последовательностью. Алгоритм А состоит в итеративном уточнении нормали а отделяющей гиперплоскости, называемой весовым вектором, по следующей схеме:

Шаг 0. do := (0,…, 0).

Шаг i (i > 0). Если у* ? a^i < 0, то a, = а*_1 + у", иначе.

di = a"-i.

Для конечного М = {уь • • • > У*} из Rⁿ введем обозначения: выпуклая оболочка множества Л/,.

Теорема 4 (Новикова). Пусть М С К^п строго линейно отделимо от 0, М < со и р (М) > 0. Пусть уьУг,… — обучающая последовательность такая, что для любого i = 1,2,… выполнено гд 6 М, и каждый элемент у из М встречается в обучающей последовательности бесконечное число раз. Пусть ai, a2,… — последовательность весовых векторов, полученных в результате применения алгоритма, А к обучающей последовательности у1, у₂,____Тогда существует натуральное N

такое, что для любого г > N выполняется di = ам, при этом для любого у € М справедливо а^ у > 0, и для числа изменений s в последовательности 01,02,… выполнено s < [ «2] •.

Доказательство. Пусть — последовательность всех индексов, для которых у^ • о^_х < 0, j = 1,2,…, т. е. это последовательность индексов, в которых последовательность ai, 02,…

изменяется. Обозначим yj = у^, do = do, dj = d{_j, j = 1,2,____.

Пусть x — ближайшая к 0 точка из V (M), т. е. ||х|| = р (М). Обозначим ё = -рц. Рассмотрим гиперплоскость Я, задаваемую уравнением ё • у = ||х||.

Легко показать, что все точки из V (M) лежат не ниже, чем гиперплоскость Я, т. е. для любой точки у € V (M) выполнено ё • у > ||ж||. В самом деле, предположим, что существует точка у € V (M) такая, что ё • у < ||х||. Проведем через 3 точки х, у и точку 0 плоскость L. На рисунке 1.9 изображены эти точки на плоскости L. Здесь прямая (1,х) — есть прямая пересечения.

Рис. 1.9:

плоскости L и гиперплоскости Я, т. е. прямая (/, х) перпендикулярна отрезку [0,х]. Так как ёу < ||х||, то угол /.Оху — острый. Из точки 0 опустим на отрезок [х, у] перпендикуляр [0, г]. Так как у е V (M) и х 6 V (M), то и z € V (M). Из остроты угла /Оху следует, что ||z|| < ||х||, что противоречит минимальности н*н;

Так как для любого допустимого индекса к справедливо <*k = ajfe-i + Ук, то.

С другой стороны.

Но у_к ук< D²(M) и а_к-1 • Ук < 0 и, значит,.

Следовательно, к²р²(М) < к:D²(M) и к < [D²(M)/p²(M)] для любого допустимого индекса к. Откуда сразу следует, что для числа s изменений весовых векторов верно.

Возьмем N = i_s. Тогда для любого индекса j > N справедливо dj = ар/, а так как в последовательности ум, уы+1″ • • • встречаются все элементы множества М, то для любого у € М справедливо ал/ • у > 0.

Теорема доказана. ?

Упражнения.

1.13. Построить линейную функцию, разделяющую множества М_ЬМ₂ С R², если.

• 1.14. Существует ли прямая, разделяющая множества М, М2 С R², если М, = {(0,2), (2,0), (2,2), (2,4), (4,2)} и М₂ = {(3,0), (4,4), (5,0)}?
• 1.15. Доказать, что множества Mi, М2 С R² нельзя отделить линейной функцией и построить нелинейную функцию разделяющую их, если

1.16. Дано: Mi = {(1,3), (2,2), (2,4), (3,1), (4,1), (4,4)};

Л/2 = {(1,4), (1,5),(2,5), (3,4), (4,2), (5,3)}. Определить, к какому классу относится точка? = (3,3).

• а) методом ближайшего соседа;
• б) методом к-ближних (рассмотреть случай к = 5).
• 1.17. Дано: Л/, = {(1,4), (2,3), (3,4), (4,3), (5,4)};

М2 = {(1,1), (2,0), (3,1), (4,0), (5,1)}. Определить, к какому классу относится точка? = (3,2).

• а) методом ближайшего соседа;
• б) методом fc-ближних (рассмотреть случай к = 3).
• 1.18. Mi = {2,5,8}, М2 = {3,4,7}. Определить, к какому классу относится точка { = 6 методом потенциальных функций. Потенциальная функция имеет вид

• 1.19. Даны множества Mi, М2 С R². Отнести точку? = (0,1) к одному из классов по методу
• а) ближайшего соседа,
• б) потенциальных функций с потенциалом Р (х, у) = тах (0, 2 —
• 1*1 — 1у1).
• в) потенциальных функций с потенциалом Р (х, у) = тах (0,5 —

N — 1у1).

при условии, ЧТО

• 1.20. Описать критерий отделимости двух множеств персептроном.
• 1.21. Какие функции алгебры логики от двух переменных представимы персептроном, а какие — нет? Ответ обосновать.
• 1.22. Дано множество М С R", строго линейно отделимое от О, |М| = 7, D (M) =? 10, р (М) = 1. Во власти экспериментатора составить обучающую выборку для подачи на вход персептрона. Каждую секунду на вход персептрона может подаваться 1 элемент обучающей выборки. Чему равно минимальное время, через которое экспериментатор гарантированно будет знать, что персептрон получил нормальный вектор отделяющей гиперплоскости для множества М? Как должна выглядеть обучающая выборка, чтобы обеспечить этот результат?