Этот алгоритм обучения применяется во всех параметрических моделей, он будет разобран более подробно на примере линейной регрессии. Градиентный спуск имеет несколько модификации для борьбы с переобучением. В данном исследовании использовались регуляризаторы и алгоритм адаптации обучающего коэффициента.
Регуляризаторы.
Одним из симптомов переобучения является слишком большие модули коэффициентов, поэтому в функционал ошибки также добавляется абсолютная или квадратичная норма весов с некоторыми коэффициентами.
,
,
,
Таким образом существуют 3 модификации линейных регрессии: c использованием L1 - Lasso; с использованием L2 - Ridge; с использованием L1 и L2 - ElasticNet. Lasso имеет сильную способность предотвращать переобучение и обнулять коэффициенты слабо значимых признаков.
Алгоритм адаптации градиента.
При обучении нейронных сетей также используют градиентный бустинг. Однако в своем изначальном виде его почти не применяют из-за сложной поверхности решения, поэтому используют 3 модификации при подсчете градиента и коэффициента обучения:
Уменьшение коэффициента обучения с номером итерации. Изначально веса модели находятся очень далеко от оптимума по поверхности решения, поэтому требуется делать большие шаги. В конце же обучения набор параметров находится близко к оптимуму, поэтому нужно делать небольшие и осторожные передвижения по поверхности решения.
Момент. Поверхность решения может быть очень шероховатой и неровной. Таким образом, большая вероятность того, что градиент в произвольной точке будет не совпадать с направлением усреднённого градиента ближайшей области. Решение этой проблемы заключается в экспоненциальном сглаживании последовательности градиентов.
,
,
Где - вес, с которым складываются градиент на этой и предыдущей итерации.
У данной модификации есть физическая интерпретация - если представить набор параметров модели как шарик на поверхности решения, то Момент добавляет инерцию к этому шарику
RMSprop. Поверхность решения может быть очень неоднородной в плане масштаба по координатам коэффициентов. Например, для одного коэффициента требуется длинные шаги в одну сторону, а для другого очень аккуратно приблизиться к точке оптимума. Таким образом, требуется нормировать градиенты на длину шага.
,
,
Где - коэффициент экспоненциального усреднения.
Комбинация всех 3 методов для адаптации называется Adam, данный оптимизатор был использован при обучении нейронных сетей.
ARMA
Самым известным инструментом для регрессии временных рядов является класс ARMA моделей. ARMA модель (Auto Regression + Moving Average) в своем изначальном виде представляет собой линейную регрессию, которая предсказывает будущее значение временного ряда за счет предыдущих значений временного ряда и значений ошибок. Количество предыдущих наблюдений, которые входят в модель, называется лагом модели.
,
Где a,b,c - коэффициенты модели, L - лаг модели, Y - показание временного ряда i наблюдений назад, e - ошибка модели на i наблюдении назад; i - смещение номер наблюдения от текущего.
Также у ARMA модель есть различные модификации - ARIMA, SARMA, SARIMAX и т.д. Суть этих модификации сводится к приведению исходного временного ряда в стационарный вид через дифференцирования различного вида. Тем не менее, класс ARMA моделей может предсказывать только трендовые и сезонные составляющие.
Рисунок 6. Пример ARMA модели - предсказание объема рынка мебели на рынке США
Логистическая регрессия
Логистическая регрессия также является простым и популярным алгоритмом классификации с интерпретируемыми коэффициентами. Представляет собой сигмиодную функцию, которая принимает вектор признаков, помноженный на вектор весов.
Рисунок 7. Пример логистической регрессии - разделение на класс положительных и отрицательных чисел
,
Где wi - веса модели i-го признака, xi - i-ый признак, b - свободный член, Y - ответ модели.
Если же это задача мультиклассификации, следует использовать формулу SoftMax.
,
Где k - номер класса, j - нумератор для перебора последовательности классов.
Обучается с помощью градиентного спуска. Если оптимизатор минимизирует hinge loss, данную модель называют SVM (support vector machine).
Нейронные сети
Главная идея нейросетей заключается в создании композиции линейных моделей, которые, свою очередь, содержат ответы других линейных моделей.
Нейронная сеть последовательно умножает вектор признаков на вектор весов и передает результат активационной функции. Таких блоков может быть бесконечно много и, поэтому, нейросеть может аппроксимировать функцию любой сложности.
,
Где - активационная функция на i слое, - вектор входных признаков на слое i, Wi - матрица весов на слое i, - выходной вектор слоя i
Ниже, на рисунке 8, находится графический пример простой нейронной сети и ее уравнение.
Рисунок 8. Пример простейшей нейронной сети
,
Видно, что даже небольшая нейронная сеть является намного сложнее, чем линейная регрессия.
Нейронные сети также обучаются градиентным спуском и всеми его приемами по контролю по обучению, но с производная ошибки высчитывается другим образом. Такая модификация называется обратным распространением.
Стоит отметить, что описанный метод и архитектура являются простейшей моделью нейронной сети, существуют также архитектуры для анализа изображений - сверточные сети, и архитектуры для анализа текста - рекуррентные сети. Однако, т.к. данные являются табличными, эти архитектуры не использовались.
,
,
,
Непараметрические методы
В данной работы использованы следующие непараметрические методы.
Решающие деревья
Рисунок 9. Пример решающего дерева
Решающее дерево представляет собой направленный граф без циклов. Образец, попавший в узловой корень графа, будет передвигать вниз, пока не достигнет какой-либо терминальной вершины - листа дерева. В каждом узле представлено некое правило, которое определит, в какой узел дальше направится вершина. У каждого листа есть значение ответа для данного образца. Чаще всего дерево является бинарным, т.е. от каждой вершины исходит только 2 ребра.
Решение о том, по какому ребру направить образец X происходит следующем образом - в каждом узле, кроме терминальных, есть правило о выборе направления. Это правило заключает в себе признак f и значение b, если значение X[f]>b, то образец направляется по одному ребру, в противном случай по другому. Если же f категориальный признак, вместо точечного значения b выбирается набор классов.
Процесс обучения:
Чтобы определить качество разбиения, нужно ввести понятия критерия информативности H(x). Он показывает то, насколько элементы в выборке неоднородны по отношению к целевой переменной Y. Для задач регресcии и классификации эти критерии совершенно разные. Для задач регрессии чаще всего используют ошибки MSE и MAE. Для классификации используют информационный критерий Джини, либо кросс энтропийный критерий. Тем не менее, гипотетически можно модифицировать любой функционал ошибки и использовать его в качестве информационного критерия
, ,
,
,
Где y - ответ модели, a - реальное значение.
Когда выборка X размером |X| попадает в какую-либо вершину, нужно выбрать такие признак f и значение b, при котором разбиение будет оптимальным, т.е. критерий информативности уменьшиться насколько это возможно при данной выборке. После разбиения выборка делится на два части - Xr и Xl.
,
Рисунок 10. Демонстрация разделения выборки в бинарном дереве
Каждая подвыборка также разбивается еще на 2 части и так далее. Очевидно, этот процесс будет происходить до тех пор, пора каждая точка не обзаведется собственной терминальной вершиной, что приведет к переобучению. Что бы этого избежать, вводят критерии останова, при которых дерево перестает расти. Критерий останова - ограничения на количество вершин, количество листьев, максимальное количество точек в терминальном узле и т.д. Ответом листа станет среднее\мода всех точек, которые попали в этот лист. градиентный бустинг нейронный сеть
Случайный лес
Идея случайного леса заключается в генерации множества деревьев со случайном подмножеством образцов и доступных признаков и усреднении ответов этих алгоритмов. Это позволяет уменьшить разброс ошибки.
Градиентный бустинг
Градиентный бустинг очень схож со случайном лесом, но деревья, в данном случай, строятся последовательно, исправляя ошибку предыдущего.
Построение градиентного бустинга на примере регрессии:
For m=1..M:
,
,
,
,
Где M - количество итерация, F0 - базовый алгоритм, r - остатки модели, y - реальные значения, h - корректирующие алгоритмы.
1.3 Машинное обучение без учителя
В рамках данного исследования использовалось 2 алгоритма по сжатию признакового пространства - Word2Vec и PCA (principal component analysis).
Principal Component Analysis.
PCA является методом сжатия признакового пространства, который разворачивает базис таким образом, что в новом базисе исходные признаки перестают коррелировать между собой.
Если взять матрицу признакового описания X и разложить ее путем сингулярного разложения, то в итоге выйдет следующая система выражений:
,
,
,
Где V - матрица собственных векторов для , - матрица собственных векторов для матрицы и - корень матрица собственных чисел матриц и . Матрицы и V являются ортогональнымы
Очевидно, что, если убрать наименьшие значения матрицы и соответствующие колонки\столбцы матриц собственных векторов, можно сократить признаковое пространство и получить новую матрицу более низкой размерности, но способную с высокой точностью восстановить исходную матрицу.
Word2Vec
Данный метод используется в обработке естественного языка, но его также можно использовать для векторного представления последовательности категориальных признаков.
Основная проблема пришла из NLP - есть большой корпус слов, каждое слово является категориальным признаком. Если закодировать слова через dummy encoding, каждое слово станет огромным вектором с одной единицей и количеством нулей, равным размеру корпуса минус один. Практика показывает, что даже небольшие тексты содержат десятки тысяч уникальных слов. В данной задаче вместо последовательности слов фигурирует последовательность больничных отделений в истории пациента.
Рисунок 11. Схема Word2Vec модели на примере SkipGram
Алгоритм Word2Vec позволяет сузить закодировать слова следующем образом - смысл слова можно определить по его контексту, поэтому есть смысл кодировать не само слово, а его контекст. Есть несколько реализации этого алгоритма, но на практике они не сильно различаются между собой, поэтому здесь будет рассмотрен только 1 подход, в котором предсказывается контекст по слову.
В данной модели есть 3 гиперпараметра - длина нового векторного представления V, размер скользящего окна, т.е. ширина контекста N, и количество уникальных слов в корпусе W. Модель представляет собой нейронную сеть с одним скрытым линейным слоем и функцией softmax на последнем слою. Входной слой принимает dummy вектор ключевого слова, а на выходе предсказывается несколько dummy векторов контекстных слов. Скрытый слой имеет заданную размерность и выдает новое векторное представление. Если среди данных правда есть последовательность, то нейросеть сможет пронести через узкий слой всю информацию и предсказать контекст слова, таким образом, можно считать, что слова поддаются кодировке.
Глава 2. Обзор литературы
При анализе литературы не было обнаружено общепринятого подхода для решений подобных задач. Вероятно, это вызвано тем, что постановка задачи машинного обучения во многом зависит от данных. Тем не менее, можно выделить несколько работ, которые помогут определить направление исследования и основные подходы к решению подобных задач. В данной главе будет рассмотрено 5 исследований, которые связаны с темой предсказывания потока пациентов, и описаны те элементы, которые были использованы или опробованы в данной ВКР.
По причинам, которые будут описаны ниже, обзор литературы следует начать со статьи опубликованной в Journal of Biomedical Informatics[1] сотрудниками ИТМО. Эта статья посвящена симуляции пациентского потока с коронарным синдромом. Целью данной работы было сгенерировать образец процесса лечения - путь департаментов клиники, история посещения, выписанные лекарство, длительность лечения и т.д. Образец лечения генерировался по базовой информации о пациенте - возраст, дата обращения, личные особенности, наличие страховки и т.д.
Обзор литературы был начат с этой статьи, т.к. в ней указаны главные проблемы, которые возникают при решении этой задачи:
В каждой медицинском учреждении будет своя архитектура бизнеса и набор медицинских отделения, поэтому построить универсальную модель с привязкой к распределению одной больницы невозможно. Т.к. медицинская история пациента является очень личной информацией, получить достаточное количество данных из множества источников на сегодняшний день довольно тяжело.