Разлагане на единична стойност срещу факторизация на матрицата в препоръчващите системи

Наскоро, след като изгледах курса за препоръчителни системи на курса по машинно обучение на проф. Андрю Нг, се почувствах много неудобно, не разбирайки как работи факторизацията на матрицата.

Знам, че понякога математиката в машинното обучение е много неясна. По-добре е да го мислим като черна кутия, но този модел беше много „вълшебен“ за моите стандарти.

В такива ситуации обикновено се опитвам да търся в Google за повече препратки, за да разбера по-добре концепцията. Този път се обърках още повече. Докато проф. Нг нарича алгоритъма като (Нисък фактор) матрица на факторизация, аз открих различна номенклатура в интернет: Разлагане на единична стойност.

Това, което ме обърка най-много, беше, че разлагането на единична стойност беше много различно от това, което преподаваше проф. Нг. Хората непрекъснато предполагаха, че и двамата са едно и също нещо.

В този текст ще обобщя констатациите си и ще се опитам да изясня част от объркването, което тези термини могат да предизвикат.

Препоръчителни системи

Системите за препоръки (RS) са просто автоматизирани начини да препоръчате нещо на някого. Такива системи се използват широко от компании за електронна търговия, стрийминг услуги и уебсайтове за новини. Помага за намаляване на триенето на потребителите, когато се опитват да намерят нещо, което им харесва.

RS определено не са нещо ново: те се представят най-малко от 1990 г. Всъщност, част от скорошния шум за машинно обучение може да се отдаде на интереса към RS. През 2006 г. Netflix нашумя, когато спонсорира състезание за намиране на най-доброто RS за техните филми. Както ще видим скоро, това събитие е свързано с номенклатурната бъркотия, която последва.

Представянето на матрицата

Има много начини човек да си помисли да препоръча филм на някого. Една стратегия, която се оказа много добра, е да третира рейтингите на филми като матрица Users x Movies като тази:

В тази матрица въпросителните знаци представляват филмите, които потребителят не е оценил. Тогава стратегията е да се предскажат по някакъв начин тези рейтинги и да се препоръчат на потребителите филмите, които вероятно ще им харесат.

Факторизация на матрицата

Наистина умно осъзнаване, направено от момчетата, които се включиха в състезанието на Netflix (по-специално Саймън Фънк), беше, че оценките на потребителите не бяха просто произволни предположения. Вероятно оценителите следват някаква логика, когато преценяват нещата, които харесват във филм (конкретна актриса или жанр), спрямо неща, които не харесват (дълготрайни или лоши шеги) и след това измислят резултат.

Този процес може да бъде представен от линейна формула от следния вид:

където xₘ е вектор на колона със стойностите на характеристиките на филма m, а θᵤ е друг вектор на колона с теглата, които потребителят u дава на всяка характеристика. Всеки потребител има различен набор от тегла и всеки филм има различен набор от стойности за своите характеристики.

Оказва се, че ако произволно фиксираме броя на характеристиките и игнорираме липсващите оценки, можем да намерим набор от тегла и стойности на характеристиките, които създават нова матрица със стойности, близки до оригиналната матрица за оценка. Това може да се направи с градиентно спускане, много подобно на използваното при линейна регресия. Вместо това сега ние оптимизираме два набора от параметри (тегла и характеристики) едновременно.

Използвайки таблицата, която дадох като пример по-горе, резултатът от проблема с оптимизацията ще генерира следната нова матрица:

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

Добре, сега имаме приблизителна матрица. Но как, по дяволите, това ни помага да предскажем липсващите рейтинги? Не забравяйте, че за да изградим новата матрица, ние създадохме формула, за да попълним всички стойности, включително тези, които липсват в оригиналната матрица. Така че, ако искаме да предскажем липсващия рейтинг на даден потребител във филм, ние просто вземаме всички характеристики на този филм, умножаваме по всички тегла на този потребител и обобщаваме всичко. Така че, в моя пример, ако искам да предскажа рейтинга на Потребител 2 на Филм 1, мога да направя следното изчисление:

