Обучение с учителем

Всем привет! Мы учёные лаборатории Машинное обучение ИТМО и команда Core ML ВКонтакте проводим совместные исследования. Одна из важных задач VK заключается в автоматической классификации постов: она необходима не только чтобы формировать тематические ленты, но и определять нежелательный контент. Для такой обработки записей привлекаются асессоры. При этом стоимость их работы можно значительно снизить с помощью такой парадигмы machine learning, как активное обучение.

Именно о его применении для классификации мультимодальных данных и пойдёт речь в этой статье. Мы расскажем про общие принципы и методы активного обучения, особенности их применения к задаче, а также инсайты, полученные в ходе исследования.

Введение

Активное обучение это раздел machine learning, где модель взаимодействует с учителем. Она запрашивает у него для тренировки лишь те данные, которые позволят обучиться лучше и, следовательно, быстрее.

Это направление интересно компаниям, которые привлекают асессоров для разметки данных (например, с помощью сервисов Amazon Mechanical Turk, Яндекс.Толока) и хотят удешевить этот процесс. Один из вариантов использовать reCAPTCHA, где пользователь должен отмечать снимки, скажем, со светофорами, и заодно получать бесплатную разметку для Google Street View. Другой способ применять активное обучение.

Некоторые уже сейчас используют его для оптимизации краудсорсинга и делятся опытом. Например, Voyage компания, которая занимается автопилотируемыми автомобилями. В статье её специалисты рассказали, как активное обучение позволило им не только сэкономить на разметке данных, но и повысить предельную точность модели. Их подход к активному обучению очень похож на тот, о котором расскажем мы.

Компания Amazon в своей работе описывает фреймворк DALC (Deep Active Learning from targeted Crowds). Он раскрывает концепцию активного обучения с точки зрения нейронных сетей, байесовского подхода и краудсорсинга. В исследовании в том числе используется техника Monte Carlo Dropout (о ней мы тоже поговорим в этой статье). Ещё авторы вводят любопытное понятие noisy annotation. Если в большинстве работ по активному обучению предполагается, что асессор говорит правду и ничего, кроме правды, то здесь допускается вероятность ошибки в силу человеческого фактора.

Про ещё одно исследование от Amazon можно прочитать здесь. В нём рассматривается концепция иерархической разметки: когда асессор вместо классической одноклассовой разметки объекта должен дать бинарный ответ о его принадлежности к определённому надклассу/классу в иерархии. При этом бинарные вопросы, как и объект для разметки, выбирает сам алгоритм. Таким образом, конечная разметка может получиться неполной: будет определён не конечный класс объекта, а его категория. Однако этого будет достаточно для обучения.

Но хватит говорить про использование парадигмы пора рассмотреть активное обучение в деталях! У него есть несколько основных подходов, или сценариев. В нашем исследовании модель взаимодействовала с учителем по сценарию pool-based sampling.

Рис. 1. Общая схема pool-based сценария активного обучения

Поясним суть этого сценария. Допустим, есть некоторое количество размеченных данных, на которых модель уже обучена (то есть прошла пассивную фазу обучения). Далее с её помощью уже можно оценивать неразмеченные данные: определять, насколько они пригодятся для дальнейшего обучения.

Наиболее полезные данные отправляются на разметку эксперту, чтобы затем вернуться для дообучения модели уже в активной фазе. Отправленные на разметку данные называют запросом (англ. query). Запрос может состоять как из одного объекта, так и из нескольких. Способы выбора объектов пула для запроса к эксперту (иными словами, способы оценить полезность данных) называются стратегиями активного обучения.

Далее опишем, как устроена решаемая задача и набор данных, и рассмотрим конкретные стратегии активного обучения на примере.

Набор данных и задача

Напомним, общая задача классификация постов ВКонтакте. Они представляют собой мультимодальные данные (изображение и текст). Предоставленный набор данных включает 250 тыс. готовых эмбеддингов постов. Здесь каждый объект (пост) размечен одним из 50 классов тематик публикаций и опционально содержит:

1. векторное представление, или эмбеддинг (англ. embedding), картинки поста;
2. векторное представление текста.

Стоит отметить, что набор данных сильно несбалансирован (см. рис. 2).

Рис. 2 гистограмма распределения классов

Модель для классификации

Важный этап в решении любой задачи ML и активного обучения в частности выбор оптимальной базовой модели. То есть той, на основе которой будет сравниваться активное обучение с пассивным.

Одним из ключевых требований к модели было отсутствие переобучения. Дело в том, что активное обучение подразумевает постоянное дообучение модели. А если она будет переобучена, то, как бы мы ни выбирали новые данные, точность не возрастёт значительно или вовсе будет уменьшаться. Конечно, можно было бы на каждом шаге активной фазы обучать модель с нуля, останавливая процесс с помощью early stopping. Но это сделает эксперименты слишком долгими, так как вместо одной эпохи дообучения на новых данных потребуется несколько десятков.

