Как изменяется косинусное сходство после линейного преобразования?

9

Есть ли математическая связь между:

  • косинусное сходство двух векторов и , иA Bsim(A,B)AB
  • косинусное сходство для и , неравномерно масштабированное с помощью заданной матрицы ? Здесь - заданная диагональная матрица с неравными элементами на диагонали.A Bsim(MA,MB)ABМMM

Я попытался просмотреть вычисления, но не смог найти простую / интересную ссылку (выражение). Интересно, есть ли такой?


Например, углы не сохраняются при неравномерном масштабировании, но какова связь между исходными углами и углами после неравномерного масштабирования? Что можно сказать о связи между набором векторов S1 и другим набором векторов S2 - где S2 получается неравномерным масштабированием S1?

TURDUS-Мерула
источник
@ whuber, спасибо! Да, M - это заданная матрица (масштабирующая матрица, то есть диагональная матрица, других ограничений нет). В некотором смысле я хотел знать, что происходит (с точки зрения косинусного сходства для любой пары векторов) с векторным пространством, которое страдает от нелинейного масштабирования.
turdus-merula
2
Возможно, стоит отметить, что если все масштабные факторы неотрицательны (как можно было бы естественно предположить), то все симметричные положительно определенные матрицы можно считать «масштабирующими» матрицами. Отношения, которые вы ищете, широко используются, в частности , для изучения и описания искажений в проекциях карты. Там, центры интереса в максимальных и минимальных углах на поверхности земли, которые будут связаны с двумя перпендикулярными направлениями на карте. Существует прямая связь между этими углами и отношениями двух масштабных факторов.
whuber

Ответы:

8

Поскольку является довольно общим, и изменение в косинусном подобии зависит от конкретных и и их отношения к , определенная формула невозможна. Однако существуют практически вычисляемые пределы того, насколько может измениться косинусное сходство . Их можно найти, выдвинув угол между и учитывая, что косинусное сходство между и является заданным значением, скажем, (где - угол между и ). Ответ говорит нам, сколько под любым угломA B M M A M B A B cos ( 2 ϕ ) 2 ϕ A B 2 ϕ MMABMMAMBABcos(2ϕ)2ϕAB2ϕвозможно , может быть согнут преобразованием .M

Расчеты грозят быть грязными. Некоторые умные варианты обозначений, а также некоторые предварительные упрощения сокращают усилия. Оказывается, что решение в двух измерениях раскрывает все, что нам нужно знать. Это поддающаяся решению проблема, зависящая только от одной реальной переменной , которая легко решается с использованием методов исчисления. Простой геометрический аргумент распространяет это решение на любое количество измерений .нθn

Математические вступительные

По определению, косинус угла между любыми двумя векторами и получается путем нормализации их к единице длины и взятия их произведения. Таким образом,BAB

AB(AA)(BB)=cos(2ϕ)

и, написав , косинус угла между изображениями и при преобразовании равенA B MΣ=MMABM

(1)(MA)(MB)((MA)(MA))((MB)(MB))=AΣB(AΣA)(BΣB).

Обратите внимание , что только имеет значение в анализе,Σ а не себя. Поэтому мы можем использовать разложение по сингулярным числам (SVD) для чтобы упростить задачу. Напомним, что это выражает как произведение (справа налево) ортогональной матрицы , диагональной матрицы и другой ортогональной матрицы :M M V D UMMMVDU

M=UDV.

Другими словами, существует основа привилегированных векторов (столбцы ), в которых действует путем изменения масштаба каждого отдельно с помощью диагональной записи в (которую я назову ) и затем применение поворота (или анти-вращения) к результату. Это окончательное вращение не изменит никаких длин или углов и, следовательно, не должно влиять на . Вы можете увидеть это формально с расчетом У М е я я й Д д я U Σe1,,enVMeiithDdiUΣ

Σ=MM=(UDV)(UDV)=VD(UU)DV=VD2V.

Следовательно, для изучения мы можем свободно заменить любой другой матрицей, которая дает те же значения в . Заказав так что уменьшение размера (и предполагая не тождественно равна нулю), выбор хороший из являетсяM ( 1 ) e i d i M MΣM(1)eidiMM