За да направим нещата по-ясни, можем да разделим θ и x и да ги поставим в техните собствени матрици (да речем P и Q ). Това на практика е матрична факторизация, откъдето идва и името, използвано от проф. Нг.

Тази матрична факторизация е основно това, което направи Фънк. Той получи трето място в състезанието на Netflix, привличайки много внимание (което е интересен случай на трето място да е по-известно от победителите). Оттогава подходът му е възпроизведен и усъвършенстван и все още се използва в много приложения.

Разлагане на единична стойност

Въведете декомпозиция на единична стойност (SVD). SVD е изискан начин за разлагане на матрица на три други матрици ( A = UΣVᵀ ). Начинът, по който се прави SVD, гарантира, че тези 3 матрици носят някои хубави математически свойства.

Има много приложения за SVD. Един от тях е анализът на основните компоненти (PCA), който просто намалява набор от данни с измерение n до измерение k ( k <n ).

Няма да ви давам повече подробности за SVD, защото не познавам себе си. Въпросът е, че това не е същото като това, което направихме с факторизацията на матрицата. Най-голямото доказателство е, че SVD създава 3 матрици, докато факторизацията на матрицата на Funk създава само 2.

И така, защо SVD продължава да се появява всеки път, когато търся препоръчващи системи? Трябваше да ровя малко, но в крайна сметка намерих някои скрити скъпоценни камъни. Според Луис Аргерих:

Алгоритмите за факторизация на матриците, използвани за препоръчващи системи, се опитват да намерят две матрици: P, Q като P * Q съответства на ЗНАЕМИТЕ стойности на матрицата на помощната програма. Този принцип се появи в известния документ SVD ++ „Факторизацията отговаря на квартала“, който за съжаление използва името „SVD ++“ за алгоритъм, който няма абсолютно никаква връзка със SVD .

За протокол, мисля, че Фънк, а не авторите на SVD ++, първо предложи споменатата факторизация на матрицата за препоръчващи системи. Всъщност SVD ++, както подсказва името му, е продължение на работата на Фънк.

Xavier Amatriain ни дава по-голяма картина:

Нека започнем, като посочим, че методът, обикновено наричан „SVD“, който се използва в контекста на препоръките, не е строго казано математическото разлагане на единична стойност на матрица, а по-скоро приблизителен начин за изчисляване на апроксимацията на ниския ранг на матрицата чрез свеждане до минимум на квадратите загуба на грешка. По-точен, макар и по-общ начин да се нарече това би бил факторизацията на матрицата. Първоначалната версия на този подход в контекста на наградата Netflix беше представена от Саймън Фънк в неговия известен блог пост Try This at Home. Важно е да се отбележи, че подходът „истински SVD“ наистина е бил прилаган към една и съща задача години преди това, с не толкова практически успех.

Уикипедия също има подобна информация, заровена в статията си за факторизация на матрицата (препоръчващи системи):

Оригиналният алгоритъм, предложен от Саймън Фънк в публикацията си в блога, раздели матрицата за оценка на потребителските елементи като продукт на две матрици с по-ниски размери, като първата има ред за всеки потребител, докато втората има колона за всеки елемент. Редът или колоната, свързани с конкретен потребител или елемент, се наричат ​​латентни фактори. Имайте предвид, че въпреки името си, във FunkSVD не се прилага разлагане на единична стойност.

Да обобщим:

1. SVD е малко сложна математическа техника, която разлага на матрици три нови матрици и има много приложения, включително PCA и RS.

2. Саймън Фънк прилага много интелигентна стратегия в състезанието за Netflix през 2006 г., разлагайки матрица на две други и използвайки градиентно спускане, за да намери оптимални стойности на характеристиките и теглото. Това не е SVD , но той все пак използва този термин, за да опише своята техника.

3. Най-подходящият термин за това, което направи Фънк, е факторизация на матрицата.

4. Поради добрите резултати и славата, която последва, хората все още наричат ​​тази техника SVD, тъй като, е, така я нарече авторът.

Надявам се, че това помага да се изяснят малко нещата.