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

А. В. Протодьяконов А. В. Дягилева П. А. Пылов







АСИМПТОТИЧЕСКИЙ АНАЛИЗ ПОВЕДЕНИЯ ПРИКЛАДНЫХ МОДЕЛЕЙ МАШИННОГО ОБУЧЕНИЯ

Учебное пособие













Москва Вологда «Инфра-Инженерия» 2023

УДК 004.89
ББК 32.813
     П83







Рецензенты:
д. т. н., профессор, академик РЭА, ведущий научный сотрудник АО «НЦ ВостНИИ» Вадим Васильевич Иванов;
д. т. н., профессор кафедры математики ФГБОУ ВО «Кузбасский государственный технический университет имени Т.Ф.Горбачева» Инна Алексеевна Ермакова






     Протодьяконов, А. В.
П83 Асимптотический анализ поведения прикладных моделей машинного обучения : учебное пособие / А. В. Протодьяконов, А. В. Дягилева, П. А. Пылов. - Москва ; Вологда : Инфра-Инженерия, 2023. - 144 с. : ил., табл.
         ISBN 978-5-9729-1455-5

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

УДК 004.89
ББК 32.813













ISBN 978-5-9729-1455-5

          © Протодьяконов А. В., Дягилева А. В., Пылов П. А., 2023
          © Издательство «Инфра-Инженерия», 2023
                                 © Оформление. Издательство «Инфра-Инженерия», 2023

                ОГЛАВЛЕНИЕ





Предисловие.......................................................5

Глава 1. Математический анализ функциональных моделей машинного обучения................................................6
  1.1. Алгоритм наивного Байесовского классификатора..............6
  1.2. Алгоритм AnyBoost..........................................9
  1.3. Алгоритм шаговой регрессии................................12
  1.4. Алгоритм логистической регрессии..........................17
  1.5. Алгоритм случайного леса..................................20
  1.6. Алгоритм Listbb...........................................20
  1.7. Алгоритм однослойного персептрона.........................22
  1.8. Векторная модель для аналитики текстовых данных...........25
  1.9. Метод парзеновского окна..................................27
  1.10. Метод поиска сходства в текстовых документах на основе замкнутого множества признаков.................................31
  1.11. Метод оптимального прореживания нейронных сетей..........41
  1.12. Метод опорных векторов для линейно разделимой выборки.....44
  1.13. Метод опорных векторов для задачи регрессии..............48
  1.14. Метод стохастического градиента..........................53
  1.15. Метод главных компонент..................................55

Глава 2. Программная реализация асимптотически устойчивых математических моделей машинного обучения........................58
  2.1. Алгоритм наивного Байесовского классификатора.............58
  2.2. Алгоритм AnyBoost.........................................67
  2.3. Алгоритм шаговой регрессии................................71
  2.4. Алгоритм логистической регрессии..........................77
  2.5. Алгоритм случайного леса..................................83

3

  2.6. Алгоритм Listbb...........................................83
  2.7. Алгоритм однослойного персептрона.........................89
  2.8. Векторная модель для аналитики текстовых данных...........94
  2.9. Метод парзеновского окна.................................100
  2.10. Метод поиска сходства в текстовых документах на основе замкнутого множества признаков................................108
  2.11. Метод оптимального прореживания нейронных сетей.........111
  2.12. Метод опорных векторов для линейно разделимой выборки....117
  2.13. Метод опорных векторов для задачи регрессии.............123
  2.14. Метод стохастического градиента.........................130
  2.15. Метод главных компонент.................................134

Библиографический список........................................139

                ПРЕДИСЛОВИЕ





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

5

