Original title:
Zlepšování škálovatelnosti doporučovacích systémů pomocí řídkých přibližných inverzů
Translated title:
Sparse Approximate Inverse for Enhanced Scalability in Recommender Systems
Authors:
Spišák, Martin ; Peška, Ladislav (advisor) ; Vančura, Vojtěch (referee) Document type: Master’s theses
Year:
2023
Language:
eng Abstract:
[eng][cze] In theory, the linear autoencoder EASE is one of the most capable collaborative filtering recommenders for large item domains with sparse user-item feedback. However, the model's weights are determined by the inverse of a matrix of dimension equal to the item set size. This inverse matrix is generally dense, and for large item sets, the computed weight matrix might be too large to store in memory during inference. Consequently, scaling the model beyond tens of thousands of items quickly becomes very expensive. We propose a modification of EASE called SANSA to alleviate the issue. SANSA approximates the weights of EASE with prescribed density via an end-to-end sparse training procedure. To find a method capable of computing the sparse approximation efficiently, we investigate approaches for constructing sparse approximate inverse precon- ditioners. We select a method fitting for very large SPD problems with general sparsity patterns. The training procedure is robust and finds a good approximation of EASE even on datasets with dense item relations. Moreover, as the number of items in datasets grows, SANSA achieves unparalleled efficiency, even compared to EASE's previous state- of-the-art modification focused on scalability. Consequently, SANSA effortlessly scales the concept of EASE to millions of items. 1Lineárny autoenkóder EASE by mal byť jedným z najvýkonnejších odporúčacích sys- témov na báze kolaboratívneho filtrovania pre veľké katalógy položiek s riedkou spätnou väzbou od používateľov. Váhy modelu sú však určené inverznou maticou dimenzie rovnej veľkosti katalógu. Táto inverzná matica je obvykle hustá, v dôsledku čoho môže byť v prípade veľkého počtu položiek váhová matica priveľká na držanie v pamäti počas in- ferencie. Výpočetné náklady na škálovanie modelu nad desiatky tisíc položiek tak veľmi prudko stúpajú. V práci navrhujeme modifikáciu EASE s názvom SANSA, ktorá tento problém rieši. SANSA aproximuje váhy EASE so zvolenou hustotou. Túto aproximáciu nájde pomocou end-to-end riedkej trénovacej procedúry. Pre voľbu metódy schopnej efektívne spočí- tať riedku aproximáciu veľkej inverznej matice, skúmame prístupy pre konštrukciu ried- kych približných inverzov pre účely predpodmienenia sústav lineárnych rovníc. Vybraná metóda je vhodná pre veľmi veľké sústavy so všeobecným vzorom riedkosti. Trénovacia procedúra je robustná a nájde dobrú aproximáciu modelu EASE aj na súboroch dát s hustými vzťahmi medzi položkami. Navyše, so zvyšujúcim sa počtom položiek v katalógu dosahuje SANSA bezkonkurenčnú efektivitu, a to aj v porovnaní s predchádzajúcou na- jefektívnejšou modifikáciou modelu EASE zameranou na...
Keywords:
EASE^R|(Sparse) approximate inverse|recommender systems; EASE^R|(Sparse) approximate inverse|recommender systems
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/184373