M=1d1DV.

Диагональные элементы имеют вид(1/d1)D

1=d1/d1λ2=d2/d1λ3=d3/d1λn=dn/d10.

В частности, влияние (в исходном или измененном виде) на все углы полностью определяется тем фактом, чтоM

Mei=λiei.

Анализ частного случая

Пусть . Поскольку изменение длины векторов не меняет угол между ними, мы можем предположить, что и являются единичными векторами. В плоскости все такие векторы могут быть обозначены углом, который они составляют с , что позволяет нам писатьA B e 1n=2ABe1

A=cos(θϕ)e1+sin(θϕ)e2.

Следовательно

B=cos(θ+ϕ)e1+sin(θ+ϕ)e2.

(Смотрите рисунок ниже.)

Применение очень просто: оно фиксирует первые координаты и и умножает их вторые координаты на . Поэтому угол от к являетсяA B λ 2 M A M BMABλ2MAMB

f(θ)=arctan(λ2tan(θ+ϕ))arctan(λ2tan(θϕ)).

Поскольку - непрерывная функция, эта разность углов является непрерывной функцией . На самом деле, это дифференцируемо. Это позволяет нам находить крайние углы, проверяя нули производной . Эту производную легко вычислить: это соотношение тригонометрических функций. Нули могут встречаться только среди нулей его числителя, поэтому давайте не будем пытаться вычислить знаменатель. Мы получаемθ f ( θ )Mθf(θ)

f(θ)=λ2(1λ2)(λ2+1)sin(2θ)sin(2ϕ).

случаи , и легко понять: они соответствуют ситуациям, когда имеет пониженный ранг (и таким образом сдавливает все векторы на линию); где - кратное единичной матрицы; и где и параллельны (откуда угол между ними не может измениться, независимо от ). Случай исключается условием .λ 2 = 1 ϕ = 0 M M A B θ λ 2 = - 1 λ 20λ2=0λ2=1ϕ=0MMABθλ2=1λ20

Помимо этих особых случаев, нули встречаются только там, где : то есть или . Это означает, что линия, определяемая делит пополам угол . Теперь мы знаем, что крайние значения угла между и должны лежать среди значений , поэтому давайте вычислим их:θ = 0 θ = π / 2 e 1 A B M A M B f ( θ )sin(2θ)=0θ=0θ=π/2e1ABMAMBf(θ)

f(0)=arctan(λ2tan(ϕ))arctan(λ2tan(ϕ))=2arctan(λ2tan(ϕ));f(π/2)=arctan(λ2tan(π/2+ϕ))arctan(λ2tan(π/2ϕ))=2arctan(λ2cot(ϕ)).

Соответствующие косинусы

(2)cos(f(0))=1λ22tan(ϕ)21+λ22tan(ϕ)2

а также

(3)cos(f(π/2))=1λ22cot(ϕ)21+λ22cot(ϕ)2=tan(ϕ)2λ22tan(ϕ)2+λ22.

Часто достаточно понять, как искажает прямые углы. В этом случае , что приводит к , которую вы можете включить в предыдущие формулы.M2ϕ=π/2tan(ϕ)=cot(ϕ)=1

Обратите внимание, что чем меньше становится , тем более экстремальными становятся эти углы и тем больше искажение.λ2

На рисунке показаны четыре конфигурации

На этом рисунке показаны четыре конфигурации векторов и разделенных углом . Единичный круг и его эллиптическое изображение под заштрихованы для справки (с равномерным изменением масштаба действия чтобы сделать ). На рисунке заголовки указывают значение , среднюю точку и . Ближайшие любые такие и могут появиться при преобразовании с помощью - конфигурация, подобная конфигурации слева сAB2ϕ=π/3MMλ1=1θABABMθ=0, Наибольшее расстояние между ними может быть конфигурация, подобная приведенной справа с . Показаны две промежуточные возможности.θ=π/2

Решение для всех размеров

