Сингулярное разложение и "самое слабое звено"

[B@R5uk]

Евгений Машеров в сообщении #1685443 писал(а):

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

А можно по-подробней? Не понимаю, что именно нужно делать после умножения матрицы A на её псевдообратную (и получения коэффициентов разложения каждой из строк на всех строках). Численный эксперимент показывает, что если в матрице есть линейно зависимые строки, то коэффициенты само-разложения (на диагонали) независимых строк оказываются равными 1 (а все остальные — 0), то есть их точно надо оставить. Выкидывать с минимальными коэффициентами на диагонали?

[Евгений Машеров]

B@R5uk в сообщении #1685446 писал(а):

А можно по-подробней? Не понимаю, что именно нужно делать после умножения матрицы A на её псевдообратную (и получения коэффициентов разложения каждой из строк на всех строках). Численный эксперимент показывает, что если в матрице есть линейно зависимые строки, то коэффициенты само-разложения (на диагонали) независимых строк оказываются равными 1 (а все остальные — 0), то есть их точно надо оставить. Выкидывать с минимальными коэффициентами на диагонали?

Я имел в виду процедуру наподобие предложенной Кайзером для расчёта "анализа образов" по Гуттману.
$v=(I-S^2R^{-1})z$
где R - корреляционная (или ковариационная) матрица, а $S^2=(\operatorname{diag}R^{-1})^{-1}$

[B@R5uk]

Не, теперь я совсем в замешательстве и не понимаю, о чём вы говорите.

[Евгений Машеров]

Этот подход не опирается на сингулярное разложение, это обыкновенный регрессионный анализ. Строим регрессию каждой переменной на прочие. Если коэффициент корреляции стремится к единице, данная переменная почти точно выражается через прочие. Проведение "в лоб" требует n обращений корреляционной матрицы R. Но был предложен подход, при котором обращение одно, из наблюдаемых векторов z строятся "образы" v, и можно посчитать корреляцию переменных с их "образами".

[B@R5uk]

Евгений Машеров, как рассчитать коэффициент корреляции для множественной регрессии? Куда ни гляну — формулы только для прямой от одной переменной. Пусть, вот, имеется набор строк X с индексом значений независимых переменных и найдены коэффициенты a с индексом разложения строки Y значений зависимой переменной такие, что они минимизируют квадратичную норму строки невязок E:

$$Y=E+\sum\limits_{k}^{}a_kX_k$$

Как теперь коэффициент корреляции посчитать?

[Евгений Машеров]

$\hat{a}=(X^TX)^{-1}X^Ty$

[B@R5uk]

Это ж коэффициенты a с индексом разложения Y по X, которые уже посчитанными предполагаются. Вы под коэффициентом корреляции разве не вот этот коэффициент имели в виду? Я не правильно понял?

[B@R5uk]

Я тут сообразил, что матрица с нулевой строкой и матрица с вычеркнутой строкой — это почти одно и то же с точки зрения SVD. Пусть, например, имеется матрица

$$A\in\mathbb{R}^{m\times n},\qquad\qquad m\le n-1$$

Запишем её сингулярное разложение:

$$A=U\Sigma V^{T},\qquad U^TU=UU^T=I_m,\qquad V^TV=VV^T=I_n$$

$$U\in\mathbb{R}^{m\times m},\qquad\Sigma\in\mathbb{R}^{m\times n},\qquad V\in\mathbb{R}^{n\times n}$$

Доработаем матрицы U и Σ следующим образом:

$$U'=\left(\begin{matrix}U&0_{m\times 1}\\0_{1\times m}&1\end{matrix}\right),\qquad\qquad\Sigma'=\left(\begin{matrix}\Sigma\\0_{1\times n}\end{matrix}\right)$$

$$U'\in\mathbb{R}^{(m+1)\times(m+1)},\qquad\Sigma'\in\mathbb{R}^{(m+1)\times n},\qquad m+1\le n$$

