Обучение дополненному алгоритму

Алгоритм с расширенным обучением — это алгоритм , который может использовать прогноз для повышения своей производительности. В то время как в обычные алгоритмы вводится только экземпляр задачи, алгоритмы с расширенным обучением принимают дополнительный параметр.Этот дополнительный параметр часто является предсказанием какого-либо свойства решения.Этот прогноз затем используется алгоритмом для улучшения времени его работы или качества вывода.

Описание

Алгоритм с расширенным обучением обычно принимает входные данные $({\mathcal {I}},{\mathcal {A}})$. Здесь ${\mathcal {I}}$ это проблемный экземпляр и ${\mathcal {A}}$ это совет: предсказание определенного свойства оптимального решения. Тип экземпляра проблемы и прогноз зависят от алгоритма. Алгоритмы расширенного обучения обычно удовлетворяют следующим двум свойствам:

• Последовательность. Алгоритм с расширенным обучением считается последовательным, если можно доказать, что алгоритм имеет хорошую производительность, когда ему предоставляется точный прогноз. Обычно это определяется количественно путем определения границы производительности, которая зависит от ошибки прогноза.
• Надежность. Алгоритм называется устойчивым, если его производительность в наихудшем случае может быть ограничена, даже если данный прогноз неточен.

Алгоритмы расширенного обучения обычно не предписывают, как следует делать прогноз. Для этой цели машинное обучение . можно использовать

Примеры

Бинарный поиск

Алгоритм бинарного поиска — это алгоритм поиска элементов отсортированного списка. $x_{1},\ldots ,x_{n}$. Это требует $O(\log(n))$ шаги по поиску элемента с некоторым известным значением $x$ в списке длины $n$.С предсказанием $i$ на должность $x$, можно использовать следующий алгоритм расширенного обучения.

• Сначала посмотрите на положение $i$ в списке. Если $x_{i}=y$, элемент найден.
• Если $x_{i}<y$, посмотрите позиции $i+1,i+2,i+4,\ldots$ до тех пор, пока индекс $j$ с $x_{j}\geq y$ найден.
  • Теперь выполните двоичный поиск по $x_{i},\ldots ,x_{j}$.
• Если $x_{i}>y$, делаем то же, что и в предыдущем случае, но вместо этого рассмотрим $i-1,i-2,i-4,\ldots$.

Ошибка определяется как $\eta =|i-i^{*}|$, где $i^{*}$ это реальный показатель $y$.В алгоритме дополненного обучения проверка позиций $i+1,i+2,i+4,\ldots$ берет $\log _{2}(\eta )$ шаги.Затем выполняется бинарный поиск по списку размером не более $2\eta$, что занимает $\log _{2}(\eta )$ шаги. Это делает общее время работы алгоритма $2\log _{2}(\eta )$.Таким образом, когда ошибка невелика, алгоритм работает быстрее, чем обычный двоичный поиск. Это показывает, что алгоритм непротиворечив.Даже в худшем случае ошибка будет максимум $n$. Тогда алгоритм занимает не более $O(\log(n))$ шагов, поэтому алгоритм устойчив.

Больше примеров

Алгоритмы дополненного обучения известны благодаря:

• Проблема с прокатом лыж
• о максимальном весе Задача
• Проблема взвешенного пейджинга

См. также

• Машинное обучение

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

• Обзор публикаций об обучении дополненных алгоритмов