Artikel

Avancerad klassificering med boosting

Problembilden

Klassificerare används i maskininlärning för att sammanföra likartat data i olika grupper, eller klasser. Mängden särdrag som används för att träna klassificerare kan ofta bli väldigt många. Begreppet Curse of dimensionality (Bellman 1961), ungefär Förbannelsen av dimensionalitet, används flitigt i maskininlärning och syftar på olika fenomen som uppstår vid analys av flerdimensionellt data. Mest specifikt påverkar det tiden det tar att träna klassificeraren och i förlängningen prestandan hos klassificeraren.

Idén med "boosting" (eller att stärka) är att endast använda de särdrag som förbättrar prestandan i klassificeraren och på så sätt förbättras exekveringstiden eftersom irrelevanta särdrag inte behöver beräknas.

Vad är "Boosting"?

Boosting är en familj av algoritmer i maskinlärning som används för att omvandla en samlinga svaga inlärare till en enda stark inlärare. Boosting en typ av övervakad inlärning och mer specifikt ensembelinlärning.

Övervakad inlärning handlar om att härleda en funktion från märkt träningsdata. Träningsdatat består av en mängd träningsexempel eller träningsinstanser. I övervakad inlärning är varje instans ett par bestående av ett ingångsobjekt (vanligtvis en vektor) och ett önskat utgångsvärde (även kallad övervakningssignal).

Algoritmer för Övervakad inlärning söker igenom en rymd av möjliga hypoteser för att hitta en enda lämplig hypotes som tros kommer göra bra förutsägelser för ett särskilt problem. Även om hypotesrymden innehåller hypoteser som mycket är väl lämpade för problemet kan det vara mycket svårt att hitta en bra hypotes. Detta leder oss in på ensembleinlärning.

Ensembler kombinerar flera hypoteser för att bilda en förhoppningsvis bättre hypotes. Med andra ord är en ensemble en teknik för att kombinera många svaga inlärare i ett försök att producera en stark inlärare.

En svag inlärningsalgoritm tillämpas på olika fördelningar av träningsdata och resultatet från de enskilda klassificerarna aggregeras till en enda övergripande stärkt klassificerare. Efter varje iteration förändras fördelningen av träningsinstanser utifrån felet nuvarande klassificerare uppvisar mot träningsmängden.

Här studerar vi Adaptiv boosting (AdaBoost), en specifik algoritm inom området boosting. Algoritmen formulerades av Yoav Freund and Robert Schapire och var då den första praktiska tillämpningen av boosting. Utsignalen från den svaga inlärningsalgorimten kombineras med en viktad summa som representerar den stärkta klassificeraren. Än idag är algoritmen en av de mest använda med tillämpningar i flera områden.

Anpassa Bayes klassficierare

Vi utgår från "Ta bort handen i bilden" och skall förbättra klassificeringen som utförs där genom boosting. Därför kommer vi utgå från att du har läst den artikeln.

Rekapitulation

För att kunna stärka Bayes klassificerare behöver vi förändra funktionen som beräknar MAP-parametrar samt funktionen som beräknar diskriminanter. Men vi börjar från början. Skapa en ny m-fil och kalla den för boosting_ta_bort_handen.m. Börja med att läsa in bilderna som vi skall arbeta med genom nedanstående rader.

%% Öppna de två bilderna

hand = imread('hand.ppm', 'ppm');
bok = imread('bok.ppm', 'ppm');
imagesc(hand);
figure;
imagesc(bok);

Precis som tidigare förbereder vi träningsdatat med nedanstående rader kod. Funktionen normalisera_etikettera skapas i artikeln "Ta bort handen i bilden".

%% Förbered träningsdata

data1 = normalisera_etikettera(hand, 0);
data2 = normalisera_etikettera(bok, 1);
traeningsdata = [data1; data2];
figure;
hold on;
plot(data2(:,1), data2(:,2), '.');
plot(data1(:,1), data1(:,2), '.c');
legend('Hand med bok', 'Hand');
xlabel('grön');
ylabel('röd');

Hantera viktade instanser

Vi inför en ny term som kallar för "vikten på en instans":

\begin{equation} \upsilon^m \end{equation}

Insatansen betecknar vi, precis som tidigare, som:

\begin{equation} (x^m, k^m) \end{equation}