В проекте мы экспериментально изучили различные конфигурации глубоких нейронных сетей. Проводились эксперименты с добавлением residual соединений, highway блоков, использованием энкодеров (англ. encoder). Рассмотрели разные варианты, учитывающие мультимодальность на основе слияния (англ. fusion): метод внимания для мультимодальных данных, матричное слияние.
Но некоторые способы учёта мультимодальности данных невозможно было применить к нашей задаче например, выравнивание и обучение различным представлениям. Это связано с готовым представлением данных в виде предобученных векторов-эмбеддингов.

Впрочем, предмет этой статьи не классификация мультимодальных данных как таковых, а активное обучение. Так что не будем подробно останавливаться на выборе базовой модели, а опишем лишь конечную.

Критерием для выбора итоговой модели стала максимизация значения метрики валидационной точности. Итак, в качестве классификатора была подобрана следующая архитектура (рис. 3):

Рис. 3. Подобранная архитектура для классификации

В данной модели производится позднее слияние модальностей. Идея в том, что эмбеддинги картинки и текста сначала обрабатываются по отдельности. Такой подход позволяет уменьшить размер нейронной сети, которая сперва извлекает из каждой модальности необходимую информацию, а потом объединяет их для финального предсказания. Кроме того, три головы модели (отдельно на текст и картинку + объединённая) дополнительно стимулируют сеть обучать веса чтобы извлекать как можно больше релевантной информации для классификации по каждой из модальностей.

Блоки, обозначенные красным и синим на рис. 3, имеют следующий вид:

Рис. 4. Описание основных блоков модели нейронной сети для классификации

Любопытно то, что изначально разрабатывалась модель с одним выходом, а дополнительные планировалось использовать для различных стратегий активного обучения. Но оказалось, что подобранная архитектура показывает бльшую точность, чем аналогичная модель с одним выходом, объединённым по двум модальностям.

Один из закономерных и важных вопросов, которые возникли при построении этой архитектуры: как считать функцию потерь? Варианты:

1. простое покомпонентное суммирование элементов функции потерь с разных голов;
2. взвешенная функция потерь с ручным перебором весов;
3. взвешенная функция потерь с обученными весами голов.

Мы выбрали третий вариант. Ещё вдохновились статьёй из области байесовского глубокого обучения: в ней комбинации функций потерь выводятся исходя из формулы maximum likelihood и учёта неопределённости предсказаний, возникающих из-за шума в данных. В итоге мы остановились на такой функции потерь:

где функции потерь для разных выходов модели (в нашем случае они представляют собой категориальную кросс-энтропию), а настраиваемые параметры, характеризующие дисперсию и шум в данных.

Pool-based sampling

С моделью определились теперь опишем, как будем применять и тестировать различные стратегии активного обучения. Согласно сценарию pool-based sampling мы составили пайплайн экспериментов:

1. Берём из тренировочного набора данных какое-то количество случайных объектов.
2. Обучаем на них модель.
3. Выбираем новую пачку данных из оставшегося тренировочного набора, основываясь на тестируемой стратегии, и добавляем их к размеченным данным.
4. Дообучаем модель.
5. Считаем метрики (валидационную точность).
6. Повторяем шаги 35 до выполнения определённого критерия (например, пока не кончится весь тренировочный набор данных).

Первые два шага соответствуют пассивной фазе обучения, шаги 36 активной.

Помимо самой стратегии, в данном пайплайне значимыми являются два параметра, а именно:

1. Размер изначального набора данных, на котором обучается модель во время пассивной фазы. Если этот параметр окажется недостаточным, то сложно будет сравнить эффект от активного обучения и дообучения на случайных данных: точность будет стремительно расти в обоих случаях. Если же, напротив, сделать начальный размеченный набор слишком большим, то модель будет хорошо обучена уже в пассивной фазе. Тогда в активной рост точности будет слабым вне зависимости от метода обучения. В нашем случае оптимальным оказался размер изначального набора данных, равный 2000.

   
   

2. Размер запроса к эксперту. С одной стороны, можно отправлять объекты к эксперту по одному. В этом случае первый объект в запросе будет максимизировать критерий рассматриваемой стратегии активного обучения (при сортировке объектов по убыванию соответствия критерию). И после обучения на этом объекте остальные в запросе, скорее всего, перестанут представлять интерес. Но если выбирать объекты по одному, то эксперимент затянется и всё исследование усложнится. Поэтому мы остановились на 20 объектах в запросе.
   Ещё можно варьировать количество шагов в фазе активного обучения. Очевидно, что с его увеличением точность модели может расти. Но цель нашего проекта не достичь максимальной возможной точности классификации, а исследовать эффективность активного обучения. Поэтому мы решили зафиксировать количество шагов на 100 или 200.

   
   

Теперь, когда мы определились, как и на чём тестировать методы активного обучения, перейдём к их реализации.

Инсайт 1: влияние выбора batch size

В качестве baseline рассмотрим, как обучается модель при случайном выборе данных (будем называть это пассивным обучением) (рис. 5).

