ТЕОРЕМА НОВИКОВА

Нехай 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 GR 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. Зворотно, нехай безлічі М і М 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_1 . Нехай М '= Mi (J {х: х? М2} і

Тоді згідно з твердженнями 1 і 2 безліч М строго лінійно віддільно від нуля.

Розглянемо наступний алгоритм А , який для строго лінійно віддільного від нуля безлічі М дозволяє знаходити нормаль відокремлює гиперплоскости. На вхід алгоритму надходить нескінченна послідовність уь $ 2, ... така, що для будь-якого r = 1,2, ... виконано у *? М. Ця послідовність називається навчальною послідовністю. Алгоритм А складається в итеративном уточнення нормалі а відокремлює гиперплоскости, званої ваговим вектором, за наступною схемою:

Крок 0. do: = (0, ..., 0).

Крок i (i> 0). Якщо у * ? a ^ i <0, то a, = а * _1 + у », інакше

di = a »-i.

Для кінцевого М = {уь • • •> У *} з R n введемо позначення: опукла оболонка безлічі Л /,

Теорема 4 (Новикова). Нехай М З К п строго лінійно віддільно від 0, М <зі і р (М) > 0. Нехай уьУг, ... - навчальна послідовність така, що для будь-якого i = 1,2, ... виконано гд 6 М, і кожен елемент у з М зустрічається в навчальній послідовності нескінченне число разів. Нехай ai, a2, ... - послідовність вагових векторів, отриманих в результаті застосування алгоритму А до навчальної послідовності в1, у 2 , ____ Тоді існує натуральне 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, х]. Так як yoу < || х ||, то кут /.Оху - гострий. З точки 0 опустимо на відрізок [х, у] перпендикуляр [0, г]. Так як у е V (M) і х 6 V (M), то і z € V (M). З гостроти кута / Оху слід, що || z || <|| х ||, що суперечить мінімальності

н * н-

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

З іншого боку

Але у до ук <D 2 (M) і а до - 1 • Ук < 0 і, отже,

Отже, до 2 р 2 (М) < до: D 2 (M) і до <[D 2 (M) / p 2 (M)] для будь-якого допустимого індексу к. Звідки відразу випливає, що для числа s змін вагових векторів вірно

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

Теорема доведена. ?

вправи

1.13. Побудувати лінійну функцію, що розділяє безлічі М Ь М 2 З R 2 , якщо

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

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 2 . Віднести точку? = (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 елемент навчальної вибірки. Чому дорівнює мінімальний час, через яке експериментатор гарантовано буде знати, що персептрон отримав нормальний вектор відокремлює гиперплоскости для безлічі М? Як повинна виглядати навчальна вибірка, щоб забезпечити цей результат?
 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >