Участник:Дарья Соболева - История изменений

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

2017-12-04T19:41:48Z

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

← Предыдущая версия		Версия от 19:41, 4 декабря 2017
Строка 79:		Строка 79:

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

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

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

2017-12-04T18:55:06Z

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

← Предыдущая версия		Версия от 18:55, 4 декабря 2017
Строка 30:		Строка 30:

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

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

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

2017-12-04T18:50:00Z

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

← Предыдущая версия		Версия от 18:50, 4 декабря 2017
Строка 33:		Строка 33:

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

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

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

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

2017-12-04T18:41:52Z

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

← Предыдущая версия		Версия от 18:41, 4 декабря 2017
Строка 78:		Строка 78:
	[[File:Time.png \| Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]		[[File:Time.png \| Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

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

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

2017-12-04T17:31:55Z

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

← Предыдущая версия		Версия от 17:31, 4 декабря 2017
Строка 51:		Строка 51:

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

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

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

2017-12-04T17:24:38Z

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

← Предыдущая версия		Версия от 17:24, 4 декабря 2017
Строка 42:		Строка 42:

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

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

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

2017-12-04T16:25:52Z

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

← Предыдущая версия		Версия от 16:25, 4 декабря 2017
Строка 36:		Строка 36:

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

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

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

2017-11-19T21:04:38Z

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

← Предыдущая версия		Версия от 21:04, 19 ноября 2017
Строка 75:		Строка 75:
	[[File:Time.png \| Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]		[[File:Time.png \| Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

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

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

2017-11-19T21:04:24Z

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

← Предыдущая версия		Версия от 21:04, 19 ноября 2017
Строка 75:		Строка 75:
	[[File:Time.png \| Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]		[[File:Time.png \| Рисунок 2. Параллельная реализация многоклассовой логистической регрессии]]

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

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

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

2017-11-19T20:53:17Z

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

← Предыдущая версия		Версия от 20:53, 19 ноября 2017
Строка 48:		Строка 48:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Для алгоритма многоклассовой логистической регрессии требуется для каждого объекта (<math>N</math> объектов) вычислить предсказания <math>M</math> двухклассовых классификаторов (<math>M</math>		Для алгоритма многоклассовой логистической регрессии требуется для каждого объекта (<math>N</math> объектов) вычислить предсказания <math>M</math> двухклассовых классификаторов (<math>M</math>
	ветвей длины <math>1</math>). Затем для каждого объекта вычисляется метка класса с наибольшей вероятностью.		ветвей длины <math>1</math>). Таким образом каждая логистическая регрессия строится независимо в отдельной ветви. Затем для каждого объекта вычисляется метка класса с наибольшей вероятностью.

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