Matrix Decomposition Methods for Data Mining : Computational Complexity and Algorithms

Matrix decompositions, where a given matrix is represented as a product of two other matrices, are regularly used in data mining. Most matrix decompositions have their roots in linear algebra, but the needs of data mining are not always those of linear algebra. In data mining one needs to have results that are interpretable -- and what is considered interpretable in data mining can be very different to what is considered interpretable in linear algebra. --- The purpose of this thesis is to study matrix decompositions that directly address the issue of interpretability. An example is a decomposition of binary matrices where the factor matrices are assumed to be binary and the matrix multiplication is Boolean. The restriction to binary factor matrices increases interpretability -- factor matrices are of the same type as the original matrix -- and allows the use of Boolean matrix multiplication, which is often more intuitive than normal matrix multiplication with binary matrices. Also several other decomposition methods are described, and the computational complexity of computing them is studied together with the hardness of approximating the related optimization problems. Based on these studies, algorithms for constructing the decompositions are proposed. Constructing the decompositions turns out to be computationally hard, and the proposed algorithms are mostly based on various heuristics. Nevertheless, the algorithms are shown to be capable of finding good results in empirical experiments conducted with both synthetic and real-world data.

Intermediate Past BE : A Paradigm Reshaped With Data Drawn From HARES

In this paper, I look into a grammatical phenomenon found among speakers of the Cambridgeshire dialect of English. According to my hypothesis, the phenomenon is a new entry into the past BE verb paradigm in the English language. In my paper, I claim that the structure I have found complements the existing two verb forms, was and were, with a third verb form that I have labelled ‘intermediate past BE’. The paper is divided into two parts. In the first section, I introduce the theoretical ground for the study of variation, which is founded on empiricist principles. In variationist linguistics, the main claim is that heterogeneous language use is structured and ordered. In the last 50 years of history in modern linguistics, this claim is controversial. In the 1960s, the generativist movement spearheaded by Noam Chomsky diverted attention away from grammatical theories that are based on empirical observations. The generativists steered away from language diversity, variation and change in favour of generalisations, abstractions and universalist claims. The theoretical part of my paper goes through the main points of the variationist agenda and concludes that abandoning the concept of language variation in linguistics is harmful for both theory and methodology. In the method part of the paper, I present the Helsinki Archive of Regional English Speech (HARES) corpus. It is an audio archive that contains interviews conducted in England in the 1970s and 1980s. The interviews were done in accordance to methods used generally in traditional dialectology. The informants are mostly elderly male people who have lived in the same region throughout their lives and who have left school at an early age. The interviews are actually conversations: the interviewer allowed the informant to pick the topic of conversation to induce a maximally relaxed and comfortable atmosphere and thus allow the most natural dialect variant to emerge in the informant’s speech. In the paper, the corpus chapter introduces some of the transcription and annotation problems associated with spoken language corpora (especially those containing dialectal speech). Questions surrounding the concept of variation are present in this part of the paper too, as especially transcription work is troubled by the fundamental problem of having to describe the fluctuations of everyday speech in text. In the empirical section of the paper, I use HARES to analyse the speech of four informants, with special focus on the emergence of the intermediate past BE variant. My observations and the subsequent analysis permit me to claim that my hypothesis seems to hold. The intermediate variant occupies almost all contexts where one would expect was or were in the informants’ speech. This means that the new variant is integrated into the speakers’ grammars and exemplifies the kind of variation that is at the heart of this paper.

"America Would Lose Its Soul" : The Immigration Restriction Debate, 1920-1924