Vikten på en instans specificerar dess relativa betydelse. Egentligen skulle det vara samma sak som om träningsmängden innehöll v identiska kopior av en viss instans. Men genom att införa vikter kan vi justera vikterna från en iteration till nästa för att få nästa iteration att fokusera på de felaktiga exemplen.

Målet nu är att skapa en funktion där vikten på instanser som är korrekt klassificerade reduceras medan de vikten på de som är felaktigt klassificerade instanser ökas.

Med viktade instanser blir ekvation 22 och 23 i "Ta bort handen i bilden" istället:

\begin{equation} \mu_{in}^*=\frac{\Sigma_{\{m|k_m=k_i\}}^{M_i}\upsilon^mx_n^m}{\Sigma_{\{m|k_m=k_i\}}^{M_i}\upsilon^m}=E_{\upsilon}[x_n] \end{equation}

\begin{equation} {\sigma_{in}^*}^2=\frac{\Sigma_{\{m|k_m=k_i\}}^{M_i}\upsilon^m(x_n^m-\mu_{in}^*)^2}{\Sigma_{\{m|k_m=k_i\}}^{M_i}\upsilon^m}=E_{\upsilon}[x_n] \end{equation}

Skapa en ny m-fil och kalla den bayes_vikt.m. Funktionen är återgiven i sin helhet nedan.

function [ my,sigma ] = bayes_vikt( data, v )
%% Hitta all data som tillhör klass 0 och klass 1
data_0 = data(find(data(:,3)==0),1:2);
data_1 = data(find(data(:,3)==1),1:2);

v_0 = v(find(data(:,3)==0));
v_1 = v(find(data(:,3)==1));
%% Beräkna antalet instanser i respektive klass
M_0 = size(data_0,1);
M_1 = size(data_1,1);

%% Bestäm MAP 

v_0_utvidgad=repmat(v_0,[1 size(data_0,2)]);
v_1_utvidgad=repmat(v_1,[1 size(data_1,2)]);

my_0 = sum(v_0_utvidgad.*data_0)/sum(v_0);
my_1 = sum(v_1_utvidgad.*data_1)/sum(v_1);

my = [my_0;my_1];

for k=1:M_0
   data_0_center(k,:)=v_0(k)*(data_0(k,:)-my_0(1,:)).^2;
end

for k=1:M_1
   data_1_center(k,:)=v_1(k)*(data_1(k,:)-my_1(1,:)).^2;
end

sigma_0 = sqrt(sum(data_0_center)/sum(v_0));
sigma_1 = sqrt(sum(data_1_center)/sum(v_1));

sigma = [sigma_0;sigma_1];

end

Gå tillbaka till boosting_ta_bort_handen.m och testa funktionen ovan.

%% Testa med en likformig fördelning

M = size(traeningsdata,1);
% Skapa en likformig vikt-vektor
v = (1/M) * ones(M,1);
% Tillämpa bayes-vikt
[my_v sigma_v] = bayes_vikt(traeningsdata,v);
% Tillämpa "vanliga" bayes
[my sigma] = bayes(traeningsdata);

Du skall få samma värden på parametrarna oavsett om du använder bayes eller bayes_vikt.

\begin{equation} \mu^*=\begin{bmatrix} 0,3744 & 0,3316 \\ 0,3609 & 0,3463 \end{bmatrix} \sigma^*=\begin{bmatrix} 0,0553 & 0,0183 \\ 0,0374 & 0,0300 \end{bmatrix} \end{equation}

Adaptiv boosting

Bestäm den starka hypotesen

Nu är det dags att skriva adaboost-algortimen. Sammanfattningsvis kommer den upprepade gånger anropa den svaga inlärningsalgoritmen, i vårt fall bayes_vikt, och efter varje gång uppdatera vikterna såsom det beskrivits tidigare. Det går till såhär:

  • Initiera alla vikter likformigt.

\begin{equation} \upsilon_m=\frac{1}{M} \end{equation}

  • Träna den svaga inläraren med distributionen υ.
  • Bestäm den svaga hypotesen och beräkna felet mellan den viktade fördelningen.

\begin{equation} \varepsilon_t=1-\sum_{m=1}^M\upsilon_t^m\delta(h_t(x^m), k^m) \end{equation}

där

