линейная регрессия высшего порядка

Question

у меня матричная система:

A x B = C

A равно a по n и B равно n по b. И A, и B неизвестны, но у меня есть частичная информация о C (у меня есть некоторые значения в нем, но не все), и n выбран достаточно маленьким, чтобы система была перегружена. Не требуется, чтобы все строк в A или столбцов в B были чрезмерно ограничены.

Я ищу что-то вроде наименьших квадратов линейной регрессии , чтобы найти лучшее соответствие для этой системы (Примечание: я знаю, что не будет единственного уникального решения, но все, что я хочу это одно из лучших решений)

---

сделать конкретный пример; все a и b неизвестны, все c известны, а? игнорируются. Я хочу найти решение a наименьших квадратов только с учетом знания c.

[ a11, a12 ]                                     [ c11, c12, c13, c14, ?   ]
[ a21, a22 ]   [ b11, b12, b13, b14, b15]        [ c21, c22, c23, c24, c25 ]
[ a31, a32 ] x [ b21, b22, b23, b24, b25] = C ~= [ c31, c32, c33, ?,   c35 ]
[ a41, a42 ]                                     [ ?,   ?,   c43, c44, c45 ]
[ a51, a52 ]                                     [ c51, c52, c53, c54, c55 ]

---

Обратите внимание, что если B обрезается только до b11 и b21, а неизвестный ряд 4 прерывается, то это почти стандартная задача линейной регрессии наименьших квадратов.

Answer 1

Эта проблема некорректна, как описано.

Пусть A, B и C = 5 - скаляры. Вы просите решить A * B = 5 который имеет бесконечное количество решений.

Один из подходов, согласно приведенной выше информации, заключается в минимизации функция g определена как

г (A, B) = || AB-C || ^ 2 = след ((AB-C) * (AB-C)) ^ 2

с использованием метода Ньютона или квазисекундного подхода (BFGS).
(Вы можете легко вычислить градиент здесь). M * - это транспонирование M, а умножение неявно. (Норма является нормой Фробениуса ... Я удалил подчеркните F, поскольку он не отображался должным образом)

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

Если вы предоставите больше информации, я могу помочь вам.

---

Еще несколько вопросов: я думаю, что проблема в том, что без больше информации, нет «лучшего решения». Мы должны определить более конкретное представление о том, что мы ищем. Одна идея, может быть "редким" решением. Эта область горячая область исследований, с некоторыми из лучших умов в мир, работающий здесь (см. Терри Тао и др. работа над ядерной нормой) Эта проблема, хотя и поддается решению, все еще трудна.

---

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

Вот идея на примере, который вы привели выше: два новых вектора V и U, каждый из которых содержит 21 элемент (одно и то же число элементы в С).

V - это точно известные элементы C, упорядоченные по столбцам, поэтому (в обозначениях matlab)

V = [C11; C21; C31; C51; С12; ....; C55]

U - вектор, который представляет собой порядок столбцов произведения AB, ВЫХОД ИЗ ЭЛЕМЕНТЫ, ОТВЕЧАЮЩИЕ НА '?' в матрице C . Сбор всех переменных в х у нас
x = [a11, a21, .. a52, b11, b21 ..., b25].

f (x) = U (как определено выше).

Теперь мы можем попытаться решить f (x) = V вашим любимым нелинейным методом наименьших квадратов.

В качестве отступления, хотя на плакате ниже рекомендуется имитировать отжиг, я рекомендую против этого. Есть некоторые проблемы, это работает, но это эвристика. Когда у тебя есть Я использую мощные аналитические методы, такие как Гаусс-Ньютон или LM. (по моему опыт то есть)

Answer 2

Дикая догадка: разложение по единственному значению может сработать?

Answer 3

Я понятия не имею, как бороться с вашими пропущенными значениями, поэтому я собираюсь игнорировать эту проблему.

Нет уникальных решений. Чтобы найти лучшее решение, вам нужен какой-то показатель, чтобы судить о них. Я собираюсь предположить, что вы хотите использовать метрику наименьших квадратов, то есть лучшие значения угадывания A и B - это те, которые минимизируют сумму чисел [C_ij- (A B) _ij] ^ 2.

Одна вещь, которую вы не упомянули, это как определить значение, которое вы собираетесь использовать для n. Короче говоря, мы можем придумать «хорошие» решения, если 1 <= n <= b. Это потому, что 1 <= rank (span (C)) <= b. Где rank (span (C)) = размерность пространства столбца C. Обратите внимание, что это предполагает a> = b. Чтобы быть более точным, мы бы написали 1 <= rank (span (C)) <= min (a, b). </p>

Теперь предположим, что вы выбрали n такое, что 1 <= n <= b. Вы собираетесь минимизировать остаточную сумму квадратов, если выбрали столбцы A, такие что span (A) = span (Первые n собственных векторов C). Если у вас нет других веских причин, просто выберите столбцы A в качестве первых n собственных векторов C. Как только вы выбрали A, вы можете получить значения B обычным способом линейной регрессии. То есть B = (A'A) ^ (- 1) A 'C </p>

Answer 4

У вас есть несколько вариантов. Алгоритм Левенберга-Марквадта обычно считается лучшим методом LS. Бесплатная реализация доступна на здесь . Однако, если расчет выполняется быстро и у вас есть приличное количество параметров, я настоятельно рекомендую метод Монте-Карло, такой как имитация отжига .

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

P = exp(-(x-x0)/T)

где T - это температурный параметр, а x-x0 - текущее значение пригодности за вычетом предыдущего. После x числа итераций вы уменьшаете T на фиксированную величину (это называется графиком охлаждения). Затем вы повторите этот процесс для другого случайного параметра. Когда T уменьшается, выбирается все меньше плохих решений, и в конечном итоге процедура превращается в «жадный поиск», который принимает только решения, улучшающие соответствие. Если в вашей системе много свободных параметров (> 10 или около того), это действительно единственный путь, по которому у вас будет шанс достичь глобального минимума. Этот метод подбора занимает около 20 минут для написания кода и пару часов для настройки. Надеюсь, это поможет.

К вашему сведению, Вольфрам неплохо обсудил это в контексте проблемы коммивояжера, и я очень успешно использовал его для решения некоторых очень сложных проблем минимизации в глобальном масштабе. Это медленнее, чем методы LM, но гораздо лучше в самых сложных / относительно больших случаях.

Answer 5

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

1. семя А со случайными значениями.
2. решить для каждого столбца B независимо.
3. переработать проблему, чтобы разрешить решение для каждой строки A с учетом значений B из шага 2.
4. повторите на шаге 2, пока все не уладится.

Понятия не имею, стабильно ли это.