Глава 1




                МАТЕМАТИЧЕСКИЙ АНАЛИЗ ФУНКЦИОНАЛЬНЫХ МОДЕЛЕЙ МАШИННОГО ОБУЧЕНИЯ




            1.1.      Алгоритм наивного Байесовского классификатора


     В подразделе науки машинного обучения, который посвящен изучению задач классификации, принято разделение между различными типами классификационных методов.
     Такая классификация позволяет сепарировать различные алгоритмы искусственного интеллекта по принципу их принадлежности к математической основе, на которой они построены. Именно математическая основа (и, как следствие, система её ограничений для условий задачи) в конечном счете останавливает выбор исследователя данных на конкретном алгоритме.
     В задачах классификации экстрагируют несколько обособленных классов методов [13]:
       • линейные модели;
       • нелинейные модели, основанные на принципе разделимости;
       • логические классификаторы;
       • статистические классификаторы;
       • метрические классификаторы;
       • композиции.
     Алгоритм классификации наивного Байеса принадлежит к группе статистических методов классификации.
     Принадлежность алгоритма наивного Байеса к этой группе очень легко доказать.
     Возьмём в качестве примера рассмотрения один класс (все его объекты).
     Очевидно, что объекты одного класса будут составлять выборку, так как они являются конечным набором прецедентов, которые были выбраны определенным образом из генеральной совокупности.
     Поскольку объекты одного класса в задаче классификации содержат общую метку целевого столбца, то параметр yi может быть исключен из рассмотрения.

6

     Рассматривая объекты одного класса, у нас не существует каких-либо математических ограничений на то, чтобы восстановить плотность.
     Согласно базовым принципам функции распределения и её первой производной (статистические законы), решая задачу восстановления плотности распределения для каждого класса в отдельности, мы сможем решать и задачу классификации в вероятностных терминах.
     Из краткого доказательства следует, что у классификатора Байеса существует частный случай, позволяющий довольно просто решать прикладные задачи, в которых целевой столбец имеет равные априорные вероятности классов. Априорная вероятность классов - это частотная оценка вероятности классов. То есть, например, априорная вероятность классов будет равна, когда в задаче классификации с общим типом ответов «да» / «нет» будет находиться одинаковое количество ответов «да» и «нет». В таком случае каждый объект X будет отнесен к тому классу, для которого плотность вероятности в точке X будет максимальна. В строгом математическом виде это уравнение можно выразить в виде формулы (1).

        Алгоритм Байеса(А) = arg max р(х |у),             (1)

                                          у е У
где p(x|y) — это совместная плотность распределения непрерывных объектов X и дискретных значений Y.
     Такой частный случай, который между тем является и самым простым типом классификации Байеса, носит особое именование оптимального Байесовского классификатора.
     Однако стоит заметить, что такой классификатор не подходит для несбалансированных априорных вероятностей (целевых классов), которые очень часто встречаются на практике.
     Кроме того, данная математическая реализация классификатора основывается на оценке качества классификации по текущей выборке - а это прямой путь к переобучению модели машинного обучения.
     Наконец, задача оценивания плотности распределения путем минимизации ошибки численным интегрированием гораздо более сложнее, чем стандартная задача классификации:
       1. При решении задачи классификации строится функция, принимающая конечное число значений. При восстановлении плотности процесс состоит уже в работе с непрерывнозначной функцией. Получается, что приходится решать задачу аппроксимации в более богатом классе функций.

