В предишната „статия“ видяхме как неравенството на Хьофдинг, с леки модификации, може да се използва в контекста на оценка на това колко добре една хипотеза ще се обобщи върху невиждани данни. Същността на проблема беше, че трябваше да направим крачка далеч от проверката на старата школа на жизнеспособността на една хипотеза, за да намерим оптималната хипотеза от набор от хипотези вместо това. Проблемът беше, че не можехме сляпо да приложим неравенството на Хьофдинг към този сценарий — вместо това трябваше значително да разхлабим границата, като използваме обединената граница на всички М хипотези. Последната статия завърши с въпрос дали е възможно да се подобри границата, като се направи приложима, когато имаме набор от хипотези с безкраен размер. В тази статия ще видим, че е възможно и как се прави с помощта на така нареченото VC измерение. Въпреки това, като начало, ще повторим откъде идва М в нашето неравенство и какво означава то.

Разбиране на M

Преди да продължим, нека първо видим неравенството, с което работим:

Където имаме следните компоненти:

  • M: Размерът на нашия набор от хипотези, H.
  • N: Размерът на извадката.
  • E_in(h): Грешката в извадката на h.
  • E_out(h): Грешката извън извадката на h.
  • ε: Това е нашата толерантност за това колко приемаме E_in да се отклонява от E_out.

За да не се объркаме по-късно, когато получим новата формула, важно е да отбележим, че границата по-горе може да бъде записана в следното неравенство:

Границата гласи, че ако изберем ниво на толерантност, δ, и тогава можем да твърдим с вероятност най-малко 1 — δ, че границата е валидна. Все пак ще започнем работа с първата версия.

Както беше посочено, имаме истински проблем, когато M е безкрайно — но нека първо отново разберем откъде идва M в нашето неравенство. В предишната статия споменахме, че идва от обединението на всички наши хипотези в набора от хипотези. Какво се има предвид под вземане на съюзна граница на тези хипотези? Когато вземем границата за една единствена хипотеза, ние ограничаваме вероятността за лошо събитие - по-конкретно, че нашата грешка в извадката се отклонява от нашата грешка извън извадката с повече от нашия толеранс, ε. В математически термини може да се напише така:

Когато преминахме от наличие на една хипотеза към наличие на множество, взехме обединението на всички тези възможни лоши събития във всяка хипотеза в нашия набор от хипотези. Тоест взехме обединението на М лоши събития. Това може да се запише като:

Това гарантирано включва нашата крайна хипотеза g, тъй като тя е обединение на всички наши хипотези в H. Тъй като g винаги се намира в H, тогава сме сигурни, че границата винаги включва g. Можем да илюстрираме този съюз от лоши събития с конкретен пример. Да кажем, че имаме 4 хипотези в нашия набор от хипотези.

Обвързаността на съюза казва, че общата площ, покрита от Event_1, Event_2, Event_3 или Event_4, е по-малка от сбора на отделните области. Това твърдение очевидно е вярно, но също така можем да видим доколко четирите хипотези се припокриват, че границата е много разхлабена. Можем да го покажем визуално:

Връзката очевидно е много разхлабена. За щастие тези събития често се припокриват не само на теория, но и на практика. Ако имате две хипотези, hi и hj, които са много познати, тогава техните събития обикновено също се припокриват. Това е добра новина - но как това ни помага да подобрим границата? Отговорът идва под формата на нещо, наречено функция за растеж.

Функция за растеж

Нека набързо повторим - когато правим набор от хипотези, H, разглеждаме цялото входно пространство, за да го създадем. Ето защо набор от хипотези може потенциално да бъде безкраен. Идеята зад функцията за растеж е, че не е необходимо да разглеждаме хипотези, покриващи цялото входно пространство, а просто хипотези, които покриват нашите проби. Сега, какво точно е входното пространство и как се различава от нашите проби?

Нека си представим, че имаме модел, който се обучава върху двуизмерни числови данни. Можем да си представим, че тогава нашите проби идват от по-голямо пространство, входното пространство. В този случай нашето входно пространство е изцяло двуизмерно, числово въвеждане, което бихме могли да подадем към нашия модел. Както си представяме, нашата извадка покрива само част от цялото входно пространство! Какво означава това?

Както беше казано, функцията за нарастване се основава на броя различни хипотези, тук наречени дихотомии, които H може да приложи, но върху нашето примерно пространство вместо върху цялото входно пространство. Дихотомията функционира по същия начин като хипотезата, просто трябва да направим разграничение, когато говорим за функцията на растеж. Това би означавало, че може да е възможно да подобрим M в нашето неравенство, ако вместо това го заменим с функцията за растеж! Първо, можем да вземем пример за това как ще бъдат намерени тези дихотомии - нека разгледаме извадка само с 3 точки в двумерното пространство.

