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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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