\begin{equation} \delta(h_t(x^m), k^m)=\left\{\begin{matrix} 1 & \text{om } h_t(x^m)=k^m \\ 0 & \text{annars} \end{matrix}\right. \end{equation}

  • Välj

\begin{equation} \alpha =\frac{1}{2}\ln\frac{1-\varepsilon_t}{\varepsilon_t} \end{equation}

  • Uppdatera vikterna enligt

\begin{equation} \upsilon_{t1}^m=\frac{\upsilon_{t1}^m}{Z_t}* \left\{\begin{matrix} \text{e}^{-\alpha_t} & \text{om } h_t(x^m)=k^m \\ \text{e}^{\alpha_t} & \text{om } h_t(x^m) \neq k^m \end{matrix}\right. \end{equation}

Z är en normaliseringsfaktor vald så att 

\begin{equation} \upsilon_{t+1} \end{equation}

blir en distribution

\begin{equation} \sum_m \upsilon_{t+t}^m=1 \end{equation}

Tidigare sa vi ju att den stärka, eller "boostade", klassificeringen av en osynlig instans x erhålls genom att lägga samman de avgivna rösterna från varje enskild Bayes klassificerare:

\begin{equation} h_t=(\mu_{tin}^*, \sigma_{tin}^*) \end{equation}

Eftersom vi har högre förtroende för hypoteser som har ett litet fel (stora värden på α) räknas deras röster relativt sett mer. Den stärkta hypotesen H(x) är därför den hypotes (eller klass) som tar emot majoriteten av rösterna:

\begin{equation} H(x)=K_{max}=argmax_{k_{i}} \sum_{t=1}^T \alpha_t \delta (h_t(x),k_i) \end{equation}

Skapa en ny m-fil och kalla den för adaboost.m. Koden som behövs för att realisera detta i Matlab är återgiven i sin helhet nedan.

function [ my, sigma, p, alpha, klasser ] = adaboost( data, T)
%% Initiera utdata-variabler

% D är som bekant flera oberoende särdrag. 
% N antal särdrag per obsveration.
[D, N] = size(data(:,1:end-1));
% C motsvarar antalet klasser, alltså två stycken.
klasser = unique(data(:,N+1));
C = length(klasser);
% Klassificerarens framröstade vikter
alpha = zeros(T,1);
my = zeros(C,N,T);
sigma = zeros(C,N,T);
p = zeros(T,C);

%% Kör AdaBoost

% Initiera vikt-vektorn
v = (1/D) * ones(D,1);

for t=1:T
   
   % Tillämpa den svaga träningsalgoritmen
   [ my(:,:,t),sigma(:,:,t) ] = bayes_vikt( data, v );
   
   % Beräkna a-priori
   p(t,:) = priori(data,v);
   
   % Beräkna den svaga hypotesen
   ht_x = diskriminant(data(:,1:end-1), my(:,:,t), sigma(:,:,t), p(t,:));
   [dummy, klass] = max(ht_x, [], 2);
   klass = klass - 1;
   % Initiatera vektorn med avvikelser
   delta = zeros(D,1);
   % Beräkna avvikelser
   delta = (data(:,end)==klass);
   % Felet mellan den svaga hypotesen och den viktade fördelningen
   eps_t = 1 - transpose(v)*delta;
   alpha(t) = (1/2)*log((1-eps_t)/eps_t);
   v(find(data(:,end)==klass),:) = v(find(data(:,end)==klass),:)*exp(-alpha(t));
   v(find(data(:,end)~=klass),:) = v(find(data(:,end)~=klass),:)*exp(alpha(t));
   Z_t = sum(v);
   v = v/Z_t;
end

Beräkna den starka hypotesen

För att bestämma den stärkta hypotesen behöver du skapa ytterligare en m-fil. Kalla denna för adaboost_diskriminant.m och lägg in nedanstående rader.

function c = adaboost_diskriminant(data, my, sigma, p, alpha, klasser, T)
[D N] = size(data);
% utdata-vektor
c = zeros(D,1);
% arbetsvektor som har en kolumn för varje klass, alltså två
cc = zeros(D,2);
for t=1:T       
   % beräkna diskriminanter
   g = diskriminant(data, my(:,:,t), sigma(:,:,t), p(t,:));

   % plocka ut värde och kolumn för varje särdrag som har högst
   % sannolikhet
   [dummy klass] = max(g, [], 2);
   % ta bort ett (1) eftersom klass returnerar 1 eller 2 medan vi uttrycker
   % klasser som 0 och 1
   klass = klass - 1;
   % delta-funktion
   h_hand = (klass == klasser(1));
   h_bok = (klass == klasser(2));

   % skapa en viktad summa
   cc(:,1) = cc(:,1) + alpha(t)*h_hand;
   cc(:,2) = cc(:,2) + alpha(t)*h_bok;
end
[dummy c] = max(cc, [], 2);
c = c - 1;
end

Beräkna felet

Vi testar algorimten med T=6 antal parametarar och beräknar felet. Lägg in nedanstående rader i m-filen.

%% Beräkna diskriminanterna

T = 6;
[my sigma p alpha klasser] = adaboost(traeningsdata, T);
klass = adaboost_diskriminant(traeningsdata(:,1:end-1), my, sigma, p, alpha, klasser, T);
boost_fel_traening = 1.0-sum(klass == traeningsdata(:,end))/M

Rita beslutsgräns

För att visualisera arbetet som görs kan vi rita in beslutsgränsen för klassificeringen som kommer göras.

%% Rita beslutsgränsen

figure;
hold on;
plot(data2(:,1), data2(:,2), '.');
plot(data1(:,1), data1(:,2), '.c');
ax = [0.2 0.5 0.2 0.45];
axis(ax);
x = ax(1):0.01:ax(2);
y = ax(3):0.01:ax(4);
[z1 z2] = meshgrid(x, y);
z1 = reshape(z1, size(z1,1)*size(z1,2), 1);
z2 = reshape(z2, size(z2,1)*size(z2,2), 1);
g = adaboost_diskriminant([z1 z2], my, sigma, p, alpha, klasser, T);
gg = reshape(g, length(y), length(x));
[c,h] = contour(x, y, gg, [0.5 0.5]);
set(h, 'LineWidth', 3);
legend('Hand med bok', 'Hand', 'Beslutsgräns');

Ta bort handen

De avslutande stegen här nu är precis som tidigare och det bör därför inte vara några problem att inse vad som händer.

Normalisera bilden

Bilden med boken har vi redan inläst i variabeln bok.  Det är den här bilden vi skall utgå ifrån. Tidigare la vi till den och bilden med handen i traeningsdata. Nu använder vi bara bilden med boken men vi måste börja med att normalisera den. Lägg in nedanstående rader.

%% Normalisera bilden med handen som håller i boken

% Alla pixlar är initialt svarta
bok_rg = zeros(size(bok,1), size(bok,2), 2);
for y=1:size(bok,1)
   for x=1:size(bok,2)
       s = sum(bok(y,x,:));
       if (s > 0)
           bok_rg(y,x,:) = [double(bok(y,x,1))/s double(bok(y,x,2))/s];
       end
   end
end

Utför klassificeringen

Sista steget handlar bara om att ta originalbilden och lägga masken ovanpå. Rent praktiskt eller formellt så är det två matriser som vi har och där vi multiplicerar individuella element med varandra. Att ta bort en pixel innebar som bekant att sätta den till noll så att den framstår som svart.

En godtycklig pixel i bok, exempelvis på rad 4 och kolumn 3, har värdet 128. Om motsvarande element i mask3D har värdet 1 kommer produkten i bi_med_mask fortsatt vara 128. Om elementet i mask3D istället har värdet 0 kommer också produkten i bi_med_mask bli 0.

%% Klassificera pixlarna i bilden och skapa en mask

tmp = reshape(bok_rg, size(bok_rg,1)*size(bok_rg,2), 2);
g = adaboost_diskriminant(tmp, my, sigma, p, alpha, klasser, T);
gg = reshape(g, size(bok_rg,1), size(bok_rg,2));
mask = gg > 0.5;
mask3D(:,:,1) = mask;
mask3D(:,:,2) = mask;
mask3D(:,:,3) = mask;
result_im = uint8(double(bok) .* mask3D);
figure;
imagesc(result_im);

Titta på resultatet nedan och jämför med resultatet från att använda enbart en svag klassificerare.

Hämta källkoden

Mot en avgift kan du hämta hem källkoden som används i artikeln så att du kan testa funktionen direkt! Gå till vår butik för att lägga till i varukorg och betala.

Varför PROSAPIO?

PROSAPIO vill bidra till att unga människor intresserar sig för ingenjörsvetenskap genom att tillgängliggöra kunskap inom intelligenta och autonoma system.

Läs mer om PROSAPIO

Genvägar