Проверка выпуклости функции
Любопытный случай выпуклых функций.
Углубленное понимание выпуклых функций и способов проверки выпуклости.
- Большая часть онлайн-литературы по введению в машинное обучение начинается с описания алгоритма линейной регрессии.
- Обычно алгоритм линейной регрессии подробно описывается с использованием среднеквадратичной ошибки (MSE) в качестве функции потерь.
- MSE - выпуклая функция. Свойство выпуклости открывает решающее преимущество, когда локальные минимумы также являются глобальными минимумами.
- Это гарантирует, что модель может быть обучена таким образом, чтобы функция потерь была минимизирована до глобального минимального значения.
- Однако доказательство выпуклости MSE (или любой другой функции потерь) обычно выходит за рамки.
- В этом сообщении блога мы рассмотрим концепции, необходимые для доказательства выпуклости функции.
- Так что держитесь крепче, и к концу этой статьи вы лучше поймете:
- Квадратные и симметричные матрицы.
- Матрицы Гессе.
- Доказательство / Проверка выпуклости функций.
- Положительные и отрицательно определенные / полуопределенные матрицы.
Без лишних слов, давайте перейдем к делу.
Основы матриц -
Мы коснемся основы некоторых основных понятий в Матрицах, которые помогут нам в доказательстве выпуклости функции. Эти основы обычно изучаются на курсах бакалавриата и должны быть вам знакомы.
Квадратная матрица -
Для матрицы X размеров m × n, X является квадратной матрицей тогда и только тогда (если и только если) m = n. Другими словами, матрица X называется квадратной матрицей, если количество строк матрицы равно количеству столбцов.
В приведенном выше примере, поскольку количество строк (m) = количеству столбцов (n), X можно назвать квадратной матрицей.
Симметричная матрица -
квадратная матрица X называется симметричной, если xᵢⱼ = xⱼᵢ ∀ i и j, где i, j обозначают i-ю строку и j-й столбец соответственно. Другими словами, матрица X является симметричной, если транспонированная матрица X равна матрице X.
Матрица Гессе
Гессиан функции многих переменных f (x₁, x₂,… xₙ) - это способ организации частных производных второго порядка в виде матрицы.
Рассмотрим многомерную функцию f (x₁, x₂,… xₙ), тогда ее гессиан можно определить следующим образом:
Обратите внимание, что матрица Гессе по определению является квадратной и симметричной матрицей.
Доказательство / Проверка выпуклости функции -
Со всеми соответствующими основами, изложенными в предыдущих разделах, теперь мы готовы определить проверки для определения выпуклости функций.
Функция f (x), определенная над n переменными на открытом выпуклом множестве S, может быть проверена на выпуклость с использованием следующих критериев:
Если Xᴴ - матрица Гессе функции f (x), то -
- f (x) является строго выпуклым в S, если Xᴴ является положительно определенной матрицей.
- f (x) является выпуклым в S, если Xᴴ - положительная полуопределенная матрица.
- f (x) строго вогнутая в S, если Xᴴ - отрицательно определенная матрица.
- f (x) является вогнутым в S, если Xᴴ - отрицательная полуопределенная матрица.
В следующем разделе давайте обсудим способы проверки определенности матрицы.
Положительно определенные и полуопределенные матрицы -
Возможно, вы встречали упоминания об этих матрицах в разных местах, но определение и способы доказательства определенности для многих остаются неуловимыми. Начнем с определения из учебника -
Квадратная матрица X размера n × n является положительно определенной, если aXa ›0 ∀ a ∈ ℝⁿ.
Сходным образом,
Квадратная матрица X размера n × n является положительной полуопределенной, если aᵀXa ≥ 0 ∀ a ∈ ℝⁿ.
Эту же логику можно легко распространить на отрицательно определенные и отрицательные полуопределенные матрицы.
Квадратная матрица X размера n × n является отрицательно определенной, если aᵀXa ‹0 ∀ a ∈ ℝⁿ.
И, наконец,
Квадратная матрица X размера n × n является отрицательной полуопределенной, если aᵀXa ≤ 0 ∀ a ∈ ℝⁿ.
- Однако при проверке определенности матрицы проверка состояния каждого значения `a` определенно не является вариантом.
- Так что давайте попробуем разбить это еще дальше.
Собственные значения и собственный вектор -
Мы знаем, что собственный вектор - это вектор, направление которого не меняется при применении к нему линейного преобразования.
Анализ
- Легко видеть, что скалярное произведение a на aᵀ всегда будет положительным.
- Возвращаясь к определению положительно определенной матрицы и уравнению (3), aᵀXa может быть больше нуля тогда и только тогда, когда λ больше нуля.
Производное определение для определенности матрицы -
Основываясь на указателях, упомянутых в приведенном выше анализе, мы можем настроить формальные определения определенности матрицы следующим образом:
- Симметричная матрица X положительно определена, если λᵢ ›0 ∀ i
- Симметричная матрица X является положительно полуопределенной, если λᵢ ≥ 0 ∀ i
- Симметричная матрица X отрицательно определена, если λᵢ ‹0 ∀ i
- Симметричная матрица X является отрицательно полуопределенной, если λᵢ ≤ 0 ∀ i
Альтернативное определение для определения определенности матрицы -
- Вычисление собственных значений для больших матриц часто включает решение линейных уравнений.
- Большие матрицы включают решение линейных уравнений с большим количеством переменных. Следовательно, не всегда возможно найти собственные значения.
На помощь приходит альтернативная теорема для определения определенности матриц -
Теоремы -
- Симметричная матрица X является положительно определенной, если Dₖ ›0 ∀ k, где Dₖ представляет k-е ведущее главное минор.
- Симметричная матрица X является положительно полуопределенной, если Dₖ ≥ 0 k, где Dₖ представляет k-й главный минор.
- Симметричная матрица X является отрицательно определенной, если Dₖ ‹0 ∀ k, где Dₖ представляет k-е ведущее главное минорное число.
- Симметричная матрица X является отрицательно полуопределенной, если Dₖ≤ 0 ∀ k, где Dₖ представляет k-й главный минор.
Основные несовершеннолетние в матрице -
- Для квадратной матрицы X основная подматрица порядка k получается удалением любых (n-k) строк и соответствующих (n-k) столбцов.
- Определитель такой главной подматрицы называется главным минором матрицы X.
Ведущие главные миноры матрицы -
- Для квадратной матрицы X ведущая основная подматрица порядка k получается удалением последних (n-k) строк и соответствующих (n-k) столбцов.
- Определитель такой ведущей главной подматрицы называется ведущей главной минорной матрицей X.
Проверка выпуклости квадратичной функции -
В этом разделе давайте попробуем применить все знания из этого блога и протестировать их.
Свойства выпуклых функций -
- Постоянные функции вида f (x) = c бывают как выпуклыми, так и вогнутыми.
- f (x) = x является как выпуклым, так и вогнутым.
- Функции вида f (x) = xʳ при r ≥ 1 выпуклы на интервале 0 ‹x‹ ∞
- Функции вида f (x) = xʳ с 0 ‹r‹ 1 вогнуты на интервале 0 ‹x‹ ∞
- Функция f (x) = łog (x) вогнута на интервале 0 ‹x‹ ∞
- Функция f (x) = eˣ всюду выпукла.
- Если f (x) выпуклый, то g (x) = cf (x) также выпуклый для любого положительного значения c.
- Если f (x) и g (x) выпуклые, то их сумма h (x) = f (x) + g (x) также выпукла.
Заключительные комментарии -
- Мы глубоко исследовали выпуклые функции, изучая различные способы доказательства выпуклости.
- В следующей статье мы докажем выпуклость функции потерь MSE, используемой в линейной регрессии.
- Выпуклые функции легко минимизировать, что приводит к их использованию во всех областях исследования.
- Итак, в следующий раз, когда вы захотите подключить другую функцию потерь вместо MSE при обучении модели линейной регрессии, вы также можете проверить ее выпуклость.