Теперь "соберём" новую матрицу A' обратно из сконструированного SVD:

$$A'=U'\Sigma'V^{T}=\left(\begin{matrix}U&0_{m\times 1}\\0_{1\times m}&1\end{matrix}\right)\left(\begin{matrix}\Sigma\\0_{1\times n}\end{matrix}\right)V^T=\left(\begin{matrix}U\Sigma\\0_{1\times n}\end{matrix}\right)V^T=\left(\begin{matrix}A\\0_{1\times n}\end{matrix}\right)$$

То есть новая матрица A' — это матрица A с дописанной снизу нулевой строкой, а их сингулярные разложения разнятся лишь:

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

Все величины остались прежними! Причём нулевую строку можно переместить на любое место матрицы A' правильным построением матрицы U'.

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

[SergeyGubanov]

(Оффтоп)

У меня похожая прикладная задача. Количество столбцов - несколько миллионов. Количество строк - несколько тысяч (максимально на сколько оперативной памяти хватит). Для экономии ресурсов, но без особого ущерба для качества хочется выкинуть как можно больше лишних строк, чтоб оставшиеся строки были максимально ортогональны. Очевидный тупой алгоритм - найти пару самых похожих друг на друга строк и одну их них выбросить, повторять это до достижения ситуации когда остались только практически ортогональные строки и дальнейшее выбрасывание пойдёт в ущерб качеству.

[B@R5uk]

SergeyGubanov в сообщении #1685515 писал(а):

...чтоб оставшиеся строки были максимально ортогональны. Очевидный тупой алгоритм - найти пару самых похожих друг на друга строк и одну их них выбросить...

Совершенно верно! Строки с малым угловым расстоянием между друг другом (как и сильно разнящиеся по норме строки) "портят" число обусловленности матрицы. Однако, тут важно не минимальное угловое расстояние между строкой-кандидатом на удаление и каждой из всех остальных по отдельности, а угловое расстояние между строкой-кандидатом и всеми остальными строками как единая совокупность. Линейная оболочка этой совокупности образует некое линейное подпространство, в котором можно найти строку-вектор, минимально удалённый по угловой мере от строки-кандидата. Получаемое угловое расстояние будет мерой близости строки-кандидата к совокупности остальных строк. Логично отбрасывать те, что имеют минимальную такую меру.

Это угловое расстояние вполне может оказаться равным нулю, даже тогда когда попарные углы все отличны от нуля и заметно велики. Это произойдёт, когда строка-кандидат лежит в линейной оболочке остальных строк, то есть линейно выражается через них. Если выявить, какие строки входят в линейную комбинацию, то выбрасывание любой из них не будет менять ранг матрицы, но от того, какая выбрасывается, будет зависеть число обусловленности результирующей матрицы. Теперь логично выбрасывать ту строку, у которой (в данном случае) попарные угловые расстояния с остальными минимальны. SergeyGubanov, спасибо за идею! Тут правда, остаётся вопрос: если имеется несколько линейных зависимостей, то есть, нужно выбросить несколько строк, будет ли жадный алгоритм давать наилучший результат (или близкий к нему), или же надо делать полный перебор для его достижения?

Вообще, сказанное выше наталкивает меня на такую мысль. Можно рассматривать строки матрицы A как набор неких признаков, при этом каждая строка — это объект со своими признаками. А в целом строки-объекты образуют популяцию, занимающую некую область в пространстве признаков. Хотелось бы сокращать эту популяцию так, чтобы её описательная сила для этой области в пространстве признаков оставалась максимальной.

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

$$A=U\Sigma V^{T}$$

Матрица V — это ортонормированный базис в пространстве признаков. Каждый её столбец задаёт некий производный совокупный признак, характеризующий эту популяцию. И все они друг другу ортогональны. Но совокупные признаки не эквивалентны, некоторые из них в популяции представлены сильнее, другие — слабее, третьи не представлены вообще, потому что количество объектов обычно значительно меньше количества признаков (в таком случае выгодно использовать экономное SVD).