Рис. 5. График обучения baseline-модели пассивным способом. Приведён результат пяти запусков с доверительным интервалом

Для достоверности этот и все последующие эксперименты запускались по пять раз с разным random state. На графиках выводится средняя точность запусков с доверительным интервалом.

Здесь мы встретились с первым инсайтом решаемой задачи. На графике обучения с определённым периодом появляются просадки точности, хотя интуитивно кажется, что точность должна монотонно расти.

Чтобы устранить этот эффект, нужно осознать важность параметра размера батча (англ. batch size). В нашем случае он был по дефолту выбран равным 512 из-за большого количества классов (50). Получалось, что при конечном размере размеченного набора данных и фиксированном batch size последний батч мог оказаться крайне мал. Это вносило шум в значение градиента и негативно сказывалось на обучении модели в целом. Мы опробовали следующие варианты решения этой проблемы:

1. upsample, чтобы порции данных были одной длины;
2. увеличение числа эпох обучения, чтобы влияние маленького батча нивелировалось последующими.

Итоговым решением стало формирование адаптивного batch size: на каждом шаге активного дообучения он вычислялся согласно формуле (1).

где изначальный batch size, а текущий размер размеченного набора данных.
Адаптивный подход помог сгладить просадки точности и получить монотонно возрастающий график (рис. 6).

Рис. 6. Сравнение использования фиксированного параметра batch size (passive на графике) и адаптивного (passive + flexible на графике)

Примечание: Эти графики показывают работу модели c одним выходом. Но, не умаляя общности, адаптивный batch size можно применять также для модели с тремя выходами. Так мы и сделали в дальнейших экспериментах.

Теперь перейдём непосредственно к исследованию методов активного обучения для нашей задачи.

Uncertainty

Первыми были реализованы наиболее простые стратегии активного обучения из обзорной статьи методы группы uncertainty sampling. Как следует из названия, стратегия основана на выборе для разметки тех объектов, в предсказании которых модель наименее уверена.

В статье приводятся три варианта подсчёта неуверенности:

1. Минимальная уверенность (англ. Least confident sampling)

В этом виде стратегии эксперту для разметки передаётся объект, наиболее вероятный предсказанный класс для которого характеризуется наименьшей уверенностью:

где класс с наибольшей вероятностью при классификации моделью, один из возможных классов, один из объектов набора данных, объект, выбранный с помощью стратегии наименьшей уверенности объект.

2. Минимальный отступ (англ. Margin sampling)

Согласно этому виду стратегии, алгоритм отправит на экспертизу те объекты, для которых наибольшую вероятность имеют два класса, причём эти вероятности близки:

где наиболее вероятный класс для объекта , второй по вероятности класс.

3. Максимальная энтропия (англ. Entropy sampling)

В этом виде стратегии для измерения неуверенности модели используется мера энтропии:

где вероятность -го класса для объекта при классификации данной моделью.

Согласно обзорной статье, среди перечисленных методов каждый последующий учитывает больше информации, чем предыдущий. Поэтому изначально ожидалось, что метод entropy sampling окажется наиболее эффективным.

Но практические результаты в рамках решаемой задачи показали расхождение с теорией (рис. 7).

Рис. 7. Результаты сравнения различных видов стратегии uncertainty sampling с пассивным обучением (слева с методом минимальной уверенности, по центру с методом минимального отступа, справа с методом максимальной энтропии)

Как можно заметить, методы least confident и entropy sampling показали себя хуже, чем пассивное обучение со случайным выбором объектов для дообучения. В то же время margin sampling оказался более эффективным.

Чтобы читатели не подозревали, что на реализацию методов могли повлиять баги, сразу отметим: все методы были протестированы также на наборе данных MNIST. И на нём, например, стратегия entropy sampling продемонстрировала результаты, не противоречащие теоретической эффективности метода. Можно сделать вывод, что практическая эффективность описанных методов неоднозначна и зависит от конкретной решаемой задачи.

Перечисленные методы просты с точки зрения реализации и обладают низкой вычислительной сложностью. Можно оценить сложность одного запроса к эксперту как , где размер неразмеченного набора данных, а число объектов в запросе к эксперту. Также эти методы легко применять на практике, так как они не требуют изменения используемой модели.

BALD

Следующая стратегия, о которой пойдёт речь, BALD sampling (Bayesian Active Learning by Disagreement). Это байесовский подход к измерению неуверенности комитета моделей.

Согласно классификации методов активного обучения, это представитель стратегии query-by-committee (QBC). Её основная идея в использовании предсказаний нескольких моделей с конкурирующими гипотезами. Можно брать их усреднённое предсказание за основу для uncertainty sampling. Или выбирать для разметки те объекты, в предсказаниях которых модели несогласны в большей степени. Эксперименты проводились с методом QBC на основе Monte Carlo Dropout, речь о котором пойдёт дальше.

