Алговики - Вклад [ru]

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

2017-12-04T19:41:48Z

Дарья Соболева: /* Масштабируемость алгоритма и его реализации */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром многоклассовой логистической регрессии является число классов (параметр <math>M</math>). Когда многоклассовая логистическая регрессия становится по сложности константой относительно количества классов, возникает уникальная возможность построения большого количества классификаторов одновременно.

=== Макроструктура алгоритма ===
Алгоритм многоклассовой логистической регрессии состоит в проведении следующих макроопераций:

* Для каждого объекта вычисление предсказаний (вероятностей наличия метки) для каждого класса <math>M</math>
* Среди всех классов <math>M</math> выбор того класса, вероятность которого оказалась максимальной

=== Схема реализации последовательного алгоритма ===
Формулы метода описаны выше. В последовательной реализации алгоритма сначала производится загрузка обучающей выборки. Далее создается массив весов при признаках модели, который инициализируются нулями. Затем для каждого класса производится обучение массива весов. Процесс обучения является итерационным. На каждой итерации для каждого объекта вычисляется предсказание модели. Затем вычисляется антиградиент минимизируемого функционала <math>Q(w)</math> и производится сдвиг вектора весов на антиградиент, умноженный на скорость обучения. Число итераций и скорость обучения подбираются на основании обучающей выборки и сходимость модели. Я зафиксировала скорость обучения, равной <math>0.001</math>, а количество итераций, равным <math>10000</math>. Это позволило мне получать точные и стабильные решения.

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

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

На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>. Синие вершины соответствуют объектам из обучающей выборки (<math>N</math> объектов). Зеленые вершины соответствуют двухклассовым классификаторам (<math>M</math> ветвей длины <math>1</math>). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем в розовых вершинах для каждого объекта вычисляется метка класса с наибольшей вероятностью. Итоговое предсказание заносится в желтую вершину.

{|align="center"
|-valign="top"
|[[File:Информаицонный граф 3.001.jpeg|мини|1000px|Рисунок 1. Схема работы параллельной логистической регрессии.]]
|}

=== Ресурс параллелизма алгоритма ===
Для алгоритма многоклассовой логистической регрессии в параллельном варианте требуется выполнить <math>N * D * N_{iter}</math> шагов. <math>N_{iter}</math> -- число итераций. Таким образом алгоритм является константным по количеству классов.

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time big.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]
[[File:Time small.png | Рисунок 3. Параллельная реализация многоклассовой логистической регрессии (увеличенная параллельная реализация)]]

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

Все запуски производились на суперкомпьютере <<Ломоносов>>. В расчетах использовался процессор Intel Xeon X5570 с частотой <math>2.93</math> GHz, кэшем <math>8192</math> KB и <math>4</math> ядрами. Эксперименты производились в очереди test, в которой доступно <math>16</math> таких процессоров. Максимальное количество доступных мне ядер в очереди test составляло <math>16 * 6 = 64</math>. В моих экспериментах число ядер было равно числу классов (<math>M</math>).

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-12-04T18:55:06Z

Дарья Соболева: /* Вычислительное ядро алгоритма */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

=== Вычислительное ядро алгоритма ===
Вычислительным ядром многоклассовой логистической регрессии является число классов (параметр <math>M</math>). Когда многоклассовая логистическая регрессия становится по сложности константой относительно количества классов, возникает уникальная возможность построения большого количества классификаторов одновременно.

=== Макроструктура алгоритма ===
Алгоритм многоклассовой логистической регрессии состоит в проведении следующих макроопераций:

* Для каждого объекта вычисление предсказаний (вероятностей наличия метки) для каждого класса <math>M</math>
* Среди всех классов <math>M</math> выбор того класса, вероятность которого оказалась максимальной

=== Схема реализации последовательного алгоритма ===
Формулы метода описаны выше. В последовательной реализации алгоритма сначала производится загрузка обучающей выборки. Далее создается массив весов при признаках модели, который инициализируются нулями. Затем для каждого класса производится обучение массива весов. Процесс обучения является итерационным. На каждой итерации для каждого объекта вычисляется предсказание модели. Затем вычисляется антиградиент минимизируемого функционала <math>Q(w)</math> и производится сдвиг вектора весов на антиградиент, умноженный на скорость обучения. Число итераций и скорость обучения подбираются на основании обучающей выборки и сходимость модели. Я зафиксировала скорость обучения, равной <math>0.001</math>, а количество итераций, равным <math>10000</math>. Это позволило мне получать точные и стабильные решения.

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

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

