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

Question

У меня есть матричная система:

А х В = С

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

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

---

Чтобы сделать конкретный пример; все буквы a и b неизвестны, все c известны, а символы «s» игнорируются. Я хочу найти 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 ] 

---

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

Answer 1

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

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

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

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

Answer 2

Дикое предположение: singular value decomposition может сделать трюк?

Answer 3

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

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

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

г (А, В) = || АВ-С ||^2 = следа ((АВ-С) * (AB-C))^2

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

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

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

---

несколько вопросов: Я думаю, что проблема заключается в том, что не более информации, нет «лучшего решения». Нам нужно, чтобы определил более конкретную идею того, что мы ищем. Одна идея, может быть «самым редким» решением.Эта область является горячей областью исследований, с некоторыми из лучших умов в мире , работающем здесь (см. Terry Tao et al., Работа над Nuclear Norm) Эта проблема, хотя и сдержанная, по-прежнему сложна.

---

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

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

В точно известные элементы С, колонки упорядочены, так (в Matlab обозначениях)

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

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

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

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

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

Answer 4

У вас есть несколько вариантов. Levenberg-Marquadt algorithm обычно признан лучшим методом LS. Свободная реализация доступна по адресу here. Однако, если расчет выполняется быстро и у вас есть достойное количество параметров, я бы настоятельно рекомендовал метод Монте-Карло, такой как simulated annealing.

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

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

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

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

Answer 5

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

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

У меня нет подсказки, если это даже стабильно.