Проблема классических байесовских методов для глубокого обучения в том, что необходимо выводить большое количество параметров, а это делает обучение моделей в два раза дороже. Поэтому авторы предложили использовать dropout в качестве способа байесовской аппроксимации. Этот подход отличается от привычного применения dropout тем, что он используется во время инференса (на стадии предсказания). Причём для каждого объекта выборки предсказание делается несколько раз одной и той же моделью, но с разными dropout-масками (рис. 8). Такой способ сэмплирования называется Monte Carlo Dropout (MC Dropout) и не требует увеличения затрат памяти при обучении модели. Так с помощью одной модели можно получить несколько предсказаний, которые могут различаться для одного и того же объекта. Несогласие моделей (где они отличаются друг от друга лишь масками dropout) считается на основе Mutual Information (MI). MI здесь представляет собой эпистемическую неопределённость, или неуверенность комитета, то есть такой вид неопределённости, которая уменьшается с добавлением новых данных. Это согласуется с концепцией активного обучения в целом.

Рис. 8. Иллюстрация MC Dropout для метода BALD

Итак, для начала мы использовали усреднённое предсказание полученного QBC на основе MC Dropout комитета и применили к нему различные методы uncertainty sampling. Это не дало прироста по сравнению с соответствующими методами, использующими только одно предсказание (рис. 9).

Рис. 9. Результаты сравнения различных видов стратегии uncertainty sampling (на основе QBC и без него) с пассивным обучением (слева с методом минимальной уверенности, по центру с методом минимального отступа, справа с методом максимальной энтропии)

На следующем шаге мы использовали меры несогласия комитета по методу BALD. Как уже было сказано, для этого применяется Mutual Information моделей комитета:

где число классов, число моделей в комитете.

Первое слагаемое в формуле (5) представляет собой энтропию усреднённого предсказания комитета, второе среднюю энтропию каждой модели в отдельности. Таким образом, выбираются только те объекты, в предсказании для которых комитет менее всего согласен. Результаты применения метода BALD представлены на рис. 10.

Рис. 10. Результаты применения стратегии BALD в сравнении с пассивным способом обучения

К сожалению, пока что данный метод не дал ожидаемого результата на долгом запуске эксперимента, несмотря на прирост по сравнению с пассивным методом в начале.
Сложность алгоритмов стратегии query-by-committee в целом и BALD в частности пропорциональна числу предсказаний, сделанных для каждого объекта. В свою очередь, сложность предсказания для каждого объекта аналогична методам uncertainty sampling. Таким образом, сложность одного запроса , где размер неразмеченного набора данных, число объектов в запросе к эксперту, а число предсказаний, посчитанных для одного объекта.

На практике применить метод BALD может быть нелегко при использовании фреймворка tf.keras, так как он не обладает достаточной гибкостью для работы со слоями. Поэтому в рамках данного проекта мы выбрали фреймворк PyTorch, который позволил не только с легкостью включать dropout во время инференса, но и отключать batch normalization в течение активной фазы, о чем пойдет речь далее.

Инсайт 2: отключение batch normalization в активной фазе

Подобранная модель классификации в своей структуре использует слои batch normalization. Суть подхода batch normalization в обучении параметров нормализации данных во время обучения и применении найденных параметров во время инференса, или предсказания. Идея, которую мы использовали, состоит в том, чтобы рассматривать активную фазу обучения как этап инференса, и отключать на ней обучение batch normalization. К тому же интуитивно кажется, что такой подход позволит избежать смещения модели. Насколько нам известно, данный вопрос ещё не исследовался в отношении методов активного обучения. Для экспериментов мы взяли за основу метод BALD. Рассмотрим результаты (рис. 11).

Рис. 11. Результаты отключения batch normalization для метода BALD в сравнении со стандартным методом и пассивным обучением

Как можно судить, такой подход позволил стратегии обойти пассивное обучение, а мы узнали ещё одну неизученную особенность активного обучения.

Чтобы успешно применять отключаемые модули batch normalization, важно располагать большим и разнообразным набором данных для обучения в пассивной фазе. Дело в том, что точность модели сильно зависит от найденных на изначальной выборке параметров нормализации.

Learning loss

Теперь взглянём на проблему активного обучения с другой стороны. Предположим, что неуверенность модели относительно классов тех или иных объектов пропорциональна значению функции потерь от предсказаний для этих объектов. Но пока мы не знаем реального класса объекта, не можем посчитать значение функции потерь.

Создадим вспомогательную модель, принимающую на вход выходы промежуточных и последних слоёв модели. Задача вспомогательной модели предсказывать значение функции потерь. Мы будем выбирать для разметки те объекты, для которых это значение максимально. Этот метод называется learning loss, подробнее про него можно почитать здесь. Рассмотрим результаты первичных экспериментов, где метод применялся для базовой модели (рис. 12).

Рис. 12. Результаты применения Learning loss для базовой модели в сравнении с ее пассивным обучением