Мы видели, как действует, расширяя каждое измерение на коэффициент . Это изменит единичную сферу на эллипсоид. В определения его главных осей. В расстояние от начала координат, вдоль этих осей, к эллипсоиду. Следовательно, самое маленькое - это самое короткое расстояние (в любом направлении) от начала координат до эллипсоида, а самое большое - это самое дальнее расстояние (в любом направлении) от начала координат до эллипсоида.Miλi{A|AA=1}eiλiλnλ1

В более высоких измерениях , и являются частью двумерного подпространства. отображает единичную окружность в этом подпространстве на пересечение эллипсоида с плоскостью, содержащей и . Это пересечение, являющееся линейным искажением круга, является эллипсом. Очевидно, что самое дальнее расстояние до этого эллипса не больше, чем а самое короткое расстояние не меньше, чем .n>2ABMMAMBλ1=1λn

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

Выводы

Крайности косинусного сходства, достижимые путем применения к двум векторам, имеющим косинусное сходство , определяются формулами и . Они достигаются путем расположения и под равными углами к направлению, в котором максимально удлиняет любой вектор (например, направление ), и разделяя их в направлении, в котором минимально удлиняет любой вектор ( например, направление ).Mcos(2ϕ)(2)(3)ABΣ=MMe1Σen

Эти крайности могут быть вычислены в терминах СВД из .M

Whuber
источник
Это фантастический ответ! Большое спасибо за это подробное обсуждение! Я полагаю, что у вас есть ошибка знака в уравнении (3), где у вас должен быть просто знак минус.
LFH
Меня интересует случай, когда угол приближается к нулю, и я хотел бы получить неравенство между и . Верно ли, что на основе ваших вычислений мне просто нужно найти самый экстремальный (самый маленький) и в этом случае асимптотическое неравенство задается как as ? 2ϕ2ϕfλn2λnϕf2λn1ϕϕ0
LFH
6

Вы, вероятно, заинтересованы в:

(MA,MB)=AT(MTM)B,

Вы можете по диагонали (или, как вы это называете, PCA), что говорит вам, что подобие при преобразовании ведет себя, проецируя на ваши главные компоненты, а затем Расчет сходства в этом новом пространстве. Чтобы уточнить это немного подробнее, позвольте основным компонентам быть с собственными значениями . затемMTM=UΣUTA,BMA,Buiλi

UB=i(ui,bi)ui, UA=i(ui,ai)ui,

что дает вам:

(MA,MB)=i=1n(ui,ai)(ui,bi)λi.

Обратите внимание, что здесь происходит масштабирование: растягивается / сжимается. Когда являются единичными векторами, и если каждый , тогда соответствует повороту, и вы получаете: , что эквивалентно тому, что внутренние произведения инвариантны относительно вращений. В общем, угол остается тем же, когда является конформным преобразованием, которое в этом случае требует, чтобы обратимо, и полярное разложение удовлетворяет с , то есть .λiA,Bλi=1Msim(MA,MB)=sim(A,B)MMMM=OPP=aIMTM=a2I

Алекс Р.
источник
1
Ваша первоначальная постановка задачи не учитывает нормализацию векторов , , и необходимых для вычисления косинусного подобия. Похоже, что последующий анализ также не рассматривает эту нормализацию. В частности, обратите внимание, что косинусные сходства сохраняются даже тогда, когда все собственные значения равны некоторому (положительному) значению, которое отличается от . Это показывает, что даже в этом простом случае можно сказать гораздо больше. ABMAMB1
whuber
@whuber: косинусное сходство сохраняется именно тогда, когда является конформным преобразованием, что в данном случае эквивалентно требованию быть обратимым и , кратным тождеству. Другими словами, полярное разложение удовлетворяет , где . Вы правы по поводу нормализации , но, кажется , глупо говорить о косинус сходстве с не нормированными векторами . М М Т М = a 2 I M M = O P P = a I A , BMMMTM=a2IMM=OPP=aIA,B
Алекс Р.
2
Совсем не глупо! Поскольку это «сходство» определяется косинусом угла между векторами, оно имеет смысл для любых двух ненулевых векторов. Что я имел в виду «гораздо больше , можно сказать , » является то , что эффективные ограничения на угол между изображениями и могут быть получены в терминах угла между и и собственных . B A B MABABM
whuber