Что делает поверхность ошибки выпуклой? Определяется ли она матрицей Коваринаса или гессианом?

17

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

... Так что именно делает его выпуклым ?

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

Покопавшись глубже (и мои вопросы начинаются здесь), я обнаружил, что для того, чтобы определить, есть ли у вас выпуклая поверхность ошибки, вы должны убедиться, что ваша матрица Гессе является положительной полуопределенной. Для симметричных матриц этот тест прост - просто убедитесь, что все собственные значения матрицы Гессе неотрицательны. (Если ваша матрица не симметрична, вы можете сделать ее симметричной, добавив ее в свою собственную транспонирование и выполнив тот же тест на собственные значения в силу грамиана , но это здесь не важно).

Что такое гессенская матрица? Матрица Гессе кодифицирует все возможные комбинации частичек вашей функции стоимости. Сколько есть частичных? Столько, сколько число объектов в вашем векторном объекте. Как вычислить частичные? Возьмите частичные производные «вручную» из исходной функции стоимости.

Так что это именно то, что я сделал: я предполагаю, что у нас есть матрица данных x n , обозначенная матрицей X , где m обозначает количество примеров, а n обозначает количество признаков в примере. (который также будет числом частичных чисел). Я предполагаю, что мы можем сказать, что у нас есть m временных выборок и n пространственных выборок от датчиков, но физическое применение здесь не слишком важно.mnXmnmn

Кроме того, у нас также есть вектор размером m x 1 . (Это ваш вектор «метки» или ваш «ответ», соответствующий каждой строке X ). Для простоты я принял m = n = 2 для этого конкретного примера. Итак, 2 «примера» и 2 «функции».ym1Xm=n=2

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

J(θ)=12mi=1m[θ0x0[i]+θ1x1[i]y[i]]2

Теперь возьмем первую частную производную по (функция 0). Таким образом:θ0

δJ(θ)δθ0=1mi=1m[θ0x0[i]+θ1x1[i]y[i]]x0[i]

δJ(θ)δθ0=1mi=1m[θ0x02[i]+θ1x1[i]x0[i]y[i]x0[i]]

Теперь давайте вычислим все вторые частичные, поэтому:

δ2J(θ)δθ02=1mi=1mx02[i]

δ2J(θ)δθ0θ1=1mi=1mx0[i]x1[i]

δ2J(θ)δθ1θ0=1mi=1mx1[i]x0[i]

δ2J(θ)δθ12=1mi=1mx12[i]

Мы знаем, что гессиан не что иное, как

H(J(θ))=[δ2J(θ)δθ02δ2J(θ)δθ0θ1δ2J(θ)δθ1θ0δ2J(θ)δθ12]

H(J(θ))=[1mi=1mx02[i]1mi=1mx0[i]x1[i]1mi=1mx1[i]x0[i]1mi=1mx12[i]]

Теперь, основываясь на том, как я построил матрицу данных (мои «особенности» идут по столбцам, а мои примеры идут по строкам), гессиан выглядит так :X

H(J(θ))=XTX=Σ

... который является ничем иным, как образцом ковариационной матрицы !

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

  • Всегда правда:

    • Матрица Гессе всегда контролирует, является ли ваша поверхность ошибки / стоимости выпуклой.
    • Если ваша матрица Гессе имеет полу-полуопределение, вы выпуклые (и можете с удовольствием использовать алгоритмы, такие как градиентный спуск, чтобы сходиться к оптимальному решению).
  • Правда только для LSE:

    • Матрица Гессе для критерия стоимости LSE - не что иное, как исходная ковариационная матрица. (!).
    • Для меня это означает, что, если я использую критерий LSE, сами данные определяют, есть ли у меня выпуклая поверхность? ... Что тогда означало бы, что собственные векторы моей ковариационной матрицы каким-то образом способны «формировать» поверхность затрат? Это всегда правда? Или это просто сработало по критериям LSE? Меня просто не устраивает, что выпуклость поверхности ошибки должна зависеть от данных.

Итак, вернемся к контексту исходного вопроса: как определить, является ли погрешность поиска ошибок (на основе выбранной вами функции стоимости) выпуклой или нет? Основано ли это определение на данных или на гессиане?

Благодарность

TLDR: Как именно и практически я могу определить, дает ли моя функция стоимости и / или набор данных выпуклую или невыпуклую поверхность ошибки?

ошалевший
источник

Ответы:

7

a22aa2

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

θ1θ2

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

J

Jx=b

J

JJ

J

J

Я написал статью о линейных и нелинейных решениях методом наименьших квадратов, которая подробно описывает эти темы:

Линейные и нелинейные наименьшие квадраты с Math.NET

Есть также ссылки на великие книги, которые посвящены сложным темам, связанным с наименьшими квадратами (ковариация в параметрах / точках данных, предварительное кондиционирование, масштабирование, регрессия ортогонального расстояния - общее количество наименьших квадратов, определение точности и точности оценки наименьших квадратов и т. Д.). ).

Я сделал пример проекта для статьи с открытым исходным кодом:

LeastSquaresDemo - двоичный файл

LeastSquaresDemo - источник (C #)

ЛИБОР
источник
θθ
2) Да, я имею в виду в целом. В линейных наименьших квадратах вся поверхность ошибки имеет постоянный гессиан. Взятие второй производной квадратичного является постоянным, то же самое относится и к гессиану. 3) Это зависит от условий вашей матрицы данных. Если гессиан является spd, у вас есть единственное замкнутое решение, и поверхность ошибки выпуклая во всех направлениях. В противном случае матрица данных плохо обусловлена ​​или единственна. Я никогда не использовал Гессиан, чтобы исследовать это, скорее проверяя единичные значения матрицы данных или проверяя, имеет ли она разложение Холецкого. Оба способа скажут вам, есть ли решение.
Libor
Libor - 1) Если можете, пожалуйста, добавьте, как вы использовали SVD ИксМатрица данных или то, как вы использовали декомпозицию Choleskey для проверки того, что у вас есть одно закрытое решение, кажется, что они очень полезны, и это хороший момент, и мне было бы интересно узнать, как их использовать. 2) И последнее, просто чтобы убедиться, что я понимаю вас о гессиане: так что гессиан, как правило, является функциейθи / или Икс, Если это SPD, мы имеем выпуклую поверхность. (Если гессиан имеетθв этом, однако, мы должны были бы оценить это везде, где это кажется). Спасибо еще раз.
Спейси
Мухаммед: 1) Я переписал ответ и добавил ссылки на свою статью о наименьших квадратах (могут быть некоторые ошибки, я еще не опубликовал это официально), включая рабочий пример проекта. Я надеюсь, что это поможет вам глубже понять проблему ... 2) В линейных наименьших квадратах гессиан постоянен и зависит только от точек данных. В целом, это также зависит от параметров модели, но это только случай нелинейных наименьших квадратов.
Libor