Метод learning loss не дал прироста по сравнению с пассивным обучением на случайно выбранных объектах. Логично было бы использовать его для моделей других архитектур или отказаться от него как от неэффективного для нашей задачи.
Но мы вместо этого попробуем провести следующий эксперимент. В обычном сценарии активного обучения модель не знает настоящих меток классов, а в нашей задаче они известны. Это позволяет посчитать идеальный learning loss: зная настоящую метку класса объекта, будем считать на нём значение функции потерь и добавлять в размеченный набор данных те объекты, у которых оно больше. Назовём такой подход ideal learning loss (рис. 13).

Рис. 13. Результаты применения ideal learning loss для базовой модели в сравнении с её пассивным обучением

Несмотря на ожидания, этот подход показал себя хуже базового метода learning loss.
Мы предположили, что значение функции потерь слабо зависит от точности модели или даже обратно пропорционально ей. Чтобы это проверить, можно построить корреляцию точности модели, обученной на какой-то выборке, и среднего значения функции потерь для объектов этой выборки. Получился следующий экспериментальный пайплайн:

1. Обучаем модель на начальной выборке (2000 объектов), как для активного обучения;
2. Выбираем из всего набора неразмеченных данных 10000 объектов (чтобы ускорить подсчёт);
3. Для выбранных объектов неразмеченной выборки считаем значения функции потерь;
4. Сортируем объекты по полученным значениям;
5. Разбиваем на группы по 100 объектов;
6. Для каждой группы параллельно обучаем на ней модель, стартуя с весов, полученных на шаге 1;
7. Фиксируем получившиеся точности.

Далее считаем корреляцию Спирмена между точностью модели, обученной на определённой выборке, и средним значением функции потерь по каждому из объектов выборки. А также вычисляем, как средняя точность модели коррелирует со средним значением параметра отступа (из метода margin sampling).

Таблица 1. Корреляции точности и метрик активного обучения для набора данных публикаций ВКонтакте

Как видим, для метода margin sampling корреляция слабая и положительная то есть, зная отступ, можно быть уверенными, что объект полезен для обучения модели. А в случае c функцией потерь корреляция слабая отрицательная.

Возникает вопрос: а что если попробовать выбирать для разметки объекты с наименьшими значениями функции потерь?
Как ни странно, эксперименты показали, что и такой вариант тоже не работает ожидаемым образом (рис. 14).

Рис. 14. Результаты применения обратного ideal learning loss для базовой модели в сравнении с прямым ideal learning loss и пассивным обучением

Несмотря на плохие результаты для целевого набора данных, для набора данных MNIST были получены следующие значения корреляции:

Таблица 2. Корреляции точности и метрик активного обучения для набора данных MNIST

При этом сам метод ideal learning loss работает так, как ожидается (рис. 15).

Рис. 15. Активное обучение классификатора символов из набора данных MNIST стратегией ideal learning loss. Синий график ideal learning loss, оранжевый пассивное обучение

Получается, что метод, предполагающий, что модели выгоднее обучаться на данных с наибольшим значением функции потерь, работает хорошо. Но при этом он не подходит для нашего набора данных.

Сложность метода learning loss та же, что и для методов uncertainty sampling: , где размер неразмеченного набора данных, а число объектов в запросе к эксперту. Но важно учесть, что при его применении обучать нужно не только основную модель, но и вспомогательную. Этот метод сложнее предыдущих в практическом применении ещё и потому, что требует проводить обучение каскада моделей.

Заключение

Не будем бесконечно раздувать статью, рассказывая обо всех применённых методах и проведённых экспериментах. Здесь мы постарались осветить основные и наиболее интересные. Любопытно, что эффективнее всех оказался самый первый и простой метод margin sampling результаты его длинного запуска можно увидеть на рис. 16.

Рис. 16. Сравнение обучения на случайно выбираемых данных (пассивное обучение) и на данных, выбираемых стратегией margin sampling

График показывает: тренируя модель с помощью активного обучения (в нашем случае стратегией margin sampling), можно достичь предельной точности такой же, как у модели, обученной пассивным способом. Но при этом использовать на 25 тыс. объектов меньше. Экономия ресурсов разметки составит порядка 25% это довольно значимо.

Также отметим, что в этой задаче эффективность методов была ограничена размером набора данных. В других обстоятельствах выборка может быть значительно больше, а следовательно, у методов активного обучения будет больше вариантов выбора и выше потенциальная эффективность.

Все методы, о которых мы говорили, просты в реализации и обладают невысокой вычислительной сложностью. Но есть моменты, на которые стоит обращать внимание:

• выбор batch size;
• целесообразность использования для активного обучения подходов, зарекомендовавших себя в глубоких нейронных сетях, например, batch normalization.

Уточнение задачи

Добрый день.
Я правильно понимаю: чтобы расшарить календарь на определенного пользователя, нужно на ПК пользователя, который хочет поделиться календарем, открыть доступ к своему календарю и вписать почту пользователя, которому он хочет дать доступ?

Hi Team,

