Я прочитал несколько объяснений алгоритма EM (например, из Бишопа «Распознавание образов и машинное обучение» и из «Первого курса по машинному обучению» Роджера и Джеролами). Вывод ЭМ в порядке, я понимаю это. Я также понимаю, почему алгоритм охватывает что-то: на каждом шаге мы улучшаем результат, и вероятность ограничена 1,0, поэтому, используя простой факт (если функция увеличивается и ограничивается, то она сходится), мы знаем, что алгоритм сходится к какое-то решение.
Однако откуда мы знаем, что это локальный минимум? На каждом шаге мы рассматриваем только одну координату (скрытую переменную или параметры), поэтому мы можем что-то упустить, например, локальный минимум требует перемещения по обеим координатам одновременно.
Я полагаю, что эта проблема аналогична проблеме общего класса алгоритмов восхождения на гору, примером которой является EM. Таким образом, для общего алгоритма восхождения на гору мы имеем эту проблему для функции f (x, y) = x * y. Если мы начнем с (0, 0) точки, то, только рассматривая оба направления одновременно, мы сможем двигаться вверх от значения 0.
Ответы:
EM не гарантируется, чтобы сходиться к локальному минимуму. Гарантируется только сходиться к точке с нулевым градиентом по параметрам. Так что он действительно может застрять в седловых точках.
источник
Прежде всего, возможно, что EM сходится к локальному минимуму , локальному максимуму или седловой точке функции правдоподобия. Точнее, как отметил Том Минка , EM гарантированно сходится к точке с нулевым градиентом .
Я могу придумать два способа увидеть это; первый взгляд - чистая интуиция, а второй - набросок формального доказательства. Сначала я очень кратко объясню, как работает EM:
Максимизация ожидания как градиентное восхождение
В каждой итерации EM требует, чтобы граница касалась функции правдоподобия при решении предыдущей итерации, т.е. что подразумевает, что их градиенты также одинаковы; то есть . Таким образом, EM по крайней мере так же хорош, как градиентное восхождение, потому что по крайней мере так же хорошо, как . Другими словами:b t L θ t - 1 g = ∇ b t ( θ t - 1 ) = ∇ L ( θ t - 1 ) θ t θ t - 1 + η gT бT L θt−1 g=∇bt(θt−1)=∇L(θt−1) θt θt−1+ηg
Эскиз формального доказательства
Можно показать, что разрыв между границами и функцией правдоподобия сходится к нулю; то есть Можно доказать, что градиент границы также сходится к градиенту функции правдоподобия; то есть: Из-за и и того, что границы, используемые в EM, дифференцируемы, и что , у нас есть и, следовательно, .
источник