На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>. Синие вершины соответствуют объектам из обучающей выборки (<math>N</math> объектов). Зеленые вершины соответствуют двухклассовым классификаторам (<math>M</math> ветвей длины <math>1</math>). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем в розовых вершинах для каждого объекта вычисляется метка класса с наибольшей вероятностью. Итоговое предсказание заносится в желтую вершину.

{|align="center"
|-valign="top"
|[[File:Информаицонный граф 3.001.jpeg|мини|1000px|Рисунок 1. Схема работы параллельной логистической регрессии.]]
|}

=== Ресурс параллелизма алгоритма ===
Для алгоритма многоклассовой логистической регрессии в параллельном варианте требуется выполнить <math>N * D * N_{iter}</math> шагов. <math>N_{iter}</math> -- число итераций. Таким образом алгоритм является константным по количеству классов.

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

Все запуски производились на суперкомпьютере <<Ломоносов>>. В расчетах использовался процессор Intel Xeon X5570 с частотой <math>2.93</math> GHz, кэшем <math>8192</math> KB и <math>4</math> ядрами. Эксперименты производились в очереди test, в которой доступно <math>16</math> таких процессоров. Максимальное количество доступных мне ядер в очереди test составляло <math>16 * 6 = 64</math>. В моих экспериментах число ядер было равно числу классов (<math>M</math>).

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-12-04T18:50:00Z

Дарья Соболева: /* Макроструктура алгоритма */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

=== Макроструктура алгоритма ===
Алгоритм многоклассовой логистической регрессии состоит в проведении следующих макроопераций:

* Для каждого объекта вычисление предсказаний (вероятностей наличия метки) для каждого класса <math>M</math>
* Среди всех классов <math>M</math> выбор того класса, вероятность которого оказалась максимальной

=== Схема реализации последовательного алгоритма ===
Формулы метода описаны выше. В последовательной реализации алгоритма сначала производится загрузка обучающей выборки. Далее создается массив весов при признаках модели, который инициализируются нулями. Затем для каждого класса производится обучение массива весов. Процесс обучения является итерационным. На каждой итерации для каждого объекта вычисляется предсказание модели. Затем вычисляется антиградиент минимизируемого функционала <math>Q(w)</math> и производится сдвиг вектора весов на антиградиент, умноженный на скорость обучения. Число итераций и скорость обучения подбираются на основании обучающей выборки и сходимость модели. Я зафиксировала скорость обучения, равной <math>0.001</math>, а количество итераций, равным <math>10000</math>. Это позволило мне получать точные и стабильные решения.

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

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

На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>. Синие вершины соответствуют объектам из обучающей выборки (<math>N</math> объектов). Зеленые вершины соответствуют двухклассовым классификаторам (<math>M</math> ветвей длины <math>1</math>). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем в розовых вершинах для каждого объекта вычисляется метка класса с наибольшей вероятностью. Итоговое предсказание заносится в желтую вершину.

{|align="center"
|-valign="top"
|[[File:Информаицонный граф 3.001.jpeg|мини|1000px|Рисунок 1. Схема работы параллельной логистической регрессии.]]
|}

=== Ресурс параллелизма алгоритма ===
Для алгоритма многоклассовой логистической регрессии в параллельном варианте требуется выполнить <math>N * D * N_{iter}</math> шагов. <math>N_{iter}</math> -- число итераций. Таким образом алгоритм является константным по количеству классов.

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

Все запуски производились на суперкомпьютере <<Ломоносов>>. В расчетах использовался процессор Intel Xeon X5570 с частотой <math>2.93</math> GHz, кэшем <math>8192</math> KB и <math>4</math> ядрами. Эксперименты производились в очереди test, в которой доступно <math>16</math> таких процессоров. Максимальное количество доступных мне ядер в очереди test составляло <math>16 * 6 = 64</math>. В моих экспериментах число ядер было равно числу классов (<math>M</math>).

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-12-04T18:41:52Z

Дарья Соболева: /* Масштабируемость алгоритма и его реализации */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

