Декомпозиција сингуларне вредности наспрам факторизације матрице у системима препоручивача

Недавно, након што сам погледао часове система препоруке на курсу машинског учења проф. Андрев-а Нг-а, осетио сам да ми је јако нелагодно не разумевајући како функционише матрична факторизација.

Знам да је понекад математика у машинском учењу врло нејасна. Боље је ако о томе размишљамо као о црној кутији, али тај модел је био врло „магичан“ за моје стандарде.

У таквим ситуацијама обично покушавам да на Гоогле-у потражим више референци како бих боље разумео концепт. Овај пут сам се још више збунио. Иако је професор Нг алгоритам назвао факторизацијом матрице (ниског фактора), на интернету сам пронашао другачију номенклатуру: Декомпозиција сингуларне вредности.

Највише ме је збунило то што се распад сингуларне вредности веома разликовао од онога што је предавао проф. Нг. Људи су стално наговештавали да су обоје иста ствар.

У овом тексту сумираћу своја открића и покушати да разјасним део забуне коју ти појмови могу да изазову.

Системи за препоруке

Системи препоручивача (РС) само су аутоматизовани начини да се некоме нешто препоручи. Такве системе широко користе компаније за е-трговину, услуге стреаминга и веб локације са вестима. Помаже у смањивању трења корисника када покушавају да пронађу нешто што им се свиђа.

РС дефинитивно нису нова ствар: појављују се најмање од 1990. године. У ствари, део недавне хипе о машинском учењу може се приписати интересовању за РС. Нетфлик је 2006. године пролетео када је спонзорисао такмичење у проналажењу најбољег РС за своје филмове. Као што ћемо ускоро видети, тај догађај повезан је са номенклатурном збрком која је уследила.

Матрични приказ

Постоји много начина на које особа може смислити да некоме препоручи филм. Једна од стратегија која се показала врло добром је третирање рејтинга филмова као матрице Корисници к филмови попут ове:

У тој матрици упитници представљају филмове које корисник није оценио. Тада је стратегија некако предвидети те оцене и препоручити корисницима филмове који ће им се вероватно свидети.

Факторизација матрице

Заиста паметно схватање момака који су се пријавили на Нетфлик-ово такмичење (посебно Симон Функ) било је да оцене корисника нису биле само случајне претпоставке. Оцењивачи вероватно следе неку логику где пондерирају ствари које им се свиђају у филму (одређена глумица или жанр) према стварима које им се не свиђају (дуго трајање или лоше шале), а затим смисле резултат.

Тај процес може бити представљен линеарном формулом следеће врсте:

где је кₘ вектор колоне са вредностима обележја филма м, а θᵤ је други вектор колоне са пондерима које корисник у даје свакој особини. Сваки корисник има различит скуп тежина, а сваки филм има различит скуп вредности за своје карактеристике.

Испада да ако произвољно поправимо број обележја и занемаримо оцене које недостају, можемо пронаћи скуп пондера и вредности карактеристика који креирају нову матрицу са вредностима блиским оригиналној матрици оцена. То се може постићи градијентним спуштањем, врло сличним оном који се користи у линеарној регресији. Уместо тога, сада истовремено оптимизујемо два скупа параметара (тежине и карактеристике).

Користећи табелу коју сам дао као пример изнад, резултат проблема са оптимизацијом генерисао би следећу нову матрицу:

Приметите да резултујућа матрица не може бити тачна копија оригиналне у већини стварних скупова података, јер у стварном животу људи не врше множења и збрајања да би оценили филм. У већини случајева оцена је само осећај стомака на који такође могу утицати све врсте спољних фактора. Ипак, надамо се да је линеарна формула добар начин да се изрази главна логика која покреће оцене корисника.

ОК, сада имамо приближну матрицу. Али како нам то, до врага, помаже да предвидимо оцене које недостају? Запамтите да смо за изградњу нове матрице креирали формулу за попуњавање свих вредности, укључујући оне које недостају у оригиналној матрици. Дакле, ако желимо да предвидимо оцену која недостаје кориснику на филму, ми само узмемо све карактеристике тог филма, помножимо са свим тежинама тог корисника и све сумирамо. Дакле, у мом примеру, ако желим да предвидим оцену корисника 2 за филм 1, могу да извршим следећи прорачун:

Да бисмо ствари постале јасније, можемо раздвојити θ и к и ставити их у своје матрице (рецимо П и К ). То је у ствари матрична факторизација, па отуда и назив који користи проф. Нг.

Та матрична факторизација је у основи оно што је Функ урадио. Добио је треће место у Нетфликовој конкуренцији, привукавши велику пажњу (што је занимљив случај да је треће место познатије од победника). Његов приступ је поновљен и усавршен од тада и још увек се користи у многим апликацијама.

Декомпозиција сингуларне вредности

Унесите декомпозицију сингуларне вредности (СВД). СВД је отмен начин да се матрица факторизира на три друге матрице ( А = УΣВᵀ ). Начин на који се врши СВД гарантује да те 3 матрице носе нека лепа математичка својства.

Постоји много апликација за СВД. Једна од њих је Анализа главне компоненте (ПЦА), која управо смањује скуп података димензије н на димензију к ( к <н ).

Нећу вам даље давати детаље о СВД-има, јер ни сам не знам. Ствар је у томе што то није иста ствар као што смо то урадили са Факторизацијом матрице. Највећи доказ је да СВД ствара 3 матрице, док Функ-ова факторизација матрице ствара само 2.

Па зашто се СВД појављује сваки пут када тражим системе за препоруке? Морао сам мало да копам, али на крају сам пронашао неке скривене драгуље. Према Луису Аргерицху:

Алгоритми за факторизацију матрице који се користе за системе који препоручују покушавају да пронађу две матрице: П, К, попут П * К, подудара се са ПОЗНАТИМ вредностима матрице корисности. Овај принцип појавио се у чувеном СВД ++ документу „Факторизација у сусрет суседству“ који је нажалост користио назив „СВД ++“ за алгоритам који нема апсолутно никакву везу са СВД-ом .

За записник, мислим да је Функ, а не аутори СВД ++, прво предложио поменуту факторизацију матрице за системе који препоручују. У ствари, СВД ++, као што му само име говори, представља продужетак Функовог дела.

Ксавијер Аматриаин даје нам ширу слику:

Почнимо са указивањем да метода која се обично назива „СВД“ и која се користи у контексту препорука није стриктно математичка декомпозиција сингуларне вредности матрице, већ приближан начин израчунавања апроксимације матрице ниског ранга минимизирањем квадрата изгубљених грешака. Тачнији, иако општији начин да се то назове био би факторизација матрице. Почетну верзију овог приступа у контексту награде Нетфлик представио је Симон Функ у свом познатом блогу Три Тхис ат Хоме. Важно је напоменути да се приступ „истинског СВД-а“ заиста примењивао на исти задатак годинама раније, са не толико практичним успехом.

Википедиа такође има сличне информације закопане у чланку о факторизму матрице (системи препоруке):

Оригинални алгоритам који је предложио Симон Функ у свом блогу факторизовао је матрицу оцењивања корисничких ставки као производ две матрице ниже димензије, прва има ред за сваког корисника, док друга има ступац за сваку ставку. Ред или колона повезани са одређеним корисником или ставком називају се латентним факторима. Имајте на уму да се, упркос свом имену, у ФункСВД не примењује декомпозиција појединачне вредности.

Да резимирамо:

1. СВД је помало сложена математичка техника која чини матрице у три нове матрице и има много примена, укључујући ПЦА и РС.

2. Симон Функ је применио врло паметну стратегију на такмичењу Нетфлик 2006. године, факторизирајући матрицу на две друге и користећи градијентни спуст да пронађе оптималне вредности карактеристика и тежине. То није СВД , али је тај израз ипак користио да опише своју технику.

3. Најприкладнији израз за оно што је Функ урадио је матрична факторизација.

4. Због добрих резултата и славе која је уследила, људи и даље називају ту технику СВД, јер, ето, тако ју је аутор назвао.

Надам се да ово помаже да се ствари мало разјасне.