[БЕЗ_ЗВУКА] В машинном обучении есть важный класс задач, занимающий промежуточное положение между задачами классификации и кластеризации, — это задачи с частичным обучением. Как обычно, у нас имеется выборка объектов, но метки учителя заданы только на части этих объектов, а часть объектов остается неразмеченной. Такие ситуации все чаще и чаще стали возникать в приложениях, связанных с анализом больших данных, особенно с анализом данных Интернета. Часто мы можем привлечь асессоров для того, чтобы разметить какую-то коллекцию документов, но если документов миллионы, размеченными могут быть тысячи. То есть, как правило, размеченных объектов много меньше. Есть два варианта постановки этой задачи. Один принято называть «частичное обучение», и там строится так же, как и в методах классификации, отображение, которое каждый объект может классифицировать. А другая постановка задачи — это трансдуктивное обучение — основана на предположении, что у нас никогда не будет других объектов, и нам не нужно строить функцию, которая способна классифицировать любой объект, а придется работать только с теми объектами неразмеченной выборки, которые у нас есть. Типичные приложения для задач частичного обучения — это классификация и категоризация текстов, изображений, сигналов, видео-, звукозаписей и так далее. Несколько примеров, которые показывают, что задачи с частичным обучением действительно не сводятся ни к классификации, ни к кластеризации. Первый пример: допустим, что у нас есть такая вот искусственная выборка, которая порождена двумя гауссовскими распределениями. Распределения совершенно одинаковые по форме. Разделяющая поверхность оптимальная должна быть прямой линией. Но если у нас размеченных объектов только по 5 штук в каждом классе, то плотности, которые мы восстановим по такой маленькой выборке, неизбежно будут сильно отличаться от исходных плотностей, и в результате разделяющая поверхность тоже получится сильно искаженной формы. А вот если бы мы знали, что есть еще огромная масса неразмеченных объектов, и видели бы, что к размеченным объектам близко подходят неразмеченные, и как-то смогли бы учесть эту информацию, то мы могли бы построить разделяющую поверхность правильней. То есть информация о плотности распределения объектов в пространстве. Вот другой пример, совершенно хрестоматийный: 2 кластера, которые имеют форму полумесяцев (или иногда их называют бананами), и если у нас для каждого их этих кластеров размечено только по одному объекту. Давайте представим, что произойдет, если мы воспользуемся любой моделью классификации — ну, скажем, методом ближайших соседей. По сути, для него выборка состоит из двух объектов, и метод ближайшего соседа тогда проведет ровно посередине между ними разделяющую гиперплоскость, и картинка окажется совершенно не такой, которую мы ожидали. Другой пример, что также задача не может быть сведена и к кластеризации. Представим себе, что в этой же искусственной задаче у нас теперь размечены 3 объекта, и учитель указал, что во втором классе объекты на разных концах все-таки должны относиться к разным классам. И тогда нам придется перекрасить второй кластер совершенно по-другому. То есть разметка учителя она имеет приоритет перед той кластеризацией, которую нам даст метод кластеризации, не учитывающий метки учителя. Поэтому задача частичного обучения она содержательна и не сводится только лишь к классификации или только лишь к кластеризации. Однако методы классификации могут быть легко приспособлены для решения задачи частичного обучения. Мы сейчас рассмотрим несколько таких простых способов, которые, как говорят, являются обертками над методами классификации, то есть они используют готовый метод. Итак, пусть у нас есть метод обучения, который произвольной обучающей выборке с метками учителя может поставить в соответствие некий алгоритм классификации. Мы будем предполагать, что этот алгоритм классификации имеет вид arg max от оценки степени принадлежности объекта x к классу y. Практически все методы классификации, которые мы изучаем, имеют такой вид, то есть сначала вычисляется оценка степени принадлежности объекта по всем классам, а потом объект относится к тому классу, для которого эта оценка максимальна. Мы можем вычислить величину разности этой оценки для того класса, для которого она максимальна, и максимум по всем остальным оценкам. Это очень похоже на ту величину, которую мы называли отступом (или margin по-английски) для задач классификации, но здесь отличие заключается в том, что в определении отступа фигурирует правильный класс объекта yi-тый, а здесь вместо yi-того мы используем ai-тое. Это тот класс, для которого оценка степени принадлежности, выданная алгоритмом a, максимальна. То есть это класс, в котором алгоритм максимально уверен. Собственно, алгоритм самообучения заключается вот в чем: что сначала классификатор обучается на той небольшой доле объектов, которая размечена, потом для всех остальных объектов вычисляются вот эти самые псевдо-отступы, и те объекты, для которых они оказались самыми большими, мы считаем, что они правильно классифицированы, и добавляем их вместе с этими метками в обучающую выборку и снова обучаемся на расширенной обучающей выборке. Вопрос: сколько нам каждый раз нужно добавлять объектов в обучающую выборку? Можно по-разному это определять. Можно ставить порог отсечения по значению отступа (псевдо-отступа) и считать, что если он больше заданной величины, то значит, классификация надежна. Мы можем считать ее как правильно определенную. А можно просто заданное количество объектов на каждой итерации классифицировать и выполнять ими обучающую выборку. То есть если мы 5 % объектов добавляем каждый раз, то за 20 итераций мы их всех исчерпаем, и у нас не останется неразмеченных объектов. Вот такой вот простой алгоритм. Придуман был он очень давно и использовался еще задолго до того, как возник Интернет и задачи на больших данных. Другой алгоритм, который очень похож, эксплуатирует аналогичную идею, но все-таки здесь появляется некий новый элемент, а именно — предположение, что у нас есть два совершенно разных метода обучения, которые будут обучать друг друга. То есть для каждого из них мы вычисляем вот эти самые псевдо-отступы, но объекты, которые надежнее всего классифицированы одним объектом, одним алгоритмом, мы добавляем в обучающую выборку для другого алгоритма, и наоборот. И так они обмениваются опытом и уточняют классификации друг друга. Есть следующая идея, в которой используется уже не один, не два, а произвольное число методов обучения. Он называется co-learning, но фактически это тот же самый self-training, если мы в качестве одного общего метода обучения возьмем всю композицию — простое голосование базовых алгоритмов, где оценки принадлежности просто вычисляются как сумма оценок принадлежности по алгоритму. Фактически, ничего особо нового этот метод не привносит, но дает дополнительную уверенность в том, что мы правильнее будем классифицировать объекты. Итак, мы увидели, что задачи с частичным обучением, это отдельный содержательный класс задач, пограничный между классификацией с учителем и кластеризацией без учителя. Мы увидели, что существуют достаточно давно изобретенные методы-обёртки, которые позволяют любой метод классификации приспособить для того, чтобы решать задачи с частичным обучением. К сожалению, они не очень вычислительно эффективны, потому что они предполагают многократное применение метода обучения к всевозрастающим объемам выбора. Есть другие подходы: это как приспособить методы кластеризации, залезть к ним внутрь и что-то в них поменять, модифицировать, чтобы учесть ограничения на размеченных объектах, и как приспособить методы классификации. Об этом мы поговорим в следующих лекциях. [БЕЗ_ЗВУКА]