Участник:Дарья Соболева

Дарья Соболева: Многоклассовая логистическая регрессия

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Логистическая регрессия (Logistic regression) -- метод построения линейного классификатора, позволяющий оценивать апостериорные вероятности принадлежности объектов классам. Многоклассовая логистическая регрессия (Multiclass Logistic regression) -- логистическая регрессия, реализованная по схеме один против всех (one-vs-rest). При таком подходе строится столько моделей логистической регрессии, сколько классов необходимо обучить.

На вход алгоритму логистической регрессии подается матрица обЪектов-признаков [math]X[/math] и вектор допустимых ответов [math]Y[/math]. Предполагается, что существует целевая функция [math]y∗ : X → Y[/math]. Задача логистической регрессии как метода машинного обучения заключается в том, чтобы по выборке [math]X[/math] построить решающую функцию [math]a: X → Y[/math], которая приближала бы целевую функцию [math]y∗[/math].

Многоклассовая логистическая регрессия вместо вектора допустимых ответов [math]Y[/math] принимает список из векторов ответов для каждой задачи классификаци. Далее для каждого класса строится решающая функция.

1.2 Математическое описание алгоритма

Вход: обучающая выборка пар «объект, ответ» [math]X^l = \{(x_1,y_1),\dots,(x_l,y_l)\}[/math].

Случай двух классов

Положим [math]Y=\{-1,+1\}[/math]. Строится линейный алгоритм классификации [math]a: X\to Y[/math] вида [math]a(x,w) = \mathrm{sign}\left( \sum_{j=1}^D w_j f_j(x) + w_0 \right) = \mathrm{sign}\langle x,w \rangle[/math], где [math]w_j[/math] — вес [math]j[/math]-го признака, [math]w_0[/math] — порог принятия решения, [math]w=(w_0,w_1,\ldots,w_D)[/math] — вектор весов, [math]\langle x,w \rangle [/math]— скалярное произведение признакового описания объекта на вектор весов. Предполагается, что искусственно введён «константный» нулевой признак: [math]f_{0}(x)=1[/math]. Задача обучения линейного классификатора заключается в том, чтобы по выборке [math]X^l[/math] настроить вектор весов [math]w[/math]. В логистической регрессии для этого решается задача минимизации эмпирического риска с функцией потерь специального вида: [math]Q(w) = \sum_{i=1}^L \ln\left( 1 + \exp( -y_i \langle x_i,w \rangle ) \right) \to \min_{w}[/math]. После того, как решение [math]w[/math] найдено, становится возможным не только вычислять классификацию [math]a(x) = \mathrm{sign}\langle x,w \rangle[/math] для произвольного объекта [math]x[/math], но и оценивать апостериорные вероятности его принадлежности классам: [math]\mathbb{P}\{y|x\} = \sigma\left( y \langle x,w \rangle\right),\;\;y\in Y[/math], где [math]\sigma(z) = \frac1{1+e^{-z}}[/math] — сигмоидная функция.

Рассматриваемый в данной статье one-vs-rest подход позволяет легко свести задачу многоклассовой классификации к двум классам, так как предполагает построение двухклассовой логистической регрессии для каждого класса в отдельности. Метки [math]+1[/math] проставляются всем обЪектам рассматриваемого класса, а [math]-1[/math] проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

1.3 Вычислительное ядро алгоритма

Вычислительное ядро многоклассовой логистической регрессии можно представить как [math]M[/math] независимых задач логистической регрессии, где [math]M[/math] -- число классов. Затем вычисление метки класса с максимальной вероятностью по выходам каждой логистической регрессии.

1.4 Макроструктура алгоритма

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

1.5 Схема реализации последовательного алгоритма

Формулы метода описаны выше. Последовательность исполнения может быть разная. Иными словами, совершенно неважно, в каком порядке будут вычисляться вероятности для каждого класса. Схемы one-vs-rest осуществляют построение M независимых классификаторов.

1.6 Последовательная сложность алгоритма

Обучение логистической регрессии в последовательном варианте имеет сложность [math] M * N * D * N_{iter} [/math], где [math]N_{iter}[/math] -- число итераций обучения алгоритма.

1.7 Информационный граф

На рисунке 1 изображён граф алгоритма для случая [math]M = 3, N = 6[/math].

1.8 Ресурс параллелизма алгоритма

Для алгоритма многоклассовой логистической регрессии требуется для каждого объекта ([math]N[/math] объектов) вычислить предсказания [math]M[/math] двухклассовых классификаторов ([math]M[/math] ветвей длины [math]1[/math]). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем для каждого объекта вычисляется метка класса с наибольшей вероятностью.

1.9 Входные и выходные данные алгоритма

Входные данные: обучающая выборка пар «объект, ответ» [math]X^l = \{(x_1,y_1),\dots,(x_l,y_l)\}[/math].

Дополнительные ограничения: отсутствуют.

Объём входных данных: N * D.

Выходные данные: Предсказания модели для каждого объекта.

Объём выходных данных: N.

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

Для запуска прямой и параллельной версии алгоритма многоклассовой логистической регрессии был сгенерирован синтетический датасет, состоящий из [math]1000[/math] ([math]N = 1000[/math]) объектов с [math]500[/math] признаками ([math]D = 500 [/math]). Как видно на рисунке 2 параллельная версия показывает константное время работы от числа классов. В то время как последовательная версия уже линейно зависит от числа классов. Результаты были получены усреднением по [math]50[/math] запускам.

2.7 Существующие реализации алгоритма

Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn -- Sklearn. Библиотека является открытой и достаточно популярной. Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- PySpark. Код этой реализации также является открытым и активно используемым в задачах Big Data.

3 Литература

Машинное обучение (курс лекций, К.В.Воронцов)