Матрица Σ сингулярных значений задаёт вес совокупного признака в популяции. Признаки, не представленные в популяции, получают нулевой вес по умолчанию. Если умножить матрицу популяции A на матрицу о/н базиса V, то в каждой строке результирующей матрицы X будут стоять коэффициенты разложения исходных признаков объекта по базису совокупных признаков:

$$X=AV=U\Sigma$$

А в каждом выбранном столбце — веса вхождения выбранного совокупного признака в описание каждого из объектов совокупности. Если найти норму этих столбцов, то получатся как раз сингулярные числа:

$$X=\left(\begin{matrix}w_1&w_2&\ldots&w_m&0_{m\times(n-m)}\end{matrix}\right)$$

$$W=\left(\begin{matrix}\lVert w_1\rVert&\lVert w_2\rVert&\ldots&\lVert w_m\rVert\end{matrix}\right)=\left[\sqrt{\operatorname{diag}\lBig(X^TX\rBig)}\right]_{(m)}=$$

$$=\left[\sqrt{\operatorname{diag}\lBig(\Sigma^TU^TU\Sigma\rBig)}\right]_{(m)}=\left[\sqrt{\operatorname{diag}\lBig(\Sigma^T\Sigma\rBig)}\right]_{(m)}=\operatorname{diag}\lbig(\Sigma\rbig)$$

Здесь квадратными скобками с индексом (m)

$$\lBig[\;\;\cdot\;\;\rBig]_{(m)}$$

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

Используется синтаксис Text

>> a = randn (4, 10)
a =
    0.8369   -0.0205   -1.7506    1.3101   -2.4490   -0.6547   -0.3304   -0.9573   -0.4977   -0.7562
   -0.7223    0.2789    0.6973    0.3271    0.4733   -1.0807   -0.4999    1.2925   -1.1187   -0.0891
   -0.7215    1.0583    0.8115   -0.6730    0.1169   -0.0477   -0.0360    0.4409    0.8076   -2.0089
   -0.2012    0.6217    0.6363   -0.1493   -0.5911    0.3793   -0.1748    1.2809    0.0412    1.0839
>> [u s v] = svd (a)
u =
   -0.8904   -0.2546    0.3533    0.1326
    0.2711   -0.0156    0.8448   -0.4610
    0.3011   -0.9275    0.0072    0.2215
    0.2077    0.2733    0.4017    0.8490
s =
    3.9784         0         0         0         0         0         0         0         0         0
         0    2.6574         0         0         0         0         0         0         0         0
         0         0    2.3630         0         0         0         0         0         0         0
         0         0         0    1.7004         0         0         0         0         0         0
v =
   -0.3016    0.1552   -0.1695    0.0666    0.7903   -0.0790    0.0098    0.3248   -0.1852    0.2847
    0.1361   -0.3051    0.2055    0.3710    0.4257    0.2645    0.2286   -0.5827    0.2496    0.0569
    0.5339   -0.0541    0.0982    0.0979   -0.1325   -0.0685   -0.0525    0.0094   -0.3801    0.7233
   -0.3296    0.0921    0.2854   -0.1488   -0.1907    0.5288    0.0996    0.2447    0.4161    0.4694
    0.5583    0.1303   -0.2971   -0.5991    0.2832    0.2390   -0.0075    0.0067    0.2891   -0.0552
    0.0891    0.1248   -0.4199    0.4251   -0.1024    0.6837   -0.1310    0.1247   -0.2824   -0.1705
    0.0280    0.0292   -0.2579    0.0178   -0.1391   -0.0701    0.9422    0.1153   -0.0779    0.0079
    0.4025    0.0620    0.5381    0.2719    0.1380   -0.0048    0.0898    0.5730    0.1075   -0.3220
    0.0984   -0.2234   -0.4649    0.3903   -0.0992   -0.2922   -0.1476    0.2381    0.6050    0.1792
    0.0677    0.8856    0.0333    0.2447   -0.0374   -0.1567    0.0085   -0.2849    0.1968    0.0647
