Data embedding and fusion by tropical matrix factorization

Omanović, Amra (author), Oblak, Polona (mentor), Curk, Tomaž (co-mentor)

Data embedding and fusion represent one of the main challenges in machine learning. Meaningful low-dimensional representations of real-world data help algorithms to perform different data mining and prediction tasks successfully. Matrix factorization methods embed data into a latent space using a two-factorization or tri-factorization approaches. These methods mostly use standard linear algebra, which is limited in modeling complex patterns. The non-linearity can be modeled by using tropical semiring, which enables a better approximation of extreme values and distributions, thus discovering high-variance patterns that differ from those found by standard linear algebra. The motivation for creating data embedding and fusion methods by tropical matrix factorization is found in properties such as non-linearity, the ability to interpret results easily, the intuition behind path-finding problems in graphs, connections with neural networks, and the lack of tropical methods in data mining and machine learning. In the thesis, we design novel models and algorithms for data embedding and fusion based on tropical matrix factorization with theoretical and experimental evaluation. We have developed a sparse tropical matrix factorization (STMF), which returns two factor matrices and performs matrix completion. We apply STMF to predict gene expression values on multiple TCGA datasets. We show that STMF expresses extreme values very well and is robust to overfitting. The main drawback of STMF is slow computational performance, so we propose an efficient version of STMF called FastSTMF. Results showed that FastSTMF outperforms STMF by achieving higher performance, such as faster convergence speed and better approximation results. In data fusion, tri-factorization methods achieve superior results than two-factorization by utilizing an intermediate approach for fusion of multiple data sources. We present the tropical matrix tri-factorization algorithm called triFastSTMF, which we apply to recover the edge lengths of a four-partition network. We use triFastSTMF to create a tropical data fusion method (tropDF) and show its correctness and convergence through experimental evaluation.

• Language: English
• Keywords: data mining, data embedding, matrix factorization, tropical factorization, subtropical semiring, tropical semiring, sparse data, matrix completion
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2023
• PID: 20.500.12556/RUL-151928
• COBISS.SI-ID: 172011011
• Publication date in RUL: 25.10.2023

Secondary language

• Language: Slovenian
• Title: Vložitev in zlivanje podatkov s tropsko matrično faktorizacijo

Abstract

Vložitev in zlivanje podatkov predstavljata glavna izziva strojnega učenja. Smiselne nizkodimenzionalne predstavitve podatkov iz resničnega sveta pomagajo algoritmom pri uspešnem izvajanju različnih nalog podatkovnega rudarjenja in napovedovanja. Metode matrične faktorizacije vložijo podatke v latentni prostor z uporabo pristopa dvofaktorizacije ali trifaktorizacije. Omenjena pristopa večinoma uporabljata standardno linearno algebro, ki je omejena pri modeliranju kompleksnih vzorcev. Nelinearnost lahko dosežemo z uporabo tropskega polkolobarja, ki omogoča boljše modeliranje ekstremnih vrednosti in porazdelitev, s čimer odkrijemo vzorce visoke variance, ki se razlikujejo od tistih, ki jih najdemo z uporabo standardne linearne algebre. Motivacijo za razvoj metod vlaganja in zlivanja podatkov s tropsko matrično faktorizacijo najdemo v lastnostih, kot so nelinearnost, zmožnost enostavne interpretacije rezultatov, intuicija za probleme iskanja poti v grafih, povezave z nevronskimi mrežami in pomanjkanje tropskih metod na področju podatkovnega rudarjenja in strojnega učenja. V delu predstavimo nove metode in algoritme za vlaganje in zlivanje podatkov, ki temeljijo na tropski matrični faktorizaciji s teoretično in eksperimentalno analizo. Razvili smo tropsko matrično faktorizacijo redkih matrik (STMF), ki vrne dve faktorski matriki in izvede dopolnjevanje matrike. STMF smo uporabili za napovedovanje vrednosti izražanja genov na več nizih podatkov TCGA. Pokazali smo, da STMF zelo dobro izraža skrajne vrednosti in je robusten na prekomerno prileganje podatkom. Glavna pomanjkljivost STMF je visoka računska zahtevnost, zato smo predlagali učinkovito različico STMF, imenovano FastSTMF. Rezultati so pokazali, da FastSTMF presega STMF, saj hitreje konvergira in boljše modelira podatke. Pri zlivanju podatkov metode trifaktorizacije,z uporabo pristopa vmesnega zlivanja več virov podatkov, dosegajo boljše rezultate kot metode dvofaktorizacije. V delu predstavimo tropski trifaktorizacijski algoritem matrične faktorizacije, imenovan triFastSTMF. Uporabili smo ga za napovedovanje dolžine povezav grafa s štirimi particijami. triFastSTMF smo uporabili za razvoj metode tropskega zlivanja podatkov (tropDF) in empirično pokazali njeno pravilnost in konvergenco.

• Keywords: podatkovno rudarjenje, vložitev podatkov, matrična faktorizacija, tropska faktorizacija, subtropski polkolobar, tropski polkolobar, redki podatki, dopolnitev matrike