Vuosien 1830 ja 1924 välillä Yhdysvaltoihin muutti noin 35 miljoonaa eurooppalaista. Tämä niinkutsuttu "maahanmuuton vuosisata" päättyi varsin äkillisesti kun Yhdysvallat päätti rajoittaa maahanmuuttoa 1920-luvulla. Vuosina 1921 ja 1924 säädetyt lait asettivat kansallisuuteen perustuvat kiintiöt kaikille eurooppalaisille maahanmuuttajille; vuoden 1924 laki myös lopetti kokonaan japanilaisten maahanmuuton. Tämä työ tutkii näihin kiintiölakeihin johtanutta maahanmuuttajavastaisuuden kasvua sekä etenkin lakien ympärillä käytyä keskustelua. Pääpaino on kongressissa esitetyissä maahanmuuton vastaisissa argumenteissa. Nämä jakautuivat karkeasti ottaen kolmeen kategoriaan: maahanmuuton vastustajat sanoivat, että siirtolaisten vaikutus taloudelliseen tilanteeseen oli epäsuotuisa, siirtolaisten rodullinen ja kulttuurinen "laatu" oli huonontunut, ja siirtolaiset olivat radikaaleja ja bolshevismiin taipuvaisia. Erityistä huolta herätti maahanmuuttajien vaikutus Amerikan kulttuuriseen, rodulliseen ja poliittiseen yhtenäisyyteen. Huoli kansakunnan yhtenäisyydestä oli tulosta paitsi siirtolaisten määrästä myös amerikkalaisessa yhteiskunnassa tapahtuneista muutoksista. Erityisen tärkeitä olivat työväenliikkeen vaikutusvallan kasvu ja teollisuusjohtajien pyrkimys pysäyttää se. Maahanmuuttajien "bolshevismi" olikin käyttökelpoinen argumentti paitsi maahanmuuttajia myös amerikkalaisia työläisiä vastaan: teollisuusjohtajat painottivat että lakot ja työväenliike olivat tulosta siirtolaisten mukanaan tuomista "epäamerikkalaisista" ajatusmalleista, eivät yhteiskunnan epäoikeudenmukaisuudesta. Kongressin keskustelun lisäksi työssä käsitellään myös eri yhteiskunnallisten ryhmien ja vaikuttajien kantaa siirtolaisuuteen. Keskusteluun maahanmuutosta vaikuttivat etenkin eugenistit ja muut sosiaalitieteilijät, jotka väittivät itä- ja eteläeurooppalaisten olevan rodullisesti anglosakseja huonompia. Tämän väitteen vaikutusvaltaa lisäsivät yhteiskunnassa vallalla olleet ennakkoluulot, ja monet yhdistykset ja liikkeet (mm. Ku Klux Klan ja erilaiset isänmaalliset järjestöt) olivatkin tärkeitä rajoittamisen kannattajia. Keskustelu maahanmuutosta painottui ideologisiin ja tunteellisiin kysymyksiin, mutta rajoitusten taustalla oli myös konkreettisempia tekijöitä. Yhteiskunnan teollistuminen ja kaupungistuminen olivat pienentäneet siirtolaisista koituvaa taloudellista hyötyä: siirtolaisia ei enää tarvittu raivaamaan uusia viljelysmaita, kun taas tuotannon koneistuminen vähensi työvoiman tarvetta huomattavasti. Pitkän aikavälin taloudellisten tekijöiden roolin merkitys käy ilmeiseksi kun otetaan huomioon, että muut maahanmuuttomaat (esim. Kanada ja Australia) eivät juuri rajoittaneet siirtolaisuutta tänä aikana vaikka niissäkin esiintyi runsaasti rodullista ja kulttuurista maahanmuuttajavastaisuutta. Pääsyy rajoitusten vähäisyyteen näissä maissa oli juuri maahanmuuttajien tuoma taloudellinen hyöty, sekä teollisena työvoimana että maanviljelijöinä. Vaikka kiintiölakiehdotusten ympärillä käytiin kiivasta väittelyä, kongressi kuitenkin hyväksyi lait varsin suurella enemmistöllä. Siirtolaisia itseään lukuunottamatta varsin harvat näkivät lait haitallisina, kun taas useat erilaiset ryhmät katsoivat hyötyvänsä maahanmuuton rajoittamisesta. Avainsanat: siirtolaisuus, maahanmuutto, Yhdysvallat, 1920-luku, kiintiölait, maahanmuuton rajoittaminen