Расслабленный алгоритм, основанный на марже

Расслабленный алгоритм с учетом маржи (MIRA) ^[1] — это алгоритм машинного обучения , онлайн-алгоритм для решения многоклассовой классификации задач . Он предназначен для изучения набора параметров (векторных или матричных) путем обработки всех заданных обучающих примеров поочередно и обновления параметров согласно каждому обучающему примеру, чтобы текущий обучающий пример классифицировался правильно с запасом на неверные. классификации, по крайней мере, такого же размера, как и их потери. ^[2] Изменение параметров сводится к минимуму.

Двухклассовая версия под названием бинарная MIRA. ^[1] упрощает алгоритм, не требуя решения задачи квадратичного программирования (см. ниже). При использовании в конфигурации «один против всех» двоичная MIRA может быть расширена до многоклассового обучающегося, что приближается к полной MIRA, но может быть быстрее в обучении.

Ход алгоритма ^[3]^[4] выглядит следующим образом:

Algorithm MIRA
  Input: Training examples  $T=\{x_{i},y_{i}\}$ 
  Output: Set of parameters  $w$

   $i$  ← 0,  $w^{(0)}$  ← 0
  for  $n$  ← 1 to  $N$ 
    for  $t$  ← 1 to  $|T|$ 
       $w^{(i+1)}$  ← update  $w^{(i)}$  according to  $\{x_{t},y_{t}\}$ 
       $i$  ←  $i+1$ 
    end for
  end for
  return  ${\frac {\sum _{j=1}^{N\times |T|}w^{(j)}}{N\times |T|}}$

« ←» означает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого изменяется на значение элемента .
« return » завершает алгоритм и выводит следующее значение.

Затем шаг обновления формализуется как квадратичное программирование. ^[2] задача: Найти $min\|w^{(i+1)}-w^{(i)}\|$ , так что $score(x_{t},y_{t})-score(x_{t},y')\geq L(y_{t},y')\ \forall y'$ , т.е. оценка текущего правильного обучения $y$ должно быть больше, чем оценка любого другого возможного $y'$ хотя бы потерей (количеством ошибок) того $y'$ по сравнению с $y$ .

Ссылки

^ Jump up to: ^а ^б Краммер, Коби; Певец Йорам (2003). «Ультраконсервативные онлайн-алгоритмы для решения многоклассовых задач» . Журнал исследований машинного обучения . 3 : 951–991.
^ Jump up to: ^а ^б Макдональд, Райан; Краммер, Коби; Перейра, Фернандо (2005). «Онлайн-обучение анализаторов зависимостей с большой прибылью» (PDF) . Материалы 43-го ежегодного собрания ACL . Ассоциация компьютерной лингвистики . стр. 91–98.
^ Ватанабэ, Т. и др. (2007): «Онлайн-обучение с большой маржой для статистического машинного перевода». В: Материалы совместной конференции 2007 г. по эмпирическим методам обработки естественного языка и вычислительному изучению естественного языка , 764–773.
^ Бонет, Б. (2009): Эффективный анализ структур синтаксической и семантической зависимости . Материалы конференции по изучению естественного языка (CoNLL), Боулдер, 67–72.

Внешние ссылки

adMIRAble — реализация MIRA на C++.
Miralium – реализация MIRA на Java
Реализация MIRA для Mahout в Hadoop

[crammer-singer2003-1] Jump up to: ^а ^б Краммер, Коби; Певец Йорам (2003). «Ультраконсервативные онлайн-алгоритмы для решения многоклассовых задач» . Журнал исследований машинного обучения . 3 : 951–991.

[mcdonald-etal2005-2] Jump up to: ^а ^б Макдональд, Райан; Краммер, Коби; Перейра, Фернандо (2005). «Онлайн-обучение анализаторов зависимостей с большой прибылью» (PDF) . Материалы 43-го ежегодного собрания ACL . Ассоциация компьютерной лингвистики . стр. 91–98.

[3] Ватанабэ, Т. и др. (2007): «Онлайн-обучение с большой маржой для статистического машинного перевода». В: Материалы совместной конференции 2007 г. по эмпирическим методам обработки естественного языка и вычислительному изучению естественного языка , 764–773.

[4] Бонет, Б. (2009): Эффективный анализ структур синтаксической и семантической зависимости . Материалы конференции по изучению естественного языка (CoNLL), Боулдер, 67–72.

[1]

[2]

[3]

[4]