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

Материал из Алговики
Перейти к навигации Перейти к поиску

Многоклассовая логистическая регрессия

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 Схема реализации последовательного алгоритма

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

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

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

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

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

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

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

3 Литература

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