>> x = a * v
x =
   -3.5423   -0.6766    0.8349    0.2254    0.0000   -0.0000    0.0000    0.0000   -0.0000    0.0000
    1.0784   -0.0415    1.9963   -0.7840    0.0000    0.0000    0.0000    0.0000    0.0000   -0.0000
    1.1977   -2.4647    0.0169    0.3767   -0.0000    0.0000    0.0000    0.0000   -0.0000    0.0000
    0.8262    0.7262    0.9493    1.4437    0.0000   -0.0000   -0.0000   -0.0000   -0.0000   -0.0000
>> sqrt (diag (x' * x))'
ans =
    3.9784    2.6574    2.3630    1.7004    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000
>> diag (s)'
ans =
    3.9784    2.6574    2.3630    1.7004
>>

Матрица U — это ортонормированный базис, но уже в пространстве объектов. Каждая выбранная строка этой матрицы задаёт разложение признаков выбранного объекта по масштабированным (сингулярными значениями) совокупным признакам. В каждом выбранном столбце матрицы U стоят веса вхождения (масштабированных) совокупных признаков в описание каждого из объектов. Поскольку матрица U — ортогональная, и, соответственно, нормы её столбцов и строк равны 1, то близкий по модулю к 1 вес совокупного признака в выбранной строке означает, что веса остальных совокупных признаков в описании выбранного объекта будут малы. То есть, что выбранный объект описывается в основном только этим совокупным признаком. Если же вес совокупного признака близок к 1 при рассмотрении выбранного столбца матрицы U, то это будет означать, что этот совокупный признак будет слабо входить в описание других объектов совокупности. То есть, что выбранный совокупный признак добавляется в совокупность в основном только одним этим объектом.

Из этих наблюдений следует такое эвристическое правило. Если мы хотим избавиться от лишнего объекта с минимальными потерями для описательной способности всей их совокупности, то лучше удалить тот объект, который в большей мере описывается "слабейшим" совокупным признаком (то есть, соответствующим минимальному сингулярному значению), или, что тоже самое, вносит в совокупность только "слабейший" совокупный признак. Другими словами, берём последний столбец матрицы U (как раз соответствующий этому минимальному сингулярному значению), находим в нём максимальный по модулю элемент и удаляем из матрицы A строку, соответствующую этому элементу. Возможно, при выборе удаляемой строки необходимо учесть (с какими-то убывающими весами) и другие столбцы матрицы U. Например, в таком духе: посчитать матрицу Y со шляпкой и в выборе руководствоваться максимальностью нормы её строк:

$$\widehat{Y}=U\left(\lBig[\Sigma\rBig]_{(m)}\right)^{-1}$$

К этому же эвристическому правилу я пришёл ранее в теме из соображений линейной зависимости строк. Правда, при этом некоторые сингулярные значения матрицы A оказываются нулевыми, и при выборе удаляемой строки необходимо руководствоваться исключительно столбцами матрицы U, соответствующими этим нулевым собственным значениям. По этой причине в формуле для Y со шляпкой выше я Σ взял в обратной степени. Возможно, я не прав, и при выборе удаляемой строки или строк нужно пользоваться только последним или последними столбцами матрицы U в количестве, равном числу удаляемых строк. В общем, как правильно действовать — это вопрос.

Свет на ситуацию пролила бы теорема, которая бы давала ограничения в виде неравенств на то, какими станут (как сильно изменятся) сингулярные значения у матрицы A, если в ней занулить/вычеркнуть одну или несколько строк. Поэтому вопрос: кто-нибудь знает какую-нибудь теорему в этом духе?

[SergeyGubanov]

B@R5uk в сообщении #1685534 писал(а):

Можно рассматривать строки матрицы A как набор неких признаков, при этом каждая строка — это объект со своими признаками. А в целом строки-объекты образуют популяцию, занимающую некую область в пространстве признаков. Хотелось бы сокращать эту популяцию так, чтобы её описательная сила для этой области в пространстве признаков оставалась максимальной.

В моей задаче наоборот. У меня миллионы объектов и тысячи признаков. Хочется уменьшить количество признаков (уменьшить размерность векторов эмбедингов) не сильно потеряв при этом в разрешающей способности различать объекты друг от друга.

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

[B@R5uk]

SergeyGubanov в сообщении #1685537 писал(а):

У меня миллионы объектов и тысячи признаков.

О! Тогда да, это будет уже совсем другая задача. В вашем случае нет необходимости заботится о представительности популяции объектов в пространстве признаков, лишь об их более-менее равномерном размещении.

Вообще, в моей задаче тоже что-то подобное возникает, если строки линейно зависимы. SVD позволяет выявить, какие из них входят в линейную комбинацию (или несколько различных ЛК, если есть многократная вырожденность) и перейти в новый базис подпространства производных совокупных признаков, в котором будет излишек объектов и недостаток признаков, то есть ваша ситуация. Большое СПАСИБО за ваш комментарий! Он натолкнул меня ещё на одно продвижение в понимании вопроса. Теперь надо над понятым поразмышлять.

[B@R5uk]

SergeyGubanov в сообщении #1685537 писал(а):

У меня миллионы объектов и тысячи признаков. Хочется уменьшить количество признаков (уменьшить размерность векторов эмбедингов) не сильно потеряв при этом в разрешающей способности различать объекты друг от друга.

ОК. Я въехал в вашу задачу, и в чём заключается проблема. А именно: нехватка оперативной памяти для хранения всех данных. Вы решаете эту проблему выбором подмножества признаков, обеспечивающих наилучшую узнаваемость объектов. Достоинство: не нужно ничего пересчитывать, лишние признаки просто отбрасываются. Я так понимаю, вы определились с подмножеством признаков по тестовому набору объектов и больше к этому вопросу не возвращаетесь? Или же имеется проблема с распознаванием вновь поступающих объектов и требуется улучшить решение?

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

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

Вы уже используете у себя SVD? А то друг я, что говорится, preaching to the choir.

[SergeyGubanov]

Я в творческом поиске. Окончательного решения еще нет. В сторону SVD посмотрю.

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

[B@R5uk]

ОК, меня тут осенило! (Случайно посмотрел на "правильный" набор циферок). Вот есть две матрицы:

$$A_1=\left(\begin{matrix}10&0&0\\0&10&0\\0&0&1\end{matrix}\right),\qquad\qquad A_2=\left(\begin{matrix}10&0&0\\0&1&0\\0&0&1\end{matrix}\right)$$

Желание удалением строки (или столбца) получить из них матрицу с наилучшим числом обусловленности приведёт к тому, что во втором случае будет удалёна первая строка с "самым сильным признаком популяции". То есть, при удалении информации из матрицы критерий с числом обусловленности, вообще говоря, противоречит критерию максимального удержания энергии (норма Фробениуса матрицы). Тем не менее, вариативность признаков, интуитивно кажется, связана в первую очередь с оптимальностью числа обусловленности, а не сохранением энергии. Этот, на первый взгляд, парадокс можно объяснить тем, что производный совокупный признак, соответствующий максимальному сингулярному значению, является сильнейшим признаком именно популяции как целого, но сама его величина ещё ничего не говорит о вариативности объектов по этому признаку внутри популяции. Для ответа на последний вопрос надо смотреть на вариативность координат в базисе объектов, соответствующих этому признаку. Тут, наверно, можно составить красивое оценочное неравенство на скальное произведение, посчитанное через урезанный список признаков. Надо над этим подумать.

SergeyGubanov, а можно глянуть на какой-нибудь тестовый набор ваших векторов поиграться?