В примера по-горе добавяме дихотомия към нашия набор всеки път, когато точка промени цвета си — и в крайна сметка получаваме 8 дихтомии в нашия набор. Можем да дефинираме функцията на растеж математически като:

С думи това казва, че функцията на нарастване е максималният брой дихотомии, които могат да бъдат генерирани от H на произволни N точки. Казано още по-просто - опитваме всички съзвездия от нашите N точки и избираме съзвездието, където можем да създадем възможно най-много дихотомии. След това можем да намерим горната граница на това колко дихотомии може да даде функцията на растеж - като цяло горната граница е:

Тъй като това е горна граница - означава ли, че можем да имаме по-малко от максималния брой хипотези? Да, и се нарича точка на прекъсване. Формално точката на прекъсване се определя като когато не е възможно за H да генерира всички дихотомии върху определен набор от данни с размер k. Тогава k е точката на прекъсване за набора от хипотези. Това ще бъде интересно по-късно, когато ще се опитаме да заменим M с функцията за растеж - но нека първо вземем пример с точка на прекъсване.

Можем да видим, че е възможно да разбием всички съзвездия от 3-те точки — следователно 3 не е точката на прекъсване за двуизмерен персептрон. Ако вместо това се опитаме да разбием 4 точки, тогава внезапно се натъкваме на проблем в случай 15 и 16 (последните две квадратчета). Както и да въртим или усукваме точките, няма да можем да ги класифицираме правилно с нашата линия! Следователно можем да кажем, че 4 е точка на прекъсване за двуизмерен перцептрон. Ако се върнем към функцията за растеж, това означава, че можем да кажем, че е вярно следното:

Сега използваме точката на прекъсване k, за да извлечем граница на функцията на нарастване за всички стойности на N. Няма да дам доказателството в тази статия, но можем да дефинираме границата на функцията на нарастване, като вземем предвид точката на прекъсване, в следното начин:

Сега намерихме начин да обвържем функцията за растеж, ако знаем точката на прекъсване на нашия модел. Има ли по-лесен начин да го дефинираме?

Размерите на VC

Дефиницията на размерите на VC е пряко свързана с точката на прекъсване — тя се определя като най-голямата стойност на N, за която:

Ако това е броят на възможните дихтомии за всички възможни N, тогава VC измерението е безкрайност. Следователно можем да кажем, че размерите на VC са равни на k — 1, като k е точката на прекъсване на нашия модел. Позната ли ви е тази реплика? Това означава, че можем да пренапишем нашата граница за функцията на растеж по-горе по по-прост начин:

Сега може да изглежда, че сме се отдалечили много от това, което сме си поставили за цел - да заменим M в нашето първоначално неравенство с нещо по-добро. Така че защо губите цялото това време, за да дефинирате VC размерите и точката на прекъсване? Защото може би ще успеем да го заменим с М, макар и не директно!

Смяна на M

Оказва се, че не можем просто да вмъкнем функцията за растеж на мястото на M, а вместо това трябва да направим няколко модификации. В крайна сметка получаваме следната граница:

Тази граница гласи, че ако изберем ниво на толерантност, δ, и тогава можем да твърдим с вероятност най-малко 1 — δ, че границата е валидна. Тази граница установява осъществимостта на обучение с безкрайни набори от хипотези, благодарение на разглеждането на извадките вместо на цялото входно пространство. Ако го базираме на VC измерението вместо на функцията за растеж, тогава ще получим следната граница:

Можем да покажем ефекта от замяната на M с обвързания VC визуално:

Предполагаме, че правоъгълникът, нашето платно, представлява пространството на всички набори от данни, с области, съответстващи на вероятности. За хипотеза цветните точки съответстват на набори от данни, където E_in не се обобщава добре до E_out (т.е. нашите предишни дефинирани лоши събития!). Неравенството на Hoeffding гарантира малка вероятност - следователно малка оцветена област. С M имаме обвързано обединение – така че не предполага припокриване, така че оцветената област е голяма. Измерението VC предполага припокриване между хипотези, следователно оцветената област е по-малка, отколкото при обвързаното обединение.

Заключение

Като цяло видяхме, че можем да заменим M в нашето неравенство с функцията на нарастване - и по този начин също с VC измерението. VC измерението означава, че е възможно да се учи с безкрайни набори от хипотези, защото можем да го заменим с нещо крайно. Освен това е по-строг от M, тъй като вече не зависим от връзката на съюза, а вместо това разглеждаме припокриванията между различни хипотези. В следващата статия ще видим как обвързаността може да се използва на практика с различни примери.

Препратки:

— — — — — — — — — — — — — — — — — — — — — — — — -

[1] H-S. Lin, M. Magdon-Ismail, Y. S. Abu-Mostafa, Учене от данни — кратък курс(2012).