Een semi-gesuperviseerde leermethode voor de
ontwikkeling van modellen die spraakverstaanbaarheid
berekenen
Evi Weymaere
Promotor: prof. dr. ir. Jean-Pierre Martens
Masterproef ingediend tot het behalen van de academische graad van
Master of Science in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Elektronica en Informatiesystemen
Voorzitter: prof. dr. ir. Jan Van Campenhout
Faculteit Ingenieurswetenschappen en Architectuur
Academiejaar 2013-2014
Een semi-gesuperviseerde leermethode voor de
ontwikkeling van modellen die spraakverstaanbaarheid
berekenen
Evi Weymaere
Promotor: prof. dr. ir. Jean-Pierre Martens
Masterproef ingediend tot het behalen van de academische graad van
Master of Science in de ingenieurswetenschappen: computerwetenschappen
Vakgroep Elektronica en Informatiesystemen
Voorzitter: prof. dr. ir. Jan Van Campenhout
Faculteit Ingenieurswetenschappen en Architectuur
Academiejaar 2013-2014
Voorwoord
Ik wil graag van dit voorwoord gebruik maken om enkele mensen te bedanken.
Als eerste wil ik graag mijn promotor, professor Jean-Pierre Martens, bedanken voor alle
brainstorming, kritische opmerkingen en feedback die ik gedurende dit jaar kreeg. Bedankt
ook aan mijn begeleiders, Catherine Middag en Dries Lagae voor alle hulp en feedback die
ervoor gezorgd hebben dat deze thesis tot stand is kunnen komen.
Oneindig veel dank aan mijn ouders en mijn zus voor hun onvoorwaardelijke steun en medeleven. Ik heb hen de laatste vijf jaar zonder twijfel meegesleurd in allerlei emoties, zowel
positieve als negatieve. Op momenten dat ik het niet meer zag zitten, gaven ze me dat extra
duwtje dat ik nodig had. Bij elke verwezenlijking waren ze trots in mijn plaats. Dank jullie
wel mama, papa en Jana, zonder jullie had ik nooit kunnen bereiken waar ik nu ben.
Tenslotte wil ik ook graag mijn vrienden, en dan in het bijzonder Thibault bedanken voor
de vijf fijne jaren. Jullie maakten de lessen aangenamer, de stressvolle momenten lichter en
zorgden voor nooit te vergeten herinneringen. Dankzij jullie kan ik naar mijn studentenjaren
terugkijken als de beste vijf jaar van mijn leven.
i
Toelating tot bruikleen
De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen
ervan te kopi¨eren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van
het auteursrecht, in het bijzonder met betrekking tot de verplichting uitdrukkelijk de bron
te vermelden bij het aanhalen van resultaten uit deze scriptie.
Gent, Juni 2014
De auteur
Evi Weymaere
ii
Een semi-gesuperviseerde leermethode voor de
ontwikkeling van modellen die
spraakverstaanbaarheid berekenen
Evi Weymaere
Promotor: prof. dr. ir. Jean-Pierre Martens
Masterproef ingediend tot het behalen van de academische graad van Master of
Science in de Ingenieurswetenschappen: computerwetenschappen
Vakgroep Elektronica en Informatiesystemen
Voorzitter: prof. dr. ir. Jan Van Campenhout
Faculteit Ingenieurswetenschappen en Architectuur
Academiejaar 2013-2014
Samenvatting
Het is vaak erg moeilijk om aan correct gescoorde spraakfragmenten te geraken voor het voorspellen van bijvoorbeeld de verstaanbaarheid van pathologische spraak op basis van akoestische kenmerken die door spraakanalyse uit die spraak werden afgeleid. In deze thesis gaat
men op zoek naar semi-gesuperviseerde leermethoden die naast gescoorde fragmenten ook
niet-gescoorde fragmenten uitbuiten teneinde tot betere modellen te komen dan degene die
uitsluitend uit de gescoorde fragmenten zijn afgeleid. Er zullen verschillende methoden uitgeprobeerd en vergeleken worden met de gesuperviseerde methode die enkel de gescoorde data
gebruikt.
Kernwoorden
semi-gesuperviseerd leren, co-training, spraakverstaanbaarheid
iii
A semi-supervised learning method for the
development of models that compute speech
intelligibility
Evi Weymaere
Supervisor(s): Jean-Pierre Martens, Catherine Middag, Dries Lagae
Abstract—It is often very hard to retrieve correctly scored speech
fragments to predict for example pathological speech intelligibility
based on the acoustic features that are derived from the speech fragments through analysis. In this thesis, semi-supervised models will
be explored in order to retrieve better results by also using unscored
fragments instead of only using the scored ones. Different methods
will be tested and a comparison is made to supervised methods, for
which only scored data is considered.
Keywords— semi-supervised learning, co-training, speech intelligibility
I. I NTRODUCTION
Speech is a powerful tool; it is used to communicate
and learn. When speech falls out, everything becomes
more difficult. Therefore, it is important to help people
with speech disorders to speak as well as possible. The
improvement of these patients can be evaluated through a
intelligibility score, ranging from 0 to 100 percent. These
scores are normally given by the speech therapist, which
is very time consuming. A tool was created to automatically predict the speech intelligibility of a speaker in order to evaluate the improvement. This tool makes use of a
machine learned algorithm that uses a set of observations
with their acoustic features and the intelligibility score
given by a therapist. Since retrieving speech fragments
is much easier than scoring them, we will examine if we
can improve the results of the tool by also taking into account acoustic features without scores. This technique is
called semi-supervised learning.
In this paper, we will first discuss existing work in Section II and we provide a detailed explanation of one of
the techniques in Section III. After this, we will introduce our test setup (Section IV) and discuss our results
(Section V). We will end with a conclusion (Section VI).
II. R ELATED W ORK
The existing tool we start with was developed by C.
Middag [3]. The hypothesis was that the tool could be
further improved by exploring new data (unscored) by
means of the co-training algorithm proposed by Zhu [1].
This algorithm combined co-training with kNN (k Nearest Neighbours) as presented by Zhou and Li [2]. In this
paper we generalize this algorithm so that it can also be
used with other techniques, such as ELR (Ensemble Linear Regression), which is the machine learning approach
in the existing tool ([3]).
III. C O - TRAINING
Based on the existing algorithms, we created a generalized framework for co-training where any regressor can
be plugged in. The framework can be found in algorithm
1. The algorithm makes use of two regressors which will
start with the same data set of all scored points. In every
iteration, the first regressor will choose the best unscored
point to compute a score for and to add it to the scored
data set which will be used to update the second regressor. Then the second regressor will search for the best
point to scored and to add this to the scored data set of the
first regressor. This will be repeated until a stop criterion
is reached.
There are a lot of options for deciding which point is
best suited for addition to a data set. One option is to
train a new model for every unscored point and to choose
the point which leads to the biggest improvement of the
model as measured on the originally scored points. Other
options can be related to the model, for example the standard deviation of the scores predicted by the submodels
in ELR.
The stop criterion also permits several options that are
often correlated to the quality measure. The algorithm can
stop when there is no more improvement anymore, when
there are no more unscored points that can be added, after
a certain time, ...
IV. T EST S ETUP
We make use of a data set consisting of 231 observations with 79 acoustic features and an intelligibility score
that was derived from human judgments of the speech.
From these 231 observations, 150 will be used as train
data and the other 81 as test data. The difference between the real and predicted intelligibility will lead to the
Root Mean Square Error (RMSE). In order to avoid exceptions, we will do 10 different runs with 10 different
training and test partitions. The training data will be decomposed further in order to test with different amounts
of scored and unscored data This will lead to five configurations: 150 scored and 0 unscored points, 120 scored and
30 unscored points, 90 scored and 60 unscored points, 60
scored and 90 unscored; and 30 scored and 120 unscored
points.
Algorithm 1 General framework for co-training
INPUT: scored data set S = {xs , ds : s = 1..Ns }, unscored data set U = {xu : u = 1..Nu }
S1 ← S; S2 ← S
while stopcriterion not satisfied do
for j ∈ {1, 2} do
hj (x) ← regressor based on Sj
for elke xu ∈ U do
dˆu ← hj (xu )
n
h0j,u ← regressor based on Sj ∪ xu , dˆu
o
qu ← Qj,u (hj , h0j,u ), quality measure of dˆu
end for
if there exists a qu > 0 then
˜xj ← arg maxxu ∈U qu
d˜j ← h
nj (˜xj ) o
πj ← (˜xj , d˜j )
Fig. 1. RMSE as a function of the number of scored points for cotraining and standard kNN
U ← U \ {˜xj }
else
πj ← ∅
end if
end for
S1 ← S1 ∪ π2
S2 ← S2 ∪ π1
if both S1 and S2 are not changed then
EXIT
end if
end while
OUTPUT: regressor h∗ (x) ← 21 (h1 (x) + h2 (x))
V. R ESULTS
We will test two regression techniques that will be
plugged into the co-training framework: kNN and ELR.
They will be compared to the standard algorithm that uses
only scored data. The next sections will discuss the results.
A. Co-training with kNN
After having tweaked the parameters for the standard
kNN algorithm, we could compare this algorithm to cotraining. As quality measure, we aim for the best improvement to choose the best unscored point. Points will
be added until there is no further improvement. Figure
1 shows the results of the tests. There is no significant
difference between the standard algorithm and the cotraining algorithm. Even after a lot of optimizations, no
difference can be made.
B. Co-training with ELR
The ELR algorithm uses several linear submodels and
averages these. As for kNN, we also started by setting the
optimal parameters for the standard ELR algorithm. The
quality measure calculates the standard deviation on the
predictions of all submodels and adds the point that has
Fig. 2. RMSE as a function of the number of scored points for cotraining and standard ELR
the lowest deviation. This is done until there are no more
points left. The comparison between standard and cotraining ELR can be found in Figure 2. We notice that the
co-training algorithm is actually contra-productive as it
lowers the performance with respect to the standard ELR.
VI. C ONCLUSION
When comparing kNN and ELR, we notice that kNN
gives better results for all data sets. On top of that, the
kNN algorithms are much faster and we thus advise to
use kNN for the tool.
We can conclude that co-training has not lead to an improvement for neither of the methods tried in this thesis.
This is probably due to a bad quality measure. In future
work, it might be useful to examine more possibilities for
this measure.
R EFERENCES
[1] Xiaojin Zhu, Semi-Supervised Learning Tutorial, Technical Report, Department of Computer Sciences, University of Wisconsin,
Madison, USA, 2007
[2] ZH. Zhou and Ming Li, Semi-Supervised Regression with CoTraining Proceedings of the 19th International Joint Conference
on Artificial Intelligence 2005, Edinburgh, Scotland, pp. 908-913.
[3] Catherine Middag, Automatic Analysis of Pathological Speech,
Universiteit Gent, 2012-2013.
Inhoudsopgave
Tabel van afkortingen en symbolen
viii
1 Situering
1
1.1
Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Doel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.4
Verdere verloop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2 Bestaande technieken
4
2.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Co-training en Self-training . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2.1
Co-training met kNN . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Semi-Gesuperviseerde Support Vector Regressie . . . . . . . . . . . . . . . . .
7
2.4
Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5
Van regressie naar classificatie? . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3 Co-training
3.1
3.2
3.3
3.4
10
Algemeen raamwerk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.1.1
De kwaliteitsmaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.1.2
Het stopcriterium
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
k Nearest Neighbours (kNN) . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2.1
De kwaliteitsmaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Support Vector Regression (SVR) . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.3.1
Wat is SVR? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.3.2
De kwaliteitsmaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
Ensemble Linear Regression (ELR) . . . . . . . . . . . . . . . . . . . . . . . .
15
3.4.1
Wat is ELR? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.4.2
De kwaliteitsmaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
vi
4 Clustering
4.1
4.2
18
Clusterstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
4.1.1
K-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.1.2
Incrementele K-Means . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
Regressiemodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
5 Experimenten
21
5.1
Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
5.2
Geteste algoritmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.3
Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.4
Prestatieanalyse
23
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 Resultaten van kNN
25
6.1
Standaard kNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
6.2
Co-training met kNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
6.2.1
Betrouwbaarheden invoeren . . . . . . . . . . . . . . . . . . . . . . . .
30
6.2.2
Invloed van de kwaliteitsmaat . . . . . . . . . . . . . . . . . . . . . . .
30
6.2.3
Invloed van het stopcriterium . . . . . . . . . . . . . . . . . . . . . . .
34
Clustering met kNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
6.3.1
35
6.3
Bepalen van de clustergrootte . . . . . . . . . . . . . . . . . . . . . . .
7 Resultaten van ELR
38
7.1
Standaard ELR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
7.2
Co-training met ELR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
7.2.1
Invloed van de kwaliteitsmaat . . . . . . . . . . . . . . . . . . . . . . .
43
7.2.2
Invloed van het stopcriterium . . . . . . . . . . . . . . . . . . . . . . .
44
8 Conclusie en verder onderzoek
47
8.1
Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
8.2
Verder onderzoek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
Lijst van tabellen
51
Lijst van figuren
52
Lijst van Algoritmes
54
vii
Tabel van afkortingen en symbolen
ELR
Ensemble Lineaire Regressie
kNN
k Nearest Neigbours
KS
kenmerkenselectie
LR
Lineaire Regressie
MCS
Multiple Classifier Systems
RMSE
Root Mean Squared Error
S3VM
Semi-gesuperviseerde Support Vector Machines
S3VR
Semi-gesuperviseerde Support Vector Regressie
SSE
Sum of Squared Errors
SSL
Semi-gesuperviseerd leren (Semi-Supervised Learning)
SVR
Support Vector Regressie
viii
Hoofdstuk 1
Situering
1.1
Probleemstelling
Taal is een krachtig medium. Het is een communicatiemiddel, een middel dat we gebruiken
om boodschappen over te brengen. Bovendien wordt taal vaak gebruikt als leerproces; we
lezen, schrijven en praten. Als spraak wegvalt, wordt het opeens een stuk moeilijker om te
communiceren en om sociale contacten te onderhouden. Daarom is het belangrijk dat mensen
met spraakstoornissen goed kunnen begeleid worden in hun revalidatie.
De revalidatie van personen met een spraakstoornis kan ge¨evalueerd worden aan de hand
van een verstaanbaarheidsscore. Om deze verstaanbaarheidsscore te kunnen toewijzen wordt
gebruik gemaakt van het Nederlands Verstaanbaarheidsonderzoek (Dutch Intelligibility Assessment - DIA). De DIA-test zal voor de pati¨ent drie woordenlijsten genereren. Deze woorden
zullen bestaan uit een medeklinker, gevolgd door een klinker en opnieuw een medeklinker. Er
zal aan de pati¨ent gevraagd worden om deze woordenlijsten in te spreken.
E´en of meer luisteraars krijgen deze spraakfragmenten te horen en zij moeten daarin ´e´en klank
identificeren. Het kan gaan om de eerste medeklinker, de klinker of de laatste medeklinker.
Telkens hebben ze de keuze uit een lijst van mogelijkheden. De verstaanbaarheidsscore die
gegeven wordt aan de pati¨ent is dan gelijk aan het percentage correct ge¨ıdentificeerde klanken.
In het doctoraatsonderzoek van C. Middag [8] werd het Nederlands Verstaanbaarheidsonderzoek geautomatiseerd. Op basis van kenmerken die ge¨extraheerd werden uit de spraakfragmenten en referentiescores die afkomstig waren van luisteraars, werd een regressor ontwikkeld.
Bij regressie wordt een waarde uit een continu domein toegekend aan de datapunten. Dit
in tegenstelling tot classificatie, waar een datapunt wordt toegekend aan een klasse uit een
eindige verzameling. Bij regressie spreekt men over scores, bij classificatie wordt de term
label gebruikt. In Figuur 1.1 wordt het verschil tussen classificatie en regressie verduidelijkt.
Aangezien de verstaanbaarheidsscore een percentage voorstelt, wordt in deze thesis geopteerd
voor een regressie die een re¨ele output oplevert.
Het probleem bij de automatische analyse is dat er geen complexe, grote modellen kunnen
gemaakt worden omdat er te weinig perceptueel gescoorde data voorhanden is. Daarom is het
interessant om te kijken wat ongescoorde data kan bijbrengen aan het model. Ongescoorde
1
(a) Classificatie, de output van neemt discrete
waarden aan (het symbool geeft aan hoe (X,Y)
wordt gemapt op klasse 1 of klasse 2)
(b) Regressie, de output neemt continue waarden
aan (de rechte geeft aan hoe X wordt gemapt op
Y)
Figuur 1.1: Verschil tussen classificatie en regressie
spraakfragmenten zijn namelijk gemakkelijker te verkrijgen en zijn dus goedkoper. Een score
geven aan een spraakfragment vergt veel meer moeite.
1.2
Doel
Het doel van deze thesis is onderzoeken of het mogelijk is op basis van ongescoorde data
een betere regressor te ontwikkelen. Hierbij zullen verschillende technieken eerst theoretisch
ge¨evalueerd worden. Daarna zullen enkele daarvan ook ge¨ımplementeerd worden, en zullen
de resultaten vergeleken worden met de resultaten van de originele regressor. Hierbij zullen
we het aantal ongescoorde datapunten vari¨eren en bekijken welke invloed dit heeft op onze
regressor.
1.3
Dataset
De dataset bestaat uit 231 sprekers waarvoor een score beschikbaar is. Deze sprekers zullen
worden opgesplitst in twee deelverzamelingen: een verzameling om het model mee te ontwikkelen en een verzameling om het model mee te testen. Er worden 150 willekeurige sprekers
gekozen voor de ontwikkeling en de overige 81 worden gebruikt om te testen. De trainingset
wordt nog verder opgesplitst in een deelverzameling waarvan de scores wel zullen gebruikt
worden, en een deelverzameling die zonder score zal beschouwd worden.
1.4
Verdere verloop
In deze thesis zullen eerst de bestaande technieken bekeken en ge¨evalueerd worden in Hoofdstuk 2. Daarna zullen enkele technieken uitgebreid besproken worden in Hoofdstukken 3 en
2
4. De experimenten die werden gedaan worden besproken in Hoofdstuk 5, gevolgd door de
resultaten in Hoofdstukken 6 en 7. We eindigen deze thesis met een conclusie in Hoofdstuk
8.
3
Hoofdstuk 2
Bestaande technieken
2.1
Inleiding
Semi-gesuperviseerd leren (SSL) is een algemene benaming voor technieken die zowel gescoorde als ongescoorde data aanwenden om een model op te stellen. Hierbij hoopt men dat
de ongescoorde data extra informatie kan bieden over de structuur van de data, waardoor
men een betere regressor kan trainen. De motivatie voor SSL is twee¨erlei. Enerzijds tonen
resultaten uit de literatuur ([7]) dat men met ongescoorde data verbeteringen kan aanbrengen
aan de regressor, vooral wanneer weinig gescoorde data voorhanden is. Anderzijds leren ook
mensen via SSL: een vader wijst een kind een bruin dier aan en benoemt het als hond, maar
het kind observeert ook honden zonder dat ze benoemd worden.
SSL kan op twee manieren gedaan worden. Enerzijds kan men vertrekken van een model
dat via gesuperviseerde methoden verkregen werd en dat daarna verbeterd wordt door ook
de ongescoorde data te gebruiken. Anderzijds kan men de gescoorde en ongescoorde data
niet-gesuperviseerd clusteren, en deze clusters vervolgens aanwenden bij het opstellen van
een model aan de hand van de gescoorde data.
In de volgende hoofdstukken zal men steeds gebruik maken van deze notaties:
•
•
•
•
•
•
2.2
x stelt een datapunt voor;
h(x) is de predictie door regressor h van de score die bij datapunt x hoort;
ds is de score van het datapunt xs (s is een index);
dˆs is de voorspelling van ds ;
S stelt de set voor van gescoorde data; en
U is de set van ongescoorde data.
Co-training en Self-training
In de tutorial van Zhu [6] wordt co-training besproken als een methode om SSL toe te passen.
Hierbij wordt gebruik gemaakt van twee verschillende regressors. De k meest betrouwbare datapunten van de ene regressor worden samen met hun predicties toegevoegd aan de gescoorde
dataset van de andere en omgekeerd. Om dit te doen werken, veronderstelt men dat de beide
4
regressors in staat zijn om een goede predictie op te leveren voor voldoende niet-gescoorde
datapunten. In Figuur 2.1a wordt de trainingsfase van co-training verduidelijkt. Tijdens de
testfase worden de predicties van de twee regressors uitgemiddeld (zie Figuur 2.1b).
Self-training (Didaci en Roli [3]) is een andere vorm van SSL. Hier zal er ´e´en classifier het
meest kwaliteitsvolle datapunt schatten en toevoegen aan zijn eigen dataset. Bij ensembledriven self-training zal deze classifier bestaan uit een aantal subclassifiers die door uitmiddeling de score en de kwaliteit ervan zullen bepalen.
2.2.1
Co-training met kNN
In het artikel van Zhou en Li [7] wordt co-training toegepast op het geval van een regressor
gebaseerd op het principe van k Nearest Neigbours (kNN). Het originele algoritme voor kNN
is te vinden onder Algoritme 1.
Algoritme 1 Bereken h(x) voor kN N
X(1 : k) ← k dichtste buren van x
Y (1 : k) ← scores van X(1 : k)
D(1 : k) ← afstand(x, X(1 : k))
Y (l)
l=1 D(l)
1
l=1 D(l)
Pk
h(x) ←
Pk
Als men co-training wil toepassen met kNN, maakt men gebruik van twee verschillende
regressors. Het verschil tussen de twee is de afstandsmaat die gebruikt wordt. Beiden maken
gebruik van de Minkowsky-afstandsmaat (2.1), maar met een verschillende waarde voor p.
Deze afstandsmaat gaat ervan uit dat alle kenmerken ongeveer dezelfde schaal (verschil tussen
maximale en minimale waarde) hebben, maar dit is niet altijd zo. Het is dan ook belangrijk
om eerst een normalisatie van de dataset uit te voeren, zodat elk kenmerk gemiddelde 0 en
variantie 1 heeft.
M inkowskyp (x, y) =
d
X
i=1
|xi − yi |p
!1/p
(2.1)
De twee regressors beginnen initieel met dezelfde dataset S (alle gescoorde datapunten), maar
zullen iteratief datapunten toevoegen aan de dataset van de andere. In de paper wordt eerst
een poel U 0 aangemaakt die een subset is van de set van ongescoorde datapunten (U ). De
datapunten die zullen worden toegevoegd, zullen gekozen worden uit de kleinere poel. Dit
is naar het voorbeeld van Blum en Mitchell [1]. Deze auteurs kregen betere resultaten op
een kleinere set, waarin ze 100 random datapunten selecteerden in plaats van 2000. Volgens
hen zorgde dit ervoor dat de regressors gedwongen werden om voorbeelden te nemen die
de onderliggende distributie beter representeerden. Aangezien voor deze thesis veel minder
ongescoorde datapunten beschikbaar zijn, is de invoering van een kleinere poel niet nodig.
Om te beslissen welk ongescoord datapunt het best kan worden toegevoegd, wordt de kwaliteit
van de score geschat. De kwaliteit wordt hier berekend aan de hand van het verschil in
Sum of Squared Errors (SSE) voor de regressor voor en na toevoeging van het ongescoorde
5
(a) De trainingsfase van co-training
(b) Scoren aan de hand van co-training
Figuur 2.1: Algemene flow-charts voor training en scoring met behulp van co-training
6
datapunt en diens predictie (zie formule 2.2). Zo wil men ervoor zorgen dat het datapunt
gekozen wordt dat de regressor maximaal consistent houdt met de oorspronkelijk gescoorde
data. We voeren hier de regressor hi (x) = h(x|S \ {xi }) in, die de regressor voorstelt die
wordt verkregen op basis van de volledige gescoorde dataset, zonder het datapunt xi . Het
is belangrijk om het datapunt te verwijderen uit de dataset, aangezien de kNN regressor
ongescoorde punten die samenvallen met een gescoord punt automatisch ook die score geeft.
De regressor h0i,u (x) = h (x|S ∪ {xu , h(xu )} \ {xi }) neemt het ongescoorde datapunt xu en
diens voorspelling op in het model.
∆SSEu =
X
xi ∈S
2 (di − hi (xi ))2 − di − h0i,u (xi )
(2.2)
In deze formule wordt gesommeerd over alle gescoorde datapunten. Door het verschil te
nemen, wordt gekeken of het ongescoorde datapunt voor een verbetering, dus voor een kleinere
fout zorgt na toevoeging. Aangezien het erg tijdrovend is om formule 2.2 te berekenen, stelden
de auteurs een benadering voor. Ze sommeren voor elk ongescoord datapunt slechts over de
verzameling Ωu van de k dichtste gescoorde buren van dat datapunt.
Het volledige algoritme van co-training met kNN is te vinden onder Algoritme 2. In de
paper van Zhou en Li [7] worden voorbeelden uitgewerkt die aantonen dat deze methode zeer
goede resultaten zou moeten opleveren. De methode wordt vergeleken met andere zelflerende
methoden, en met de twee regressors apart. Er wordt echter nergens een vergelijking gemaakt
met de uitmiddeling van de twee regressors, zoals het in het co-trainingsalgoritme ook gebeurt.
De resultaten in de paper kunnen dus overoptimistisch zijn.
Co-training is ook toe te passen in combinatie met andere regressors. In de doctoraatsthesis
van Middag [8] wordt bijvoorbeeld gebruik gemaakt van Support Vector Regressie (SVR)
en Ensemble Lineaire Regressie (ELR). In Hoofdstuk 3 wordt het algoritme voor co-training
veralgemeend zodat het ook in combinatie met die technieken kan gebruikt worden.
2.3
Semi-Gesuperviseerde Support Vector Regressie
In de tutorial van Zhu [6] wordt een alternatieve manier voorgesteld om SSL toe te passen
bij Support Vector Machines (SVM), namelijk Semi-Supervised Support Vector Machines
(S3VM). SVM is een classificatiemethode die de marge tussen twee klassen zo groot mogelijk
probeert te maken. Bij S3VM wordt de ongelabelde data gebruikt om samen met de gelabelde
data de kloof tussen de klassen te maximaliseren. Op deze manier ligt de grens tussen de
klassen in regio’s met lage densiteiten.
Support Vector Regressie (SVR) is de corresponderende regressor en wil in tegenstelling tot
SVM een hypervlak vinden waarbij de meeste datapunten binnen een bepaalde marge liggen.
Enkel datapunten die buiten deze marge vallen, worden gebruikt in de objectieve functie.
SVR wordt in meer detail besproken in Sectie 3.3.1.
In het artikel van Xu et al. [5] wordt Semi-gesuperviseerde Support Vector Regressie (S3VR)
voorgesteld als semi-gesuperviseerde variant van SVR. Men gaat er echter wel van uit dat
de ongescoorde datapunten al een score gekregen hebben, bijvoorbeeld aan de hand van een
kNN algoritme.
7
Algoritme 2 Co-training met kN N
INPUT: gescoorde dataset S = {xs , ds : s = 1..Ns }, ongescoorde dataset U
{xu : u = 1..Nu }, aantal dichtste buren k, afstandsmaten p1 en p2
S1 ← S; S2 ← S
while niet voldaan aan stopcriterium do
for j ∈ {1, 2} do
hj ← kN N (Sj , k, pj )
for elke xu ∈ U do
dˆu ← hj (xu )
hj,i (x) ← hj (x|S
\ {xin}) ∀i o
0
hj,i,u (x) ← hj x|S ∪ xu , dˆu \ {xi } ∀i
Ωu ← N eighbours(x
u , k, S)
2 P
2
0
∆xu ← xi ∈Ωu (di − hj,i (xi )) − di − hj,i,u (xi )
end for
if er bestaat een ∆xu > 0 then
˜ j ← arg maxxu ∈U ∆xu
x
d˜j ← h
xj ) o
nj (˜
πj ← (˜
xj , d˜j )
˜j
U ←U \x
else
πj ← ∅
end if
end for
S1 ← S1 ∪ π2
S2 ← S2 ∪ π1
if zowel S1 als S2 is ongewijzigd then
EXIT
end if
end while
OUTPUT: regressor h∗ (x) ← 12 (h1 (x) + h2 (x))
8
=
2.4
Clustering
In de paper van Seeger [4] wordt nog een andere werkwijze voorgesteld: de datapunten worden
eerst opgedeeld in clusters, en pas daarna zullen scores gegeven worden aan de datapunten in
die clusters (zie Algoritme 3). Er zijn verschillende mogelijke clustermethoden voorhanden,
bijvoorbeeld k-means clustering.
Zhu [6] bespreekt graafgebaseerde algoritmes om te clusteren. Hier worden alle datapunten
voorgesteld door knopen. De takken tussen de knopen stellen een gewicht voor. Men gaat
ervan uit dat een zwaar gewicht staat voor een gelijkaardige datapunt dat meestal een gelijkaardige score bezit. Het gewicht kan bijvoorbeeld voorgesteld worden door e−D(xi ,xj ) , waarbij
D de afstand is tussen de twee knopen.
Voor het graafgebaseerd clusteren van datapunten kan men het random walk algoritme gebruiken (zie tutorial van Zhu [6]). Hierbij wordt er vanuit het datapunt een tak gekozen
met een waarschijnlijkheid die evenredig is met het takgewicht. Toegekomen in het volgende
datapunt, doet men hetzelfde. Het pad loopt verder totdat een datapunt wordt bereikt dat
al aan een cluster is toegekend. Het datapunt wordt dan aan die cluster toegevoegd.
Algoritme 3 Scoren met clusters
INPUT: aantal clusters k, gescoorde dataset S, ongescoorde dataset U
INITIALISATIE:
cluster S ∪ U in k clusters
hi ← regressor op basis van alle datapunten uit cluster i
SCORING:
i ← cluster waartoe datapunt x behoort
dˆ ← hi (x)
2.5
Van regressie naar classificatie?
Aangezien de meeste semi-gesuperviseerde technieken ontwikkeld zijn voor classificatie, zou
men kunnen overwegen om het huidige regressieprobleem te discretiseren. De [0, 100]-ruimte
zou kunnen ingedeeld worden in k klassen met bijhorend label.
Als k klein is, zal dit leiden tot een te beperkt aantal scores, waardoor het systeem aan
nauwkeurigheid zou verliezen. Als men dit wil vermijden en k groot kiest, zal men veel
gescoorde datapunten nodig hebben om toch enkele datapunten te hebben van alle klassen.
Hieruit kan men concluderen dat het voor de scope van deze thesis niet mogelijk is om een
regressieprobleem om te zetten naar een classificatieprobleem.
9
Hoofdstuk 3
Co-training
In het vorige hoofdstuk werd co-training al besproken in combinatie met kNN (zie Sectie
2.2.1). Hier verbreden we het raamwerk zodat het toepasbaar wordt op verschillende regressiemethodes.
3.1
Algemeen raamwerk
Het raamwerk voor kNN kan veralgemeend worden door enkele aanpassingen te doen in
Algoritme 2. Een eerste stap in de veralgemening is het vervangen van de kNN regressor
door een algemene regressor h(x). Deze regressor kan vervangen worden door de gekozen
regressiemethode.
De regressors hj,i en h0j,i,u uit Algoritme 2 zijn specifiek voor kNN, aangezien het voor de
kNN nodig was om het punt xi uit te sluiten (zie bespreking in sectie 2.2.1). De regressor
hj,i zal dus herleid worden tot hj , die al berekend werd, en de regressor h0j,i,u zal aangepast
worden tot h0j,u .
Ook de kwaliteitsmaat die moet aanwijzen welk datapunt eerst moet worden toegevoegd, kan
vervangen worden door een algemene kwaliteitsmaat Q(hj , h0j,u ) die zelf in te vullen is door
de gebruiker.
Het is ook mogelijk om de finale regressor h∗ te veralgemenen en de gebruiker vrij te laten
kiezen hoe deze ingevuld wordt. Naast uitmiddeling van de twee deelregressors met hun
respectievelijke dataset, kan men ook kiezen voor slechts ´e´en regressor die gebruik maakt van
de samengevoegde dataset van de twee deelregressors. Aangezien we deze optie niet zullen
testen, wordt de veralgemening van de finale regressor niet opgenomen in het algoritme.
Het algoritme neemt opnieuw alle gescoorde datapunten als startset voor de twee regressors.
Op basis van die dataset worden de beide regressors ge¨ınitialiseerd. Zolang niet voldaan is
aan het stopcriterium (zie Sectie 3.1.2), zullen de regressors alternerend een datapunt zoeken
dat kan worden toegevoegd aan de gescoorde dataset van de ene of de andere regressor. De
keuze van dat een datapunt wordt bepaald aan de hand van een kwaliteitsmaat (zie Sectie
3.1.1). Het datapunt dat de hoogste kwaliteit oplevert, zal worden geselecteerd. Het algemeen
raamwerk voor het co-trainingsalgoritme is te vinden onder Algoritme 4.
10
Algoritme 4 Algemeen algoritme voor co-training
INPUT: gescoorde dataset S
{xu : u = 1..Nu }
=
{xs , ds : s = 1..Ns }, ongescoorde dataset U
S1 ← S; S2 ← S
while niet voldaan aan stopcriterium do
for j ∈ {1, 2} do
hj (x) ← regressor op basis van Sj
for elke xu ∈ U do
dˆu ← hj (xu ) n
o
h0 (x) ← hj x|S ∪ xu , dˆu
j,u
qu ← Qj,u (hj , h0j,u ), maat om kwaliteit te schatten van dˆu
end for
if er bestaat een qu > 0 then
˜ j ← arg maxxu ∈U qu
x
d˜j ← h
xj ) o
nj (˜
πj ← (˜
xj , d˜j )
U ← U \ {˜
xj }
else
πj ← ∅
end if
end for
S1 ← S1 ∪ π2
S2 ← S2 ∪ π1
if zowel S1 als S2 is ongewijzigd then
EXIT
end if
end while
OUTPUT: regressor h∗ (x) ← 12 (h1 (x) + h2 (x))
11
=
3.1.1
De kwaliteitsmaat
De kwaliteitsmaat is een functie van het huidige model, het nieuwe datapunt en de originele
dataset. Er zijn meerdere mogelijkheden om de kwaliteitsmaat te bepalen.
Een voor de hand liggende method is om eerst een nieuwe regressor (h0j,u ) te trainen, op basis
van Sj ∪ {(xu , h(xu )))}. Het nieuwe model kan dan op verschillende manieren vergeleken
worden met het oude om een kwaliteit te schatten. Een eerste manier is de Sum of Square
Errors (SSE) (zie formule (3.1)) bepalen op basis van de berekende en de correcte scores van
de datapunten van Sj .
Qj,u =
X
xi ∈S
2 (di − hj (xi ))2 − di − h0j,u (xi )
(3.1)
Een andere methode zal kiezen voor het model dat aanleiding geeft tot de geringste verandering (zie formule (3.2)). |S| staat hier voor het kardinaalgetal van de verzameling S.
−1
Qj,u = e |S|
P
2
xi ∈S
(hj (xi )−h0j,u (xi ))
(3.2)
Voor bepaalde regressiemodellen is de kwaliteit te bepalen zonder een nieuw model te moeten
trainen. Dit is vooral het geval bij mengselmodellen die bestaan uit meerdere regressors, zoals
bijvoorbeeld ELR (zie Sectie 3.4). Voor deze modellen zou men voor elk datapunt xu het
gemiddeld verschil tussen de voorspellingen van de verschillende regressors als kwaliteitsmaat
kunnen beschouwen. Als verschillende regressors ongeveer dezelfde voorspelling geven, is het
datapunt waarschijnlijk beter gescoord dan wanneer de voorspellingen ver uit elkaar liggen.
3.1.2
Het stopcriterium
Het stopcriterium dat bepaalt wanneer de while-lus stopt, kan op verschillende manieren
ingevuld worden (al dan niet afhankelijk van de gebruikte kwaliteitsmaat):
•
•
•
•
als alle ongescoorde datapunten een score hebben gekregen;
na een bepaald aantal toevoegingen;
als de verbetering kleiner wordt dan een bepaalde drempel;
...
In de volgende secties wordt dit algemeen raamwerk ingevuld met enkele regressiemethoden.
De methoden zullen eerst worden uitgelegd, gevolgd door het toepassing van de methode in
het raamwerk.
3.2
k Nearest Neighbours (kNN)
Het kNN algoritme werd al besproken in Sectie 2.2.1 en zal hier dus niet hernomen worden.
12
3.2.1
De kwaliteitsmaat
De kwaliteitsmaat die gebruikt werd in Algoritme 2, is niet de enige die in aanmerking zou
komen om te gebruiken met kNN. Om te bepalen welke datapunten betrouwbaar geschat
zijn, kunnen we ook kijken naar de afstand tussen de datapunten en zijn buren (of enkel de
dichtste buur). We vermoeden namelijk dat een voorspelling van een score betrouwbaar is
als het corresponderende datapunt niet ver verwijderd is van zijn buren.
3.3
3.3.1
Support Vector Regression (SVR)
Wat is SVR?
Bij gegeven datapunten S = {xs , ds : s = 1..Ns } zal SVR op zoek gaan naar een functie
f (x) = w · x + b die een voorspelling dˆs oplevert die maximaal verschilt van de effectieve
waarde ds en die zo vlak mogelijk is. Deze laatste vereiste houdt in dat kwk2 zo klein mogelijk
moet zijn. Dit geeft aanleiding tot volgend optimalisatieprobleem:
1
kwk2
w
2
op voorwaarde dat di − w xi − b ≤ ∀i
minimaliseer
(3.3)
w xi + b − di ≤ ∀i
Omdat het niet altijd mogelijk zal zijn om de functie zo te kiezen dat het verschil maximaal
is, worden de losse variabelen ξi en ξi? ge¨ıntroduceerd, die 0 zullen zijn als het datapunt
binnen de marge van valt, en de waarde |ds − dˆs | − aannemen in het andere geval. Dit
past het optimalisatieprobleem aan tot:
N
s
X
1
2
kwk + C
(ξi + ξi? )
2
minimaliseer
w
i=1
op voorwaarde dat di − w xi − b ≤ + ξi
w xi + b − di ≤ + ξi?
ξi , ξi?
≥0
∀i
(3.4)
∀i
∀i
De constante C maakt de afweging tussen hoe vlak de functie is en hoe nauwkeurig de regressie
is voor datapunten buiten de marge. Als we dit probleem willen optimaliseren, levert ons dit
de volgende Langrangiaan op:
N
N
i=1
Ns
X
i=1
s
s
X
X
1
(ξi + ξi? ) −
(ηi ξi + ηi? ξi? )
L ← kwk2 + C
2
−
−
i=1
Ns
X
i=1
αi ( + ξi − di + w xi + b)
αi? ( + ξi? + di − w xi − b)
13
(3.5)
De variabelen α, α? , η, η ? worden Lagrange vermenigvuldigers genoemd en moeten voldoen
aan α, α? , η, η ? ≥ 0. Na parti¨ele afleiding van L naar de variabelen b, w, ξi en ξi? , gelijkstelling
aan 0 en substitutie van deze vergelijkingen in bovenstaande vergelijking van L, krijgen we
volgend optimalisatieprobleem:
Ns
1 X
(αi − αi? )(αj − αj? )(xi · xj )
−
2
maximaliseer
i,j=1
Ns
X
−
(αi +
+
i=1
Ns
X
op voorwaarde dat
αi? )
Ns
X
i=1
di (αi − αi? )
(3.6)
(αi − αi? ) = 0
i,j=1
αi , αi? ∈ [0, C]
∀i
Dit leidt tot:
l
X
f (x) =
(αi − αi? )(xi · x) + b
(3.7)
i=1
We zijn er in het begin van deze sectie vanuit gegaan dat de relatie tussen de datapunten en
de score kan geschreven worden in de vorm van een lineaire vergelijking. Dit is natuurlijk
niet altijd het geval. Om deze data om te zetten naar het lineaire geval, maken we gebruik
van een niet-lineaire transformatie Φ(x). Aangezien men in het optimalisatieprobleem enkel
gebruik maakt van een dotproduct, hoeven we de transformatie Φ niet te kennen, maar
volstaat het om de kernfunctie k(xi , xj ) = Φ(xi ) · Φ(xj ) te evalueren. In dit geval wordt het
optimalisatieprobleem herleid tot:
−
maximaliseer
Ns
1 X
(αi − αi? )(αj − αj? )k(xi · xj )
2
−
op voorwaarde dat
i,j=1
Ns
X
Ns
X
(αi + αi? ) +
i=1
Ns
X
i=1
di (αi − αi? )
(3.8)
(αi − αi? ) = 0
i,j=1
αi , αi? ∈ [0, C]
∀i
En dit geeft ons:
f (x) =
l
X
i=1
(αi − αi? )k(xi · x) + b
Voor de kernel zijn veel verschillende functies mogelijk, de meest voorkomende zijn:
14
(3.9)
• de lineaire kernel: k(xi , xj ) = xTi · xj ;
• de polynomische kernel: k(xi , xj ) = (xTi · xj + 1)p ; en
• de Gaussiaanse kernel: k(xi , xj ) = e
3.3.2
−
kxi −xj k
2σ 2
2
.
De kwaliteitsmaat
Zoals gezegd zijn er verschillende mogelijkheden om het meest kwalitatieve datapunt te selecteren uit de set van ongescoorde datapunten.
De beste mogelijkheid zou erin bestaan om een nieuw model te trainen voor elk ongescoord
datapunt xu en te kijken welk datapunt de beste SSE (zie formule (3.1)) oplevert. Dit zorgt
er voor dat in elke iteratie Nu nieuwe modellen moeten getraind worden, wat veel rekentijd
kan vergen.
Een alternatieve en eenvoudigere manier zou kunnen gebruik maken van de densiteit van
de dataruimte. Als er veel gescoorde datapunten aanwezig zijn in de nabijheid van een
ongescoord datapunt, zijn er meer voorbeelden voorhanden die men kan gebruiken voor de
voorspelling van de score van dit datapunt. We verwachten dus ook dat deze voorspelling
dan betrouwbaarder zal zijn dan de voorspelling in minder dense regio’s.
3.4
3.4.1
Ensemble Linear Regression (ELR)
Wat is ELR?
Ensemble Lineaire Regressie (ELR) zal de prestatie van lineaire regressie proberen verbeteren
door meerdere kleine regressors te laten samenwerken. De lineaire regressors worden elk
getraind op een andere subset van de set van gescoorde datapunten. Figuur 3.1 verduidelijkt
de werking van deze methode.
De data wordt op m verschillende manieren in twee verdeeld. Het eerste deel dient als
trainingsset en wordt gebruikt om de co¨effici¨enten van de regressors te berekenen, het tweede
deel is de validatieset en dient om die regressors te evalueren.
Lineaire regressie gaat op zoek naar een lineaire relatie tussen de observaties en de scores. Door de vele opsplitsingen van de data, worden het klein modelletjes en is het aantal
kenmerken groot in vergelijking met het aantal observaties. Daarom is het nodig om eerst
kenmerkenselectie toe te passen.
Het algoritme dat kenmerken zal selecteren (zie Algoritme 5), begint initieel zonder geselecteerde kenmerken. Het zal iteratief het beste niet-geselecteerde kenmerk kiezen door voor elk
kenmerk de RMSE te berekenen op de interne trainingsset na toevoeging van dit kenmerk.
Het kenmerk met de kleinste RMSE zal gekozen worden. Dit kenmerk zal worden toegevoegd
aan de geselecteerde set kenmerken als het ook de RMSE op de validatieset zal verbeteren.
In het andere geval stopt het algoritme.
Uiteindelijk zal het lineaire model enkel getraind worden op de interne trainingsset met enkel
de geselecteerde kenmerken, wat aanleiding zal geven tot n × m gewichtsvectoren. Het finale
model wordt berekend door deze verschillende gewichtsvectoren op te tellen.
15
Figuur 3.1: Schematische voorstelling van ELR
16
Algoritme 5 Kenmerkenselectie met lineaire regressie
INPUT: interne trainingsset T = {xt , dt : t = 1..Nt }, validatieset V = {xv , dv : v = 1..Nv },
C: set van alle kenmerken
C˜ ← {}, geselecteerde kenmerken
RM SEtmp ← grote waarde
repeat
RM SEV ← RM SEtmp
for c ∈ C \ C˜ do
w ← LR training(T, C˜ ∪ c)
RM SEc ← RM SE(LR scoring(V, w))
end for
RM SEtmp ← minc RM SEc
if RM SEtmp < RM SEV then
C˜ ← C˜ ∪ {arg minc RM SEc }
end if
until RM SEtmp ≥ RM SEV
3.4.2
De kwaliteitsmaat
We kunnen hier opnieuw gebruik maken van de SSE (3.1), maar een alternatief zou zijn om
de spreiding te bekijken van de individuele deelmodellen van ELR. De datapunten waarvan
de predicties het dichtste bij elkaar liggen, zullen de meest kwalitatieve zijn. Hiervoor zouden
we Q = std(d) kunnen bepalen voor alle datapunten en dit gebruiken als kwaliteitsmaat, met
d de vector van alle n × m voorspellingen.
17
Hoofdstuk 4
Clustering
In dit hoofdstuk willen we bestaande regressors gebruiken in combinatie met clustering ([4].
Hiertoe beschouwen we clustering als een voorverwerkingsstap, zoals weergegeven in Algoritme 6.
Algoritme 6 Algemeen raamwerk voor clustering
INPUT: gescoorde dataset S = {xs , ds : s = 1..Ns }, ongescoorde dataset U
{xu : u = 1..Nu }, beoogd aantal clusters K
=
TRAINING
deel S ∪ U op in K clusters CK op basis van verwantschap tussen datapunten
for elke cluster do
hj ← regressor op basis van gescoorde datapunten uit Cj
end for
SCORING
j ← cluster waartoe x behoort
h(x) ← hj (x)
Met het oog op de clustering dient men eerst een maat voor de verwantschap tussen datapunten te kiezen. Meestal is dat de Mahalanobis afstand tussen de datapunten (zie compendium
van Reed [2]). Vervolgens dient men een clusterstrategie te kiezen die zal worden toegepast
op de volledige set van datapunten (zie Sectie 4.1). Na de clustering wordt per cluster een
regressor getraind die enkel zal toegepast worden op datapunten die aan deze cluster worden
toegekend.
4.1
Clusterstrategie
Hieronder worden enkele mogelijkheden gegeven om te clusteren.
18
4.1.1
K-Means Clustering
Het K-means algoritme vertrekt van K willekeurige datapunten die als voorlopige clustercentra zullen fungeren. In opeenvolgende iteraties wordt elk datapunt eerst aan een cluster
toegewezen op basis van de kleinste afstand tot het clustercentrum. Daarna worden nieuwe
clustercentra bepaald als gemiddelden van de datapunten die aan dezelfde cluster werden
toegewezen (zie Algoritme 7).
Algoritme 7 Algoritme voor K-means clustering
INPUT: gescoorde dataset S = {xs , ds : s = 1..Ns }, ongescoorde dataset U
{xu : u = 1..Nu }, beoogd aantal clusters K
=
INITIALISATIE:
c = {ck : k = 1..K} ← willekeurig gekozen datapunten uit S ∪ U
OPTIMALISATIE:
while niet geconvergeerd of max steps niet bereikt do
for alle datapunten in S ∪ U do
voeg datapunt toe aan cluster Ck als datapunt dichtst bij ck ligt
end for
for k = 1..K do
ck ← gemiddelde van alle datapunten in Ck
end for
end while
4.1.2
Incrementele K-Means
Incrementele K-means begint met ´e´e clusters en splitst gaandeweg de dataruimte op in meer
clusters. Dit gebeurt doorgaans door de cluster met de meeste datapunten te beschouwen,
en deze in twee te splitsen (zie Algoritme 8).
Algoritme 8 Algoritme voor incrementele k-means clustering
INPUT: gescoorde dataset S = {xs , ds : s = 1..Ns }, ongescoorde dataset U
{xu : u = 1..Nu }, beoogd aantal clusters K
C = {c1 } ← centrum van alle datapunten in S ∪ U
k=1
while k < K do
doe k-means optimalisatie op C
cj ← clustercentrum met meeste datapunten
cx , cy ← clustercentra na 2-means clustering op cj
C ← C \ {cj } ∪ {cx } , {cy }
k =k+1
end while
19
=
4.2
Regressiemodel
Voor de regressor kunnen we gebruik maken van alle eerder genoemde regressors zoals kNN,
SVR of ELR. Het voordeel van dit raamwerk is dat eerder ge¨ımplementeerde regressors kunnen hergebruikt worden en men gemakkelijk van regressor kan veranderen bij het testen.
Een groot verschil met co-training is dat de regressor hier berekend zal worden op minder
data (gemiddeld Ns /k). Het is dus belangrijk dat er regressors gebruikt worden die ook goed
presteren met weinig data. Dit laat vermoeden dat clustering enkel gebruikt kan worden in
combinatie met kNN. In dat geval kan men zich afvragen of clustering wel een verbetering
kan opleveren. Immers, zowel de clustering als de kNN maakt gebruik van afstanden tot de
andere datapunten. Als er voldoende datapunten in een cluster zitten, zullen de k dichtste
buren in de cluster waarschijnlijk ook gelijk zijn aan de k dichtste buren uit de volledige
dataset.
20
Hoofdstuk 5
Experimenten
5.1
Datasets
We beschikken over een dataset bestaande uit 231 observaties. Van iedere spreker zijn 79
kenmerken berekend. De 79 kenmerken werden bekomen door de akoestische eigenschappen
van de spraakfragmenten te analyseren. Iedere observatie is ook vergezeld van een score die
de verstaanbaarheid van de spreker aangeeft. Figuur 5.1 toont een histogram van die scores.
Hieruit zien we dat de meeste sprekers een relatief hoge score hebben (80% en meer). Dit
kan ervoor zorgen dat regressors die op de data getraind zijn minder goede voorspellingen
zullen opleveren voor lage verstaanbaarheden. Indien dit het geval zou zijn, kunnen we de
dataset wat uniformer proberen te verdelen door enkele hoge waarden uit de dataset weg
te laten. Voor de testen in de volgende hoofdstukken maken we wel steeds gebruik van de
volledige dataset. Alvorens de data te gebruiken wordt ze eerst genormaliseerd zodanig dat
alle genormaliseerde kenmerken een gemiddelde 0 en een standaardafwijking 1 bezitten.
Voor de tests zullen we steeds gebruik maken van een ontwikkelset en een testset. Van de
231 observaties gebruiken we er 150 als ontwikkeldata en 81 als testdata. De ontwikkeldata
wordt gebruikt om een regressor te trainen, waarna deze regressor wordt ge¨evalueerd op de
testdata. Aan de hand van de voorspelde en echte output van de testdata, kan de Root Mean
Square Error (RMSE) berekend worden volgens formule (5.1). Hier staat Nt voor het aantal
datapunten in de testset.
v
u
Nt
u 1 X
RM SE = t
(dt − h(xt ))2
Nt
(5.1)
t=1
Aangezien we door te testen een zo correct mogelijk beeld willen krijgen van de prestatie van
de regressor, willen we uitzonderingen vermijden die zijn toe te schrijven aan een bepaalde
indeling van de data in ontwikkeldata en testdata. We kunnen dit voorkomen door de tests
10 keer uit te voeren met 10 verschillende random indelingen. De totale RMSE is dan de
gemiddelde RMSE van deze 10 deelexperimenten.
Van de ontwikkeldata worden vijf verschillende combinaties gemaakt met een vari¨erend aantal
gescoorde en ongescoorde datapunten. De ongescoorde datapunten worden verkregen door
21
Figuur 5.1: Verdeling van de scores in de volledige dataset
22
enkel de kenmerken van de observaties te gebruiken, en de scores weg te laten. De combinaties
zien er als volgt uit:
•
•
•
•
•
5.2
150 gescoorde en 0 ongescoorde datapunten;
120 gescoorde en 30 ongescoorde datapunten;
90 gescoorde en 60 ongescoorde datapunten;
60 gescoorde en 90 ongescoorde datapunten; en
30 gescoorde en 120 ongescoorde datapunten.
Geteste algoritmes
De verschillende algoritmes worden in Matlab gerealiseerd. De voordelen hiervan zijn dat een
heleboel functies reeds voorhanden zijn, dat matrixbewerkingen snel kunnen gebeuren en dat
het gemakkelijk is de code te debuggen.
5.3
Planning
We kiezen ervoor om eerst met kNN te werken, aangezien dit een eenvoudige methode is, en
er in de literatuur al goede resultaten mee bekomen zijn. We zullen co-training met kNN,
clustering met kNN en standaard kNN met elkaar vergelijken. Hierna zullen we ook ELR
uitproberen teneinde zo algemeen mogelijke conclusies te kunnen trekken. Merk op dat ELR
een geparametriseerde methode is, in tegenstelling tot kNN.
We zullen SVR niet testen, hoewel dit wel besproken werd. Hier zijn twee redenen voor. Ten
eerste is het SVR algoritme traag en dus niet geschikt om complexe testen mee te doen. Ten
tweede verwachten we dat we na het testen van zowel kNN als ELR een vrij goed beeld zullen
hebben over de prestatie van co-training.
In de tests die we zullen doen, zal het aantal gescoorde datapunten vari¨eren van 30 tot 150
in stappen van 30. Het aantal ongescoorde datapunten varieert mee, zodat de som van beide
steeds gelijk is aan 150.
5.4
Prestatieanalyse
We verwachten dat geen enkel algoritme het beter kan doen dan gesuperviseerde regressie
met 150 gescoorde datapunten. Dit zal dus de ondergrens zijn voor de semi-gesuperviseerde
methoden. Gesuperviseerde regressie met 120, 90, 60 en 30 gescoorde datapunten fungeert
al bovengrens voor de prestatie van de semi-gesuperviseerde methoden omdat deze regressie
helemaal geen gebruik maakt van de ongescoorde voorbeelden. Indien de toevoeging van
ongescoorde data voor slechtere resultaten zou zorgen, zouden ze geen nut hebben, integendeel
zelfs.
In Figuur 5.2 werden deze boven- en ondergrens geplot. De semi-gesuperviseerde methoden
zouden dus idealiter zo dicht mogelijk bij de ondergrens moeten liggen, en op z’n minst een
RMSE onder de bovengrens moeten opleveren.
23
Figuur 5.2: RMSE in functie van het aantal gescoorde datapunten voor gesuperviseerde
regressie als bovengrens, de lijn van gesuperviseerd 150 werd doorgetrokken als ondergrens
24
Hoofdstuk 6
Resultaten van kNN
In dit hoofdstuk zullen we semi-gesuperviseerde methoden met kNN onderzoeken en ze vergelijken met standaard (gesuperviseerde) kNN. Eerst zullen we de parameters voor standaard
kNN optimaliseren (zie Sectie 6.1). In Sectie 6.2 zullen we standaard kNN vergelijken met
co-training en zal gepoogd worden de co-training verder te optimaliseren. In Sectie 6.3 wordt
ditzelfde gedaan met de combinatie van clustering en kNN. Uiteindelijk zullen we standaard
kNN, co-training met kNN en clustering met kNN met elkaar vergelijken.
6.1
Standaard kNN
Teneinde het standaard kNN algoritme op een eerlijke manier te kunnen vergelijken met cotraining, zal ook hier gebruik gemaakt worden van een uitmiddeling van twee regressors. De
parameters die men daarbij kan kiezen zijn k (de grootte van de omgeving van een datapunt)
en p1 , p2 (de machten in de Minkowsky afstanden die de beide regressors hanteren). Aangezien
bij co-training de waarden 2 en 5 werden aangeraden voor p1 en p2 , zullen deze ook hier
gebruikt worden. Voor k worden wel een aantal waarden uitgeprobeerd, om zo de beste
waarde voor elke grootte van de gescoorde dataset te vinden. De resultaten zijn te vinden in
Tabel 6.1.
Uit deze tabel zien we dat we de beste resultaten krijgen voor k = 4, 5 en 6. Als we deze
waarden uitzetten op een grafiek (zie Figuur 6.1), zien we dat de resultaten heel dicht bij
elkaar liggen. Omdat k = 5 voor de meeste datasets het beste resultaat geeft, en de RMSE
dataset
30
60
90
120
150
k=1
11,42
10,99
10,62
10,36
10,33
k=2
10,5
9,95
9,52
9,34
9,37
k=3
10,33
9,59
9,23
9,26
9,00
k=4
10,17
9,55
9,18
9,15
8,90
k=5
10,13
9,61
9,17
9,06
8,89
k=6
10,13
9,64
9,26
9,10
8,86
k=7
10,13
9,68
9,24
9,09
8,84
k=8
10,17
9,72
9,28
9,08
8,84
k=9
10,22
9,78
9,32
9,14
8,88
Tabel 6.1: Overzicht van de RMSE voor verschillende k-waarden, de beste waarde per dataset
werd schuin gezet
25
Figuur 6.1: RMSE in functie van het aantal gescoorde datapunten voor standaard kNN met
verschillende k-waarden
26
(a) Originele afstandsmaat
(b) Nieuwe afstandsmaat
Figuur 6.2: De twee afstandsmaten voor kNN
voor de andere datasets niet veel verschilt met de beste waarde, kiezen we k = 5 voor alle
datasets.
In het kNN algoritme dat nu gebruikt wordt, wordt de score van een ongescoord datapunt
berekend door de scores van de buren te vermenigvuldigen met de inverse van de afstanden
tot die buren. In Figuur 6.2a zien we dat dit de heel nabijgelegen datapunten fel bevoordeelt.
Om dit te milderen zou men een andere functie kunnen gebruiken, namelijk een functie
die slechts langzaam daalt voor kleine
afstanden, en snel voor grote. We kunnen hiervoor
−1
D
2
gebruik maken van de functie e 2 D0 (zie Figuur 6.2b). Hier staat D voor de afstand van
het datapunt tot de buur, D0 is een referentie afstand die bepaalt wat ‘dicht’ betekent. Een
voorstel voor de berekening van een geschikte D0 is het volgende: neem D0 evenredig met
de gemiddelde afstand tussen een datapunt en diens dichtste buur. Twee voorbeelden van
waarden voor D0 zijn te vinden onder formule (6.1) en (6.2), waarbij de waarde voor β nog
vrij gekozen kan worden.
27
dataset
30
60
90
120
150
β = 0.2
10,36
9,79
9,50
9,19
9,18
kwadraat
β = 0.3 β = 0.4 β = 0.5
10,18
10,13
10,10
9,56
9,53
9,55
9,22
9,15
9,14
9,04
9,02
9,03
8,95
8,89
8,88
β = 0.6
10,10
9,57
9,15
9,04
8,88
origineel
10,13
9,61
9,17
9,06
8,89
Tabel 6.2: Overzicht van de RMSE voor verschillende waarden van β bij formule (6.1) (kwadraat)
dataset
30
60
90
120
150
β = 0.2
10,39
9,82
9,53
9,21
9,21
geen kwadraat
β = 0.3 β = 0.4 β = 0.5
10,19
10,14
10,11
9,56
9,53
9,54
9,23
9,15
9,14
9,04
9,02
9,03
8,97
8,90
8,88
β = 0.6
10,10
9,56
9,15
9,04
8,88
origineel
10,13
9,61
9,17
9,06
8,89
Tabel 6.3: Overzicht van de RMSE voor verschillende waarden van β bij formule (6.2) (geen
kwadraat)
v
u
N
u1 X
D0 = β ∗ t
Di2
N
(6.1)
i=1
D0 = β ∗
N
1 X
Di
N
(6.2)
i=1
Eerst zullen we formule 6.1 vergelijken met het vorige resultaat. De RMSE voor verschillende
waarden van β is te vinden in Tabel 6.2. Men kan zien dat er weinig verschil is tussen verschillende waarden voor β, en dat de nieuwe gewichtsfunctie ook geen significante verbetering
oplevert ten opzichte van de originele aanpak met gewichtsfunctie D1i .
Uit Tabel 6.3 kan men zien dat voor formule (6.2) dezelfde conclusies kunnen getrokken
worden. Toch kiezen we ervoor om met de nieuwe gewichtsfunctie verder te gaan. Het lijkt
ons namelijk een eerlijkere maat. Op basis van Tabellen 6.2 en 6.3 kiezen we voor formule
(6.1) met β = 0.5, aangezien die voor de meeste datasets tot de kleinste RMSE leidt.
6.2
Co-training met kNN
Nu de parameters voor standaard kNN geoptimaliseerd zijn, kunnen we het algoritme inbedden in het co-training raamwerk, zodat het resultaat werkt volgens Algoritme 2 (zie Sectie
2.2.1). De resultaten zijn te vinden in Figuur 6.3. Daaruit blijkt dat co-training het niet beter
doet dan standaard kNN. In de volgende secties zullen we onderzoeken of we co-training nog
kunnen optimaliseren opdat het alsnog beter zou presteren dan standaard kNN.
28
Figuur 6.3: RMSE in functie van het aantal gescoorde datapunten voor co-training en standaard kNN
29
30
60
90
120
150
formule (6.3)
α = 0.25 α = 0.50 α = 0.75
10,34
10,24
10,28
9,54
9,54
9,50
9,12
9,07
9,11
9,00
8,98
8,99
8,88
8,88
8,88
formule (6.4)
α = 0.25 α = 0.50 α = 0.75
10,26
10,34
10,33
9,59
9,52
9,51
9,09
9,11
9,14
8,99
8,98
8,97
8,88
8,88
8,88
Tabel 6.4: Overzicht van de RMSE voor verschillende waarden van α voor de betrouwbaarheid
6.2.1
Betrouwbaarheden invoeren
We vinden toch dat er iets ontbreekt aan het originele co-trainingsalgoritme, namelijk het
gebruik van betrouwbaarheden bij ongescoorde datapunten die worden toegevoegd aan de
gescoorde dataset. Deze datapunten zijn immers voorspeld, en bijgevolg minder betrouwbaar
dan de origineel gescoorde datapunten.
Voor initieel gescoorde datapunten nemen we aan dat ze een betrouwbaarheid 1 bezitten.
Voor datapunten die nadien gescoord worden, stellen we twee formules voor. In beide formules
wordt de betrouwbaarheid B verkregen als een gewogen gemiddelde van de betrouwbaarheden
van de k buren. We nemen hiervoor dezelfde gewichten (gerelateerd aan de afstand tussen
xi en xu ) als bij kNN.
B(dˆu ) = α ∗
P
B(dˆu ) = α ∗
P
xi ∈neigbours(xu ) B(di )
P
∗ gewicht(xi , xu )
(6.3)
∗ gewicht(xi )
(6.4)
xi ∈neigbours(xu ,xu ) gewicht(xi )
xi ∈neigbours(xu ,xu ) B(di )
k
Er zijn verschillende waarden van α mogelijk voor beide formules. In Tabel 6.4 worden de
resultaten van enkele waarden opgelijst. Hieruit zien we dat er nauwelijks verschil is tussen
de verschillende waarden voor α. We kiezen toch voor α = 0.50 en (6.3). We kunnen nu
co-training met en zonder betrouwbaarheden vergelijken met standaard kNN (zie Figuur 6.4).
Uit de figuur blijkt dat betrouwbaarheden geen verbetering opleveren ten opzicht van het
originele co-trainingsalgoritme. Omdat betrouwbaarheden ons ’eerlijker’ lijken, gaan we ze
behouden in volgende experimenten.
6.2.2
Invloed van de kwaliteitsmaat
Het kritische punt in co-training is de kwaliteitsmaat die bepaalt welke datapunten zullen
worden toegevoegd aan de gescoorde dataset. Als we de datapunten op een random wijze
zouden toevoegen, dan is de gemiddelde fout op de score van die datapunten even groot als
de overeenkomstige RMSE van het standaard algoritme. We hopen dat de kwaliteitsmaat
ervoor kan zorgen dat enkel die datapunten worden toegevoegd waarvoor de berekende score
een kleinere fout vertoont.
30
Figuur 6.4: RMSE in functie van het aantal gescoorde datapunten voor co-training met en
zonder betrouwbaarheden
31
Figuur 6.5: Absolute verschil tussen de voorspelde en echte score in functie van de verbetering
door toevoeging van het datapunt
Het huidige co-trainingsalgoritme voegt het datapunt toe dat voor de beste verbetering zorgt
op de voorspellingen van de trainingsdata. Dit geeft niet zo’n goede resultaten en we willen
dus graag weten wat er mis gaat. Daarom hebben we in de eerste iteratie van het algoritme
gekeken naar de echte en voorspelde waarde van alle ongescoorde datapunten. Daarna onderzochten we welke datapunten eerst werden toegevoegd en al snel werd duidelijk dat dit
niet altijd de best voorspelde datapunten waren. In Figuur 6.5 is de fout op de voorspelling
uitgezet in functie van de berekende verbetering van de regressor. Hier verwachten we dat
de datapunten met een grote verbetering een goede voorspelling zullen hebben en dat de
fout voor zulke datapunten minimaal is. We zien in deze figuur dat dit niet het geval is:
datapunten met een grote verbetering hebben vaak ook een grote fout.
Een probleem dat optreedt bij de beste verbetering is dat de gekozen datapunten de fout
wel verbeteren, maar eigenlijk niet correct gescoord zijn. Door toevoeging van het datapunt
wordt de RMSE kleiner, maar zal de fout kunnen propageren naar naburige datapunten.
Daarom kan men op zoek gaan naar andere methoden om aan te geven of een datapunt goed
voorspeld is.
Een eerste alternatief zou kunnen zijn om de gemiddelde afstand tot de buren als kwaliteitsmaat te beschouwen. Op Figuur 6.6 werd de fout uitgezet in functie van deze gemiddelde
afstand. We zien dat er wel een correlatie tussen beide waar te nemen is; datapunten die een
kleinere gemiddelde afstand hebben tot hun buren, zijn ook vaak vrij goed voorspeld.
Een tweede alternatief zou kunnen gebruik maken van de hypothese dat een datapunt goed
32
Figuur 6.6: Absolute verschil tussen de voorspelde en echte score in functie van de gemiddelde
afstand van het datapunt tot zijn buren
voorspeld is als er niet veel verschil zit op de scores van zijn buren. Daarom bekeken we
de fout in functie van de standaardafwijking op de scores van de buren (zie Figuur 6.7).
Hieruit blijkt dat de standaardafwijking geen goede indicator is voor de correctheid van de
voorspelling van een datapunt.
Een mogelijke reden hiervoor is dat het aantal buren (k = 5) eerder beperkt is, en de schatting
van een standaardafwijking hiervan niet zeer betrouwbaar is. Een alternatief zou kunnen zijn
om te kijken hoe ver de twee uiterste scores van de buren uit elkaar liggen. De resultaten
hiervan zijn te vinden in Figuur 6.8. Ook hier zien we dat er niet echt een verband te vinden
is. Er zijn datapunten waarbij de scores heel dicht bij elkaar liggen, die toch een grote fout
hebben.
Omdat de afstand tussen de buren het meest een verband toonde van alle besproken methoden, zullen we deze methode uitproberen. In onze testen zullen we in elke iteratie het
datapunt toevoegen dat de kleinste afstand heeft tot zijn buren. We zullen deze methode
vergelijken met de originele methode, waarbij het datapunt met de grootste verbetering eerst
zal worden toegevoegd, en met een methode waarbij een willekeurig datapunt wordt gekozen
om toe te voegen.
In Figuur 6.9 zijn de resultaten van deze tests te vinden. Om deze drie methoden met elkaar
te kunnen vergelijken, werd slechts een derde van de datapunten toegevoegd. De figuur toont
dat er geen verschil is tussen de uitgeteste methoden. Aangezien het doel van co-training is
om met de ongescoorde punten het model zo goed mogelijk te verbeteren, kiezen we om in
verdere tests gebruik te maken van de beste verbetering.
33
Figuur 6.7: Absolute verschil tussen de voorspelde en echte score in functie van de standaardwafwijking op de scores van de buren
6.2.3
Invloed van het stopcriterium
We kunnen ons tenslotte afvragen of het stopcriterium een merkbare invloed heeft op de resultaten. Het huidige algoritme stopt als er geen verbetering meer optreedt op de trainingsdata
door datapunten toe te voegen. De experimenten hebben aangetoond dat dit gemiddeld is
nadat 2/3 van de ongescoorde dataset is toegevoegd. Om de invloed van het stopcriterium
te onderzoeken, zullen we een test doen met meer en met minder data. In het eerste geval
voegen we alle ongescoorde datapunten toe, in het tweede stoppen we als een derde van de
ongescoorde datapunten is toegevoegd. De resultaten hiervan zijn te vinden in Figuur 6.10.
Uit de figuur zien we dat het stopcriterium eigenlijk niet veel effect heeft. Enkel bij veel ongescoorde datapunten is vroegtijdig stoppen een beter oplossing, waarschijnlijk omdat slechte
voorspellingen anders kunnen propageren. Omdat het voorzichtiger is om met een weldoordacht stopcriterium te werken, maken we gebruik van het criterium dat stopt als er geen
verbetering meer optreedt.
6.3
Clustering met kNN
Clustering met kNN is een andere methode om SSL toe te passen. In deze sectie zullen we
bekijken wat de mogelijkheden zijn met deze methode.
34
Figuur 6.8: Absolute verschil tussen de voorspelde en echte score in functie van het verschil
tussen de maximale en de minimale score van de buren
6.3.1
Bepalen van de clustergrootte
Voordat we clustering kunnen vergelijken met standaard kNN, zullen we eerst de ideale
grootte van de cluster (K) bepalen. Hiervoor maken we enkel gebruik van gescoorde data en
nemen we de grootte van de omgeving van een datapunt (k) gelijk aan 1. De resultaten voor
verschillende clustergroottes zijn te vinden in Tabel 6.5.
Uit deze tabel kunnen we besluiten dat de beste resultaten bekomen worden met slechts ´e´en
cluster, wat betekent dat we het standaard kNN algoritme zouden toepassen. In dat geval is
het niet nuttig om over te gaan naar verdere testen met clustering.
30
60
90
120
150
K=1
11,42
10,99
10,62
10,36
10,33
K=2
11,65
11,35
10,63
10,58
10,40
K=3
11,81
11,60
11,06
10,56
10,71
K=4
11,84
11,53
11,33
10,19
10,69
K=5
11,90
11,33
11,21
10,61
11,03
K=6
11,81
11,58
10,93
10,57
10,56
K=7
11,82
11,37
10,99
10,63
10,53
K=8
11,92
11,28
10,93
10,52
10,45
Tabel 6.5: Overzicht van de RMSE voor verschillende clustergroottes met k = 1, de kleinste
waarde staat schuin
35
Figuur 6.9: RMSE in functie van het aantal gescoorde datapunten voor co-training met
toevoeging op basis van de beste verbetering, de kleinste gemiddelde afstand, en random
toevoeging. Slechts een derde van de ongescoorde datapunten werden toegevoegd.
36
Figuur 6.10: RMSE in functie van het aantal gescoorde datapunten voor co-training met en
zonder stopcriterium
37
Hoofdstuk 7
Resultaten van ELR
In dit hoofdstuk zullen we de semi-gesuperviseerde methoden bekijken in combinatie met
ELR. We optimaliseren eerst de parameters voor standaard ELR, daarna onderzoeken we het
effect van co-training bij deze parameters.
7.1
Standaard ELR
De parameter die we kunnen laten vari¨eren bij ELR is het aantal random permutaties m van
de trainingsset waarop een regressor geleerd wordt (zie Sectie 3.4.1). We zullen het aantal
random permutaties laten vari¨eren om zo de optimale waarde te vinden. We zullen testen
uitvoeren voor m = 5, 10, 20, 50 en 100. De resultaten zijn te vinden in Tabel 7.1.
We zien dat de resultaten weinig afhankelijk zijn van het aantal permutaties. Teneinde ook
rekening te houden met de rekentijd, kiezen we daarom voor 10 permutaties van de data.
We zijn ge¨ınteresseerd in het aantal kenmerken dat geselecteerd wordt voor de verschillende
datasets. Een grafiek hiervan is te vinden in Figuur 7.1. Zoals verwacht neemt het aantal
geselecteerde kenmerken toe met de grootte van de gescoorde dataset. Aangezien er door
co-training datapunten zullen bijkomen, vermoeden we dat er meer kenmerken zullen kunnen
geselecteerd worden.
We vragen ons af hoe standaard ELR presteert in vergelijking met standaard kNN. Beide
algoritmen werden getest en de resultaten hiervan zijn te vinden in Figuur 7.2. Uit deze figuur
kunnen we afleiden dat er geen significant verschil is tussen de beide regressiemethoden.
dataset
30
60
90
120
150
5
10,40
10,37
9,61
9,46
9,11
10
10,32
10,36
9,57
9,26
9,05
20
10,28
10,42
9,62
9,21
9,07
50
10,35
10,27
9,61
9,21
9,07
100
10,28
10,30
9,54
9,22
9,08
Tabel 7.1: Overzicht van de RMSE met een verschillend aantal random permutaties voor
standaard ELR
38
Figuur 7.1: Gemiddeld aantal geselecteerde kenmerken in functie van de grootte van de
gescoorde datasets voor zowel de deelmodellen als het volledige model
39
Figuur 7.2: Vergelijking tussen standaard kNN en standaard ELR voor de RMSE in functie
van het aantal gescoorde datapunten
40
Figuur 7.3: RMSE in functie van het aantal gescoorde datapunten voor co-training en standaard ELR
7.2
Co-training met ELR
Standaard ELR is geoptimaliseerd, nu kunnen we het standaard algoritme vergelijken met
co-training. Doordat gewerkt wordt met m deelmodellen, kunnen we deze gebruiken in de
kwaliteitsmaat. Als de voorspellingen van alle deelmodellen gelijkaardig zijn, kunnen we
verwachten dat het datapunt een vrij correcte score zal gekregen hebben. Daarom zullen
we in het co-trainingsalgoritme ongescoorde datapunten toevoegen op basis van de kleinste standaardafwijking op de voorspelling van de m deelmodellen van ELR. De datapunten
worden toegevoegd totdat er geen meer over zijn. De vergelijking tussen co-training en standaard ELR is te vinden in Figuur 7.3. Het aantal kenmerken dat nu geselecteerd wordt, kan
gevonden worden in Figuur 7.4.
We zien dat co-training het vooral voor weinig gescoorde datapunten een slechter doet dan
standaard ELR. Het probleem zou - net als bij co-training met kNN - kunnen liggen aan de
kwaliteitsmaat. We zullen dit verder onderzoeken in Sectie 7.2.1.
Als we kijken naar het aantal kenmerken dat geselecteerd wordt voor co-training in vergelijking met standaard ELR (zie Figuur 7.4), zie we dat onze verwachtingen niet kloppen.
Hoewel er in de deelmodellen een kleine stijging waar te nemen is van het aantal geselecteerde kenmerken, zien we voor het volledige model toch een opvallende daling. Dit betekent
41
Figuur 7.4: Gemiddeld aantal geselecteerde kenmerken in functie van de grootte van de
gescoorde datasets voor standaard ELR en co-training ELR voor de deelmodellen en de
volledige regressor
42
Figuur 7.5: Absolute verschil tussen de voorspelde en echte score in functie van de standaardafwijking op de voorspelling van de deelmodellen van ELR
dus dat de verschillende submodellen vaker dezelfde datapunten selecteren.
Een mogelijke verklaring hiervoor kan zijn dat de datapunten die worden toegevoegd degene
zijn die de beste veralgemening zijn van de verschillende trainingssets. Het datapunt wordt
gekozen als de modellen gelijkaardige voorspellingen doen voor de score van dat datapunt.
Dit zal het datapunt zijn dat het meest algemeen is, en dus het meest vergelijkbaar is met
alle trainingsdata. De toevoeging van datapunten zal er dan voor zorgen dat de datasets
gelijkaardiger worden en dus vaker dezelfde kenmerken zullen selecteren.
7.2.1
Invloed van de kwaliteitsmaat
De huidige kwaliteitsmaat gaat op zoek naar het datapunt dat de kleinste standaardafwijking
heeft op de voorspellingen van de submodellen. We hebben ook hier de voorspelling van de
ongescoorde datapunten in de eerste iteratie bekeken en vergeleken met de standaardafwijking
die bepaalt welk datapunt wordt toegevoegd. Het resultaat is te zien in Figuur 7.5.
Uit de figuur blijkt dat de standaardafwijking op de deelmodellen weinig verband houdt met
de fout op de voorspelling van een ongescoord datapunt. Daarom zouden we kunnen kiezen
voor een andere kwaliteitsmaat, zoals de beste verbetering. Deze kwaliteitsmaat werd al
gebruikt voor kNN (zie Hoofdstuk 6). Het nadeel van het gebruik van de beste verbetering
bij ELR is dat er voor elk ongescoord punt een nieuw model moet worden opgesteld, wat zeer
lang duurt aangezien het ELR algoritme trager is. Uit het vorige hoofdstuk (Hoofdstuk 6)
43
Figuur 7.6: RMSE op de testset en gemiddelde RMSE van de validatiesets van ´e´en regressor
in functie van de iteratie, getest voor 60 gescoorde datapunten
bleek dat de kwaliteitsmaat niet veel verschil maakte voor het algoritme. We zullen dan ook
geen andere mogelijkheden testen in dit hoofdstuk.
7.2.2
Invloed van het stopcriterium
Als we datapunten toevoegen totdat er geen meer over zijn, riskeren we dat op het einde ook
slechte voorspellingen zullen worden toegevoegd die de RMSE niet ten goede zullen komen.
Daarom kan het belangrijk zijn om vroegtijdig te stoppen met het toevoegen van datapunten.
Een mogelijk stopcriterium zou het volgende kunnen zijn: we stoppen van zodra de gemiddelde RMSE op de validatiesets niet meer afneemt. Bij het testen hiervan merken we echter
dat de RMSE op de validatiesets erg variabel is, wat er zou toe leiden dat het algoritme al na
enkele iteraties zou stoppen (zie Figuur 7.6). Bovendien zien we dat de gemiddelde RMSE
op de validatieset bijna geen verband heeft met de RMSE op uiteindelijke testset. Het lijkt
dan ook niet nuttig om dit stopcriterium uit te proberen.
Een andere mogelijkheid zou kunnen zijn om te stoppen wanneer de standaardafwijking op
de voorspellingen van de deelmodellen te groot wordt. Als dat het geval is, is de kans kleiner
dat de uitmiddeling van alle deelmodellen de juiste score oplevert. De moeilijkheid bestaat
er nu in om de juiste maximale waarde te vinden voor de standaardafwijking. Aangezien de
RMSE op de testset ongeveer 10 is, en we willen dat de toegevoegde datapunten een kleinere
fout hebben dan het gemiddelde, zetten we deze grens op 10.
Het resultaat van de invoering van het stopcriterium is te vinden in Figuur 7.7. We kunnen
44
Figuur 7.7: RMSE in functie van het aantal gescoorde datapunten voor co-training zonder
stopcriterium, met stopcriterium, en standaard ELR
45
uit deze figuur besluiten dat het stopcriterium weinig effect heeft op de prestatie van het
co-trainingsalgoritme.
46
Hoofdstuk 8
Conclusie en verder onderzoek
In dit hoofdstuk zullen we enkele algemene conclusies trekken uit onze experimenten (zie
Sectie 8.1). In Sectie 8.2 zullen we bespreken wat de mogelijkheden nog zijn voor verder
onderzoek.
8.1
Conclusie
We kunnen besluiten dat co-training en clustering (en dus semi-gesuperviseerd leren in het
algemeen) momenteel nog geen verbetering kunnen opleveren. Bij clustering hebben we het
probleem dat de clusters te weinig gescoorde data bevatten om daaruit een goede regressor te
kunnen afleiden. Voor co-training blijkt het moeilijk een maat te vinden die kan inschatten
welke datapunten voldoende goed voorspeld werden. Doordat slechte voorspellingen vaak
vroeg toegevoegd worden, kunnen fouten propageren en ervoor zorgen dat volgende datapunten ook een slechtere voorspelling krijgen.
Om de keuze te kunnen maken tussen kNN en ELR, zetten we de twee even naast elkaar in
Figuur 8.1. We zien dat kNN het beter doet dan ELR voor alle datasets. Bovendien is het
kNN algoritme ook sneller dan ELR. Op basis van deze twee bevindingen, raden we aan om
te kiezen voor kNN.
8.2
Verder onderzoek
In verder onderzoek zou kunnen gezocht worden naar een kwaliteitsmaat die correct voorspelde datapunten beter zou kunnen identificeren. Het kan hierbij handig zijn om ook de a
priori waarschijnlijkheid van de scores in rekening te brengen, aangezien in Figuur 5.1 kon
gezien worden dat er veel meer data voorhanden is voor hoge scores. Dit probleem zou ook
kunnen omzeild worden door de dataset uniformer te proberen maken.
Een andere interessante piste om te onderzoeken is of het niet beter is te werken met twee
regressors die niet op dezelfde dataset werken, maar met een andere set van kenmerken. Op
die manier kunnen we meer data gebruiken en zullen de regressors toch verschillend zijn.
47
Figuur 8.1: RMSE in functie van het aantal gescoorde datapunten voor co-training en standaard kNN en ELR
48
Hierop aansluitend kan het ook interessant zijn om meer dan twee regressors te gebruiken.
Wanneer voldoende ongescoorde data voorhanden is, kunnen meer regressors zorgen voor een
betrouwbaardere score. De regressors kunnen werken op verschillende data- en/of kenmerkensets, en voegen een voorspelling toe aan de gescoorde datasets van alle andere regressors.
Meerdere regressors zorgen er natuurlijk ook voor dat het standaard algoritme beter zal
presteren, waardoor we niet zeker zijn dat het verschil tussen co-training en het standaard
algoritme groter zal worden.
49
Bibliografie
[1] Avrim Blum en Tom Mitchell, Combining labeled and unlabeled data with co-training,
Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT
98), 1998, pp. 92-100.
[2] Colorado Reed, Compendium of Machine-Learning-Related Knowledge: A Quick Reference, University of California, Berkeley, 2012.
[3] Luca Didaci en Fabio Roli, Using Co-training and Self-training in Semi-supervised Multiple Classifier Systems, Lecture Notes in Computer Science 2006, vol. 4109, pp. 522-530.
[4] Matthias Seeger, Learning with labeled and unlabeled data, Technical Report, University
of Edinburgh, Edinburgh, UK, December 2002.
[5] Shuo Xu et al., Semi-supervised Least-squares Support Vector Regression Machines, Journal of Information and Compututing Science 2011, vol. 8, pp. 885-892.
[6] Xiaojin Zhu, Semi-Supervised Learning Tutorial, Technical Report, Department of Computer Sciences, University of Wisconsin, Madison, USA, 2007.
[7] ZH. Zhou en Ming Li, Semi-Supervised Regression with Co-Training, Proceedings of the
19th International Joint Conference on Artificial Intelligence 2005, Edinburgh, Scotland,
pp. 908-913.
[8] Catherine Middag. Automatic Analysis of Pathological Speech. Universiteit Gent, 20122013.
50
Lijst van tabellen
6.1
6.2
6.3
6.4
6.5
7.1
Overzicht van de RMSE voor verschillende k-waarden, de beste waarde per
dataset werd schuin gezet . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
Overzicht van de RMSE voor verschillende waarden van β bij formule (6.1)
(kwadraat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
Overzicht van de RMSE voor verschillende waarden van β bij formule (6.2)
(geen kwadraat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
Overzicht van de RMSE voor verschillende waarden van α voor de betrouwbaarheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
Overzicht van de RMSE voor verschillende clustergroottes met k = 1, de kleinste waarde staat schuin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Overzicht van de RMSE met een verschillend aantal random permutaties voor
standaard ELR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
51
Lijst van figuren
1.1
Verschil tussen classificatie en regressie . . . . . . . . . . . . . . . . . . . . . .
2
2.1
Algemene flow-charts voor training en scoring met behulp van co-training . .
6
3.1
Schematische voorstelling van ELR . . . . . . . . . . . . . . . . . . . . . . . .
16
5.1
Verdeling van de scores in de volledige dataset
. . . . . . . . . . . . . . . . .
22
5.2
RMSE in functie van het aantal gescoorde datapunten voor gesuperviseerde
regressie als bovengrens, de lijn van gesuperviseerd 150 werd doorgetrokken
als ondergrens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
RMSE in functie van het aantal gescoorde datapunten voor standaard kNN
met verschillende k-waarden . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
6.2
De twee afstandsmaten voor kNN . . . . . . . . . . . . . . . . . . . . . . . . .
27
6.3
RMSE in functie van het aantal gescoorde datapunten voor co-training en
standaard kNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
RMSE in functie van het aantal gescoorde datapunten voor co-training met en
zonder betrouwbaarheden . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
Absolute verschil tussen de voorspelde en echte score in functie van de verbetering door toevoeging van het datapunt . . . . . . . . . . . . . . . . . . . . .
32
Absolute verschil tussen de voorspelde en echte score in functie van de gemiddelde afstand van het datapunt tot zijn buren . . . . . . . . . . . . . . . . . .
33
Absolute verschil tussen de voorspelde en echte score in functie van de standaardwafwijking op de scores van de buren . . . . . . . . . . . . . . . . . . .
34
Absolute verschil tussen de voorspelde en echte score in functie van het verschil
tussen de maximale en de minimale score van de buren . . . . . . . . . . . . .
35
RMSE in functie van het aantal gescoorde datapunten voor co-training met
toevoeging op basis van de beste verbetering, de kleinste gemiddelde afstand,
en random toevoeging. Slechts een derde van de ongescoorde datapunten werden toegevoegd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
6.10 RMSE in functie van het aantal gescoorde datapunten voor co-training met en
zonder stopcriterium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
6.1
6.4
6.5
6.6
6.7
6.8
6.9
52
7.1
7.2
7.3
7.4
7.5
7.6
7.7
8.1
Gemiddeld aantal geselecteerde kenmerken in functie van de grootte van de
gescoorde datasets voor zowel de deelmodellen als het volledige model . . . .
39
Vergelijking tussen standaard kNN en standaard ELR voor de RMSE in functie
van het aantal gescoorde datapunten . . . . . . . . . . . . . . . . . . . . . . .
40
RMSE in functie van het aantal gescoorde datapunten voor co-training en
standaard ELR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
Gemiddeld aantal geselecteerde kenmerken in functie van de grootte van de gescoorde datasets voor standaard ELR en co-training ELR voor de deelmodellen
en de volledige regressor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
Absolute verschil tussen de voorspelde en echte score in functie van de standaardafwijking op de voorspelling van de deelmodellen van ELR . . . . . . .
43
RMSE op de testset en gemiddelde RMSE van de validatiesets van ´e´en regressor
in functie van de iteratie, getest voor 60 gescoorde datapunten . . . . . . . .
44
RMSE in functie van het aantal gescoorde datapunten voor co-training zonder
stopcriterium, met stopcriterium, en standaard ELR . . . . . . . . . . . . . .
45
RMSE in functie van het aantal gescoorde datapunten voor co-training en
standaard kNN en ELR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
53
Lijst van Algoritmes
1
2
3
4
5
6
7
8
Bereken h(x) voor kN N . . . . . . . . . . . . .
Co-training met kN N . . . . . . . . . . . . . .
Scoren met clusters . . . . . . . . . . . . . . . .
Algemeen algoritme voor co-training . . . . . .
Kenmerkenselectie met lineaire regressie . . . .
Algemeen raamwerk voor clustering . . . . . .
Algoritme voor K-means clustering . . . . . . .
Algoritme voor incrementele k-means clustering
54
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
8
9
11
17
18
19
19

Productinformatie Combial AS/1x150HIT-DE K TW nw TOC

Lage bouwhoogte luchtkoelers PX

SPIT FIX 3 - Spit Paslode

complete workshopoverzicht januari - juni 2015

multimax met draadst..

Bevolkingsonderzoek darmkanker

Eligibility criteria NL 2015.pdf

OFF ON stijlgids

Model HP DX - High Performance Line voor

structurele vergelijkingsmodellen deel 1