Računalna analiza sličnosti matematičkih zadataka zadanih riječima

undergraduate thesis

• Title (english): Computational Analysis of the Similarity of Math Word Problems
• Author: Doria Šarić
• Mentor: Jan Šnajder (mentor)
• Committee member: Jan Šnajder (predsjednik povjerenstva)
• Committee member: Mladen Karan (član povjerenstva)
• Committee member: Domagoj Alagić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-09-08, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Cilj ovog rada bio je napraviti sustav za kategorizaciju matematičkih zadataka.
Tvrtka PhotoMath prije nekoliko je godina uspješno izašla na tržiste sa istoimenom
aplikacijom koja omogućuje korisnicima da mobitelom skeniraju zadatak te u kratkom
vremenu dobiju detaljan postupak rješavanja. PhotoMath mi je dao priliku da riješim
ovaj problem i osigurao vlastiti skup podataka za ovaj rad. Svaki matematički za-
datak predstavljen je stablom naredbi odnosno postupaka koji čine rješenje zadatka.
Svakom zadatku cilj je pridijeliti matematičku kategoriju. Sve su kategorije ranije
definirane taksonomijom te svaka kategorija predstavlja neko matematičko područje.
Implementirana su dva različita pristupa. Prvi je pristup obuhvaćao pretvorbu stabla
postupaka u pripadajuće vektore značajki. Vektori su bili generirani tako da sadržavaju
i informacije o strukturi podataka. Nad vektorima značajki zatim se radila klasifikacija
podataka. Rezultati su se pokazali poprilično uspješnima. Drugi pristup sastojao se
od izgradnje matrice med̄usobne sličnosti svih podataka u skupu. Isprobane su dvije
metode mjerenja sličnosti izmed̄u stabla. Najbolje rezultate postigla je mjera sličnosti
koja ovisi o broju zajedničkih naredbi saržanih u oba stabla. Druga metoda pokazala
se manje učinkovitom.

Abstract (english)

The task of this thesis was to build a system that can classify computer-solvable
mathematical tasks into predefined mathematical categories. A few years ago, a com-
pany named PhotoMath released its homonymous app that is able to output solution
steps to the user after recognizing the mathematical task scanned with a mobile phone.
They provided me with the data set and the idea for this project. Each mathematical
category represents some area of mathematics. The categories are hierarchically re-
lated. Each task is represented by a corresponding solver tree. Solver tree is a tree
that consists of steps which explain task resolution to the user. There were two main
ideas to implement. The first approach consisted of mapping solver trees from each
task in the data set to a vector in the feature space. Although this approach may not
be optimal, the results are quite successful. The cause of that might be that our trans-
formation to feature space encoded the tree structure into feature vectors to the right
extent. In contrast, the second approach avoids operating on feature space directly and
uses kernel methods. I have implemented two kernel functions and passed their refer-
ence to Support Vector Machine. The first kernel function calculated a kernel based on
the string similarities between trees encoded as strings. This method proved even more
successful than the first approach with mapping solver trees to the feature space. Later
on, I implemented a kernel function that generates a kernel matrix based on common
subpaths in solver trees. Despite my expectations, this proved to be much less efficient.

• Keywords: višeklasna klasifikacija; sličnost kod stabla; kernel metode; hijerarhijska klasifikacija; kategorizacija matematičkih zadataka; strojno učenje; kernelizirana klasifikacija
• Keywords (english): hierarchical multinomial classification; hierarchical data; tree similarity; mathematical categories; task categorization; classification; kernel; machine learning
• Language: english
• URN:NBN: urn:nbn:hr:168:605367
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-14 01:07:59