The sites were down again for few minutes from 2020-07-15 14:59:53 to 2020-07-15 15:12:50 (UTC time zone), now they are working fine. Could you please check and let us know why the sites are fluctuating many times.

Thanks

Изучение теории

Выбор реализации

1. Предварительно настраивается каркас нейросети: несколько слоев нейронов, соединенных связями-синапсами.
   
   
2. В память загружается набор данных для обучения с заранее известным результатом.
   
3. Данные для обучения прогоняются через каркас нейросети. В результате у каждого синапса в зависимости от данных выстраиваются веса.По этим весам нейросеть принимает то или иное решение.
   
4. После прогоняем нейросеть через тестовую выборку и анализируем ошибку сети: насколько результат, выдаваемый нейросетью, соответствует известному результату из набора данных.
   
5. Пункты 3 и 4 повторяются до получения минимально допустимой ошибки. При этом важно, чтобы на каждой следующей итерации ошибка уменьшалась. Если этого не происходит, значит какие-то из параметров были выбраны некорректно.
   

Первый вариант векторизации: по буквам

Второй вариант векторизации: по словарю

1. Униграмма текст разбивается на слова: добро, пожаловать, в, ДатаЛайн.
   
2. Биграмма разбиваем на пары слов: добро пожаловать, пожаловать в, в ДатаЛайн.
   
3. Триграмма аналогично по 3 слова: добро пожаловать в, пожаловать в ДатаЛайн.
   
4. N-грамма ну вы поняли. Сколько N, столько и слов подряд.
   
5. Также иногда используют символьные N-граммы. Текст делится не на слова, а на последовательность букв. Например 4-символьная N-грамма выглядела бы так: добр,о по, жало, вать и т. д. Но тут получится очень большой словарь.
   

Обучение нейросети

1. Словарь из 3k слов.
   
2. Векторизованное представление словаря.
   
3. Размеры входного и выходного слоев нейросети.
   По теории на первом слое (входном) предоставляется словарь, а финальный слой (выходной) количество классов-решений. У меня их 44 по количеству подразделений компании.
   
   

1. Метод обучения.
   
2. Функцию активации.
   
3. Количество скрытых слоев.
   

1. На 10k я обучал нейронную сеть.
   
2. На 1k проверял уже обученную сеть.
   

В продакшен!

1. Прикрутил Spark, чтобы можно было общаться с нейронкой по REST.
   
2. Научил сохранять результаты расчета в файл. Не каждый же раз пересчитывать при перезапуске сервиса.
   
3. Добавил возможность вычитывать актуальные данные для обучения напрямую из Service Desk. Ранее тренировался на csv-файлах.
   
4. Добавил возможность пересчета нейросети, чтобы прикрутить пересчет к планировщику.
   
5. Собрал все в толстый jar.
   
6. Попросил у коллег сервер помощнее разрабской машины.
   
7. Задеплоил и зашедулил пересчет раз в неделю.
   
8. Прикрутил кнопку в нужное место Service Desk и написал коллегам, как этим чудом пользоваться.
   
9. Сделал сбор статистики по тому, что выбирает нейронка и что выбрал человек (статистика ниже).
   

Содержание

• В следующем разделе я бегло опишу математическую постановку задачи обучения машины опорных векторов, к какой задаче оптимизации она сводится, а также некоторые гиперпараметры, позволяющие регулировать работу алгоритма. Этот материал лишь подводящий к нашей конечной цели и нужен чтобы вспомнить ключевые факты, если такое напоминание не требуется можете его пропустить без ущерба для понимания дальнейших частей. Если же вы ранее не сталкивались с машинами опорных векторов, то понадобиться куда более полное изложение обратите внимание на соответствующую лекцию уже ставшего классикой курса Воронцова [2] или на десятую лекцию курса [3], в которую, кстати, входит представленный ниже метод.
• В разделе Алгоритм SMO я подробно расскажу как решить поставленную задачу минимизации упрощенным методом SMO и в чём, собственно, состоит упрощение. Будут выкладки, но их объём гораздо меньше, чем в тех подходах к SMO, что доводилось видеть мне.
• Наконец, в разделе Реализация будет представлен код классификатора на Python и схема обучения в псевдокоде.
• Узнать насколько алгоритм удался можно в разделе Сравнение с sklearn.svc.svm там приведено визуальное сравнение для небольших датасетов в 2D и confusion matrix для двух классов из MNIST.
• А в Заключении что-нибудь да заключим.

Машина опорных векторов

Алгоритм SMO

• Откажусь от сложной эвристики выбора индексов (так сделано в курсе Стэнфордского университета [11]) и буду итерировать по одному индексу, а второй выбирать случайным образом.
• Откажусь от проверки ККТ и буду выполнять наперёд заданное число итераций.
• В самой процедуре оптимизации, в отличии от классической работы [9] или стэнфордского подхода [11], воспользуюсь векторным уравнением прямой. Это существенно упростит выкладки (сравните объём [12] и [13]).

