Saddle point. Седловая точка

Перевод — saddle point — с английского — на русский

Saddle point. Седловая точка

  • 1 saddle point; седловая точка В математическом программировании точка, где функция Лагранжа (см. Лагранжиан) достигает максимума по исходным переменным (прямой задачи) и минимума по множителям Лагранжа. При некоторых условиях в задачах выпуклого и линейного программирования оказывается возможным заменить исходную задачу задачей разыскания С.т. функции Лагранжа, поскольку существование такой точки — необходимое и достаточное условие оптимальности решения. Вообще в математике С.т. соответствует случаям, когда значение функции двух переменных представляет собой одновременно максимум относительно одной переменной (вектора переменных) и минимум относительно других (другого вектора переменных). Поясним это на функции двух переменных. Представьте себе седло: некоторая его точка находится ниже всех остальных, расположенных в направлении вдоль лошади, и в то же время — выше всех точек, расположенных в поперечном направлении (отсюда и название “С.т.”). См. рис. С.1. С.т. матрицы — элемент akl матрицы (aij), удовлетворяющий условию: (Обозначения см. в статьях Матрица, Минимакс, Максимин.) В теории игр С.т. (седловой элемент) — это наибольший элемент столбца матрицы игры, который одновременно является наименьшим элементом соответствующей строки (в игре двух лиц с нулевой суммой). В этой точке, следовательно, максимин одного игрока равен минимаксу другого; С.т. есть точка равновесия. Выбор игроком стратегии, не соответствующей С.т., в конце концов нанесет ему ущерб, если он имеет дело с опытным противником (который со своей стороны выберет С.т.). Рис. С.1 Седловая точка функции двух переменных[ http://slovar-lopatnikov.ru/]

EN

Англо-русский словарь нормативно-технической терминологии > saddle point

  • 2 saddle-point

    Большой англо-русский и русско-английский словарь > saddle-point

  • 3 saddle-point

    перевал

    – saddle-point configuration
    – saddle-point method

    Англо-русский технический словарь > saddle-point

  • 4 saddle point

    Английский-русский словарь по теории вероятностей, статистике и комбинаторике > saddle point

  • 5 saddle point

    English-Russian big polytechnic dictionary > saddle point

  • 6 saddle point

    English-Russian dictionary on nuclear energy > saddle point

  • 7 saddle point

    The English-Russian dictionary general scientific > saddle point

  • 8 saddle point

    Большой англо-русский и русско-английский словарь > saddle point

  • 9 saddle point

    седловая точка; точка перевала

    Англо-русский словарь технических терминов > saddle point

  • 10 saddle point

    Англо-русский экономический словарь > saddle point

  • 11 saddle point

    1) седловая точка

    2) седлообразная точка

    Англо-русский технический словарь > saddle point

  • 12 saddle point

    Универсальный англо-русский словарь > saddle point

  • 13 saddle-point

    Универсальный англо-русский словарь > saddle-point

  • 14 saddle point

    Англо русский политехнический словарь > saddle point

  • 15 saddle point

    Англо-русский словарь по машиностроению > saddle point

  • 16 saddle point

    English-russian dictionary of physics > saddle point

  • 17 saddle point

    English-Russian dictionary of computer science and programming > saddle point

  • 18 saddle point

    Англо-русский словарь по экономике и финансам > saddle point

  • 19 saddle point

    Англо-русский словарь по робототехнике > saddle point

  • 20 SADDLE POINT

    Седловая точка
    1. Такое сочетание значений переменных величин в функции, при котором получающееся в результате значение функции является максимальным в одном измерении и минимальным в другом. Рассмотрим функцию Y = f(Х, Z). Если показатель Y сначала растет, а затем снижается по мере роста величины Х или если Y сначала падает, а затем увеличивается по мере роста величины Z, функция может иметь седловую точку SP. На диаграмме она соответствует минимальному значению функции относительно Z при максимальном значении относительно Х (рисунок напоминает седло). 2. Равновесие, которое в некоторых случаях устойчиво, а в других — нет. Например, можно задаться вопросом, существует ли в отрасли тенденция уравновешивания цен. Если такая тенденция наблюдается только на определенном уровне цен, но она отсутствует на других уровнях, такое равновесие называется седловой точкой.  

    Новый англо-русский словарь-справочник. Экономика. > SADDLE POINT

  • Страницы

    Источник: https://translate.academic2.ru/saddle%20point/en/ru/

    Побег из седловой точки

    Saddle point. Седловая точка

    Выпуклые функции (convex function) достаточно просты, поскольку имеют только один локальный минимум. Невыпуклые функции (non-convex function) могут быть намного сложнее.

    В этой статье мы рассмотрим различные типы критических точек, которые могут встретиться при работе с невыпуклыми функциями.

    В частности, мы увидим, что во многих случаях простой эвристический подход на основе градиентного спуска (gradient descent) позволяет достичь локального минимума за полиномиальное время.

    Различные типы критических точек

    local min – локальный минимум local max – локальный максимум saddle point – седловая точка

    Согласно наиболее популярному методу, чтобы минимизировать функцию [latex]f:\mathbb{R}n\to \mathbb{R}[/latex], необходимо двигаться в направлении противоположном градиенту [latex]abla f(x)[/latex] (для простоты все функции, о которых идет речь, мы будем считать бесконечно дифференцируемыми):

    [latex]y = x — \eta abla f(x)[/latex]

    Здесь [latex]\eta[/latex] – малый шаг. Это и есть алгоритм градиентного спуска.

    Если градиент [latex]abla f(x)[/latex] отличен от нуля, и мы выбираем достаточно малое значение [latex]\eta[/latex], алгоритм будет гарантированно локально прогрессировать.

    Если же градиент [latex]abla f(x)[/latex] равен [latex]\vec{0}[/latex], значит, мы достигли критической точки, в которой алгоритм градиентного спуска остановится.

    Для (сильно) выпуклой функции эта критическая точка является единственной и представляет собой глобальный минимум.

    Однако в случае невыпуклой функции равенство градиента нулю еще не говорит об успехе. Хорошим примером является следующая функция:

    [latex]y = x_12 — x_22.[/latex]

    В точке [latex]x = (0,0)[/latex] градиент равен [latex]\vec{0}[/latex], однако очевидно, что эта точка не является локальным минимумом, поскольку при [latex]x = (0, \epsilon)[/latex] функция имеет меньшее значение. Точка [latex](0,0)[/latex] называется седловой точкой (saddle point) данной функции.

    Чтобы различать описанные выше случаи, необходимо рассмотреть производную второго порядка [latex]abla2 f(x)[/latex], то есть матрицу [latex]n\times n[/latex], называемую гессианом (Hessian), [latex]i,j[/latex]-элементы которой вычисляются следующим образом: [latex]\frac{\partial2}{\partial x_i \partial x_j} f(x)[/latex]. Если гессиан является положительно определенным (то есть [latex]u\topabla2 f(x) u > 0[/latex] для любого [latex]ue 0[/latex]) посредством разложения в ряд Тейлора второго порядка для любого направления [latex]u[/latex] [latex]f(x + \eta u) \approx f(x) + \frac{\eta2}{2} u\topabla2 f(x) u > f(x)[/latex], тогда [latex]x[/latex] является локальным минимумом. Аналогично, если гессиан является отрицательно определенным, – точка представляет собой локальный максимум. Если же гессиан имеет как положительные, так и отрицательные собственные значения (eigenvalue), – точка является седловой.

    Считается, что для многих задач, включая обучение глубоких сетей, почти все локальные минимумы имеют значения функции близкие к глобальному оптимуму. Следовательно, для решения таких задач достаточно найти локальный минимум. Однако даже поиск локального минимума является NP-трудным (см.

    обсуждение в работе [Anandkumar, Ge]). Многие популярные методы оптимизации на практике являются алгоритмами оптимизации первого порядка, то есть используют лишь градиент, не вычисляя при этом гессиан в явном виде. Следовательно, подобные алгоритмы не могут преодолевать седловые точки.

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

    Симметрия и седловые точки

    Многие задачи машинного обучения можно абстрагировать, как поиск k различных компонент (иногда называемых признаками (feature), центрами (center) и т.д.).

    Например, в задаче кластеризации (clustering) мы имеем n точек и ищем k компонент, минимизирующих сумму расстояний от точек до ближайших центров. В случае двухслойной нейронной сети мы ищем сеть, содержащую k различных нейронов в среднем слое.

    В задаче разложения тензора (tensor decomposition) также выполняется поиск k различных компонент на единицу меньшего ранга.

    Распространенным способом решения таких задач является применение целевой функции: пусть [latex]x_1, x_2, \ldots, x_k \in \mathbb{R}n[/latex] обозначают центры, и пусть целевая функция [latex]f(x_1, \ldots, x_k)[/latex] оценивает качество решения. Целевая функция достигает минимума, когда векторы [latex]x_1, x_2, \ldots, x_k[/latex] являются искомыми [latex]k[/latex] компонентами.

    Естественная причина, в результате которой любая подобная задача по своей сути является невыпуклой, заключается в симметрии перестановок (permutation symmetry). Например, если поменять местами первую и вторую компоненту, решения будут эквивалентны: [latex]f(x_1, x_2, \ldots, x_k) = f(x_2, x_1, \ldots, x_k)[/latex].

    Однако если мы возьмем среднее данного решения, мы получим решение [latex]\frac{x_1+x_2}{2}, \frac{x_1+x_2}{2}, x_3, \ldots, x_k[/latex], не являющееся эквивалентным! Если исходное решение является оптимальным, данное среднее решение, вероятно, будет неоптимальным. Следовательно, целевая функция не может быть выпуклой, потому что для выпуклой функции среднее оптимального решения также является оптимальным решением.

    Optimal Solution – оптимальное решение Equivalent Solution – эквивалентное решение Not optimal – неоптимальное решение

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

    На рисунке ниже представлена функция [latex]y = x_14-2x_12 + x_22[/latex]: мы видим два симметричных локальных минимума [latex](-1,0)[/latex] и [latex](1,0)[/latex], между которыми находится седловая точка [latex](0,0)[/latex].

    Выбираемся из седловых точек

    Чтобы оптимизировать описанные выше невыпуклые функции со множеством седловых точек, алгоритм оптимизации должен прогрессировать даже оказавшись в седловой точке. Простейшим решением является разложение в ряд Тейлора второго порядка:

    [latex]f(y) \approx f(x) + \left+\frac{1}{2} (y-x)\top abla2 f(x) (y-x)[/latex]

    Если градиент [latex]abla f(x)[/latex] равен [latex]\vec{0}[/latex], мы можем найти вектор [latex]u[/latex], такой, что [latex]u\top abla2 f(x) u < 0[/latex].

    Тогда, если [latex]y = x+\eta u[/latex], значение функции [latex]f(y)[/latex], вероятно, будет меньше.

    Многие алгоритмы оптимизации, такие как метод доверительных областей (trust region algorithm) и кубическая регуляризация (cubic regularization), используют эту идею и способны выходить из седловых точек за полиномиальное время.

    Строго седловые функции

    Как мы уже сказали, в общем случае, NP-трудно найти локальный минимум, причем многие алгоритмы могут остановиться в седловой точке. Сколько же нужно шагов, чтобы выбраться из седловой точки? Это зависит от того, насколько корректна (well-behaved) седловая точка.

    Интуитивно, седловая точка [latex]x[/latex] является корректной, если существует такое направление [latex]u[/latex], для которого слагаемое второго порядка [latex]u\top abla2 f(x) u[/latex] значительно меньше нуля.

    Геометрически это означает, что имеет место крутой спуск, в направлении которого значение функция уменьшается. Чтобы количественно оценить описанную характеристику, в нашей публикации [Ge et al.

    ] мы ввели понятие строго седловой функции (strict saddle function) (эта концепция также рассматривается в работе [Sun et al.]).

    Функция [latex]f(x)[/latex] является строго седловой, если все точки [latex]x[/latex] удовлетворяют хотя бы одному из следующих условий:

    1. Градиент [latex]abla f(x)[/latex] имеет большое значение.
    2. Гессиан [latex]abla2 f(x)[/latex] имеет отрицательное собственное значение.
    3. Точка [latex]x[/latex] находится вблизи локального минимума.

    По сути, локальная область каждой точки [latex]x[/latex] соответствует одному из представленных ниже вариантов:

    large gradient – большой градиент saddle point – седловая точка local min – локальный минимум

    Для таких функций метод доверительных областей и кубическая регуляризация способны эффективно находить локальный минимум.

    Теорема (неформальная). Существуют алгоритмы полиномиального времени, позволяющие найти локальный минимум строго седловой функции.

    Какие же функции являются строго седловыми? Строго седловые функции имеют место в таких задачах, как: разложение тензоров [Ge et al.], обучение словаря (dictionary learning) и восстановление фазы (phase retrieval) [Sun et al.].

    Метод первого порядка, позволяющий преодолевать седловые точки

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

    Эта задача может показаться сложной, поскольку градиент в седловой точке равен [latex]\vec{0}[/latex] и не дает нам никакой информации.

    Однако здесь нам поможет тот факт, что положение в седловой точке является очень неустойчивым: если положить воображаемый шарик в седловую точку, а затем слегка подтолкнуть его, – шарик, скорее всего, скатится вниз, покинув седловую точку! Безусловно, необходимо формализовать эту идею для случая большой размерности, поскольку наивный подход для поиска направления, вероятно, потребует вычисления наименьшего собственного вектора (eigenvector) гессиана.

    Чтобы формализовать нашу идею, мы используем так называемый шумный градиентный спуск (noisy gradient descent):

    [latex]y = x — \eta abla f(x) + \epsilon[/latex]

    Здесь [latex]\epsilon[/latex] представляет собой вектор шума со средним значением, равным 0. Этот вектор обеспечит первоначальный толчок, в результате которого наш воображаемый шарик начнет скатываться по склону.

    На самом деле, зачастую намного легче вычислить шумный градиент, чем истинный градиент. Этот факт лежит в основе алгоритма стохастического градиентного спуска (stochastic gradient descent).

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

    В случае же невыпуклой оптимизации шум улучшает сходимость, поскольку выталкивает алгоритм из седловых точек. Это не недостаток, это полезное свойство!

    Ранее не был известен приемлемый верхний предел количества итераций, необходимых для преодоления седловых точек и достижения локального минимума. В нашей работе [Ge et al.] мы показали следующее:

    Теорема (неформальная). Шумный градиентный спуск позволяет достичь локального минимума строго седловой функции за полиномиальное время.

    Полиномиальная зависимость от размерности n и наименьшего собственного значения гессиана создают определенные неудобства на практике. Поиск оптимальной скорости сходимости для строго седловых задач остается открытой проблемой.

    В недавней работе [Lee et al.] было показано, что даже без добавления шума, градиентный спуск не сойдется ни к одной строго седловой точке, если исходная точка выбрана случайным образом. Однако результаты этой работы опираются на теорему об устойчивом многообразии (stable manifold theorem) из теории динамических систем, которая не оговаривает верхний предел количества шагов.

    Вырожденные седловые точки

    Мы рассмотрели алгоритмы, справляющиеся с простыми седловыми точками.

    Тем не менее в контексте невыпуклых задач могут иметь место намного более сложные поверхности, где присутствуют вырожденные седловые точки – точки, гессиан которых является положительно полуопределенным и имеет нулевые собственные значения.

    Подобная вырожденная структура обычно указывает на сложную седловую точку (например, обезьянье седло (monkey saddle), рис. (a)) или множество связанных седловых точек (рис. (b), (c)). В работе [Anandkumar, Ge] мы предложили алгоритм, способный работать с некоторыми вырожденными седловыми точками.

    Поверхности невыпуклых функций могут быть очень сложными, соответственно, в этой области по-прежнему остается много открытых вопросов.

    Какие еще функции являются строго седловыми? Как создавать алгоритмы оптимизации, способные справляться с вырожденными седловыми точками и даже с ложными локальными минимумами? Мы надеемся, что данная тема привлечет внимание многих новых исследователей, которые помогут найти ответы на эти вопросы!

    Источник: http://datareview.info/article/pobeg-iz-sedlovoy-tochki/

    Все термины
    Добавить комментарий

    ;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: