[БЕЗ ЗВУКА] Сегодня мы рассмотрим один важный класс методов машинного обучения — это методы, использующие функции расстояния или метрики в пространстве объектов. Исходная идея их использования лежит в предположении, что в практических задачах часто встречаются зависимости, которые непрерывны. Таких зависимостей вообще очень много в природе, в технике. Но это понятие непрерывности оно скорее подходит для задач восстановления регрессии. А в задачах классификации аналогом непрерывности является так называемая гипотеза компактности — предположение о том, что близкие объекты, как правило, лежат в одном классе. Что такое близость между объектами, как ее можно формализовать? Как правило, задается некая функция расстояния — это функция от пары объектов, которая паре ставит соответствие — неотрицательное число. Часто еще накладывают требование, чтобы это была метрика в пространстве объектов, то есть чтобы она была и симметричной, и выполнялось неравенство треугольника. Однако формально в методах нигде не используется предположение о том, что это метрика, поэтому, в общем-то, и функции расстояния, не являющиеся метриками, нам тоже подходят. Самым известным примером расстояния, наверное, является евклидово расстояние в признаковом пространстве. Напомню, что объекты, как правило, у нас задаются n признаками. Если эти признаки числовые, то мы можем использовать знакомую нам со школы конструкцию — евклидово расстояние. Можно эту конструкцию слегка обобщить, чтобы получить дополнительную гибкость в модели: например, ввести вместо двойки какую-то другую степень p или ввести веса признаков wj-тое. Но появление параметров оно, конечно, всегда потребует от нас неких дополнительных усилий, неких процедур, которые будут обучать эти параметры. Но далеко не всегда, не во всех задачах, именно использование евклидовой метрики осмысленно, и есть масса задач, где у нас исходно нет признаковых описаний объектов, и гораздо проще пользоваться не признаками, а непосредственно мерять расстояние между объектами. Примеры таких объектов — это символьные строки. Это могут быть тексты естественного языка, это могут быть нуклеотидные или аминокислотные последовательности, которые изучаются в биоинформатике. И вот в таких задачах, чтобы сравнить текстовые строки, вообще говоря, произвольной длины, часто используется так называемое редакторское расстояние Левенштейна — это количество вставок и замен символов, которое необходимо произвести, чтобы привести одну строку в другую. Ну вот описать две сравниваемых строки признаками было бы намного труднее, чем посчитать вот такое вот расстояние, которое к тому же достаточно эффективно считается. Другой, очень похожий пример, но уже между объектами еще более сложной природы: допустим, мы хотим сравнить 2 подписи, которые сделали люди специальным пером электронным, которое запоминает координаты кончика пера ну и еще азимут движения пера. Значит, мы как подпись имеем 3 кривые, 3 временных ряда, и нам нужно сравнивать такие временные ряды. Ну, на картинке представлен пример такого сравнения, когда 2 похожие буквы сравниваются, и мы видим, что эти 3 кривые они очень похожи с точностью до каких-то сжатий, растяжений, выравниваний. Можно придумать модель расстояния между такими траекториями, как модель пружинок, которые слегка сжимаются или растягиваются между маленькими локальными кусочками этих кривых, и посчитать энергию сжатий и растяжений пружинок — это и будет расстояние между этими объектами. Расстояние посчитать легко, а придумать здесь признаки было бы значительно сложнее. Таким образом, расстояния бывают разные в прикладных задачах. Допустим, что кто-то нам уже дал функцию расстояния и теперь перед нами стоит задача — научиться классифицировать объекты. Ну, наверное, самый простой алгоритм классификации вообще из всех алгоритмов, известных в машинном обучении, — это алгоритм ближайшего соседа. Чтобы классифицировать объект x, давайте возьмем все объекты обучающей выборки и найдем среди них ближайший к x, и отнесем x к тому же классу, к которому принадлежит этот объект. Ну, конечно же, использовать для классификации только одного ближайшего соседа — это не очень удачная идея, лучше взять окрестность, учесть несколько ближайших соседей, как-то по ним усреднить. И поэтому возникает такая обобщенная идея: давайте упорядочим все объекты обучающей выборки по возрастанию расстояний до нашего классифицированного объекта x и еще дополнительно введем вес i-того соседа или его ценность, полезность при классификации объекта x. Будем обозначать этот вес w(i, x), то есть это функция от объекта и от порядкового номера соседа. Ну если мы усредним в каждом классе значение вот этих весов, то мы получим в итоге оценку близости объекта к классу: мы ее обозначаем Γ с индексом y от объекта x. Индекс y показывает, что такая оценка она относится к определенному классу. Ну и самый естественный принцип классификации — это отнести объект x к тому классу, для которого эта оценка близости максимальна. Есть масса частных случаев этой общей формы метрического алгоритма классификации. Ну, например, это метод ближайших соседей или совсем уж его частный самый простой случай — это метод первого ближайшего соседа. Преимущество этого метода в том, что он очень просто реализуется, еще говорят, что это «ленивое» обучение, потому что, собственно, никакого обучения здесь не происходит — мы просто запоминаем выборку, и потом классификация заключается в поиске ближайших соседей. Ну вот параметр k — число соседей, которое мы учитываем, он очень полезен тем, что его можно пытаться оптимизировать и выбрать его так, чтобы классификация была максимально надежной. Дело в том, что если мы берем слишком мало соседей, то среди них могут оказаться какие-то случайные шумовые выбросы. Если мы берем слишком много соседей, то мы слишком простой классификатор построим, который в любой точке пространства по сути будет выдавать одно и то же значение. И где-то посередине находится тот классификатор, который действительно будет прилично работать. Проблемы метода ближайших соседей, во-первых, в том, что мы можем столкнуться с ситуацией, когда для двух классов оценки степени близости объекта к классу совпадают, и мы поэтому не понимаем, к какому из этих двух классов отнести наш объект. А другой недостаток в том, что мы нигде не учитываем сами значения расстояний. После того как мы отранжировали объекты обучения по возрастанию расстояний, у нас остались только порядковые номера этих объектов. Может возникнуть ситуация, когда вы, например, классифицируете по пяти ближайшим соседям: четыре соседа находятся действительно близко от объекта, а пятый где-то совсем далеко. Конечно, в таком случае его надо было бы учесть с меньшим весом. Ну а... И пару слов о том, как происходит оптимизация параметра числа ближайших соседей и почему обязательно надо использовать функционалы, которые сам классифицируемый объект изымает из обучающей выборки. Нам этом графике приведены две кривые: это известная уже вам выборка цветков ириса, и использованы два алгоритма. Первый алгоритм — это классификация методом k ближайших соседей. И когда классифицируется некий объект обучающей выборки, сам же он является своим собственным соседом, и это дает синюю кривую. Если же сам объект исключается из числа своих соседей, получается красная кривая. Ну видно, что синяя кривая нам дает оптимистически смещенную оценку числа ошибок на контрольных выборках. И видно, что... Нам кажется, что оптимально использовать одного соседа, но если объект сам же является своим собственным соседом, то понятно, что это некий обман и так делать нельзя. И здесь на красной кривой мы видим, что в данной задаче оптимально брать где-то от 30 до 60 соседей, а синяя кривая нам дает ложный ответ, что надо пользоваться методом первого ближайшего соседа. Этот метод практически никогда не работает надежно. [БЕЗ ЗВУКА]