=== Схема реализации последовательного алгоритма ===
Формулы метода описаны выше. В последовательной реализации алгоритма сначала производится загрузка обучающей выборки. Далее создается массив весов при признаках модели, который инициализируются нулями. Затем для каждого класса производится обучение массива весов. Процесс обучения является итерационным. На каждой итерации для каждого объекта вычисляется предсказание модели. Затем вычисляется антиградиент минимизируемого функционала <math>Q(w)</math> и производится сдвиг вектора весов на антиградиент, умноженный на скорость обучения. Число итераций и скорость обучения подбираются на основании обучающей выборки и сходимость модели. Я зафиксировала скорость обучения, равной <math>0.001</math>, а количество итераций, равным <math>10000</math>. Это позволило мне получать точные и стабильные решения.

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

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

На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>. Синие вершины соответствуют объектам из обучающей выборки (<math>N</math> объектов). Зеленые вершины соответствуют двухклассовым классификаторам (<math>M</math> ветвей длины <math>1</math>). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем в розовых вершинах для каждого объекта вычисляется метка класса с наибольшей вероятностью. Итоговое предсказание заносится в желтую вершину.

{|align="center"
|-valign="top"
|[[File:Информаицонный граф 3.001.jpeg|мини|1000px|Рисунок 1. Схема работы параллельной логистической регрессии.]]
|}

=== Ресурс параллелизма алгоритма ===
Для алгоритма многоклассовой логистической регрессии в параллельном варианте требуется выполнить <math>N * D * N_{iter}</math> шагов. <math>N_{iter}</math> -- число итераций. Таким образом алгоритм является константным по количеству классов.

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

Все запуски производились на суперкомпьютере <<Ломоносов>>. В расчетах использовался процессор Intel Xeon X5570 с частотой <math>2.93</math> GHz, кэшем <math>8192</math> KB и <math>4</math> ядрами. Эксперименты производились в очереди test, в которой доступно <math>16</math> таких процессоров. Максимальное количество доступных мне ядер в очереди test составляло <math>16 * 6 = 64</math>. В моих экспериментах число ядер было равно числу классов (<math>M</math>).

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-12-04T17:31:55Z

Дарья Соболева: /* Ресурс параллелизма алгоритма */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

=== Схема реализации последовательного алгоритма ===
Формулы метода описаны выше. В последовательной реализации алгоритма сначала производится загрузка обучающей выборки. Далее создается массив весов при признаках модели, который инициализируются нулями. Затем для каждого класса производится обучение массива весов. Процесс обучения является итерационным. На каждой итерации для каждого объекта вычисляется предсказание модели. Затем вычисляется антиградиент минимизируемого функционала <math>Q(w)</math> и производится сдвиг вектора весов на антиградиент, умноженный на скорость обучения. Число итераций и скорость обучения подбираются на основании обучающей выборки и сходимость модели. Я зафиксировала скорость обучения, равной <math>0.001</math>, а количество итераций, равным <math>10000</math>. Это позволило мне получать точные и стабильные решения.

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

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

На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>. Синие вершины соответствуют объектам из обучающей выборки (<math>N</math> объектов). Зеленые вершины соответствуют двухклассовым классификаторам (<math>M</math> ветвей длины <math>1</math>). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем в розовых вершинах для каждого объекта вычисляется метка класса с наибольшей вероятностью. Итоговое предсказание заносится в желтую вершину.

{|align="center"
|-valign="top"
|[[File:Информаицонный граф 3.001.jpeg|мини|1000px|Рисунок 1. Схема работы параллельной логистической регрессии.]]
|}

=== Ресурс параллелизма алгоритма ===
Для алгоритма многоклассовой логистической регрессии в параллельном варианте требуется выполнить <math>N * D * N_{iter}</math> шагов. <math>N_{iter}</math> -- число итераций. Таким образом алгоритм является константным по количеству классов.

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-12-04T17:24:38Z

Дарья Соболева: /* Информационный граф */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

=== Схема реализации последовательного алгоритма ===
Формулы метода описаны выше. В последовательной реализации алгоритма сначала производится загрузка обучающей выборки. Далее создается массив весов при признаках модели, который инициализируются нулями. Затем для каждого класса производится обучение массива весов. Процесс обучения является итерационным. На каждой итерации для каждого объекта вычисляется предсказание модели. Затем вычисляется антиградиент минимизируемого функционала <math>Q(w)</math> и производится сдвиг вектора весов на антиградиент, умноженный на скорость обучения. Число итераций и скорость обучения подбираются на основании обучающей выборки и сходимость модели. Я зафиксировала скорость обучения, равной <math>0.001</math>, а количество итераций, равным <math>10000</math>. Это позволило мне получать точные и стабильные решения.

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

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