$$display$$ \begin{aligned} \mathscr{L} &= \lambda_\M + \lambda_\L - \sum_{j} \lambda_\M \lambda_j K_{\M,j} - \sum_{i} \lambda_\L \lambda_i K_{\L,i} + \text{const} + \\ {\text{компенсация}\atop\text{двойного подсчета}} \rightarrow\qquad &+ \frac{1}{2}\lambda_\M^2 K_{\M,\M} + \lambda_\M \lambda_\L K_{\M,\L} + \frac{1}{2}\lambda_\L^2 K_{\L,\L} = \\ &= \lambda_\M \left(1-\sum_{j} \lambda_j K_{\M,j}\right) + \lambda_\L \left(1-\sum_{i} \lambda_i K_{\L,i}\right)+\\ &+\frac{1}{2}\left(\lambda_\M^2 K_{\M,\M} + 2 \lambda_\M \lambda_\L K_{\M,\L}+\lambda_\L^2 K_{\L,\L} \right) + \text{const} = \\ &=\boldsymbol{k}^T_0 \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}, \end{aligned} $$display$$

$$display$$ \begin{align} \boldsymbol{v}_0 &= (\lambda_\M, \lambda_\L)^T, \tag{4a}\\ \boldsymbol{k}_0 &= \left(1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\M}, 1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\L}\right)^T, \tag{4b}\\ \boldsymbol{Q} &= \begin{pmatrix} K_{\M,\M} & K_{\M,\L} \\ K_{\L,\M} & K_{\L,\L} \\ \end{pmatrix},\tag{4c}\\ \boldsymbol{u} &= (-y_\L, y_\M)^T. \tag{4d} \end{align} $$display$$

$$display$$ \boldsymbol{k}_0 = \begin{pmatrix} 1 - \lambda_\M K_{\M,\M} - \lambda_\L K_{\M,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \lambda_\M K_{\L,\M} - \lambda_\L K_{\L,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} = \begin{pmatrix} 1 - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} - \boldsymbol{Q} \boldsymbol{v}_0. $$display$$

$$display$$ (\lambda_\M^\text{new}, \lambda_\L^\text{new})^T = \boldsymbol{v}(t) = \boldsymbol{v}_0 + t \boldsymbol{u}. $$display$$

$$display$$ y_\M\lambda_\M^\text{new} + y_\L\lambda_\L^\text{new} = y_\M \lambda_\M + y_\L \lambda_\L + t (-y_\M y_\L + y_\L y_\M) = y_\M\lambda_\M + y_\L\lambda_\L. $$display$$

$$display$$ (\lambda_\M^\text{new}, \lambda_\L^\text{new}) = \boldsymbol{v}_0 + t_*^{\text{restr}} \boldsymbol{u}. $$display$$

Реализация

import numpy as npclass SVM:  def __init__(self, kernel='linear', C=10000.0, max_iter=100000, degree=3, gamma=1):    self.kernel = {'poly'  : lambda x,y: np.dot(x, y.T)**degree,         'rbf': lambda x,y: np.exp(-gamma*np.sum((y-x[:,np.newaxis])**2,axis=-1)),         'linear': lambda x,y: np.dot(x, y.T)}[kernel]    self.C = C    self.max_iter = max_iter  # ограничение параметра t, чтобы новые лямбды не покидали границ квадрата  def restrict_to_square(self, t, v0, u):     t = (np.clip(v0 + t*u, 0, self.C) - v0)[1]/u[1]    return (np.clip(v0 + t*u, 0, self.C) - v0)[0]/u[0]  def fit(self, X, y):    self.X = X.copy()    # преобразование классов 0,1 в -1,+1; для лучшей совместимости с sklearn    self.y = y * 2 - 1     self.lambdas = np.zeros_like(self.y, dtype=float)    # формула (3)    self.K = self.kernel(self.X, self.X) * self.y[:,np.newaxis] * self.y        # выполняем self.max_iter итераций    for _ in range(self.max_iter):      # проходим по всем лямбда       for idxM in range(len(self.lambdas)):                                            # idxL выбираем случайно        idxL = np.random.randint(0, len(self.lambdas))                                 # формула (4с)        Q = self.K[[[idxM, idxM], [idxL, idxL]], [[idxM, idxL], [idxM, idxL]]]         # формула (4a)        v0 = self.lambdas[[idxM, idxL]]                                                # формула (4b)        k0 = 1 - np.sum(self.lambdas * self.K[[idxM, idxL]], axis=1)                   # формула (4d)        u = np.array([-self.y[idxL], self.y[idxM]])                                    # регуляризированная формула (5), регуляризация только для idxM = idxL        t_max = np.dot(k0, u) / (np.dot(np.dot(Q, u), u) + 1E-15)         self.lambdas[[idxM, idxL]] = v0 + u * self.restrict_to_square(t_max, v0, u)        # найти индексы опорных векторов    idx, = np.nonzero(self.lambdas > 1E-15)     # формула (1)    self.b = np.mean((1.0-np.sum(self.K[idx]*self.lambdas, axis=1))*self.y[idx])     def decision_function(self, X):    return np.sum(self.kernel(X, self.X) * self.y * self.lambdas, axis=1) + self.b  def predict(self, X):     # преобразование классов -1,+1 в 0,1; для лучшей совместимости с sklearn    return (np.sign(self.decision_function(X)) + 1) // 2