7

       2. При решении задачи классификации главная задача состоит в построении границы разделения классов - определении разделяющей плоскости групп.
         При восстановлении плотности распределения классов большое внимание уделяется на точность восстановления повсюду: не только в тех местах, где находятся границы одного класса с другим, но и на периферии.
         Для классификации не нужно, чтобы восстановление плотности внутри определенного класса было таким же хорошим, как на его границе с другими классами, поэтому несколько этапов подхода делается «впустую».
     Основной проблемой в машинном обучении является нахождение границы между классами и правильное построение разделяющей плоскости. По этой причине в прикладной алгоритм наивного Байеса были включены некоторые видоизменения, которые, кроме его математической структуры, внесли свою лепту в его современное название - наивный.
     По какой причине классификатор стали называть наивным? Потому что в его основе лежит предположение: признаки являются независимыми случайными величинами с одномерными плотностями распределения, но зато в каждом классе.
     В таком случае математическая ситуация сводится почти к аналитическому решению (за исключением вероятностной части). Благодаря этому прикладное решение становится очень простым и позволяет перенести оптимальный Байесовский классификатор с предположением независимости в программный вид, свободно¹ реализуемый на многих языках программирования.
     Благодаря предположению открывается и простая возможность оценивания алгоритма: оценки получаются одномерными, а восстанавливать одномерные плотности (для каждого признака в отдельности) - это гораздо более простая задача, нежели восстанавливать многомерные плотности.
     К тому же практически пропадает сложнейшая зависимость от количества признаков в наборе данных (столбцов): теперь их может быть сколь угодно много, разница во временных затратах будет почти незаметной, чего нельзя сказать о геометрически прогрессирующей сложности алгоритма от количества столбцов набора данных в первом случае [2].
     Получить математический вид наивного Байесовского классификатора представляется весьма несложной задачей после факторизации плотности -

¹ Для аппаратной и вычислительной части компьютерной системы.

8

записи произведения одномерных плотностей по каждому признаку в совокупности. После этого, для получения итоговой формулы достаточно прологарифмировать вероятностные выражения по параметру argmax (2).

        Алгоритм Наивного Байеса(Х) =
        = arg max(Zn Af ■ Т³⁽у⁾ + X”-: Zn pj(xj|y)),       (2)

где Zn Aj ■ T³(у) - это константа:
    Zn Aj - это натуральный логарифм штрафа потери на объектах класса у;
    ZnP(y) - это натуральный логарифм априорного распределения.
    Эти величины задаются самим исследователем: значение штрафа задается при реализации решения, а оценку частоты вероятности класса легко получить по самой выборке.
    Zn pj(х] |у) - это сумма натуральных логарифмов одномерных плоскостей по каждому признаку в каждом классе.
      Оценивая два типа алгоритма классификации Байеса, необходимо отметить, что первый тип наиболее часто используется в средствах математической статистики и при решении аналитических задач математики. Это объясняется тем, что априорные распределения классов и их функции правдоподобия чаще всего известны, поэтому можно определить математическое ожидание потерь, чтобы в дальнейшем его проинтегрировать.
      На практике всегда используется алгоритм наивного Байесовского классификатора. Так получается, потому что совместная плотность X и Y неизвестна, то есть невозможно аналитически определить функции правдоподобия классов. В связи с этим, нет никакого доступа к численному решению, тем более в программном виде [3], где многие величины должны быть представлены дискретно.
      Благодаря математическим концепциям и законам, стало возможным перенести «наивное» утверждение в формализованный вид уравнения, создав тем самым новую, особо значимую для прикладной реализации, модель машинного обучения.



            1.2. Алгоритм AnyBoost


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


9

     Возникший в канун нового тысячелетия (алгоритм начал формироваться в 1995 году и лишь к началу 2000 года был полностью формализован математическим языком) [4].
     Фундаментальная концепция AnyBoost состоит в обобщение функции потерь, но при этом утверждает, что функция потерь в данном методе - это некая произвольная, гладкая, убывающая функция от отступа данных (1).
£(Ь,у) = £(-by), bₜ е R.                  (1)
     До появления алгоритма машинного обучения AnyBoost исследователи данных применяли различные способы для аппроксимации пороговой функции потерь (рисунок 1).


Рисунок 1. Аппроксимирующие функции при значении M < 0

     В большинстве случаев этими функциями выступали (рисунок 1):
       •  E (обозначена желтым) - экспоненциальная;
       •  L (обозначена фиолетовым) - логарифмическая;
       •  V (обозначена синим) - кусочно-линейная;
       •  G (обозначена голубым) - гауссовская (функция «купола» или нормального распределения данных);
       •  S (обозначена зеленым) - сигмоидная;
       •  Q (обозначена красно-коричневым) - квадратичная.
     Такое многообразие функций отнюдь не означает их универсальность. Скорее наоборот, эти функции стали плодом «легкого» научного труда, так как написание нового алгоритма сводилось к изменению базисной функции (функции потерь), лежащей в его основе.
     Изменение функций потерь могло продолжаться достаточно долго, но именно появление AnyBoost ознаменовало прекращение попыток модификации этих функций.


