notes/machine_learning/miscellaneous.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"tags": [
"подготовка_данных"
]
},
"source": [
"## Автоматическое обнаружение выбросов\n",
"\n",
"#### Введение\n",
"\n",
"Выброс (outlier) — объект, считающийся нетипичным для генеральной совокупности, фигурирующей в задаче. Выбросы могут искажать процесс обучения модели, а также результаты оценки качества модели (что создаёт риск неправильного подбора гиперпараметров). Строго говоря, является ли какой-то объект выбросом или нет, должен определять человек, отталкиваясь от своего понимания предметной области и от знаний о том, как именно собирались данные. Тем не менее на практике автоматическое удаление выбросов тоже может существенно улучшить конечный результат.\n",
"\n",
"Способы автоматического обнаружения выбросов делятся на две группы в зависимости от того, на какие выбросы они реагируют:\n",
"\n",
"1. Способы, позволяющие выявить одномерные выбросы, то есть выбросы, являющиеся аномальными значениями какого-либо одного признака. Пример одномерного выброса: среди точек на плоскости с координатами (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (100, 6) у последней точки подозрительно большая абсцисса.\n",
"\n",
"2. Способы, позволяющие выявить многомерные выбросы, то есть выбросы, являющиеся аномальными объектами с точки зрения распределения данных. Пример многомерного выброса: среди точек на плоскости с координатами (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 5) последняя точка лежит в стороне от прямой, на которой лежат все остальные точки, но при этом и её абсцисса, и её ордината не выбиваются из диапазона значений остальных точек.\n",
"\n",
"В зависимости от задачи возможны следующие ситуации:\n",
"* обнаружение выбросов с учителем — есть выборка, в которой все объекты полагаются пришедшими из генеральной совокупности, а в другой выборке нужно найти выбросы;\n",
"* обнаружение выбросов без учителя — единственная выборка, которая дана, сама может содержать выбросы.\n",
"\n",
"Для обнаружения выбросов без учителя существует правило, что если данных мало, то при подсчёте оценки аномальности для какого-либо одного объекта всё, что вычисляется по данным (статистики, оценки плотности генеральной совокупности и т.д.), должно вычисляться на выборке без этого объекта. Если же данных много, то вычисления, зависящие от них, можно сделать один раз на всей выборке, а потом использовать для всех объектов.\n",
"\n",
"#### Одномерные способы\n",
"\n",
"К одномерным способам относятся:\n",
"* Стандартизированная оценка (Z-score) — из всех значений признака вычитается эмпирическое среднее этого признака, а полученные разности делятся на оценку стандартного отклонения признака; если получившееся отношение по модулю превышает 3, то объект считается выбросом. Порог 3 выбран, потому что в случае нормального распределения вероятность отклониться от среднего больше, чем на 3 стандартных отклонения, составляет 0,03% ([правило трёх сигм](https://ru.wikipedia.org/wiki/%D0%A1%D1%80%D0%B5%D0%B4%D0%BD%D0%B5%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BE%D1%82%D0%BA%D0%BB%D0%BE%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5#%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE_%D1%82%D1%80%D1%91%D1%85_%D1%81%D0%B8%D0%B3%D0%BC)). Данный способ хорошо подходит для детекции выбросов с учителем.\n",
"* Устойчивая стандартизированная оценка (robust Z-score) — то же самое, что и стандартизированная оценка, но теперь вычитается медиана, а не среднее, и разности делятся на средний модуль отклонения от медианы, а не на стандартное отклонение. Предпочтительнее в тех задачах детекции без учителя, где выбросов достаточно много для того, чтобы они могли исказить среднее и стандартное отклонение.\n",
"* Метод межквартильного размаха (interquartile range method) — берётся расстояние между 0,75-й и 0,25-й квантилями (так называемый межквартильный размах), а затем выбросами объявляются все наблюдения, отстоящие от медианы более чем на 1,5 межквартильных размаха. Численные параметры приведены в соответствии с классическим вариантом, но, разумеется, их можно поменять (например, вместо двух квартилей взять две другие квантили).\n",
"\n",
"#### Многомерные способы\n",
"\n",
"В многомерном случае для каждого объекта считается оценка его типичности (например, оценка плотности генеральной совокупности в нём), а затем выбросами объявляются те объекты, у которых оценка типичности ниже некоторого порога.\n",
"\n",
"Способы оценить типичность таковы:\n",
"* Метод ядерного сглаживания (kernel density estimate) для оценки плотности генеральной совокупности. Правда, он подвержен «проклятью размерности» и работает только в случае, когда размерность данных низкая. Если же размерность высокая, то для применения ядерного сглаживания можно предварительно снизить её, использовав PCA, t-SNE или MDS на отмасштабированных данных, однако как проводить масштабирование — нетривиальный вопрос, вносящий долю субъективности.\n",
"* Расстояние Махаланобиса от объекта до некоторого оценённого по данным распределения, принимаемого за генеральную совокупность. Для вектора $x$ и многомерного вероятностного распределения $\\tau(\\mu, S)$ с вектором средних $\\mu$ и ковариационной матрицей $S$ «расстоянием» от $x$ до $\\tau(\\mu, S)$ можно положить величину:\n",
"$$D_M(x, \\tau(\\mu, S)) = \\sqrt{(x - \\mu)^T S^{-1} (x - \\mu)},$$\n",
"которая и называется расстоянием Махаланобиса. Интуитивно говоря, расстояние Махаланобиса отличается от евклидова расстояния между $x$ и $\\mu$ тем, что каждое направление учитывается с весом, обратно пропорциональным разбросу распределения по этому направлению. Само по себе расстояние Махаланобиса не является плотностью, но если $\\tau$ является гауссовским распределением, то плотность выражается через него и $S$. В литературе этот способ также известен как эллиптическая огибающая (elliptic envelope).\n",
"* [Приближение распределения данных смесью многомерных нормальных распределений](__home_url__/notes/Восстановление плотности при помощи EM-алгоритма). Этот подход можно считать обобщением подхода с расстоянием Махалонобиса от $x$ до $\\tau$, являющегося многомерным нормальным распределением, на случай смеси подобных распределений.\n",
"* Изолирующий лес. Строятся деревья глубины $\\log_2 l$, где $l$ — количество объектов в выборке, по следующей процедуре: в каждом узле равновероятно выбирается признак, по которому проводить деление, и равновероятно на отрезке от минимума этого признака по объектам, дошедшим до текущего узла, до аналогичного максимума выбирается порог для деления. Оценка типичности объекта определяется как среднее по всем деревьям леса количество узлов, через которые этот объект проходит до того, как оказывается отдельно от всех остальных объектов выборки. Понятно, что сильно выбивающиеся объекты будут изолированы недалеко от корней деревьев, а объекты из регионов с высокой плотностью могут и доходить до конца вместе с соседями."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"подготовка_данных"
]
},
"source": [
"## Обработка пропущенных значений\n",
"\n",
"#### Введение\n",
"\n",
"Пусть рассматривается задача машинного обучения (с учителем или без) на табличных данных. Для некоторых объектов некоторые их признаки могут быть пропущены.\n",
"\n",
"Определим различные виды пропусков в значениях какого-либо одного признака:\n",
"* полностью случайные пропуски — для каждого объекта вероятность того, что этот признак пропущен, одинакова;\n",
"* случайные пропуски — по другим признакам объекты можно разбить на группы, а в каждой группе вероятность, что признак пропущен, одинакова для всех объектов;\n",
"* неслучайные пропуски — все остальные случаи (например, вероятность пропуска может зависеть от значения признака).\n",
"\n",
"Также отметим, что если процедура заполнения пропусков недетерминирована, её можно применить несколько раз к одному и том же набору данных. В контексте машинного обучения польза от этого под вопросом, ведь качество модели, обученной на конкатенации получившихся нескольких заполненных наборов данных, необязательно будет выше, чем качество модели, обученной только на одном из них. Однако в контексте [математической статистики](__home_url__/tags/математическая_статистика) кратные заполнения важны, ведь в них найдёт своё отражение неопределённость, вносимая недетерминированной процедурой заполнения пропусков.\n",
"\n",
"Ниже разбирается, какие есть варианты решения проблемы пропущенных значений.\n",
"\n",
"#### Использование алгоритмов обучения, умеющих работать с пропусками\n",
"\n",
"С пропусками умеют работать [решающие деревья](__home_url__/tags/решающие_деревья) и ансамбли над ними. В некоторых программных реализациях на этапе обучения пропуск считается отдельным значением, для которого на основании оптимизации критерия, используемого в этом узле, решается, по какой из веток его отправить. Если же на этапе применения появляется объект с пропуском признака, используемого в узле, где при обучении пропусков не было, он отправляется в ту ветку, куда ушло больше объектов обучающей выборки. В других реализациях вместо отправки пропуска строго в одну ветку используется отправка сразу в обе ветки с весами, пропорциональными тому, как этот узел делит объекты обучающей выборки с заполненным признаком, и в сумме дающими 1. Таким образом, на этапе обучения один объект влияет на предсказания в каждом из листьев, куда он пришёл, но с соответствующим уменьшенным весом, а на этапе предсказания итоговым значением для некого объекта является взвешенная сумма предсказаний, возвращаемых листьями, до которых он дошёл.\n",
"\n",
"Также с пропусками может работать метод ближайших соседей, если понятие евклидова расстояния доработать под пропуски. Если есть векторы $u, v \\in (\\mathbb{R} \\cup \\{\\mathrm{None}\\})^n$, то модифицированное расстояние между ними можно определить как:\n",
"$$d(u, v) = \\sqrt{\\frac{n}{\\# I} \\sum_{i \\in I} (u_i - v_i)^2},$$\n",
"где символ $\\#$ обозначает количество элементов в множестве, а\n",
"$$I = \\{i: i \\in \\{1, \\dots, n\\}, u_i \\ne \\mathrm{None}, v_i \\ne \\mathrm{None}\\},$$\n",
"то есть $I$ — множество индексов, для которых оба вектора не содержат пропусков.\n",
"\n",
"#### Одномерные методы\n",
"\n",
"Одномерные методы работают с каждым из признаков, содержащих пропуски, по отдельности. В результате для некого объекта может получиться заполненный вектор признаков, лежащий в области признакового пространства, где плотность генеральной совокупности нулевая. Только многомерные методы избавлены от этого недостатка. Зато одномерные методы просты и работают быстро.\n",
"\n",
"Пожалуй, базовый вариант — заполнять пропуски признака его статистикой, которой может быть:\n",
"* среднее,\n",
"* медиана,\n",
"* мода (подходит для категориальных признаков),\n",
"* минимум, уменьшенный на 1, или максимум, увеличенный на 1 (подходит, например, для тех программных реализаций решающих деревьев, которые не поддерживают пропуски).\n",
"\n",
"Кроме предельной простоты никаких достоинств у этого метода нет. Зато есть пара важных недостатков (помимо общего недостатка одномерных методов):\n",
"* искажается распределение признака (а именно, создаётся вероятностный атом в том значении, которым заполняются пропуски),\n",
"* если пропуски неслучайны, вменённые значения могут сильно отличаться от фактических.\n",
"\n",
"Чтобы избежать первого из этих двух недостатков, можно использовать случайное сэмплирование. Для каждого пропуска значение, на которое он будет заменён, сэмплируется (с возвращением) из списка заполненных значений этого признака. Поскольку этот способ недетерминированный, можно проверить, не улучшатся ли результаты, если модель будет обучаться на конкатенации данных, заполненных с разными зёрнами случайности.\n",
"\n",
"#### Многомерные методы\n",
"\n",
"Популярный подход — предсказывать пропущенные значения методом ближайших соседей, где в качестве расстояния используется описывавшаяся выше модификация евклидова расстояния. Если вычислительные ресурсы ограничены, можно для каждого объекта, содержащего хотя бы один пропуск, найти ближайших соседей ровно один раз, используя все признаки. Если же ресурсы позволяют, можно для каждого пропущенного значения искать ближайших соседей объекта, к которому оно относится, по всем признакам кроме того, к которому оно относится.\n",
"\n",
"Достоинства этого подхода:\n",
"* не искажает распределения признаков (изменяет их, скорее, в сторону уточнения),\n",
"* если для каждого пропуска найдутся похожие объекты без пропуска, может корректно работать даже с неслучайными пропусками.\n",
"\n",
"Недостатки связаны с недостатками метода ближайших соседей:\n",
"* подверженность проклятью размерности,\n",
"* чувствительность к масштабу признаков (в частности, результаты сильно зависят от единиц измерения).\n",
"\n",
"Чтобы вместо метода ближайших соседей можно было использовать любой другой алгоритм машинного обучения, был предложен метод [MICE](https://www.researchgate.net/publication/44203418_MICE_Multivariate_Imputation_by_Chained_Equations_in_R) (Multiple Imputation by Chained Equations). В виде псевдокода он устроен так:\n",
"* Все пропуски заполняются как-то.\n",
"* Пока не пройдёт заданное число итераций (обычно берут 10):\n",
" - Для каждого признака, исходно содержавшего пропуски:\n",
" - На объектах, где этот признак исходно не был пропущен, обучается модель, предсказывающая значение этого признака по всем остальным признакам.\n",
" - Для объектов, где этот признак исходно был пропущен, его значения заменяются на предсказания модели."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"временные_ряды",
"практические_приёмы"
]
},
"source": [
"## Прогнозирование на несколько шагов вперёд\n",
"\n",
"Допустим, в момент времени $t$ требуется предсказать значения временного ряда в периоды $\\{t + i: i \\in \\{1, \\dots, h\\}\\}$, где $h$ — желаемый горизонт прогнозирования. В общем случае, временной ряд может предсказываться не только по своим прошлым значениям, но и по каким-то иным факторам, которые уже известны в момент времени $t$.\n",
"\n",
"Говоря верхнеуровнево, можно выделить следующие подходы:\n",
"* для каждого $i$ обучить свою собственную модель независимо от остальных,\n",
"* для всех $i$ последовательно обучать свои собственные модели, использующие в качестве признаков в том числе предсказания всех предыдущих моделей,\n",
"* обучить одну модель, предсказывающую сразу $h$ значений (multi-output learning),\n",
"* если никакие внешние факторы не используются, обучить модель прогнозирования на один шаг вперёд, а потом добавлять её предсказания ко временному ряду, предсказывать на следующий шаг и т.д.\n",
"\n",
"Первые два варианта хороши тем, что работают с любыми алгоритмами машинного обучения. Какой из них выбрать, зависит от того, насколько сильно предыдущие значения влияют в сравнении с внешними факторами. Если не очень сильно и в их предсказаниях больше шума, чем полезного сигнала, то лучше первый вариант, а иначе — второй. Четвёртый вариант, по сути, является крайней формой второго варианта, когда отказ от внешних факторов позволяет вместо $h$ моделей ограничиться одной.\n",
"\n",
"Третий вариант может выиграть, если данных мало, ведь многозадачность является одним из видов регуляризации. Также третий вариант может выиграть, если отрезок временного ряда длины $h$ не может быть каким угодно, но $h$ отдельных моделей, неидеально скоординированных между собой, порождают неправдоподобные конфигурации из $h$ предсказанных значений. С другой стороны, к недостаткам третьего варианта можно отнести то, что не любой метод машинного обучения с ним совместим. Без доработок способны предсказывать сразу несколько целевых переменных нейронные сети, метод ближайших соседей и случайный лес.\n",
"\n",
"Популярные реализации градиентного бустинга неспособны предсказывать сразу несколько целевых переменных. Однако, поскольку градиентный бустинг поддерживает произвольные признаки, есть обходной способ. Возьмём обучающую выборку для задачи прогнозирования на один шаг вперёд. При группировке по идентификатору объекта применим операцию сдвига целевой переменной на $j$ шагов вперёд, где $j$ принимает значения от 0 до $(h-1)$. Получим выборку, которая в $h$ раз больше по размеру, чем исходная. Добавим в эту выборку признак, принимающий значения от 1 до $h$ и равный $(j+1)$. Этот признак можно интерпретировать как то, на сколько шагов вперёд строится прогноз. Если теперь обучить модель на таких данных, то в зависимости от поданного на стадии предсказания значения нового признака модель сможет предсказывать на любое количество шагов вперёд от 1 до $h$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рабочий_процесс"
]
},
"source": [
"## Откуда может взяться недовольство заказчика машинно-обученной моделью?\n",
"\n",
"Любая прикладная задача моделирования имеет заказчика, неважно, внутреннего или внешнего. Когда заказчик принимает модель, он решает, устраивает ли она его. Причины недовольства заказчика бывают такие:\n",
"\n",
"1. Модель, и в самом деле, плохая;\n",
"\n",
"2. Заказчик не умеет пользоваться моделью;\n",
"\n",
"3. Ожидания заказчика неоправданно завышены.\n",
"\n",
"Какой бы ни была истинная причина, заказчик, скорее всего, решит, что реализовался первый сценарий: модель плохая. Поэтому в интересах специалиста по моделированию избежать ситуаций, когда хорошая модель попадает во второй или третий сценарий.\n",
"\n",
"Разберём эти два сценария подробнее.\n",
"\n",
"Пример сценария, когда моделью не умеют пользоваться, таков: сервис на базе модели рассылает своевременные уведомления о появлении объектов положительного класса, но люди, которым они приходят, игнорируют их. Говоря более общо, можно сказать, что возможны осложнения с интеграцией в бизнес-процессы заказчика. Чтобы упредить их возникновение, полезно задать следующие вопросы:\n",
"* Что должно происходить с результатами работы сервиса?\n",
"* Как именно сервис приносит конечную ценность?\n",
"* Все ли исполнители знают и понимают ответы на два предыдущих вопроса?\n",
"* Можно ли оперативно отслеживать сбои в исполнении действий на базе сервиса и можно ли предложить количественные метрики оценки качества исполнения таких действий?\n",
"* Все ли признаки, использованные при обучении модели, будут доступны на стадии применения модели вовремя и в сопоставимом качестве?\n",
"\n",
"Что касается второго сценария, проблему завышенных ожиданий проще всего решить, ещё до старта работ по проекту согласовав метрику успеха и её целевой уровень. Сделать это можно, проведя оценку конечного эффекта от внедрения сервиса. Этот конечный эффект может быть как финансовым, то есть выражающимся в деньгах, так и каким-либо более широким (скажем, социальным), но, так или иначе, измеримым.\n",
"\n",
"Впрочем, бывают ситуации, когда заказчик рассуждает не в терминах конечного эффекта, а в терминах всестороннего описания зависимостей — в этом случае заказчик может потребовать, скажем, почти стопроцентную точность по положительному классу. Разумеется, модель, не способная точно описать все зависимости, тоже может быть полезна. Проиллюстрировать это заказчику можно при помощи такого сравнения: если есть лотерея, где вероятность выиграть равна $p$, стоимость участия составляет $c$, а выигрыш приносит $g$, то ответ на вопрос, рационально ли участвовать в такой лотерее, зависит не от того, насколько вероятность $p$ близка к 100%, а от того, как друг с другом соотносятся все три указанных параметра, ведь ожидаемый чистый выигрыш равен $pg - c$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"постановка_задачи",
"функции_потерь"
]
},
"source": [
"## Обучение метрик (metric learning)\n",
"\n",
"В машинном обучении есть задача, похожая на задачу классификации, но тем не менее отличная от неё. Пусть множество рассматриваемых объектов — множество пар, элементами которого являются пары $(x_i, x_i^\\prime)$, где $x_i$ и $x_i^\\prime$ принадлежат одному и тому же пространству, а целевая переменная $y_i$ равна 1, если $x_i$ и $x_i^\\prime$ похожи друг на друга, и равна 0, если $x_i$ и $x_i^\\prime$ не похожи друг на друга. Требуется выучить отображение $f$, такое что евклидово расстояние между $f(x_i)$ и $f(x_i^\\prime)$ мало для похожих объектов и велико для непохожих объектов. Поскольку после решения задачи появляется возможность находить расстояние между объектами, а не только предсказывать, похожи ли они, данная задача отличается от задачи бинарной классификации с признаковым описанием удвоенной длины.\n",
"\n",
"Обучение метрик может быть полезно для решения задачи многоклассовой классификации с высоким числом классов, таких что каждый класс представлен малым числом объектов обучающей выборки. Положим все объекты одного и того же класса похожими друг на друга, а объекты разных классов отличающимися. Предсказывать классы новых объектов можно, применяя метод ближайшего соседа в пространстве, получающемся после применения отображения $f$.\n",
"\n",
"Для обучения метрик иногда используют функцию потерь, называемую contrastive loss:\n",
"$$l(x_i, x_i^\\prime, f, y_i) = y_i\\Vert f(x_i) - f(x_i^\\prime)\\Vert_2 + (1 - y_i)\\max(1 - \\Vert f(x_i) - f(x_i^\\prime)\\Vert_2, 0).$$\n",
"Эта функция потерь состоит из двух слагаемых. Первое может быть отлично от нуля, только когда взята пара похожих объектов, и это слагаемое побуждает минимизировать евклидово расстояние между тем, во что переходят похожие объекты. Второе слагаемое может быть отлично от нуля, только когда взята пара непохожих объектов, и это слагаемое побуждает отображать непохожие объекты так, чтобы расстояние между их образами под действием $f$ было больше некоторого фиксированного порога.\n",
"\n",
"Эмпирический риск для задачи обучения с contrastive loss, как и следовало ожидать, имеет вид:\n",
"$$E(f) = \\frac{1}{n}\\sum_{i = 1}^n l(x_i, x_i^\\prime, f, y_i) + \\alpha R(f),$$\n",
"где через регуляризатор $R$ и силу регуляризации $\\alpha$ можно наложить дополнительные ограничения.\n",
"\n",
"Если считать, что отображение $f$ задаётся умножением слева на матрицу $M$ размера $k \\times n$, то вышеуказанная функция потерь будет плоха тем, что задача её оптимизации по $M$ не является выпуклой из-за отрицательного знака перед вторым слагаемым. В таком случае берут немного другую функцию потерь, отталкивающуюся от того, что если обозначить матрицу $M^TM$ размера $n \\times n$ за $S$, то $\\Vert Mx_i - Mx_i^\\prime\\Vert_2 = (x_i - x_i^\\prime)^T S (x_i - x_i^\\prime)$:\n",
"$$l(x_i, x_i^\\prime, S, y_i) = y_i(x_i - x_i^\\prime)^T S (x_i - x_i^\\prime) + (1 - y_i)\\max(1 - (x_i - x_i^\\prime)^T S (x_i - x_i^\\prime), 0).$$\n",
"При минимизации эмпирического риска по матрице $S$ размера $n \\times n$ стоит учитывать ограничение, что $S$ должна быть неотрицательно определённой, иначе её нельзя было бы представить в виде $S = M^TM$. Данное ограничение является выпуклым. Однако платой за превращение задачи оптимизации в выпуклую является то, что нельзя заранее задать размерность выходного пространства, ведь ограничения на ранг матрицы $S$ не являются выпуклыми."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"постановка_задачи"
]
},
"source": [
"## Искусственная целевая переменная\n",
"\n",
"Бывают ситуации, когда достоверно целевая переменная неизвестна, но её можно восстановить оценочно. Например, в задаче обнаружения подозрительного трафика, приходящего на сайт, каких-то пользоваталей можно отнести к ботам или к живым людям на основании экспертного мнения.\n",
"\n",
"Рассмотрим две ситуации:\n",
"* Специалисты по предметной области написали детерминированную программу, на базе свода правил и формул вычисляющую целевую переменную по входным признакам;\n",
"* Специалисты по предметной области не смогли составить список правил и формул, по которым можно вычислять целевую переменную, но внимательно изучили данные и разметили каждый пример вручную.\n",
"\n",
"Вопрос: в каких из этих двух ситуаций стоит применять машинное обучение?\n",
"\n",
"Ответ: только во второй. В первой ситуации построенная модель будет вести себя точно так же, как уже написанная программа, с точностью до ошибок, вызываемых нерепрезентативностью обучающей выборки, малым количеством данных и/или артефактами обучения. Иными словами, нет ничего, что позволило бы модели стать лучше, чем программа. А вот во второй ситуации модель, если хорошо обучится, станет автоматизированным воплощением интуиции и знаний экспертов.\n",
"\n",
"Однако если немного изменить условие первой ситуации, то и в ней машинное обучение может помочь. Например, пусть программа в своих вычислениях использует также некоторые дополнительные внешние признаки, такие что измерять их дорого или долго, и которые поэтому не будут доступны на стадии регулярного применения. Тогда можно рассчитать целевую переменную по всем признакам включая трудноизмеримые, а потом обучить модель предсказывать полученную целевую переменную только по признакам, которые всегда будут доступны. Точно так же программа может использовать для разметки и информацию из более поздних моментов времени, которая на стадии применения станет неизвестна, поскольку будет относиться к будущему."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"функции_потерь"
]
},
"source": [
"## Классификация с очень большим количеством классов\n",
"\n",
"Пусть есть задача классификации, где различных меток много в сравнении с количеством объектов обучающей выборки (например, меток лишь в три раза меньше, чем объектов). В таком случае задача осложняется тем, что модель будет довольно редко угадывать правильную метку, и, значит, оптимизировать функции потерь, связанные с точными попаданиями, непрактично.\n",
"\n",
"Предположим, что задача классификации с $q$ классами, где $q$ большое в вышеописанном смысле, решается путем настройки параметров $\\theta$ некоторого классификатора, способного оценивать степени уверенности в принадлежности к классам (этим степеням даже необязательно давать в сумме 1). Обозначим за $p_\\theta(x_i, c)$ предсказанную на $i$-м объекте $x_i$ степень уверенности в классе $c$.\n",
"\n",
"Для $y_i$, истинного класса $i$-го объекта $x_i$, введём функцию $\\mathrm{rank}_\\theta(y_i)$. Эта функция вычисляется как порядковый номер класса $y_i$ при ранжировании классов по невозрастанию $f(c) = p_\\theta(x_i, c)$. Формальное определение выглядит так:\n",
"$$\\mathrm{rank}_\\theta(y_i) = \\#\\!\\left\\{\\left. c \\in Q \\: \\right| \\: p_\\theta(x_i, c) > p_\\theta(x_i, y_i)\\right\\} + 1,$$\n",
"где $Q$ — $q$-элементное множество классов, а решётка обозначает количество элементов в множестве. С учётом того, что предсказанные степени уверенности разных классов могут совпадать, стоит обратить внимание, что стоит знак >, а не $\\ge$.\n",
"\n",
"Для обучения $\\theta$ можно использовать функции потерь из следующего параметрического семейства, зависящего от параметров $\\alpha_1$, ..., $\\alpha_q$:\n",
"$$l(x_i, y_i, \\theta) = \\sum_{k = 1}^{\\mathrm{rank}_\\theta(y_i) - 1}\\alpha_k,$$\n",
"где если верхний предел суммы равен 0, то сумма по пустому множеству индексов полагается равной нулю, а зависимость правой части от $x_i$ заложена в определении $\\mathrm{rank}_\\theta(y_i)$.\n",
"\n",
"Некоторые известные метрики оптимизируются при обучении с функциями потерь из данного семейства:\n",
"* точность (accuracy) будет оптимизирована при $\\alpha_1 = 1$ и $\\alpha_k = 0$ для $k \\in \\{2, ..., q\\}$;\n",
"* вероятность угадать с $m$ попыток будет оптимизирована при $\\alpha_m$ = 1 и остальных $\\alpha_k = 0$;\n",
"* средний ранг будет оптимизирован при всех $\\alpha_k$, равных друг другу.\n",
"\n",
"Наконец, важно отметить, что функции из предложенного семейства не являются непрерывными, так что оптимизировать их напрямую затруднительно. Однако можно оптимизировать так называемые [суррогатные функции потерь](__home_url__/notes/Аппроксимация функции потерь), построенные для них."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"изображения"
]
},
"source": [
"## Метод Виолы-Джонса\n",
"\n",
"#### Общее описание\n",
"\n",
"Метод Виолы-Джонса применяется для детекции определённых объектов на изображениях. Чаще всего его используют для детекции лиц на фотографиях. При этом под детекцией имеется в виду обведение интересующего объекта в рамку (bounding box) без дальнейшего распознавания, какой именно из интересующих объектов представлен в этой рамке.\n",
"\n",
"Хотя метод был предложен в [работе](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.6807) 2001-го года и с тех пор появились решения на базе нейронных сетей, он используется и поныне благодаря относительно высокой точности и масштабируемости.\n",
"\n",
"Метод Виолы-Джонса предполагает, что изображения хранятся в чёрно-белом формате. Таким образом, с точки зрения метода Виолы-Джонса с каждым пикселем изображения ассоциировано ровно одно число, а именно число, кодирующее интенсивность чёрного.\n",
"\n",
"#### Обучение\n",
"\n",
"Детектор, получаемый методом Виолы-Джонса, нуждается в предварительной настройке (обучении) на данных.\n",
"\n",
"Обучающая выборка собирается как для задачи бинарной классификации. Объектами положительного класса в ней являются изображения, на которых представлено непосредственно то, что впоследствии необходимо будет обводить в рамки (скажем, сами лица, а не люди в полный рост). При этом все такие изображения должны быть приведены к одному размеру $n \\times m$ пикселей. В оригинальной работе изображения лиц сжимались до размера 24 пикселя на 24 пикселя, где число 24 выбрано по той причине, что имеет много целочисленных делителей (2, 3, 4, 6, 8, ...). Объектами отрицательного класса в такой выборке являются фрагменты того же размера $n \\times m$, полученные из посторонних изображений, не содержащих то, что необходимо детектировать.\n",
"\n",
"Признаковое описание объектов, используемое методом Виолы-Джонса, нетривиально. Входящие в него признаки называют вдохновлёнными преобразованием Хаара (Haar-like features), и, упрощённо говоря, можно считать, что эти признаки реагируют на наличие граней и линий в определённых местах. Интересно то, что в методе Виолы-Джонса признаки сами имеют параметры, настраиваемые по данным.\n",
"\n",
"Даже для изображений размера 24 $\\times$ 24 получается более 100 тысяч признаков. Любой из этих признаков может быть отнесён к одной из следующих групп:\n",
"* Вертикальная грань. Каждому признаку из этой группы сопоставлен некоторый прямоугольный фрагмент обучающего объекта размера $k \\times l$, где $l$ должно быть чётным, $l = 2p$. Если сумма интенсивностей левой половины этого фрагмента меньше (или больше — есть и такой признак, и такой) суммы интенсивностей правой половины этого фрагмента на некоторый обучаемый порог $\\theta$ (свой для каждого признака), то признак равен 1, а иначе он равен -1.\n",
"* Горизонтальная грань. Всё аналогично предыдущей группе, но теперь от обучающего изображения берутся фрагменты размером $k \\times l$, где уже $k$ обязано быть чётным, а разность считается между суммами по верхней и нижней половинам.\n",
"* Вертикальная линия. Каждому признаку из этой группы сопоставлен некоторый прямоугольный фрагмент обучающего объекта размера $k \\times l$, где $l$ представимо в виде $l = 2p + q$. Если средняя интенсивность по центральному прямоугольнику размера $k \\times q$, вложенному в этот фрагмент, меньше (или больше) средней интенсивности по двум боковым прямоугольникам размера $k \\times p$ на некоторый обучаемый порог $\\theta$ (свой для каждого признака), то признак равен 1, а иначе он равен -1.\n",
"* Горизонтальная линия. Определяется аналогично вертикальной линии.\n",
"* Четыре прямоугольника крест-накрест. Каждому признаку из этой группы сопоставлен некоторый прямоугольный фрагмент обучающего объекта размера $k \\times l$, где и $k$, и $l$ чётные, $k = 2p$, $l = 2q$. Если сумма интенсивностей по левому нижнему и правому верхнему прямоугольникам размера $p \\times q$ меньше (или больше) суммы интенсивностей по левому верхнему и правому нижнему прямоугольникам размера $p \\times q$ на некоторый обучаемый порог $\\theta$ (свой для каждого признака), то признак равен 1, а иначе он равен -1.\n",
"\n",
"Вычисление всех этих признаков, если его проводить в лоб по определению, окажется вычислительно затратным. Однако существует приём, позволяющий считать каждый из этих признаков за константное время вне зависимости от размеров прямоугольного фрагмента, по которому он считается. Этот приём связан с так называемым интегральным изображением (integral image), получаемым из исходного изображения. Строго говоря, интегральное изображение — это не изображение, потому что интенсивность чёрного в нём может выходить за максимально допустимое значение. Скорее, это таблица размера $n \\times m$. В ней на пересечении $i$-й строки и $j$-го столбца стоит число, равное сумме интенсивностей по всем пикселям исходного изображения, находящимся на расстоянии не более $i$ от левого края и не более $j$ от верхнего края. Благодаря интегральному изображению можно вычислить сумму интенсивностей по какому-либо прямоугольному фрагменту, сложив или вычтя всего четыре числа.\n",
"\n",
"Определим предсказанную метку на каком-либо объекте $x_i$ как:\n",
"$$\\hat{y}_i = \\mathrm{sign}\\left(\\sum_{j=1}^N \\alpha_j f_j(x_i)\\right),$$\n",
"где $N$ — количество признаков (оно зависит от $n$, $m$ и того, какие именно признаки включены: скажем, какая толщина линий рассматривается), $\\alpha_j$ — обучаемый коэффициент при $j$-м признаке, $f_j(x_i)$ — значение $j$-го признака на $i$-м объекте. При таком определении модели обучить потребуется $2N$ параметров: $N$ коэффициентов при признаках и $N$ порогов для признаков. В методе Виолы-Джонса обучение проводится алгоритмом, близким к алгоритму AdaBoost.\n",
"\n",
"#### Применение\n",
"\n",
"На этапе детекции нужных объектов на изображении перебираются различные размеры рамки (но с отношением сторон, близким к отношению $n$ к $m$) и различные положения этой рамки относительно изображения. То, что попадает в текущую рамку, классифицируется детектором, и, если предсказывается положительная метка, рамка наносится, а иначе нет. Разумеется, может оказаться так, что один и тот же объект будет обведён в несколько немного сдвинутых друг относительно друга рамок.\n",
"\n",
"Важно отметить, что при вычислении признаков размеры фрагментов, на которых они считаются, увеличиваются пропорционально тому, во сколько раз рамка больше, чем размер изображений, подававшихся на стадии обучения.\n",
"\n",
"Не менее важно обсудить один приём, благодаря которому применение происходит быстро. Если бы вычислялись именно предсказания вышеописанной модели, для каждого нового положения текущей рамки потребовалось бы вычислять все признаки (а их сотни тысяч). Чтобы этого избежать, используется каскадирование (cascading). Оно заключается в том, что наряду с финальным классификатором, обученным на всех признаках, обучается также цепочка более слабых классификаторов, обученных на меньших подмножествах признаков. Все эти классификаторы должны иметь близкую к единице полноту, но их точность не обязана быть высокой. Если в каскаде поначалу легковесных и постепенно усложняющихся классификаторов текущее положение рамки будет отвергнуто каким-либо классификатором, оно отвергается и для всей процедуры. И только то, что через весь каскад дойдёт до финального классификатора и пройдёт его, принимается за участок с детектируемым объектом. Благодаря каскадированию большая часть рамок отвергается на ранних стадиях классификаторами, использющими небольшое число признаков."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"активное_обучение",
"постановка_задачи"
]
},
"source": [
"## Оценивание дисперсии целевой переменной\n",
"\n",
"#### Введение\n",
"\n",
"Если функцией потерь, с которой обучается регрессор, является среднеквадратичная ошибка (MSE), то регрессор будет пытаться предсказать условное среднее целевой переменной при условии признаков. Если взять средний модуль ошибки (MAE), то тогда получится оценка условной медианы целевой переменной при условии признаков. Оценка условной дисперсии целевой переменной при условии признаков тоже может быть получена, хотя это и не делается просто выбором специальной функции потерь. Нужна же оценка условной дисперсии, например, тогда, когда есть возможность дополнительно запрашивать примеры в обучающую выборку — из областей признакового пространства, где дисперсия выше, хочется иметь больше примеров, чем из областей признакового пространства, где дисперсия ниже.\n",
"\n",
"#### Универсальный метод\n",
"\n",
"Как известно, дисперсия равна разности математического ожидания квадрата случайной величины и квадрата математического ожидания этой величины. В соответствии с этим для получения оценки условной дисперсии применим следующий эвристический подход:\n",
"* с MSE в качестве функции потерь обучим модель, предсказывающую исходную целевую переменную;\n",
"* с MSE в качестве функции потерь обучим модель, для которой целевой переменной является квадрат исходной целевой переменной;\n",
"* предсказанием дисперсии на некотором объекте назовём разность предсказания второй модели и квадрата предсказания первой модели, если эта разность больше 0, и 0 иначе.\n",
"\n",
"Очевидным недостатком этого метода является то, что иногда могут получаться нулевые предсказания там, где на самом деле дисперсия больше нуля. Зато его преимущество в том, что можно использовать любой метод машинного обучения.\n",
"\n",
"#### Нейросетевой метод\n",
"\n",
"Предположим, что условное распределение целевой переменной при условии признаков $p(y \\vert x)$ параметризуется некоторыми параметрами, которые зависят от вектора признаков $x$. Зная эти параметры, по ним можно вычислить дисперсию. Например, рассмотрим частный случай $p(y \\vert x) = \\mathcal{N}(\\mu, 1 / \\beta)(y)$, где $\\mu$ — условное среднее при условии $x$, а $\\beta$ — условная точность при условии $x$. В этом случае дисперсия $\\sigma^2 = 1 / \\beta$ по определению точности.\n",
"\n",
"Введём нейронную сеть, выходом которой на объекте с признаками $x$ является вектор параметров условного распределения $p(y \\vert x)$. В качестве функции потерь возьмём отрицательное прологарифмированное правдоподобие обучающей выборки относительно предсказанного распределения (точнее, ещё нужна какая-нибудь доработка на случай предсказаний, не попадающих в допустимый диапазон: например, неположительных значений точности). Остаётся только обучить нейронную сеть, получить предсказания для параметров и по ним вычислить оценку дисперсии.\n",
"\n",
"Преимуществом данного подхода является явный учёт вероятностной модели. Недостаток же этого подходя связан с тем, что при небольшом количестве признаков и/или малом размере обучающей выборки нейронные сети могут уступать другим алгоритмам машинного обучения. "
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рабочий_процесс"
]
},
"source": [
"## Об итеративности сведения реальной задачи к задаче машинного обучения\n",
"\n",
"При наличии прикладной задачи и относящихся к ней данных далеко не всегда удаётся с первого раза подобрать такую постановку задачи машинного обучения, при которой её решение было бы частью решения исходной прикладной задачи. Ниже этот тезис иллюстрируется примером.\n",
"\n",
"Допустим, стоит такая задача: агрегатор такси хочет находить пользоваталей, которые в ближайшее время откажутся от его услуг, и отправлять им сообщение с купоном на скидку на следующую поездку. Казалось бы, почему нельзя сформулировать задачу машинного обучения как задачу бинарной классификации, где объектами являются пары `(клиент, дата)`, а целевая переменная равна единице, если клиент после соответствующей даты не пользовался услугами компании на протяжении некоторого зафиксированного срока, и нулю иначе? В принципе, данная постановка может оказаться хорошей. Однако предположим, что после разработки решения обнаружилось, что для отправки купона на скидку отбираются только пользователи, оставившие об агрегаторе такси негативные отзывы в интернете или позвонившие с жалобами на горячую линию, причём разбор этих отзывов и жалоб показал, что клиенты недовольны тем, что водители такси создавали аварийные ситуации. Очевидно, скидка здесь будет неэффективным инструментом удержания аудитории, но цель заказчика — именно удержание клиентов, а не просто угадывание тех из них, кто склонен уйти к конкурентам.\n",
"\n",
"Существование риска замены постановки задачи машинного обучения является аргументом в пользу того, что при появлении более-менее готовой первой версии решения лучше как можно скорее опробовать её в деле и собрать по ней обратную связь."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"последовательности",
"генеративные_модели"
]
},
"source": [
"## Лучевой поиск для порождения последовательностей\n",
"\n",
"Пусть дана порождающая вероятностная модель $\\mathbb{P}\\!\\left(x_i \\, \\left| \\, \\{x_j\\}_{j=1}^{i-1}, v\\right.\\right)$, где $x_i$ — текущий элемент последовательности, $\\{x_j\\}_{j=1}^{i-1}$ — предшествующее ему начало этой последовательности, а $v$ — некоторый вектор (или иной объект), хранящий в себе дополнительную известную информацию (например, если порождается предложение, являющееся переводом заданного предложения на другом языке, то $v$ может быть векторным представлением переводимого предложения). Возникает вопрос: как из такой модели сэмплировать (порождать) последовательности?\n",
"\n",
"Простейшим решением является «жадное» порождение. Можно выбрать начало по правилу:\n",
"$$x_1 = \\arg \\max_x \\mathbb{P}\\!\\left(x \\, \\left| \\, \\{\\}, v\\right.\\right),$$\n",
"а всякий раз далее выбирать следующий элемент по правилу:\n",
"$$x_i = \\arg \\max_x \\mathbb{P}\\!\\left(x \\, \\left| \\, \\{x_j\\}_{j=1}^{i-1}, v\\right.\\right).$$\n",
"Как это и бывает с «жадными» алгоритмами, нет никаких гарантий, что полученная таким образом последовательность будет иметь наибольшую вероятность. Например, пусть рассматриваются последовательности длины 2 над символами $a$ и $b$, дополнительной информации нет (так что $v$ можно опустить), а вероятностная модель имеет вид:\n",
"$$\\mathbb{P}\\!\\left(a \\, \\left| \\, \\{\\}\\right.\\right) = 0.6,$$\n",
"$$\\mathbb{P}\\!\\left(b \\, \\left| \\, \\{\\}\\right.\\right) = 0.4,$$\n",
"$$\\mathbb{P}\\!\\left(a \\, \\left| \\, \\{a\\}\\right.\\right) = 0.5,$$\n",
"$$\\mathbb{P}\\!\\left(b \\, \\left| \\, \\{a\\}\\right.\\right) = 0.5,$$\n",
"$$\\mathbb{P}\\!\\left(a \\, \\left| \\, \\{b\\}\\right.\\right) = 0.9,$$\n",
"$$\\mathbb{P}\\!\\left(b \\, \\left| \\, \\{b\\}\\right.\\right) = 0.1.$$\n",
"В рамках такой модели наиболее вероятной последовательностью является последовательность $ba$, однако «жадный» поиск закончится ничьёй между $aa$ и $ab$.\n",
"\n",
"Другой крайностью является полный (экспоненциальный) перебор, когда для каждой возможной последовательности считаются её вероятности, а затем выбирается та последовательность, у которой вероятность наибольшая. Разумеется, данный подход является вычислительно неподъёмным для порождения хоть сколько-нибудь длинных последовательностей.\n",
"\n",
"Лучевой поиск (beam search) является компромиссным соединением двух вышеописанных подходов в один новый подход. По сути, это тоже «жадный» алгоритм, но чуть более дальновидный.\n",
"\n",
"Алгоритм лучевого поиска для порождения последовательности длины $l$ (или не более чем $l$, если среди символов есть символ конца последовательности, после появления которого сэмплирование останавливается) получает на вход помимо собственно вероятностной модели и вектора $v$ массив из $l$ чисел $\\{n_i\\}_{i=1}^l$, интерпретируемых как количества подпоследовательностей, остающихся в рассмотрении после каждого шага.\n",
"\n",
"Устроен же сам алгоритм так. На первом шаге отбираются $n_1$ различных одноэлеметных подпоследовательностей, составленных каждая из одного из $n_1$ элементов с наибольшей $\\mathbb{P}\\!\\left(x \\, \\left| \\, \\{\\}, v\\right.\\right)$. На каждом же из последующих шагов (обозначим номер шага за $i$, $i > 1$) для каждой из $n_{i-1}$ отобранных на предыдущем шаге подпоследовательностей рассматриваются все её возможные продолжения на один элемент вперёд и из получившихся таким образом новых подпоследовательностей отбираются $n_i$ наиболее вероятных. Под конец из $n_l$ отобранных последовательностей выбирается одна наиболее вероятная и возвращается как результат.\n",
"\n",
"«Жадный» алгоритм, приводившийся как пример решения в начале этой заметки, является частным случаем лучевого поиска при всех $n_i = 1$, а полный перебор является частным случаем лучевого поиска при значениях $n_i$, равных количествам всех без исключения возникающих на соответствующих шагах последовательностей."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"практические_приёмы"
]
},
"source": [
"## Обучение на выборке с малым количеством положительных примеров\n",
"\n",
"Допустим, предстоит решить задачу бинарной классификации, где объектов положительного класса не более нескольких десятков (а объектов отрицательного класса заметно больше). Опасность здесь кроется в том, что при хоть сколько-нибудь большом количестве исходных признаков резко возрастает риск переподгонки (overfitting), вызванной обнаружением иллюзорных закономерностей. Высоки шансы того, что какая-либо комбинация признаков чисто случайно позволит хорошо отделить объекты положительного класса. На то же самое можно посмотреть и под таким углом: для отделения небольшого количества точек в пространстве высокой размерности подойдут многие довольно простые разделяющие поверхности.\n",
"\n",
"Иногда решить проблему удаётся при помощи вовлечения автокодировщика. Пусть автокодировщик со скрытым слоем ощутимо меньшей размерности будет обучен по признакам объекта восстанавливать их же. Тем самым будет выучено признаковое представление, от которого ожидается, что все новые признаки будут информативными и отражающими важные для задачи стороны реального мира. Если выйдет получить такое признаковое представление, риск переподгонки сократится. "
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"решающие_деревья"
]
},
"source": [
"## Прунинг решающих деревьев\n",
"\n",
"Обучению решающего дерева присущи следующие недостатки:\n",
"* Чем дальше какой-либо узел от корня, тем меньше количество данных, на которых подбирается критерий разбиения в этом узле.\n",
"* Структура обучаемого дерева нестабильна. Малое изменение обучающей выборки может привести к построению сильно отличающегося дерева (например, потому что могут измениться признак и его пороговое значение, по которым происходит какое-то более раннее разбиение).\n",
"\n",
"Две этих особенности приводят к тому, что решающее дерево, обученное каким-либо жадным алгоритмом наподобие CART, скорее всего, окажется переобученным. Чтобы сделать дерево менее переобученным, его подрезают, выкидывая часть узлов большой глубины. Соответствующие техники называют прунингом.\n",
"\n",
"Существует два основных вида прунинга:\n",
"* reduced error pruning;\n",
"* cost-complexity pruning.\n",
"\n",
"Остановимся на них подробнее.\n",
"\n",
"Reduced error pruning так же, как и, скажем, [ранняя остановка](__home_url__/notes/Ранняя остановка), требует наличия дополнительной валидационной выборки. Для каждой пары листьев, имеющих общего прямого родителя, на валидационной выборке оценивается качество дерева, где этих листьев нет (и, стало быть, зато листом является их родитель). Если качество на валидационной выборке не ниже, эти листья убираются. Процесс продолжается до тех пор, пока больше не останется соседних листьев, которые было бы можно объединить.\n",
"\n",
"Reduced error pruning считается методом, слишком сильно обрезающим дерево. Так, в частности, если в какой-либо узел не придёт ни одного объекта из валидационной выборки, этот узёл и всё, что идёт после него, будут удалены.\n",
"\n",
"А вот в cost-complexity pruning есть специальный гиперпараметр $\\alpha$, регулирующий агрессивность обрезки дерева.\n",
"\n",
"Задача для этого прунинга ставится в виде минимизации регуляризованной ошибки на обучающем множестве, а именно:\n",
"$$E_{\\mathrm{train}}(T) + \\alpha \\, s(T)\\to \\min_T,$$\n",
"где $T$ — какой-то обрезанный вариант исходного дерева, $E_{\\mathrm{train}}(T)$ — значение функции потерь на тренировочном множестве для дерева $T$, $s(T)$ — количество листьев в дереве $T$. Таким образом, сложностью дерева считается количество листьев в нём.\n",
"\n",
"Решение поставленной задачи можно найти итеративно. На $i$-м шаге будем удалять из дерева всё, что идёт после какого-либо одного узла $t$. Этот узел ищется перебором по следующему критерию:\n",
"$$\\frac{E_{\\mathrm{train}}(T_{i-1}^{(t)}) - E_{\\mathrm{train}}(T_{i-1})}{s(T_{i-1}) - s(T_{i-1}^{(t)})} \\to \\min_t,$$\n",
"где $T_{i-1}$ — дерево, оставшееся после $(i-1)$-го шага (в этой нотации $T_0$ — исходное дерево), а $T_{i-1}^{(t)}$ — дерево, получающееся из него удалением всего, что идёт после узла $t$. Обозначим за $\\alpha_i$ то, чему равна левая часть формулы выше при оптимальном узле $t$. Итеративный процесс заканчивается, как только $\\alpha_i$ оказывается больше, чем $\\alpha$ (или как только дерево обрезается под корень). Критерий остановки взят таким, потому что для него продолжение процесса означает, что новое дерево не хуже старого с точки зрения минимизируемой функции. \n",
"\n",
"При этом рассуждением от противного можно показать, что ряд $\\alpha_i$ является неубывающим. Действительно, если бы для какого-то $i$ было бы верно, что $\\alpha_i > \\alpha_{i+1}$, то это означало бы, что на $i$-м шаге дерево было обрезано неоптимально, ведь вариант обрезки по узлу из $(i+1)$-го шага лучше.\n",
"\n",
"Говоря верхнеуровнево, описанный итеративный процесс решения минимизационной задачи выглядит так: сначала совершается обрубание «ветки», максимально улучшающее минимизируемую величину, затем совершается лучшее обрубание «ветки» для оставшейся части дерева, и так до тех пор, пока обрубание не перестанет приводить к улучшениям."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"решающие_деревья",
"интересные_факты"
]
},
"source": [
"## Решающие деревья и монотонные преобразования признаков\n",
"\n",
"Существует распространённый миф, что монотонные преобразования признаков не влияют на предсказания решающих деревьев. Приведём контрпример, опровергающий это. Рассмотрим решающий пень, которому дали задачу бинарной классификации с одним признаком, в котором у объектов нулевого класса этот признак был равен 1 и 2, а у объектов положительного класса — 3 и 4 (то есть всего в обучающей выборке было четыре объекта). Очевидно, этот решающий пень может добиться идеального разделения классов, проведя порог где угодно между 2 и 3. Строго говоря, как именно проводить этот порог зависит от конкретной реализации алгоритма, но выберем наиболее естественное решение: проведём порог посередине, то есть на уровне 2,5. Теперь предположим, что этот же классификатор обучался на выборке, где исходный признак возвели в квадрат. Тогда порог будет проведён на уровне 6,5. Таким образом, на этапе применения объекты, у которых исходный признак лежит в полуинтервале $[2.5, \\sqrt{6.5})$, из-за возведения признака в квадрат будут вместо положительного класса отнесены к нулевому.\n",
"\n",
"Как правило, вышеописанная особенность не заметна на практике, что и объясняет, почему разбираемое заблуждение смогло укорениться. Но на соревнованиях по машинному обучению эту особенность иногда используют, чтобы внести больше разнообразия в ансамбли моделей."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"практические_приёмы",
"векторные_вложения"
]
},
"source": [
"## Способы получения вложений объектов по вложениям связанных объектов\n",
"\n",
"Допустим, есть объекты двух видов, между которыми существуют взаимосвязи: например, есть тексты и есть пользователи, причём про пользователей известно, какие тексты они читали, а какие нет. Также допустим, что для одного из видов объектов уже есть готовые векторные представления: например, вложения для текстов были получены через [word2vec](__home_url__/notes/Вероятностная интерпретация word2vec) или [BERT](__home_url__/notes/BERT (Bidirectional Encoder Representations from Transformers)). Предположим, что требуется, затратив не слишком много вычислительных ресурсов, получить вложения для объектов второго вида на базе вложений объектов первого вида.\n",
"\n",
"Сделать это можно следующими способами:\n",
"* Проведя ALS-шаг (один шаг попеременного метода наименьших квадратов). По сути, этот шаг является решением $n$ независимых задач линейной регрессии, где $n$ — количество объектов второго вида. В $i$-й задаче выборка основывается на том, с какими объектами первого вида было взаимодействие $i$-го объекта второго вида: скажем, можно взять все тексты, которые читал пользователь, и просэмплировать сколько-то текстов, которые пользователь не читал. Целевой переменной является результат взаимодействия (например, 1, если текст был прочтён, и 0, если текст попал в выборку в результате отрицательного сэмлирования). Признаками являются векторные вложения выбранных объектов первого вида. Вектор коэффициентов, найденных при решении получившейся задачи линейной регрессии, и станет вложением $i$-го объекта.\n",
"* Проагрегировав векторные представления тех объектов первого вида, с которыми взаимодействовал объект второго вида. При этом можно использовать не только сумму, среднее, максимум или минимум: например, если известно время взаимодействия, то можно рассчитать взвешенную сумму с весами, затухающими в зависимости от прошедшего с момента взаимодействия времени."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"пререквизиты_из_математики"
]
},
"source": [
"## Применение SVD в задачах анализа данных\n",
"\n",
"#### Введение\n",
"\n",
"Пусть есть квадратная матрица $M$ размера $n \\times n$, такая что у неё существует $n$ линейно независимых собственных векторов $q_i$, $i \\in \\{1, \\dots, n\\}$. Тогда верно, что:\n",
"$$M = Q \\Lambda Q^{-1},$$\n",
"где $Q$ — матрица размера $n \\times n$, $i$-м столбцом которой является $q_i$, а $\\Lambda$ — диагональная матрица размера $n \\times n$, у которой $\\Lambda_{ii}$ является собственным значением, соответствующим вектору $q_i$. Доказывается это так: $MQ = Q\\Lambda$ по определению собственных векторов, а домножение справа на $Q^{-1}$ даёт описанную формулу. А интерпретировать это можно так: если посмотреть на $M$ как на линейный оператор, то $Q^{-1}$ переводит в собственный базис, $\\Lambda$ выполняет преобразование, соответствующее $M$ в этом базисе, а $Q$ возвращает в исходный базис.\n",
"\n",
"Разложение матрицы $M$ из предыдущего абзаца называется разложением на основе собственных векторов или спектральным разложением. Как видно, оно существует не для всякой матрицы $M$: в частности, его нет для неквадратных матриц. Обобщением является сингулярное разложение, существующее у любой матрицы $M$ размера $m \\times n$. Сингулярное разложение (сокращённо SVD, от singular value decomposition) выглядит так:\n",
"$$M = U \\Sigma V^T,$$\n",
"где $U$ — ортогональная матрица (т.е. $U^T = U^{-1}$) размера $m \\times m$, $\\Sigma$ — матрица размера $m \\times n$, у которой везде нули кроме главной диагонали, а $V$ — ортогональная матрица размера $n \\times n$.\n",
"\n",
"Пусть для двух векторов единичной длины $u \\in \\mathbb{R}^m$ и $v \\in \\mathbb{R}^n$ верно, что:\n",
"$$Mv = \\sigma u,$$\n",
"$$Mu = \\sigma v,$$\n",
"где $\\sigma$ — неотрицательное число. Тогда $\\sigma$ называют сингулярным числом матрицы $M$, $u$ называют левым сингулярным вектором матрицы $M$, а $v$ называют правым сингулярным вектором матрицы $M$. Оказывается, что в сингулярном разложении матрица $U$ составлена из левых сингулярных векторов матрицы $M$ (т.е. её $i$-м столбцом является $i$-й левый сингулярный вектор), на главной диагонали $\\Sigma$ стоят сингулярные числа матрицы $M$, а матрица $V$ составлена из правых сингулярных векторов матрицы $M$.\n",
"\n",
"Рассмотрим следующее равенство:\n",
"$$M^TM = (V \\Sigma^T U^T) (U \\Sigma V^T) = V(\\Sigma^T\\Sigma)V^T.$$\n",
"Справа получилось спектральное разложение матрицы $M^TM$ (оно существует, потому что это вещественная квадратная симметричная матрица). Тем самым доказано, что правые сингулярные векторы матрицы $M$ являются собственными векторами матрицы $M^TM$, а квадраты сингулярных значений матрицы $M$ являются собственными значениями матрицы $M^TM$.\n",
"\n",
"С точки зрения машинного обучения сингулярное разложение интересно тем, что находить его можно вычислительно эффективными численными методами, а это означает, что если решение какой-то задачи выражается через SVD, то и эту задачу можно решить вычислительно эффективно.\n",
"\n",
"#### Применение в МНК\n",
"\n",
"Пусть $w$ — вектор-столбец размера $n \\times 1$, а $y$ — вектор-столбец размера $m \\times 1$. Рассмотрим уравнение $Mw = y$, где $y$ и $M$ заданы, а $w$ требуется найти. Если считать, что строки матрицы $M$ соответствуют объектам, а столбцы признакам, и считать, что $y$ задаёт значения целевой переменной на объектах, то получится задача линейной регрессии. В случае, когда функцией потерь является среднеквадратичная ошибка, эту задачу можно решить методом наименьших квадратов, дающим решение в аналитическом виде:\n",
"$$w = (M^TM)^{-1}M^Ty.$$\n",
"\n",
"Матрицу $M^{\\prime} = (M^TM)^{-1}M^T$ называют псевдообратной к матрице $M$. При $m \\ge n$ приближённое решение $w = M^{\\prime}y$ минимизирует $\\Vert Mw - y\\Vert_2$ среди всех возможных значений вектора $w$, а при $m < n$ решение $w = M^{\\prime}y$ является точным решением с наименьшей $L_2$-нормой среди всех точных решений.\n",
"\n",
"Найти псевдообратную матрицу можно просто по её определению. Однако если данных много, вычисление обратной матрицы для $M^TM$ требует серьёзных затрат, а ещё оно может быть неустойчивым. Подстановка вместо матрицы $M$ её сингулярного разложения после сокращения множителей даёт другую формулу:\n",
"$$M^{\\prime} = V \\Sigma^{\\prime} U^T,$$\n",
"где $\\Sigma^{\\prime}$ — матрица, получающаяся из матрицы $\\Sigma$ заменой всех ненулевых элементов на обратные к ним и транспонированием. В такой формуле уже не надо обращать матрицы, но нужно каким-либо численным методом получить сингулярное разложение.\n",
"\n",
"#### Понижение размерности\n",
"\n",
"Пусть матрицу $M$ требуется приблизить матрицей ранга не выше чем $k$, где приближение ищется в смысле минимизации $L_2$-нормы разности между $M$ и искомым решением. Обозначим за $\\Sigma_k$ матрицу, получающуюся из $\\Sigma$ занулением всех диагональных элементов (а недиагональные и так нули) кроме $k$ наибольших. Утверждается, что матрица $U \\Sigma_k V^T$ будет решением поставленной задачи.\n",
"\n",
"Также существует связь между сингулярным разложением и методом главных компонент. Напомним, что метод главных компонент опирается на спектральное разложение эмпирической ковариационной матрицы. Обозначим за $\\overline{m}$ вектор размера $1 \\times n$, в котором стоят средние значения столбцов матрицы $M$. Тогда матрица $N = M - \\overline{m}$ является матрицей центрированных данных. Эмпирическая ковариационная матрица для данных, заданных матрицей $M$, равна $C = \\frac{1}{m - 1}N^TN$, где множитель $\\frac{1}{m - 1}$ является поправкой на число степеней свободы (среднее, посчитанное по $m$ наблюдениям, забирает одну степень свободы у этих $m$ наблюдений). Таким образом, в методе главных компонент можно найти спектральное разложение матрицы $C$ через сингулярное разложение матрицы $N$."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"естественные_языки",
"подготовка_данных"
]
},
"source": [
"## Разбиение текстов на токены\n",
"\n",
"#### Введение\n",
"\n",
"В области автоматической обработки текстов первичные векторные вложения строятся для токенов, а уже из них получаются вложения для более крупных сущностей (предложений, текстов, названий и т.д.).\n",
"\n",
"В качестве токенов можно брать слова, как это сделано, например, в word2vec, но у такого подхода есть недостаток: слова, не попавшие в обучающую выборку, должны заменяться на специальный токен неизвестного слова (\\<UNK\\>). Однако если в таких словах есть какие-либо информативные составляющие (например, угадывается знакомая часть слова), это хотелось бы тоже использовать.\n",
"\n",
"Крайностью, гарантирующей, что любой текст будет разбит на известные токены, является подход, в котором токенами являются все отдельные символы, но это влечёт за собой свои проблемы:\n",
"* вложения символов, скорее всего, окажутся неинформативными, потому что у символов нет смысловой нагрузки (мало ли в каких словах встретилась буква «а»);\n",
"* длина каждого из текстов, измеренная в токенах, будет максимальной, что замедлит обучение и применение, а также в некоторых случаях может отрицательно сказаться на последовательной генерации из-за возросшей вероятности прийти к сгенерированному началу, не похожему ни на что из обучающей выборки.\n",
"\n",
"Таким образом, нужны специальные алгоритмы токенизации, которые позволяли бы вычленить из текстов максимум полезной информации, превращая хоть сколько-нибудь частые слова в токены, а редкие или незнакомые слова разбивая на по возможности более длинные токены.\n",
"\n",
"#### Кодирование биграмм (BPE, Byte Pair Encoding)\n",
"\n",
"Кодирование биграмм изначально было предложено в 1994 году для сжатия текстов. Позже оно получило модификацию для токенизации в компьютерной обработке естественных языков. Этот метод токенизации может применяться как к текстам в человекочитаемом виде (где отдельный символ — это буква, цифра, знак препинания и т.д.), так и к текстам, представленным в виде последовательности байтов в какой-либо кодировке (и тогда отдельный символ — это байт). С точки зрения самого алгоритма никакой разницы нет, так что далее будут просто упоминаться символы без уточнения их природы.\n",
"\n",
"Концептуально (т.е. без учёта вычислительных оптимизаций) алгоритм «обучения» BPE-токенизации выглядит так:\n",
"* в список токенов помещаются все отдельные символы и специальный символ конца слова \\<w\\>;\n",
"* обучающий корпус представляется через токены из этого списка;\n",
"* список слияний инициализируется пустым списком;\n",
"* пока количество токенов не достигло требуемого значения (это гиперпараметр, интерпретируемый как размер словаря):\n",
" - самая частая во всём обучающем корпусе последовательность из двух подряд идущих в одном слове токенов объявляется новым токеном, и этот новый токен добавляется в список токенов (если есть ничья между несколькими вариантами, выбирается один случайный);\n",
" - в обучающем корпусе везде, где встретились рядом два токена из наиболее частой биграммы, они заменяются на новый токен;\n",
" - в список слияний добавляется пара из этих двух токенов;\n",
" - если вдруг все биграммы стали встречаться в корпусе ровно по одному разу, цикл досрочно прекращается, потому что дальше что-то объединять смысла нет.\n",
" \n",
"Важно отметить, что в списке слияний количество вхождений в корпус каждой объединяемой пары монотонно не возрастает. Это позволяет представить этап «применения» как один проход по списку слияний:\n",
"* текст, который надо токенизировать, представляется в виде токенов, являющихся исходными символами и специальным символом конца слова \\<w\\>;\n",
"* для каждого элемента списка слияний:\n",
" - везде, где эта пара есть в тексте, она заменяется на токен, в который была объединена.\n",
"* то, что получится по окончании цикла, и есть токенизированный текст.\n",
"\n",
"#### WordPiece\n",
"\n",
"Этот метод токенизации с точки зрения «обучения» похож на BPE. Есть всего два отличия:\n",
"* пара, которая должна образовать новый токен, ищется не по количеству вхождений, а по количеству вхождений, разделённому на произведение вхождений каждого из токенов этой пары;\n",
"* список слияний не нужен.\n",
"\n",
"А вот этап «применения» устроен по-другому:\n",
"* для каждого слова текста, который надо токенизировать:\n",
" - это слово представляется в виде токенов, являющихся исходными символами;\n",
" - текущая позиция ставится в последний символ этого слова;\n",
" - пока то, что до текущей позиции (включая её саму) не содержится в списке токенов:\n",
" - текущая позиция сдвигается на один символ влево;\n",
" - то, что до текущей позиции (включая её саму), заменяется на соответствующий токен;\n",
" - то, что строго после текущей позиции, обрабатывается как отдельное слово теми же шагами, что были выше, пока ничего не останется;\n",
"* токенизированный текст получается вышеописанным разбиением слов на токены.\n",
"\n",
"#### Unigram\n",
"\n",
"Если BPE и WordPiece начинали со списка символов, а потом наращивали список токенов до нужного размера, то в методе токенизации под названием Unigram подход противоположный. Исходно токенами считаются все слова, а также все возможные $n$-граммы, такие что они встретились внутри хотя бы одного слова. Затем на каждой итерации удаляется сколько-то наименее полезных токенов, и так до тех пор, пока список токенов не сократится до требуемого размера.\n",
"\n",
"Для токенов, являющихся отдельными символами, полезность считается бесконечной, потому что, если хотя бы один из них удалить, некоторые слова нельзя будет токенизировать.\n",
"\n",
"Полезность остальных токенов определяется через падение правдоподобия обучающего корпуса при их удалении. Это правдоподобие считается так. «Вероятностью» токена объявляется количество вхождений в корпус $n$-граммы, соответствующей этому токену, разделённое на сумму аналогичных количеств по всем токенам, оставшимся к текущей итерации (кавычки вокруг слова «вероятность» стоят, потому что $n$-граммы могут пересекаться). Вероятностью слова считается максимальное произведение вероятностей токенов, на которые это слово разбивается, где максимум ищется по всем способам разбить это слово на имеющиеся на данной итерации токены. Вероятностью корпуса считается произведение вероятностей всех его слов.\n",
"\n",
"Поскольку подсчёт полезности токенов вычислительно затратный, на одной итерации удаляются сразу 10%-20% от общего числа токенов. \n",
"\n",
"«Применение» устроено точно так же, как у метода WordPiece."
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.12"
}
},
"nbformat": 4,
"nbformat_minor": 2
}