Я прочитаю спецкурс под названием «Математическая основа машинного обучения и прогнозирования». Вы видели в расписании МФК, что есть несколько спецкурсов на эту тему. Я просмотрел программы их всех и должен, прежде всего, сказать, чем отличается мой спецкурс от других, которые тоже посвящены машинам обучения. Поскольку спецкурс считается от имени Мехмата, то, конечно, в нем должно быть первостепенное внимание уделено математическим вопросам, связанным с машинным обучением, а это вопросы точных оценок.
качество алгоритмов обучения, есть такое понятие обобщающих способностей алгоритма обучения. Этого нет почти во всех других спецкурсах. Я смотрел не только МГУшные спецкурсы, но и спецкурсы Яндекс, которые читает.
Исторически там было самое первое чтение спецкурсов по машинному обучению. Там это организовал Воронцов Константин Вячеславович. К сожалению, математики там гораздо меньше, чем должно было бы быть, а ее знать очень важно. То есть вы строите алгоритм, вам интересно, насколько он дает качественное решение задачи обучения. И то, что в других спецкурсах касается оценки качества алгоритмов, там такие слова, что рекомендуется избрать такой-то метод.
нейросеть или случайные леса, или бустинг, но нету каких-то таких точных оценок, насколько хорошо мы решили задачу обучения. У меня это будет иметь первостепенное значение. Я считаю, что это нужно знать тем, кто использует методы машинного обучения. Что касается этой области в целом, она на самом деле состоит из нескольких направлений.
То, чего буду касаться я, это, с одной стороны, классическая теория машинного обучения, и с другой стороны, то, что связано с прогнозированием. По прогнозированию у нас, насколько мне известно, вообще нигде ничего не читается. Точнее говоря, читается на физтехе в курсе Вьюгина.
Владимир Викторович, кажется, его зовут. Он издал книгу, ровно с таким названием, которым называется «Мой курс». По-моему, ее можно купить.
Она издана в Московском центре непрерывного математического образования. Читать ее очень сложно, я ее читал с большим трудом. Я пытался переделывать то, что содержится в такой читабельный текст.
И некоторые лекции я набрал. Я вам все пошлю в чат. Вы все знаете, что у меня есть чат, на который вы знаете об этом.
Кто не знает, посмотрите, где вы подписывались на мой спецкурс. Там есть вот такие объявления про то, что желательно подписаться на мой чат, в который я буду выкладывать все видеозаписи. И, кроме того, вам там будет интересно посмотреть предыдущие сообщения.
Некоторые из них это книги, которые я... Они актуальны. Книга Мерфи очень важная, это базовый учебник по машинному обучению в Стэнфорде. Потом книга Бишоп. Там надо очень сильно отмотать назад, чтобы книги, которые я посылал, вы могли скачать и тоже их изучать.
Я заранее скажу, что то, что я вам успею рассказать, это капля в море тех знаний, которые сейчас связаны с машинным обучением. Я совсем мало расскажу про нейросети. В нейросети это читается отдельный курс. И там книжка даже есть хорошая.
Гудфеллоу, Бенджо и третий не помню кто. То есть вам, если хотите серьезными знаниями здесь овладеть, надо очень много читать самостоятельно литературы. Сейчас очень много появилось переводных книг. Есть, как я уже сказал... Мерфи, Бишоп, книга по обучению с подкреплением, это Сатана Барто, кажется.
Вы все это можете найти в моем чате и изучать. Я читаю... Курс, вот у меня так получается, что всегда я читаю курс, и несколько студентов находятся, которые хотят эти знания развивать и применять в проектах.
Я буду очень рад, если кто-либо из вас, чем раньше, тем лучше, выразит желание не просто слушать лекции, но и вместе с моими ребятами. Ребята очень успешные, особенно есть один Сергей Артамонов, он, кстати, читает тоже спецкурс. МФК есть, которые читаются от Института теоретической и математической физики, они в самом конце списка, там 500 участников каждого спецкурса. Один из спецкурсов читает мой студент Сергей Артамонов, он феноменально работоспособный, несколько проектов ведет одновременно в Скалтехе и в фонде «Интеллект», ему дали грант «Умник», он уже других людей приглашает в нем участвовать.
Сейчас они создали свою команду «Валберес». Я так понял, что сегодня очень бурно развивается. Вы, кто хотите, ко мне обращайтесь, можете попробовать присоединиться. Постановок задач машинного обучения много бывает. Мы не будем касаться такого раздела, как «Reinforcement Learning».
Почему не будем касаться? Надо было бы хотя бы одну лекцию провести, но дело в том, что там я, к сожалению, не дошел до математических теорем. Мне неудобно читать лекцию, если я там ни одной теоремы не могу сформулировать.
Но в reinforcement learning подход к обучению такой, что рассматривается поведение некоторых агентов, они могут выполнять действия. И вот когда действие выполняется, то... агента возникает понятие награды, то есть там сразу ему сигнал, правильно он поступил или неправильно. Это значит заставляет его как-то исправляться, если он получил отрицательную награду или продолжать в том же духе, если награда положительная.
Вот это один подход к машинному обучению. Мы будем рассматривать другой подход, ну точнее говоря, несколько лекций будут посвящены подходу. связанному с обучению распознаванию.
Значит, у нас задача ставится следующим образом. Имеется некоторое множество х, которые называются объекты. Это могут быть изображения, текстовые файлы, значит, любые в общем сущности, которые мы хотим как-то научиться относить к одному определенному, то есть к... к какому-либо из имеющихся классов. Эти классы называются словом «ответы».
Например, объект изображения, ответы, что изображено. Самый простейший случай, когда ответов всего два. И это общий, на самом деле, универсальный случай.
То есть если мы научимся обрабатывать ситуацию, когда ответов всего два, то мы сведем именно к этой задаче все остальные задачи, где множество ответов произвольно. Имеется функция, которую мы не знаем, но хотим научиться вычислять. Эта функция называется классификатор.
То есть каждому объекту... Функция сопоставляет ответ или класс, к которому относится этот объект. Например, объектами могут быть люди, а классами являются два признака, хороший или плохой. Это, разумеется, относительно какой-то задачи, хороший или плохой.
Например, это клиент, который хочет получить кредит. Это самая часто встречающаяся задача в банках. Приходят люди за деньгами, кому-то деньги дают, кому-то отказывают.
У человека собираются какие-то признаки, и на основании этих признаков вычисляется функция, значение которой либо хорошее, то есть дать ему кредит, либо не дать. Что касается функции, а именно ее аргументов. Что мы подаем на ее вход? Все-таки это некоторый алгоритм, у него должен быть какой-то формат входных значений. Когда мы имеем человека, разумеется, не его самого мы подаем на вход этого алгоритма, а мы собираемся Мы делаем какие-то признаки для этого человека.
И вот мы на самом деле здесь делаем переход от объектов к их векторному представлению. То есть про объект мы можем, например, ну человек, да, что у него является признаками, значит, возраст, там, не знаю, зарплата, его кредитная история. К каждому признаку сопоставляется множество значений.
Бывают признаки, которые мы можем числом измерить, например, возраст или зарплата. Что еще можно числом измерить? Если это объекты, которые космонавты проходят. отбор на космические полеты, наверное, какие-то медицинские еще показатели, среднее давление, или нет, просто верхнее и нижнее давление, и так далее по здоровью. Бывают признаки, которые можно числом измерить, бывают признаки, которые числом измерить нельзя.
Пол, например, два значения. Хотя сейчас в некоторых странах существует несколько десятков полов. Давайте будем считать, что мы люди нормальные, у нас два пола только.
Даже если это не числовые признаки, все равно их можно полом назвать один, значение 0, второе единица. Любые признаки можно считать числовыми признаками. Сколько признаков?
Нам достаточно, это на самом деле вопрос сложный. Иногда требуется много признаков, мы не знаем, какие из них существенны, а какие можно игнорировать. Сколько бы их ни было, их какое-то конечное множество. Каждый признак является числом.
какой-то компоненте вот этого вектора признаков. И сам вектор признаков у нас таким образом является вектором действительных чисел. Ответов давайте будем считать два у нас.
Иногда это ноль или один, иногда это минус один. И значит у нас таким образом функция Числовая, которую мы не знаем. Но что мы про нее можем знать?
Что она принимает какие-то заданные значения на каких-то объектах. У нас задана, как говорят, обучающая выборка. Значит, эта выборка называется S Это совокупность пар. Оля-ля, я же икс и ты.
Так, как нам теперь компоненты вектора? Давайте так, компоненты этого вектора у нас будут обозначаться другими буквами, там xi1, там xin. И у нас каждый вектор, который кодирует какой-то объект, обозначается буковкой x.
То есть xi, yi, где i от 1 до l. Это совокупность пар, которая называется обучающая выборка. Откуда взялись такие ответы на объекты, мы не уточняем. Мы считаем, что какие-то объекты мы размятили, и значение функции, которую мы восстанавливаем, на этих объектах задано точно.
Это мы имеем. Наша задача придумать то, как эта функция могла бы быть устроена. Нам надо научиться вычислять значение этой функции на новых объектах, которые сюда не вошли. И вот встает такой вопрос, как именно эту функцию можно было бы найти. В каком виде ее искать?
Это отдельный философский вопрос. И вот здесь понятно, что у нас данная функция должна быть как можно более простой. Здесь ситуация во многом аналогична задаче аппроксимации функции одного переменного.
Мы имеем какую-то функцию, у которой мы знаем какие-то значения в каких-то точках. То есть объекты это точки оси абсцисс, а ответы, действительно числа это ординаты этих точек. Вопрос, какую функцию лучше всего взять, которая бы имела заданные значения на этих точках.
Для чего? Для того, чтобы предсказывать ее значение на новых точках. Это вопрос сложный. Допустим, функцию можно провести точно. Вы знаете, интерполяционный многочлен Лагранжа существует для любой конечной совокупности точек.
Он строит полином. Но полинома это сложная функция. И вопрос, а надо ли искать эту функцию максимально точно, чтобы она на каждом объекте из заданных объектов принимало ровно то значение, которое там изображено. Ответ такой.
Не надо искать сложные функции. Если мы будем искать решение задачи сложным, мы, как говорят, переобучимся. Мы научимся точно предсказывать значение в заданных точках, но появляются новые точки. То есть наше решение не статичное.
Обучение как раз это именно движение от какого-то решения для какого-то заданного обучающей выборки. Вопрос, как это решение можно далее уточнить, когда появляются новые объекты с новыми ответами. То есть может получиться так, что придет новая пара и... Значит, у нас, допустим, она не будет точно ложиться на ту кривую, которую мы построим, тогда нашу кривую надо менять.
И вот, значит, говорят, что решение переобученное, если когда мы добавляем новые пары, то наше решение сильно скачет, то есть радикально там другой вид имеет наша кривая, когда мы добавляем новые точки. Поэтому решение должно быть максимально простым, но, тем не менее, оно должно примерно соответствовать этой обучающей выборке. Здесь самое лучшее решение, например, прямая. Точки не вполне на нее ложатся, но, тем не менее, какая-то близость этих точек к прямой есть. Можно квадратичную функцию, она, наверное, поточнее будет нам аппроксимировать.
Но здесь надо принимать во внимание вот какой факт. Вот эта функция, на самом деле, она изначально может быть не вполне точная. Ну, то есть, вот там функция, которая изображает стоимость квартир. Вот там объекты это квартиры, там у них есть разные качества, там, не знаю, расположенность у парка или у метро, или там есть что-то еще.
дополнительная этажность, по квартире можно поставить такой вектор, и затем стоимость квартиры можно указать примерно. Покупатели как-то покупают эти квартиры за такую-то цену. Можно такую функцию сделать, известную на каких-то векторах, путем доверия. Здесь, в общем, может быть не точное у нас значение функции, а какой-то диапазон.
То есть, вот примерно вот столько, как квартира может стоить. Это уточняется всякий раз, и это, к тому же, меняется с течением времени. То есть, допустим, квартира стоила сегодня столько-то, завтра там провели где-то метро, что квартира в другом районе, где это метро. они стали более выгодными, стоимость повысилась или понизилась.
Вы знаете, что сейчас у нас это очень сильно меняется. В общем, ответы на объекты изначально могут быть неизвестными точно. И поэтому, если мы строим такую зависимость, которая точно нам аппроксимирует нашу функцию, это неправильно по причине того, что само значение может быть, как говорят, засумленным. Вот.
И мы вот... когда точно проводим эту функцию, мы аппроксимируем и шумы тоже, а это нельзя делать, шумы, наоборот, надо из модели изгонять. В общем, это я как мог объяснил, что, когда мы ничего не знаем, то есть, разумеется, Можно эту функцию как-то, наверное, найти максимально точно, если мы детально знаем природу этого соответствия.
То есть, как вообще изначально можно точно определить цену. Но на самом деле мы этого не знаем, мы никогда его не узнаем. И не надо здесь нарушать такой принцип, который называется бритва Лемма.
Который заключается в том, что... Нельзя делать излишние усложнения в том случае, когда у нас мало информации. То, что мы имеем, как-то надо пытаться осознать путем построения такой функции, но не слишком сложной. То есть нельзя слишком простое решение находить и нельзя слишком сложное тоже находить. Ну и в соответствии с этим принципом...
Такой вопрос встает, а в каком виде искать эту зависимость? Давайте в случае рассмотрим, когда у множество из двух элементов, и объекты это какие-то вектора действительных чисел. Я думаю, что такая ситуация многим знакома. У меня два примера приходят.
Первый это когда студенты поступают в аспирантуру. Человек, допустим, не МГУшный, а с внешней организацией приходит, у него учитывается средний балл в дипломе, статьи, награды, всякие грамоты за участие в каких-то конкурсах. По нему составляется такой вектор признаков. И каждому признаку сопоставляется некоторый вес. А еще такая ситуация возникает, когда у меня знакомые эмигрировали в Канаду, там тоже разные признаки, сколько ему лет, в какой области он работает, сколько у него заслуг профессиональных и так далее.
И ему за каждый признак ставится точка. Не точка, а point. Это не точка, а это какой-то количественный оценок. Далее происходит следующая ситуация.
Значение этого признака умножается на вес этого признака. Каждому признаку сопоставляется вес некоторый. Некоторые признаки важны, например, его профессиональная успешность.
Признак очень важный, а там всего лишь несколько значений. И вес большой. А другой признак, может быть, например, у него семья, это тоже важно для принятия решения о том, давать ему разрешение на ПМЖ или нет. Это может иметь другое значение, не такое, как профессиональная успешность.
Суммируется его. показатели, умноженные на веса. Если эта сумма больше какого-то порога P, то принимается решение, чтобы дать ему ПМЖ, если нет, то противоположное решение принимается.
Вот это самая естественная схема классификации. И, разумеется, можно рассмотреть эту схему в математическом аспекте следующим образом. У вас имеется некоторое множество пар.
Вы не знаете, как их классифицировать. Вы ищете ответ на вопрос, по какому принципу новому объекту ставить в соответствии результат. Ответ вы решаете путем вычисления.
вот этих весов, как правильно определить веса, чтобы для уже известных элементов обучающей выборки то решение, которое вы примете с этими весами, было в точности то же самое, что указано в обучающей выборке. Таким образом, задача ставится вот как. Значит, имеется вот такое множество.
Значит, вот выражение. Она называется линейной формой. И когда вы рассматриваете, то есть здесь выражение с переменными ксиитами. Коэффициенты известны, и p тоже действительно число какое-то.
Вы ищете коэффициенты, то есть у вас имеется набор таких неравенств для каждого элемента обучающей выборки. Когда вы знаете элемент, а, извиняюсь, вы и p тоже не знаете, неправильно, я здесь не p, а должно быть w0. Значит, у вас требуется найти w, и t, где i от 0 до n. И вот каждая пара в обучающей выборке создает свое собственное неравенство такого типа. Как именно неравенство определяется?
Если y и t равно 0, тогда у вас неравенство в соответствующей паре имеет вид вот такая вот сумма. Значит, xi и t это известные числа, коэффициенты вектора и xi и t. меньше либо равно w0.
Вот такое неравенство у вас имеется для пары из обучающей выборки с y равным 0. А если y равен 1, то тогда неравенство больше используется. Вот вам задается такая система неравенств. И решением задачи обучения является...
нахождения какого-нибудь решения вот этой системы неравенств. Понятно, что у системы неравенств может быть самое разнообразное количество решений, может вообще ни одного решения не быть, как в таких случаях быть. Это один вопрос. А может быть там и бесконечно много решений у такой системы неравенств. Вопрос, как выбрать наилучшее решение.
системы неравенств. Мы будем этим заниматься, то есть мы будем решать задачи нахождения классификатора в линейном виде. Есть ситуация, когда вообще ни одного решения такой системы неравенств не существует. Если такое случилось, то обучающая выборка называется линейно неразделимой.
И вот встает такой вопрос, как по выборке определить, является ли она линейно разделимой или линейно неразделимой. Давайте сейчас геометрические представления будем использовать. В инмерном пространстве я рисовать не могу, как говорят, это довольно неудобно. Я в двумерном пространстве буду рисовать.
В случае, когда n равно 2, объектами являются пары чисел. То есть двумерный вектор это пара чисел или точка на плоскости. Вот вы можете изобразить вашу обучающую выборку парами такими точками. Вот, допустим, объект x и t это пара чисел, значит, вот эта точка на плоскости.
И ответ на этот объект это метка этой точки, например, 1. То есть объект x1 это точка на плоскости, и ответ на этот объект это метка, которая рисуется рядом с этой точкой. Другая какая-нибудь точка, то есть объект x2 это тоже пара чисел. Напомню, что n равно 2. Ответ, например, 0. Давайте я еще несколько нарисую.
Вот тут 1, тут 0, допустим, тут тоже 0, тут тоже 1. Достаточно. Я нарисовал 6 точек. Понятно, что...
Значит, я должен найти коэффициенты, чтобы у меня для точек с меткой 1 неравенство было выполнено, а с точкой для точек с меткой 0 вот это. Если бы у меня вот эти самые числа... W и ты и W0 были известными, значит все знают, что вот если я напишу так сумма ксии ты W и ты Равно w0, то есть вот здесь уже это известные числа, а это переменные.
Вот, и от единицы до n. Вот такое уравнение определяет гиперплоскость. Это все знают?
Да. Вот, и вот на прямой гиперплоскость, вернее на плоскости гиперплоскостью является прямая. Значит, вот на плоскости...
Все точки, то есть вот эти вектороксиды, у которых здесь не равно, а больше, это полуплоскость по одну сторону от этой прямой. А когда неравенство строго меньше, то это полуплоскость по другую сторону этой прямой. В общем, вот если у нас найдется прямая...
для которой верны нужные неравенства, то это равносильно тому, что эта прямая делит нашу плоскость на две полуплоскости, по одну сторону точки, у которых метка 1, а по другую точки, у которых метка 0. Я думаю, что что-либо уточнять здесь не надо мне, детали объяснять, почему так. Вот эта прямая имеет уравнение сумма ксенитов W и так равно W0. Каждая такая прямая соответствует каким-то конкретным значениям весов W и W0.
Если мы их возьмем, то у нас возникнет прямая на плоскости. Если у нас... Вот неравенство, то есть в обучающей выборке, если у и t равно нулю, то неравенство больше выполняется, если единица, то неравенство больше, если нулю, то меньше.
Если такие неравенства у нас для данных значений весов выполняются, это равносильно тому, что Точки, у которых метка 1, лежат по одну сторону от этой прямой, а точки, у которых метка 0, лежат по другую сторону этой прямой. Вот, допустим, такая прямая нашлась. Ну и вопрос, какую прямую лучше всего взять, чтобы она разделяла. То есть найти.
Такую прямую, которая разделяет наше множество. Как говорят, положительные примеры это отрицательные примеры. Значит, найти такую прямую... Вот вопрос, если это неоднозначно можно сделать, то какая прямая была бы самой лучшей? Из таких соображений здравого смысла...
Понятно, что надо, чтобы эта прямая как можно дальше отстояла от обоих классов. То есть класс объектов, у которых ответ единица, это мы будем называть C+, это C это класс по-английски, а это C-. Значит, вот у нас классы это конечное множество. И что такое прямая?
Расстояние от прямой до множества это минимум расстояний от каждой точки до этой прямой. Это можно померить, перпендикулярно опустить, и минимальное расстояние это расстояние от всего множества до прямой. То есть это расстояние от прямой до класса мы будем считать. И вот с другого класса тоже можно для каждой точки найти расстояние до этой прямой. И у нас минимальное из этих двух чисел, расстояние до С+, расстояние до С-, будет нам давать меру расстояния от этой прямой до нашей обучающей выборки.
По некоторым причинам... Мы считаем, что прямая тем лучше, чем дальше она от обоих этих классов. Ну, то есть, например, если бы прямая была вот такого типа, например, вот такая, да, вот она очень близко подходит к точке, значит, из одного класса и далеко отстоит от другого класса. Вот это решение для нас было бы менее. хорошим.
Почему? Дело в том, что здесь, опять же, все здесь у нас зашумлено. У нас каждая точка это какой-то вектор признаков реального объекта.
Может быть, в действительности у реального объекта не те признаки, которые мы указали. Например, там признаки это Ну, неважно, то есть там дом, допустим, в каком он месте стоит, уровень загрязняющих веществ в атмосфере важно тоже учитывать. Тоже это может быть не вполне точно измерено. И другие признаки, все они на самом деле неточные величины. И вот если прямая подходит близко к одному из классов, например, здесь 0. то этот объект, который мы изображаем такой точкой, на самом деле может реально представляться другим вектором признаков, и который уже находится по другую сторону от этой прямой.
То есть мы считаем, что у нас реальные объекты это не сами точки, а какие-то шарики вокруг этих точек. И нам важно не подходить близко не к самим точкам, а к шарикам. Мы должны сделать максимально удаленное расположение нашей прямой от всех этих шариков. По некоторым другим причинам тоже можно считать, что не надо делать такое неравномерное отношение нашей прямой к обоим классам.
Надо, чтобы она как можно дальше отстояла от обоих этих классов. Построение такой прямой, которая максимально далеко отстает от обоих классов, это центральный объект изучения в таком разделе, который называется метод опорных векторов. Метод опорных векторов до того, как нейронные сети устроили взрыв в машинном обучении, был центральным разделом в машинном обучении.
Приятно, что метод был создан двумя нашими соотечественниками. Это Вапник и Червоненкес. Червоненкес умер, а Вапник живет в США уже с 90-х годов. У нас это впервые возникло.
Сила этого метода в том, что он допускает очень сильное обобщение. На базе него была создана ядерная. ядерной методологии машинного обучения. Но я про это сейчас не буду рассказывать. Я только такой аспект изложу.
Где возникают ядра? Ядра возникают там, где у нас имеется обучающая выборка, которая линейно неразделима. Что делать в такой ситуации? Например, давайте я опять на плоскости нарисую эту ситуацию. Вот у нас объекты, которые вблизи нуля, они все имеют метку 1. То есть это хорошие объекты, а объекты далеко от начала координат имеют метку 0. Понятно, что здесь линейно разделить невозможно.
Но все-таки здесь как-то уж очень гармонично нарисованы. То есть то, что вблизи нуля это ноль, вблизи нуля один, а далеко от нуля метка ноль. Вопрос как нам придумать какой-нибудь простенький алгоритм, не слишком более сложный, чем линейный классификатор, чтобы таким алгоритмом классифицировать новые точки. Здесь вполне естественное решение это взять еще одну компоненту.
То есть вот у нас объекты представляются векторами, вот у них компоненты соответствуют признакам, а мы можем сочинить искусственно новый признак, который будет строиться из старых. Например, там xi1 квадрат плюс xi2 квадрат. То есть вот такой новый признак.
который вычисляется по уже известным признакам. Как только мы добавим такой признак к нашим точкам, то у нас будет уже... Уже очень простой правило классификации. И на самом деле там вот первые два признака уже не важны, важен третий признак.
Вот это у нас будет кси-3. Вот если кси-3 больше какого-то порога, ну да, правильно, кси-3, это значит координата. Если она велика, то есть больше какого-то дублевой нули, то мы метку ставим 0, а если меньше, то метка 1. То есть мы сейчас сделали погружение нашего пространства в признаков, в большее пространство, и там уже наша выборка линейно разделилась. То есть понятно, что у нас была выборка линейно неразделимая, вот она. Мы по ней построили новую выборку, то есть к объектам мы добавили еще одну координату, искусственно ее определили, и там случилось, что она может быть тогда линейно разделена какой-то гиперплоскостью.
Вот встает такой вопрос, всегда ли это возможно. Возможно, что именно? Если выборка линейно неразделима, то есть решение задачи классификации найти нельзя. Можно ли ее как-то там подправить, чтобы новая выборка линейно разделилась?
Ответ да. Это можно всегда. Вложить в вашу выборку пространство большей размерности, чтобы в нем уже ваши дополненные точки всегда были линейно разделимы.
Почему так можно сделать? И вопрос а сколько новых координат надо добавлять? Здесь ответ дается теоремой Мерсера.
Я не знаю, буду ли я доказывать. Это называется обобщенное Гильбертово пространство признаков. Мораль такая, что есть всегда подходящее вложение. Сила ядерного метода в том, что не надо это пространство искать явно. Надо придумать функцию ядра, и в общем там решение задачи разделения классов можно искать при помощи, в общем, без всякого вложения, в общем решение можно найти.
Но ядра бывают разные, какое взять, это искусство, это сайентисты. Я там спрашивал у одного нашего коллеги, там в Самсунге работал руководитель лаборатории, как ядро искать для заданной выборки, он сказал, никак, просто подбираем, там что-нибудь получится и хорошо. Таким образом, мы сейчас что поняли? Простейший вид у нас лекции вводной, я рассказываю только самые простейшие решения. Самая простейшая постановка задач.
Дана обучающая выборка, по ней надо построить хоть какую-нибудь линейную структуру, которая дает ответ на задачу классификации. То есть заданные классы для некоторых объектов у нас имеются, то есть класс это ответ. И мы ищем ответы на новые объекты путем построения.
Самого простого классификатора, который только может быть, это линейный классификатор. Если даже выборка линейно неразделима, все равно мы ее можем подправить, чтобы новый вид уже был линейно разделим. Для нас сейчас все выборки линейно разделимы.
Точнее говоря, мы так можем подправить, но для нас очень важен ответ на самый первый вопрос. Исходная выборка, является ли она линейно разделимой. Есть ли хоть одно решение задачи построения этой линейной структуры, которая гиперплоскость. Вопрос, как это определить.
Здесь я только могу сказать, такое необходимое достаточное условие, когда выборка является линейно разделимой. Условие такое, это если угодно теорема 1, есть такое понятие выпуклой оболочки множества точек. Я не знаю, на разных факультетах. Наверное, есть практика по программированию.
Вот выпуклая оболочка. Всем известно, что это такое? Значит так, выпуклое множество в n-мерном пространстве это множество, которое вместе с каждой парой точек содержит отрезок, соединяющий эти точки.
Это известно, да? И, значит, выпуклая оболочка это наименьшее выпуклое множество, которое содержит заданное множество. То есть вот имеется у нас...
С это выборка, S, S, X может быть. Это первые компоненты пар. У нас пары, их конечно множество.
Давайте мы возьмем все первые компоненты. Это будут точки в инмерном пространстве. Значит, эти точки образуют множество Sx, а вот если мы разделим их на две совокупности, одна это те объекты, у которых y равен 1, ну это мы обозначим Sx+, а другая это будет Sx-. Значит, Sx+, это вот то, что я написал здесь, C+.
Это объекты, у которых признак равен единице, и Sx-объект, у которых признак равен нулю. Это конечное множество векторов. И мы для каждого из этих множеств строим выпуклую оболочку.
То есть, конвекс выпуклый. Вот такая и вот такая. Теорема номер один. Есть линия на разделимость, есть строгая линия на разделимость.
Точки могут быть такие, что прямая гиперплоскость. То, что я говорю прямая, это на двумерном рисунке она прямая. Когда n больше чем 2, то это уже гиперплоскость называется.
Даже не гиперплоскость, а гиперпространство. Пусть это будет гиперплоскость. Это множество решений.
Когда у нас заданы W и W0, множество решений с переменными ксиитами, это уравнение называется гиперплоскость. Она разделяет наши... С плюс и С минус строго, если ни одна точка из С плюс и С минус не попадает на эту гиперплоскость.
То есть там неравенства все строгие. То есть тут не меньше либо равно, а строго меньше. Вот эта строгая разделимость, значит, там либо по одну сторону строго, либо по другую, ни одной точки из этого множества на гиперплоскость не попадает.
Вот. Ну и, значит, вот теорема. Номер один звучит так. Существует гиперплоскость, которая строго разделяет два множества заданных, тогда и только тогда, когда выпуклые оболочки этих множеств имеют нулевое пересечение. То есть вот это пересеченное с вот этим равно пустому множеству.
Вопрос, как это доказать. Я уже сказал, что выпуклая оболочка это наименьшая выпуклая оболочка, содержащая данное множество. А вы крутите прибор, а то я хожу туда-сюда, может не попасть.
Когда у вас конечное множество точек, как строится их выпуклая оболочка? Вот у нас на мехмате. Правда, не на всех кафедрах, но студенты решают такую задачу. По-моему, она есть в книге «Олимпиадные задачи Шеня» и «Программирование теоремы и задачи». А еще она есть в книге Кушнеренко и Лебедева, называется «Программирование для математиков».
В общем, выпукло оболочком множество точек. Это многогранник. Есть разные многогранники, мы их можем ужимать до тех пор, пока это возможно. То есть самый маленький многогранник содержащий, я даже может быть на плоскости это изображу, вот у вас точки, вот такая, такая, такая, такая, такая, такая, да, вот их выпуклая оболочка. Надо найти такой периметр, который содержит все остальные точки.
Это она внутри уже находится. Короче говоря, выпуклая оболочка для задного множества точек это такой многогранник, то есть объект, у которого есть вершины, грани, ребра. Вот и он.
Самый маленький из всех. Давайте я еще раз напомню, что множество выпукло, если оно вместе с каждой парой точек содержит отрезок, соединяющий эти точки. Выпуклая оболочка можно определить формально как пересечение. Бесконечное множество их будет, но пересечение всех выпуклых множеств, содержащих заданное множество. Теперь давайте вот эту теорему, я теорему даже не написал, но вы ее напишите словами.
Еще раз теорема про то, что если множество двух, вернее так, два класса линейно разделимы, тогда и только тогда. Давайте я это напишу все-таки. Теорема 1. Си плюс х.
Питая си минус х, они разделимы тогда и только тогда, когда это пересечение, которое я там написал, равно пустому множеству. Давайте докажем слева направо. Пусть эти классы линейно разделимы.
Один содержится в полупространстве, которое не содержит точек из разделяющей гиперплоскости. Это открытое полупространство. На плоскости это просто полуплоскость без границы.
Эта полуплоскость является выпуклым множеством. Это надо доказать. Это все могут доказать?
Или как-то еще надо это пояснить? Почему полупространство это выпуклое множество? Ну, не знаю, даже как-то там мне казалось, что...
Ну, то есть можно считать так, что, допустим, это все точки... Ксииты переэлеменные, для которых верны все вот эти неравенства. Рассмотрим произвольную пару точек из полупространства.
Первую точку это ксииты с индексом 1, вторая точка это тоже набор ксииток с индексом 2. Известно из линейной алгебры уравнение отрезка, которое соединяет... данную пару точек. Есть такое, значит, вот t xi1 плюс 1 минус t xi2. Вектор это значит n-мерный вектор.
Точки можно складывать, их можно умножать на числа, вы знаете это, да? Вектора можно на числа умножать, вектор умножить на число t. t принадлежит отрезку 0,1.
Ну хорошо, вот это отрезок, то есть вектор xi1 и xi2 это точки. Отрезок, который их соединяет, это тоже вектора. Все вектора из этого семейства, где t пробегает 0,1, это отрезок, соединяющий xi1 и xi2.
Докажите, пожалуйста, сами, что если xi1 и xi2 этому неравенству удовлетворяют, то тогда их вот такая вот сумма тоже удовлетворяет этому же неравенству. Это просто доказать. Если это так, то умножить на t больше, чем tw0, и умножить на 1-t, тоже, вот второй тоже, больше либо равно. тогда такая сумма больше либо равна Тw0 плюс 1 минус Тw0.
В общем, это все я доказал уже сам. Значит, полупространство это выпуклое множество, и нам известно, что первый класс целиком содержится в одном полу... пространстве, а второй в другом.
Значит, два выпуклых множества содержат наши классы и они не пересекаются, да, вот у них пересечения нету. Это по одну сторону от прямой, это по другую, нет ни одной точки, чтобы она одновременно была по обе стороны от прямой. Вот, значит, мы нашли пару выпуклых множеств, каждый из которых содержит какой-то из наших классов, и они не пересекаются. Ну, тогда по приоритету выпуклой оболочки.
Конвы будут подмножествовать в этих выпуклых множеств. Это наименьшие выпуклые, то есть какой-то есть, а наименьший это значит вот еще меньше, чем то, что у нас уже есть. Если полупространство содержит наши классы и не пересекаются, тогда и выпуклооболочки тоже не будут пересекаться, потому что они содержатся в этих полупространствах. В одну сторону мы доказали, что Как доказать в обратную сторону, если балочки не пересекаются, то тогда можно линейно разделить. Это сложнее.
Здесь надо математику использовать. Компакт это центральное понятие в математическом анализе, а машинное обучение основано на математическом анализе. Там все алгоритмы используют то, что некоторые множество объектов, компакт.
Почему важен компакт? Потому что, ну вот сейчас мы будем рассмотреть ситуацию, значит, выпуклая оболочка является компактом. Это надо тоже доказать.
Ну давайте, я сейчас, допустим, это принимаю как данность. А значит, если... Да, значит, еще такое... Да, компакт это замкнутое ограниченное множество, знаете, да?
Значит, вот у нас... Вот эти самые выпуклые оболочки это замкнутые ограниченные множества ВРН. Это компактные множества. И есть такое понятие, вернее теорема, что непрерывная функция на компакте достигает своего наибольшего и наименьшего значения.
Все помнят эту теорему? Мы сейчас такую штуку сделаем. У нас есть два компакта. Давайте введем функцию ρ от x плюс запятая x минус.
Значит, x плюс это произвольная точка выпуклой оболочки вот этого множества в одном компакте, а x минус в другом. Ну и значит, у вас имеется функция ρ. Да, ρ это расстояние Евклидова обычное, то есть корень суммы квадратов. И эта функция опрелена на декартовом произведении ваших компактов, у нее аргументами является пары.
И есть теорема, я ее тоже не доказываю, что декартовое произведение компактов это тоже компакт. Вот у вас таким образом ρ. Это функция из конф S плюс X запятая конф.
Да, крестик, крестик. крестик conf Sx минус vr, вот эта функция больше нуля, то есть если вы возьмете любые две точки, то они разные, значит расстояние между ними больше нуля. Значит давайте я вам даю домашнее задание доказать, что декартово произведение компактов это компакт. Второе, функция расстояния между точками, вот одна из...
С плюс, вторая из С минус, она непрерывна. И по теореме Каво, все-таки Кантера или Верфстрасса, забыл я, но неважно. То есть функция, определенная на компакте, принимает наибольшее и наименьшее значение.
Есть наименьшее значение у этой функции ρ. То есть есть какие-то точки в наших выпуклых оболочках. такие, что функция ρ принимает наименьшее значение на паре из этих точек.
Они конкретные есть, я их нарисую и соединю отрезочком. Этот отрезочек имеет длину больше нуля. Я поделю отрезочек пополам, давайте будем считать, что это половина.
На самом деле можно любую точку внутренности этого отрезка выбрать. И через эту точку проведу перпендикуляр. То есть на плоскости это просто прямая перпендикулярная моему отрезку, который соединяет эти точки, у которых расстояние наименьшее.
Я утверждаю, что вот этот перпендикуляр как раз и будет линейно разделять мои точки, то есть мои две выпуклые оболочки. Одна содержит S, вторая содержит S-. Ну вот, как это можно было бы доказать? Здесь геометрические методы.
Давайте будем считать, что это перпендикуляр, а это серединка. У меня точка перпендикуляр. Здесь нарисую. Вот у меня S, вот у меня S-. Вот пара точек таких, что они принадлежат.
Первая принадлежит S, вторая принадлежит S-. Точнее говоря, это выпуклая оболочка. Это конф, и это тоже конф. Точки принадлежат выпуклым оболочкам.
Я нарисовал прямую, значит, я буду строить доказательства для прямой. В инверном случае доказательства абсолютно такой же. Значит, вот у меня точка, которая принадлежит первой выпуклой оболочке.
Значит, я знаю, что... Или вот как мы рассмотрим. Давайте здесь нарисуем стрелочку и нарисуем произвольную точку из полупространства, которое слева от прямой.
Если мы соединим эту точку с нашим центром, то есть серединой нашего отрезка, то угол всегда будет больше 90 градусов. А если мы нарисуем любую точку из правого полупространства, соединим ее вот с этим центром О, то угол всегда будет меньше 90 градусов. Вот, ну и теперь, значит, у нас вот какая ситуация.
Значит, нам известно, что это лежит по одну сторону от нашей гиперплоскости, а это лежит по другую сторону. Ой, извиняюсь, извиняюсь, я неправильно сказал. я должен как раз доказать, что точка из этого множества всегда лежит по одну сторону от гиперплоскости. Сказать это и это это то же самое, что сказать, что если мы соединим точку отсюда с нашим нулем, то угол всегда будет тупой. Вот этот угол всегда будет тупой.
Вот, значит, если вдруг возникнет ситуация, что какая-то... Так, сейчас, сейчас, сейчас, я вспомню, как это доказывается. Ну, значит, короче говоря, вот если точка лежит... То есть я рассматриваю, значит, сейчас расстояние. Мне известно, что это расстояние меньше либо равно вот этого расстояния.
Я не могу... Все точки, которые принадлежат одному классу, почему все они находятся... по одну сторону от этой гиперплоскости, которая, я напомню, бралась как перпендикулярная гиперплоскость к этому отрезку и проходящая через его середину.
Если бы нашлась какая-то точка... Сейчас... Значит, вот... Вот это расстояние у меня минимальное. То есть, если я нарисую, возьму любую точку из левого класса, то вот это...
Расстояние до вот этой точки будет больше. То есть для данной пары точек расстояние наименьшее. То есть расстояние от вот этой точки до правого конца этого отрезка уже будет строго больше, чем вот это расстояние. Значит, здесь, смотрите, если бы... Какая-то точка отсюда.
Мы можем нарисовать круг вокруг этого центра. Все точки, у которых расстояние до этой меньше либо равны, чем длина этого отрезка. Понятно, что точки из этого класса лежат левее этого круга.
Это означает, что вся эта выпуклая оболочка лежит левее этого круга. и она целиком содержится в полуплоскости, которая является перпендикулярной нашему отрезку. Давайте так, я не все должен вам говорить детально, я хочу, чтобы вы сами доказали это.
Геометрически это тривиально. Все, что находится за пределами этого круга, и у них расстояние. На самом деле, может быть, ситуация такая, что какая-то точка попала вот сюда. Попала во второй класс.
Если точка попала во второй класс, и вот этот отрезочек, правый его конец, тоже попал во второй класс, тогда и все. все, что между этими точками, то есть сам отрезочек, соединяющий вот эту точку и конец этого отрезочка, тоже попал бы целиком в выпуклую оболочку, поскольку концы его попали в эту выпуклую оболочку. Ну а то, что находится вблизи второй точки, попало вот в этот вот круг, в который нельзя заходить. В общем, мы поняли, что то, что находится в одном классе...
оно целиком содержится по одну сторону этой прямой, которая перпендикулярна середине этого отрезка. Это я еще попозже более детально расскажу, сейчас я только в виде задачи. Мне сейчас важно еще некоторые вещи доказать. Мы поняли, что выпуклая оболочка множества точек это компакт.
Откуда мы это взяли? Давайте я сейчас это в виде задачи вам сформулирую. Выпуклую оболочку можем определить еще одним способом.
Вот как. Если у нас имеются точки кси-1 и так далее кси-n, как мы можем определить выпуклую оболочку не абстрактно, как наименьшее выпуклое множество, содержащее данные точки, а как что-то алгоритмическое. Значит, вот докажите это, Лемма.
которая вот как звучит. Выпуклая оболочка вот такого множества точек равна таким вот выражением. Сумма t и тых, xi и тых, значит, и от единицы до n, и с таким свойством, что... Так, это вот сумма таких выражений, таких, что сумма t и тых равна единице, и каждый из них... или да, каждое t и t больше либо равно нуля.
Вот, значит, выпуклая оболочка это все такие суммы, это говорят, выпуклые комбинации этих векторов. Значит, вот это надо доказать, и это надо использовать для доказательства замкнутости ограниченности выпуклой оболочки. Если выпуклая оболочка это то, что написано справа, то ограниченность просто следует из того, что норма вектора справа не превосходит суммы норм. Теиты не превосходят единицы, а норма ксиитова ограничена величина, и у нас их конечное множество.
У нас таким образом ограниченность есть. Почему есть замкнутость такого множества? Надо рассмотреть произвольную последовательность точек из этого множества и доказать, что ее предел тоже будет принадлежать этому множеству.
А это, наверное, проще сделать. Не так, а вот как. У нас, когда есть конечное множество, оно ограничено, оно в шаре может целиком содержаться.
Шар это выпуклое множество. Это множество замкнутое. И выпуклое множество можно считать все замкнутыми. То есть, если множество выпуклое, то его пополнение предельными точками тоже будет выпуклым. И пересечение всех таких замкнутых выпуклых множеств, это тоже будет множество замкнутое, это тоже надо доказать.
Пересечение любого числа замкнутых множеств, это тоже замкнутое множество. В общем, все, мы доказали то, что выпуклая оболочка это компакт. Так, значит, и таким образом сейчас мы решили нашу...
полностью. Так, ну вот вопрос, значит, таким образом мы абстрактно доказали, что разделяющая гиперплоскость существует. Вопрос, а как же ее строить? Ну, значит, вот я на следующей лекции расскажу теорему, в которой алгоритм, то есть там имеется алгоритм, вот он такой проблематичный. Это на самом деле был алгоритм обучения одного нейрона.
И там алгоритм строит хоть какую-то разделяющую гиперплоскость для выборки, которую можно линийно разделить. Но вот меня всегда волновал вопрос, а какого качества будет решение, которое будет давать этот алгоритм. Но это мы в следующий раз тогда изучим.
Так, ну все, я сегодня заканчиваю пораньше, а так у нас обычно в 16.40 будет связано. Все, спасибо большое за внимание.