10

     Почему так произошло? Ответ кроется в аналитике области графика (рисунок 1): многообразие функций потерь несло в себе задачу максимального обобщения всех важных взаимосвязей в данных. И это получалось достаточно слабо при использовании какой-то определенной функции потерь. Перебор всех функций не мог коренным образом изменить ситуацию с улучшением обобщающей способности [5], что и было доказано временным отсутствием модели AnyBoost.
     Главное изменение математической архитектуры, которое несет в себе AnyBoost состоит в использовании ансамбля моделей. То есть итоговая точность формируется как «голосование» совокупности отдельных моделей в составе одной общей. На первый взгляд может показаться, что несколько слабых моделей не могут эффективно решить поставленную задачу даже в том случае, если модели будут объединены в одну структурную связь.
     Попытка реализации этой идеологии (объединения слабых моделей для итогового общего голосования) на практике явила неожиданный результат [3, 6]. Модель AnyBoost функционировала лучше, чем много оптимизированные, но обособленные слабые модели машинного обучения [4].
     Кроме того, математическая основа реализованной модели получилась обобщенной, то есть она довольно просто обобщалась до отдельных частных случаев обособленных алгоритмов.
     Рассмотрим, например, в понятиях формализованного математического языка обобщение алгоритма до обобщенного бустинга с произвольной функцией потерь. Доказав это, мы докажем возможность обобщения AnyBoost до любого частного случая независимого обособленного алгоритма машинного обучения.
     Запишем математическое уравнение задачи (2):

        ELi£(yiSy=iatbₜ(x,)) = E/=i^(Mᵣ_₁(xf) + ytaTbT (х,)).    (2)

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

11

смысла обобщающей способности алгоритма [3, 7-9], то мы отбрасываем их из уравнения разложения функции (2) в ряд Тейлора.
      Аппроксимировано, разложение представляется в виде формулы (3).
    у (Алгоритм) ~'Llᵢ₌i£{MT_i⁽xᵢ)')- aT’Zlᵢ₌₁-£'^MT_₁(xᵢ)')yᵢbT⁽xₜ⁾. (3)
      В уравнении (3) множитель —£' (M-ᵣ_₁(xᵢ)) является весовым множителем объектов Xi.
      После применения метода явной максимизации отступов [3, 4, 10] к уравнению (3), параметр aT будет определяться методом одномерной минимизации функционала математического алгоритма, лежащего в основе Апу-Boost (3).
      Это означает, что при выполнении математических условий ограничения (4) функции алгоритма AnyBoost (3), алгоритм AnyBoost переходит в частный случай машинного обучения - алгоритм адаптивного бустинга [11, 12].

        bₜ: Х^ {-1,+1} && £(M) = е⁻м.                    (4)

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



            1.3. Алгоритм шаговой регрессии


     Шаговая регрессия - это один из представителей семейства алгоритмов жадного добавления [1].
     Также от всего семейства алгоритмов полного перебора шаговая регрессия выгодно отличается тем, что её применимость не является узкой. Например, когда в наборе данных количество признаков будет достигать 1000 (а оптимальным в алгоритмах полного перебора состав признаков равен —100), то модели полного перебора будут очень долго проходить обучение, вне зависимости от типа предоставленного им аппаратного обеспечения и вычислительных мощностей [2].
     Неэффективность алгоритмов полного перебора вынудила искать новую эвристику для создания иной концептуальной модели машинного обучения. Первоначальной целью шаговой регрессии в формализованном математическом языке была идея поиска оптимума параметров обобщающей функции

12