Сравнение с sklearn.svm.SVC

from sklearn.svm import SVCimport matplotlib.pyplot as pltimport seaborn as sns; sns.set()from sklearn.datasets import make_blobs, make_circlesfrom matplotlib.colors import ListedColormapdef test_plot(X, y, svm_model, axes, title):  plt.axes(axes)  xlim = [np.min(X[:, 0]), np.max(X[:, 0])]  ylim = [np.min(X[:, 1]), np.max(X[:, 1])]  xx, yy = np.meshgrid(np.linspace(*xlim, num=700), np.linspace(*ylim, num=700))  rgb=np.array([[210, 0, 0], [0, 0, 150]])/255.0    svm_model.fit(X, y)  z_model = svm_model.decision_function(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)    plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')  plt.contour(xx, yy, z_model, colors='k', levels=[-1, 0, 1], alpha=0.5, linestyles=['--', '-', '--'])  plt.contourf(xx, yy, np.sign(z_model.reshape(xx.shape)), alpha=0.3, levels=2, cmap=ListedColormap(rgb), zorder=1)  plt.title(title)X, y = make_circles(100, factor=.1, noise=.1)fig, axs = plt.subplots(nrows=1,ncols=2,figsize=(12,4))test_plot(X, y, SVM(kernel='rbf', C=10, max_iter=60, gamma=1), axs[0], 'OUR ALGORITHM')test_plot(X, y, SVC(kernel='rbf', C=10, gamma=1), axs[1], 'sklearn.svm.SVC')X, y = make_blobs(n_samples=50, centers=2, random_state=0, cluster_std=1.4)fig, axs = plt.subplots(nrows=1,ncols=2,figsize=(12,4))test_plot(X, y, SVM(kernel='linear', C=10, max_iter=60), axs[0], 'OUR ALGORITHM')test_plot(X, y, SVC(kernel='linear', C=10), axs[1], 'sklearn.svm.SVC')fig, axs = plt.subplots(nrows=1,ncols=2,figsize=(12,4))test_plot(X, y, SVM(kernel='poly', C=5, max_iter=60, degree=3), axs[0], 'OUR ALGORITHM')test_plot(X, y, SVC(kernel='poly', C=5, degree=3), axs[1], 'sklearn.svm.SVC')

from sklearn import datasets, svmfrom sklearn.model_selection import train_test_splitfrom sklearn.metrics import confusion_matriximport matplotlib.pyplot as pltimport seaborn as snsclass_A = 3class_B = 8digits = datasets.load_digits()mask = (digits.target == class_A) | (digits.target == class_B)data = digits.images.reshape((len(digits.images), -1))[mask]target = digits.target[mask] // max([class_A, class_B]) # rescale to 0,1X_train, X_test, y_train, y_test = train_test_split(data, target, test_size=0.5, shuffle=True)def plot_confusion(clf):  clf.fit(X_train, y_train)  y_fit = clf.predict(X_test)  mat = confusion_matrix(y_test, y_fit)  sns.heatmap(mat.T, square=True, annot=True, fmt='d', cbar=False, xticklabels=[class_A,class_B], yticklabels=[class_A,class_B])  plt.xlabel('true label')  plt.ylabel('predicted label');  plt.show()print('sklearn:')plot_confusion(svm.SVC(C=1.0, kernel='rbf', gamma=0.001))print('custom svm:')plot_confusion(SVM(kernel='rbf', C=1.0, max_iter=60, gamma=0.001))

Заключение

Список литературы

1. https://fbeilstein.github.io/simplest_smo_ever/
2. страница на http://www.machinelearning.ru
3. Начала Машинного Обучения, КАУ
4. https://en.wikipedia.org/wiki/Kernel_method
5. https://en.wikipedia.org/wiki/Duality_(optimization)
6. Статья на http://www.machinelearning.ru
7. https://www.youtube.com/watch?v=MTY1Kje0yLg
8. https://en.wikipedia.org/wiki/Sequential_minimal_optimization
9. Platt, John. Fast Training of Support Vector Machines using Sequential Minimal Optimization, in Advances in Kernel Methods Support Vector Learning, B. Scholkopf, C. Burges, A. Smola, eds., MIT Press (1998).
10. https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
11. http://cs229.stanford.edu/materials/smo.pdf
12. https://www.researchgate.net/publication/344460740_Yet_more_simple_SMO_algorithm
13. http://fourier.eng.hmc.edu/e176/lectures/ch9/node9.html
14. https://github.com/fbeilstein/simplest_smo_ever