Я продолжаю сталкиваться с этим термином, читая об обучении с подкреплением, например, в этом предложении:
Если проблема смоделирована с осторожностью, некоторые алгоритмы обучения усилению могут сходиться к глобальному оптимуму
http://reinforcementlearning.ai-depot.com/
или здесь:
Было доказано, что описанный выше алгоритм TD для любой фиксированной политики Pi сходится к VPi.
http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node62.html
Я понимаю, что слово сходится, что это означает, что несколько вещей собираются вместе в одну точку, но как одна вещь (алгоритм) может это сделать?
algorithms
machine-learning
морская звезда
источник
источник
Ответы:
Итерационный алгоритм сходится , когда, как итерации продолжаются, выход становится все ближе и ближе к некоторому определенному значению. Точнее, независимо от того, какой маленький диапазон ошибок вы выберете, если вы продолжите достаточно долго, функция в конечном итоге останется в этом диапазоне ошибок около конечного значения.
В некоторых случаях алгоритм не будет сходиться, имея выходные данные, которые всегда изменяются на некоторое количество. Он может даже расходиться, когда его продукция будет подвергаться все большим и большим колебаниям, никогда не достигая полезного результата. Точнее, независимо от того, как долго вы продолжите, значение функции никогда не будет устанавливаться в диапазоне какого-либо «окончательного» значения.
Фраза «сходится к глобальному оптимуму» в вашем первом предложении является ссылкой на алгоритмы, которые могут сходиться, но не на «оптимальное» значение (например, алгоритм подъема на холм, который, в зависимости от функции и начальных условий, может сходиться к локальный максимум, никогда не достигший глобального максимума).
источник
Что такое сходимость, в общем
Понятие конвергенции - это хорошо определенный математический термин. По сути это означает, что «в конце концов» последовательность элементов становится все ближе и ближе к одному значению. Мы называем это единственное значение «предел».
Формальное определение выглядит примерно так:
Учитывая (бесконечную) последовательность действительных чисел,
X0, X1, X2, ... Xn ...мы говорим, чтоXn converges to a given number Lесли для каждой положительной ошибки, которую вы думаете, естьXmтакая, что каждыйXnпоследующий элементXmотличается отLэтой ошибки меньше.Пример:
Представьте себе последовательность как таковую:
Сходится ли Xn к нулю? Да! Зачем?
Подумайте об ошибке E (например,
E = 0.0025). Есть ли в последовательности элемент, после которого каждый элемент находится ниже0.025? Да! Этот элемент естьX3 = 0.001. После Х2 каждыйXNниже0.0025. Можно ли это сделать для каждого E> 0? Да. Для каждой положительной ошибки, которую мы выбираем, мы можем видеть, сколько нулей у нее есть до ее первой десятичной запятой, и последовательность будет ниже, чем начиная с элемента, имеющего такое же количество нулей.Это значит что
Xn = 1/(10^5) converges to 0. Как и в «он может становиться все ближе и ближе к нулю» столько, сколько мы хотим.Что означает, что алгоритм сходится?
«С технической точки зрения» сходится не алгоритм, а значение, которым алгоритм манипулирует или итерирует. Например, допустим, мы пишем алгоритм, который печатает все цифры PI.
Алгоритм начинает печатать числа как:
Мы могли бы спросить себя: алгоритм печатает числа, которые становятся все ближе к PI? Другими словами,
X0, X1, ... XN ...сходится ли последовательность, которую печатает наш алгоритм, к PI?Если так, то мы говорим, что наш алгоритм сходится к PI.
Мы обычно заинтересованы в доказательстве правильности алгоритма.
Обычно, когда мы пишем алгоритм, нам интересно знать, является ли решение, предлагаемое алгоритмом, правильным для решаемой проблемы. Иногда это может прийти в форме конвергенции.
В общем, алгоритмы имеют то, что мы называем метриками . Метрика - это число, которое мы даем данному результату, который выдает алгоритм. Например, в итерационных алгоритмах AI / Machine Learning для нас очень распространено отслеживать «ошибку», которую алгоритм генерирует на основе входных данных. Эта ошибка является метрикой.
В этих итерационных алгоритмах каждый шаг генерирует различную ошибку. Алгоритм пытается минимизировать эту ошибку, чтобы она становилась все меньше и меньше. Мы говорим, что алгоритм сходится, если сходится последовательность ошибок.
В этих случаях
global optimumобычно определяется как установка с наименьшей возможной ошибкой. В этом случае «алгоритм сходится к глобальному оптимуму» означает, что «алгоритм генерирует ошибки в последовательности, которая сходится к минимально возможной ошибке».Если «глобальный оптимум» является нашим «правильным решением», утверждение, что наш алгоритм сходится, равнозначно утверждению, что наш алгоритм является правильным.
Кроме того, имейте в виду, что утверждение, что алгоритм сходится, требует доказательства (как мы сделали для нашего примера 0,001, 0,0001, ...,).
Как пример, классификатор
Примером этого может быть случай классификатора. Предположим, мы хотим классифицировать, являются ли числа нечетными или даже использовать алгоритм машинного обучения, и что у нас есть следующий набор данных:
Наш алгоритм для каждого набора чисел выплевывает для каждого из них, если они четные или нечетные. Для этого мы можем определить метрическую ошибку как количество ошибочных делений, деленное на общее количество заданных элементов.
Итак, если наш алгоритм выплевывает следующее:
Наш показатель ошибки будет
3/5 = 0.6. Теперь допустим, что мы снова запустили алгоритм и теперь он выплевывает:Наш показатель ошибки будет
1/5 = 0.2.Допустим, он запускается все больше и больше, и наша последовательность ошибок выглядит примерно так:
0.6, 0.2, 0.1, 0.01, 0.000456, 0.00000543, 0.000000000444 ....Итак, главный вопрос: наш алгоритм когда-нибудь будет равен нулю? Будет ли оно когда-либо сходиться к нулю? Будет ли каждый наш алгоритм сходиться? Можем ли мы доказать, что в конечном итоге все получится правильно (или как можно ближе к правильному)?
Надеюсь, что так :)
источник