На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>. Синие вершины соответствуют объектам из обучающей выборки (<math>N</math> объектов). Зеленые вершины соответствуют двухклассовым классификаторам (<math>M</math> ветвей длины <math>1</math>). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем в розовых вершинах для каждого объекта вычисляется метка класса с наибольшей вероятностью. Итоговое предсказание заносится в желтую вершину.

{|align="center"
|-valign="top"
|[[File:Информаицонный граф 3.001.jpeg|мини|1000px|Рисунок 1. Схема работы параллельной логистической регрессии.]]
|}

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-12-04T16:25:52Z

Дарья Соболева: /* Схема реализации последовательного алгоритма */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

=== Схема реализации последовательного алгоритма ===
Формулы метода описаны выше. В последовательной реализации алгоритма сначала производится загрузка обучающей выборки. Далее создается массив весов при признаках модели, который инициализируются нулями. Затем для каждого класса производится обучение массива весов. Процесс обучения является итерационным. На каждой итерации для каждого объекта вычисляется предсказание модели. Затем вычисляется антиградиент минимизируемого функционала <math>Q(w)</math> и производится сдвиг вектора весов на антиградиент, умноженный на скорость обучения. Число итераций и скорость обучения подбираются на основании обучающей выборки и сходимость модели. Я зафиксировала скорость обучения, равной <math>0.001</math>, а количество итераций, равным <math>10000</math>. Это позволило мне получать точные и стабильные решения.

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T21:04:38Z

Дарья Соболева: /* Масштабируемость алгоритма и его реализации */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T21:04:24Z

Дарья Соболева: /* Масштабируемость алгоритма и его реализации */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T20:53:17Z

Дарья Соболева: /* Ресурс параллелизма алгоритма */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T20:43:11Z

Дарья Соболева:

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T20:19:45Z

Дарья Соболева:

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png | Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T20:12:38Z

Дарья Соболева: /* Масштабируемость алгоритма и его реализации */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===
[[File:Time.png] Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T16:32:42Z

Дарья Соболева: /* Ресурс параллелизма алгоритма */

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-11-19T13:35:48Z

Дарья Соболева:

'''[[Дарья Соболева: Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

=== Информационный граф ===
На рисунке 1 изображён граф алгоритма для случая <math>M = 3, N = 6</math>.
[[File:Информаицонный граф 3.001.jpeg|1000 px|Рисунок 1. Схема работы параллельной логистической регрессии.]]

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

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

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

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

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

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

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

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

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

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===
Существует масса различных реализаций логистической регрессии на языке python. Приведу пример параллельной реализация из библиотеки sklearn --
[http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LogisticRegression.html Sklearn]. Библиотека является открытой и достаточно популярной.
Также стоит отметить реализацию параллельной логистической регрессии на программном каркасе PySpark -- [https://spark.apache.org/docs/2.2.0/ml-classification-regression.html PySpark]. Код этой реализации также является открытым и активно используемым в задачах Big Data.

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-10-30T12:27:06Z

Дарья Соболева:

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

2017-10-24T12:14:07Z

Дарья Соболева: /* Общее описание алгоритма */

'''[[Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

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

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

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

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

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

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

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

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

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

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]

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

2017-10-21T20:05:07Z

Дарья Соболева:

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

2017-10-21T19:55:35Z

Дарья Соболева: Новая страница: «'''Многоклассовая логистическая регрессия''' == Свойства и структура алгоритма == === Обще…»

'''[[Многоклассовая логистическая регрессия]]'''
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
'''Логистическая регрессия (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> принимает список из векторов ответов для каждой задачи классификаци.
Далее для каждого класса строится решающая функция.

=== Математическое описание алгоритма ===
Вход: обучающая выборка пар «объект, ответ» <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> проставляются обЪектам всех остальных классов. Для тестового объекта вычисляются предсказания всех обученных классификаторов, в качестве предсказания берется класс, с максимальной вероятностью.

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

== Литература ==
[http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_(курс_лекций%2C_К.В.Воронцов) Машинное обучение (курс лекций, К.В.Воронцов)]