Расслабленный алгоритм с учетом маржи
Алгоритм машинного обучения

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

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

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

Алгоритм MIRA Вход: Примеры обучения Выход: Набор параметров    Т = {  х  я   ,  у  я   }   {\displaystyle T=\{x_{i},y_{i}\}}      ж   {\displaystyle w} 
     я   {\displaystyle я} ← 0, ← 0 для ← 1 для для ← 1 для ← обновить в соответствии с ← конец для конец для возврата     ж  ( 0 )     {\displaystyle w^{(0)}}      н   {\displaystyle n}      Н   {\displaystyle N}       т   {\displaystyle т}       |  Т  |    {\displaystyle |Т|}       ж  ( я + 1 )     {\displaystyle w^{(i+1)}}      ж  ( я )     {\displaystyle w^{(я)}}     {  х  т   ,  у  т   }   {\displaystyle \{x_{t},y_{t}\}}      я   {\displaystyle я}     я + 1   {\displaystyle я+1}             ∑  дж = 1   Н ×  |  Т  |     ж  ( дж )     Н ×  |  Т  |       {\displaystyle {\frac {\sum _{j=1}^{N\times |T|}w^{(j)}}{N\times |T|}}}
  • "←" обозначает назначение . Например, " largest ← item " означает, что значение largest изменяется на значение item .
  • « return » завершает алгоритм и выводит следующее значение.

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

Ссылки

  1. ^ ab Crammer, Koby; Singer, Yoram (2003). «Ультраконсервативные онлайн-алгоритмы для многоклассовых задач». Журнал исследований машинного обучения . 3 : 951–991 .
  2. ^ ab Макдональд, Райан; Краммер, Коби; Перейра, Фернандо (2005). "Онлайн-обучение анализаторов зависимостей с большим запасом" (PDF) . Труды 43-го ежегодного собрания ACL . Ассоциация компьютерной лингвистики . С.  91–98 .
  3. ^ Ватанабэ, Т. и др. (2007): «Онлайн-обучение с большим объемом данных для статистического машинного перевода». В: Труды Объединенной конференции 2007 года по эмпирическим методам обработки естественного языка и компьютерному обучению естественному языку , 764–773.
  4. ^ Bohnet, B. (2009): Эффективный анализ структур синтаксической и семантической зависимости . Труды конференции по изучению естественного языка (CoNLL), Боулдер, 67–72.
  • adMIRAble – реализация MIRA на C++
  • Miralium – реализация MIRA на Java
  • Реализация MIRA для Mahout в Hadoop
Взято с "https://en.wikipedia.org/w/index.php?title=Расслабленный_алгоритм_с_наполненной_маржей&oldid=1232393850"