Prestatieverbeterende technieken voor tensorontbindingen in data-analyse

Mettertijd groeien datasets niet alleen qua grootte, maar in vele gevallen ook op het vlak van dimensionaliteit. Numerieke data in de vorm van tabellen met 3 of meer dimensies, ook wel tensoren genoemd, komen regelmatig voor als hyperspectrale afbeeldingen, diffusietensorbeelden, simulatieresultaten, röntgenscans, enzovoort. Zelfs relationele databanken kunnen voorgesteld worden als ijle tensoren. Ten gevolge van deze trend zijn er tensorontbindingen ontwikkeld om dergelijke multidimensionale data te verwerken. De Tuckerontbinding is binnen deze verzameling een erg populair hulpmiddel voor dataverwerking alsook de voorverwerking van tensoren voor verdere analyse. Aangezien het veld van de numerieke multilineaire algebra nog steeds relatief jong is, zijn vele problemen gerelateerd aan deze ontbinding slechts suboptimaal of helemaal niet opgelost, zeker op het gebied van efficiënte algoritmische implementaties.

Het doel van deze thesis is om technieken te ontwikkelen die de prestaties van bestaande oplossingen voor enkele van de voornoemde problemen verbeteren, zowel op het vlak van algoritme- als implementatieverbeteringen. We verifiëren de prestaties van onze voorgestelde technieken aan de hand van experimenten met datasets uit de praktijk. Binnen de context van deze doelstellingen worden twee hoofdproblemen onderzocht.

In het eerste deel richten we ons op het probleem van Tuckergebaseerde datacompressie van tensoren tot op het byteniveau. Hiervoor bouwen we voort op de algoritmische pijplijn van de state-of-the-art TTHRESH-compressor om onze eigen nieuwe compressiesoftware te ontwikkelen, genaamd "de geavanceerde Tuckercompressor" (ATC). We stellen een reeks algoritmische aanpassingen voor om snelheid, geheugengebruik, compressie-efficiëntie en foutencontrole te verbeteren. Ten eerste beschrijven we een hybride-afknottingsmethode voor waarin zowel rang- als bitvlakafknotting gecombineerd worden terwijl we controle over de compressiefout behouden. Ten tweede paralleliseren we de kwantiserings- en encoderingsfasen, welke een belangrijk deel van de compressieprocedure omvatten. Ten derde verbeteren we de foutencontrole drastisch door de dekwantisatiecorrectie in rekening te brengen gedurende compressie. Verder stellen we veel andere, kleinere optimalisaties voor en beschrijven we verschillende belangrijke implementatie-aspecten. Onze experimenten tonen aan dat ATC state-of-the-art compressie-efficiëntie behoudt terwijl de software versnellingen behaalt van 2,2 tot 3,5, het geheugengebruik halveert en de compressiefout 25 keer preciezer controleert. Vergeleken met niet-Tuckergebaseerde compressoren behaalt ATC ook veel grotere compressiefactoren in het hogecompressiedomein. Ten slotte is ATC ook ontworpen als een hoogwaardige geparalleliseerde softwarebibliotheek, met verschillende interfaces, een brede ondersteuning voor datatypes, verschillende types in- en output alsook uitgebreide documentatie.

In het tweede deel verkennen we het probleem van het berekenen van ijle tensor- maal-matrix-kettingen (TTMC's), een cruciale stap gedurende de berekening van Tuckerontbindingen. We beschrijven het intermediaire-opblaasprobleem dat optreedt bij het gebruik van naïeve methoden en bespreken verschillende oplossingen, wat leidt tot het state-of-the-art algoritme gebaseerd op het gecomprimeerde-ijlevezelformaat (CSF) voor ijle tensoren. We stellen drie afgeleide algoritmen voor gebaseerd op het principe van volledige accumulatie om de prestaties van deze methode verder te verbeteren zonder het gebruik van overbodige tensorvoorstellingen. Binnen deze context halveren onze algoritmen de kost van laat-één-weg-TTMC's en reduceren deze ook het aantal nodige operaties voor en de uitvoeringstijd van volledige TTMC's met respectievelijk 70% en 38%. Ten slotte observeren we ook enorme afnames in het geheugengebruik van 23x tot 75x vergeleken met de referentie-implementatie van het bestaande CSF-gebaseerde werk.