Artikel

Grunder i klassificering - Bayes klassificerare

Introduktion

Bilden nedan visar en hand som håller i en bok. Vi skall lära oss grunder i maskininlärning genom att försöka ta bort handen så att bara boken återstår. För att göra det måste vi lära vårt program hur en hand ser ut.

Bok och hand
Bok och hand.

Vi skall titta på färgen i varje pixel och bedöma om det är mest troligt att den tillhör handen eller boken. Om den tillhör handen så ändrar vi färgen på pixeln till svart så att den får samma färg som bakgrunden och därmed försvinner. För att lära oss hur en hand ser ut har vi ytterligare en bild att arbeta med som visar enbart en hand. 

Enbart hand
Enbart hand.

Varje pixel beskrivs av två diskreta egenskaper som vi kallar x1 och x2. Vidare tillhör varje pixel en av två klasser {0, 1} som motsvarar hand och bok. Det är alltså här vi kommer behöva en klassificerare för att säkerställa att rätt pixel hamnar i rätt klass.

Förbered träningsdata

Kort om klassificerare

Med klassifikation menas att likartat data sammanförs i olika grupper, eller klasser. En klassificerare används således för att avgöra vilken klass som varje delmängd av data skall tillhöra. Klassningen utförs enligt statistiska metoder som klassificeraren lärt sig på förhand. Mer formellt så tränas klassificeraren i hur den skall utföra klassningen genom att den i ett träningsskede matas med en träningsmängd av redan klassificerad data. 

Läs in bilderna

Skapa en m-fil och kalla den för ta_bort_handen.m. Lägg in nedanstående rader och titta på bilderna som vi kommer arbeta med.

%% Öppna de två bilderna 
hand = imread('hand.ppm', 'ppm'); 
bok = imread('bok.ppm', 'ppm'); 
imagesc(hand); 
figure; 
imagesc(bok);

Normalisera och etikettera

Tanken nu är att vi skall använda bilden med handen som vår träningsmängd. Vi behöver göra om formatet lite bara så att vi får en Nx3-matris där de två första kolumnerna håller pixels intensitet och den tredje kolumnen håller klassen som pixeln är associerad med. För träningsmängden är detta alltså hand. Vi begränsar oss således till att använda normaliserade röda och grön enligt följande ekvationer:

\begin{equation} \begin{matrix} r_{norm}=\frac{r}{rgb} & g_{norm}=\frac{g}{rgb} \end{matrix} \end{equation}

Skapa en m-fil som du kallar normalisera_etikettera.m och lägg in raderna nedan.

function rg_bi = normalisera_etikettera(bi, etikett) 
% omvandla till double 
bi = double(bi); 
rg_bi = []; 
% gå igenom första dimensionen 
for y=1:size(im,1) 
% gå igenom andra dimensionen 
for x=1:size(im,2) 
% summera rgb-värdet 
s = sum(bi(y,x,:)); 
if (s > 0) 
% ej svart 
rg_bi = [rg_bi; im(y,x,1)/s im(y,x,2)/s etikett]; 
end 
end 
end

Sätt ihop träningsdata

Gå tillbaka till ta_bort_handen.m och lägg in nedanstående rader.

%% 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('green'); 
ylabel('red');

Matrisen med träningsdata innehåller nu alltså data från båda bilderna. Notera dessutom att några pixlar i bok-bilden är felaktigt klassificerade som bok då de i själva verket visar en hand. Vi kommer att förlita oss på vår klassificerare att skilja dessa pixlar från de pixlar som är korrekt etiketterade.

Studera bilden som dyker för att förstå vad det är som vår klassificerare behöver göra.

Intensiteter
Intensiteter

Hypotes för respektive klass

Ordet hypotes definieras ibland som ett antagande om något eller som en föreslagen förklaring till ett fenomen. Med andra ord vill vi formulera en hypotes kring vilken intensitet en pixel skall ha för att sägas tillhöra en viss klass.

Kort om Bayes klassificerare

Bayes klassificerare är en klassificerare som tillämpar Bayes sats. För varje ny obseveration som vi gör i bilden (tittar på en pixels intensitet) så försöker vi identifiera vilken klass den nya obsverationen tillhör (klassificering). Bayes klassificerare tolkas därmed bäst som en beslutsregel klassifieraren är en mätbar funktion där vi utgår från klassen. Vi söker ett estimat på klassen givet en observation uttryckt i en särdragsvektor.

Vi kommer dessutom att anta att särdragen inte korrelerar. Det gör den här klassificeraren till en typ av Naiv Bayes klassificerare. Det naiva i sammanhanget är alltså att antar vi att särdragen är oberoende givet klassen istället för att modellera den fulla betingade fördelningen givet klassen.

I bayesiansk inlärning är vi intresserade av den mest sannolika hypotes givet en viss träningsdata.  När vi har tränat vår klassificerare går vi igenom varje pixel och testar den mot vår hypotes.

Den mest sannolika hypotesen

Vi betecknar vår hypotes som h. I bayesiansk statistik uppfattas h som ett utfall av en stokastisk variabel H, som har en fördelning beskriven av exempelvis en täthetsfunktion. Sannolikheten för h betecknas som

\begin{equation} P(h) \end{equation}

och beskriver sannolikheten a-priori (i förväg), alltså sannolikheten innan vi får information om färgen, eller enklare uttyckt, utan att vi har någon information om färgen. Ponera nu att vi undersöker färginformationen och därigenom gör en observation. Även färginformation ses som ett utfall av en stokastisk variabel och vi anger därför sannolikheten att vi gör en viss observation D som

\begin{equation} P(D) \end{equation}

Vi kan kombinera ovanstående och beskriva en betingad sannolikhet

\begin{equation} P(D|h) \end{equation}

Den är betingad i den bemärkelsen att vi har tingat på att H=h. Resultatet vi får är sannolikheten för observationen D när h är givet. På engelska kallas ovanstående uttryck för likelihood, alltså trolighet. Den hypotes som maximerar värdet på troligheten \(P(D|h)\) kallas den maximalt troliga hypotosen eller maximum likelihood (ML) hypothesis. Formellt handlar det om att estimera eller att göra skattningar av h för att maximera troligheten. Vi kallar detta för ML-metoden. I praktiken innebär det att vi väljer det h som gör att den betingade sannolikheten blir så stor som möjligt. Alltså, den maximalt troliga hypotes som genererade den data som vi har observerat.

\begin{equation} h_{ML}=argmax_{h\in H}P(D|h) \end{equation}

Uttrycket skulle med andra ord innebära att vi känner till om h härstammar från handen eller inte. I bayesiansk inlärning är vi istället intresserade av sannolikheten för hypotesen h  givet det observerade datat D. Vi vill göra en klassificering baserat på vad vi har sett. Bayes sats är ett verktyg för att beräkna sannolikheten a-postiori (=i efterhand) eftersom den säger att

\begin{equation} P(h|D)=\frac{P(D|h)P(h)}{P(D)} \end{equation}

Ovanstående uttryck är grunden för bayesianks klassificering eftersom det speglar vår tilltro till att h håller efter att vi har sett D. Vi vill alltså välja den mest sannolika hypotes givet den observervation som vi gjort. Man kan uppfatta detta som att vi uppdaterar a-priori-fördelningen av H med observationen D och på såvis erhåller fördelningen a-posteriori för H givet observationen D.  

På motsvarande sätt som ML så förekommer begreppet maximum a-posteriori probability (MAP) som den mest sannolika hypotes bland alla möjliga hypoteser:

\begin{equation} h_{MAP}=argmax_{h\in H}P(h|D) \end{equation}

Här har vi alltså ett uttryck för att identifiera en hypotes för intensiteten i en pixel som krävs för en viss klass.

Modell över intensiteten

Vi skall nu skapa en modell över vårt data. Vi skall först införa lite beteckningar. Observationen D betecknar vi som

\begin{equation} \vec{x}=\{x_1,...,x_N\} \end{equation}

vilket motsvarar en viss pixel med N antal egenskaper eller särdrag som vi antar vara okorrelerade. I vårt fall använder vi två särdrag: intensiteterna för rött och grönt.

Hypotesen h är relaterad till en viss klass och vi betecknar därför denna som \(k_i\) där i=0 är hand och i=1 är bok. Troligheten \(P(D|h)\) betecknar vi alltså som \(p(\vec{x}|k_i)\) och vi approximerar då en multivariat normalfördelning. Täthetsfunktionen för en modell eller hypotes med diagonal kovarians-matris ges av

\begin{equation} p(\vec{x}|k_i)=\prod_{n=1}^{N}(\frac{1}{\sqrt{2\pi \sigma_{in}^2}})e^{-\sum_{n=1}^{N}\frac{(x_n-\mu_{in})^2}{2\sigma_{in}^2}} \end{equation}

Resultatet, p(x|ci), ger alltså ett mått på hur troligt det är att obsevera pixeln \(\vec{x}\) givet klassen \(k_i\). Du minns säkert att vi, i bayesiansk inlärning, istället var intresserade av sannolikheten för klassen \(k_i\) givet den observerade pixeln \(\vec{x}\), som vi betecknar som \(p(k_i|\vec{x})\)

Sammanfattningsvis ges strukturen på en bayesiansk klassificerare av troligheterna, \(p(\vec{x}|k_i)\), samt a-priori-sannolikheterna, \(p(k_i)\) och \(p(\vec{x})\)\(p(k_i)\) är helt enkelt frekvensen av klass \(k_i\) i datamängden.

\begin{equation} p(k_i)=\alpha_i \end{equation}

Vi använder Bayes sats för att räkna ut a-posteriori-sannolikheterna, \(p(k_i|\vec{x})\):

\begin{equation} \label{eq:aposteriori} p(k_i|\vec{x})=p(\vec{x}|k_i)\frac{p(k_i)}{p(x)}=\prod_{n=1}^{N}(\frac{1}{\sqrt{2\pi \sigma_{in}^2}})e^{-\sum_{n=1}^{N}\frac{(x_n-\mu_{in})^2}{2\sigma_{in}^2}}\frac{\alpha_i}{p(\vec{x})} \end{equation}

Resultatet, \(p(k_i|\vec{x})\), är en täthet, ett mått på sannolikheten, som vi använder som grund när vi klassificerar. Om sannolikheten för klassen \(k_i\) är tillräckligt stor så kan vi anta att pixeln \(\vec{x}\) är en del av klassen. 

Den mest sannolika hypotes a-posteriori (MAP) är, återigen, den som bäst förklarar datat. Vi betecknar denna som

\begin{equation} \{\vec{\mu_i^*},\vec{\sigma_i^*}\} \end{equation}

Kom ihåg att \eqref{eq:aposteriori} enbart ger sannolikheten a-posteriori för en enda särdragsvektor, \(\vec{x}\). I bilden har vi flera pixlar. Antag därför att D innehåller, inte en bara en, utan flera oberoende särdragsvektorer, \(D=\{ \vec{x}^1,..., \vec{x}^{M_i}\}\), tilllhörande klass \(k_i\)\(M_i\)är antalet instanser som tillhör klassen.

Sannolikheten a-posteriori för ci givet hela datamängden D är proportionerlig mot produkten av de individuella sannolikheterna a-posteriori:

\begin{equation} \label{eq:postprob} P(k_i|D)\sim \prod_{\{m|k=k_i\}}^{M_i}p(k_i|\vec{x}^m) \end{equation}

Den mest sannolika hypotes a-posteriori (MAP) är, återigen, den som bäst förklarar datat. Vi beräknar den genom att maximera \eqref{eq:postprob} med avseende på \(\{\vec{\mu_i},\vec{\sigma_i}\}\):

\begin{equation} \{\vec{\mu_i^*},\vec{\sigma_i^*}\}=argmax_{\vec{\mu_i} ,\vec{\sigma_i}}p(k_i|D) \end{equation}

Men istället för att maximera ovanstående ekvation så använder vi en vanlig transformation. Vi väljer att maximera det mindre komplexa uttrycket, logaritmen av ekvation \eqref{eq:postprob}:

\begin{align} \log p(c_i|D)= &- \frac{M_i}{2}\sum_{n=1}^{N}\log{2\pi \sigma_{in}^2} \\ \label{eq:logmap} &- \sum_{\{m|c_m=c_i\}}^{M_i}\Sigma_{n=1}^{N}\frac{(x_n^m-\mu_{in})^2}{2\sigma^2}\log{\alpha_i}-\log{p(\vec{x}^m)} \end{align}

För att hitta maximum sätter vi de partiella derivatorna av \(\log{p(k_i|\vec{x})}\) med avseende på \(\mu_{in}\) och \(\sigma_i\) lika med noll. Eftersom a-priori av datat \(\log{p(\vec{x}^m)}\) inte beror på vår modell försvinner den sista termen i ekvation \eqref{eq:logmap}.

\begin{equation} \frac{\partial\log p(k_i|D)}{\partial\log \mu_{in}}=\sum_{\{m|k_m=k_i\}}^{M_i}-\frac{(x_n^m-\mu_{in})}{\sigma_{in}^2}=0 \end{equation}

\begin{equation} \frac{\partial\log p(k_i|D)}{\partial\log \sigma_{in}}=-\frac{M_i}{\sigma_i}\sum_{\{m|c_m=c_i\}}^{M_i}\frac{(x_n^m-\mu_{in})^2}{\sigma_{in}^3}=0 \end{equation}

Från dessa kan vi nu få den mest sannolika hypotesen (MAP) baserat på vår modell över intensiteten:

\begin{equation} \mu_{in}^*=\frac{\Sigma_{\{m|c_m=c_i\}}^{M_i}x_n^m}{M_i}=E\left [ x_n \right ] \end{equation}

\begin{equation} {\sigma_{in}^{*}}^{2}=\frac{\Sigma_{\{m|c_m=c_i\}}^{M_i}(x_n^m-\mu_{in}^*)^2}{M_i}=E\left [ (\vec{x}_n^m-\vec{\mu}_{in}^*)^2 \right ] \end{equation}

Beräkna parametrarna i respektive hypotes

Skapa nu en ny m-fil som du kallar för bayes.m. Den här skall hjälpa oss att beräkna my och sigma för respektive klass. Lägg in nedanstående rader i filen.

function [mu, sigma] = bayes(data) 
% D är som bekant flera oberoende särdrag 
D = data(:,1:end-1); 
% N är antalet särdrag i varje pixel som vi använder 
N = size(D,2); 
% hur många klasser? 
c = unique(data(:,end)); 
% C är antalet klasser 
C = length(c); 
% initiera utdata 
mu = zeros(C,N); 
sigma = zeros(C,N); 
% För varje klass... 
for i=1:C 
% Särdrag i just den här klassen. 
xmn = D(find(data(:,end)==c(i)),:); 
% Antelet instanser som tillhör klassen 
M = size(xmn,1); 
% Medelvärdet av alla särdrag i just den här klassen 
mu(i,:) = sum(xmn)/M; 
% Vi beräknar sigma i tre steg. Först skapar vi matrisen mumat 
% som en lika stor matris som ci 
mumat = repmat(mu(i,:),M,1); 
% Vi subtraherar med medelvärdet och kvadrerar 
centered = (xmn - mumat).^2; 
% Slutligen tar vi kradratroten på summan 
sigma(i,:) = sqrt(sum(centered,1) / M);
end
end

Lägg in nedanstående rader i ta_bort_handen.m.

%% Beräkna parametrarna i respektive hypotes 
[my, sigma] = bayes(traeningsdata); 
theta = [0:0.01:2*pi]; 
x1 = 2*sigma(1,1)*cos(theta) + my(1,1); 
y1 = 2*sigma(1,2)*sin(theta) + my(1,2); 
x2 = 2*sigma(2,1)*cos(theta) + my(2,1); 
y2 = 2*sigma(2,2)*sin(theta) + my(2,2); 
plot(x1, y1, 'm'); 
plot(x2, y2, 'k');

Det första som sker är att vi skapar träningsdata på det sätt som beskrivs i avsnittet med samma namn. Nästa steg är att estimera parametrarna för respektive hypotes. Vi kan kontrollera att vårt estimat stämmer genom att rita in ett 95%-konfidensintervall:


Konfidensintervall

Färdigställ klassificeraren

Hittils har vi arbetat med träningsdata där vi alltså har känt till klassen för varje särdrag. Nu är vi redo att börja klassificera data på riktigt.

Ekvationens diskriminant

Formellt behöver vi behöver beräkna diskriminantfunktioner för att förutsäga klassen av ett inte tidigare känt särdrag. Den mest sannolika klassificeringen är den som maximerar a-posteriori \(p(k_i|\vec{x})\) från ekvation \eqref{eq:aposteriori}:

\begin{equation} k^*=argmax_{k_i\in H}p(k_i|\vec{x}) \end{equation}

Precis som tidigare är enklare att arbeta med logaritmen av uttrycket:

\begin{equation} \log p(k_i|\vec{x})=\log \alpha_i-\frac{N\log(2\pi)}{2}-\sum_{n=1}^{N}\log\sigma_{in}-\sum_{n=1}^{N}\frac{(x_n-\mu_{in})^2}{2\sigma_{in}^2}-\log p(\vec{x}) \end{equation}

Vi kan stryka \(-N\log2(2\pi))/2\) och \(\log{p(\vec{x})}\) eftersom de inte beror på  \(\alpha_i, \vec{\mu}, \vec{\sigma_i}\) och därför är identiska för alla klasser:

\begin{equation} g_i(\vec{x})=\log \alpha_i-\sum_{n=1}^{N}\log\sigma_{in}-\sum_{n=1}^{N}\frac{(x_n-\mu_{in})^2}{2\sigma_{in}^2} \end{equation}

Beräkna diskriminanterna

Skapa en m-fil och kalla den för diskriminant.m. Lägg in nedanstående rader.

function g = diskriminant(data, mu, sigma, p) 
% N är antalet särdrag i varje pixel som vi använder 
% M är antalet instanser som tillhör klassen. Mi kommer kommer inkludera 
% alla klasser. [Mi N] = size(data); 
% C är antalet klasser 
C = size(mu,1); 
% Vi initierar utdatat g = zeros(Mi,C); 
% My för handen gör vi till storlek M 
mu_0_stl_M=repmat(mu(1,:),Mi,1); 
% My för boken gör vi till storlek M 
mu_1_stl_M=repmat(mu(2,:),Mi,1); 
% Sigma2 för handen gör vi till storlek M 
sigma2_0_stl_M=repmat(2*(sigma(1,:).^2),Mi,1); 
% Sigma2 för boken gör vi till storlek M 
sigma2_1_stl_M=repmat(2*(sigma(2,:).^2),Mi,1); 
% Utdata för handen. sum(A,dim) innebär att raderna summeras 
g(:,1) = log(p(1)) - sum(log(sigma(1,:))) - sum((((data-mu_0_stl_M).^2)./(sigma2_0_stl_M)),2); 
% Utdata för boken. sum(A,dim) innebär att raderna summeras 
g(:,2) = log(p(2)) - sum(log(sigma(2,:))) - sum((((data-mu_1_stl_M).^2)./(sigma2_1_stl_M)),2); 
end

Återgå till ta_bort_handen.m och lägg in nedanstående rader för att beräkna diskriminanterna.

%% Beräkna diskriminanterna 
[M N] = size(traeningsdata); 
p = priori(traeningsdata); 
g = diskriminant(traeningsdata(:,1:2), my, sigma, p); 
[dummy klass] = max(g, [], 2); 
klass = klass - 1; 
fel_treaning = 1.0-sum(klass == traeningsdata(:,end))/M

Rita beslutsgränsen

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

%% Rita beslutsgränsen 
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 = diskriminant([z1 z2], my, sigma, p); 
gg = g(:,1) - g(:,2); 
gg = reshape(gg, length(y), length(x)); 
[c,h] = contour(x, y, gg,[0.0 0.0]); 
set(h, 'LineWidth', 3);
Särdrag med beslutsgräns.
Särdrag med beslutsgräns.

Ta bort handen

Nu är det dags att klassificera pixlar i bilden med handen som håller boken utifrån den klassificerare som vi har tränat, för att därefter ta bort dem som vi klassificerat som en del av handen.

Normalisera

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

Klassificera pixlarna

Klassificeringen utför vi genom att först beräkna diskriminanterna och därefter skapa en mask där de pixar som är klassificerade som en del av handen sätts till noll. Lägg in nedanstående rader.

%% Klassificera pixlarna i bilden och skapa en mask 
% Omforma så att vi får två kolumner 
tmp = reshape(bok_rg, size(bok_rg,1)*size(bok_rg,2), 2); 
g = diskriminant(tmp, my, sigma, p); 
gg = g(:,1) - g(:,2); 
% Omforma tillbaka till originalet 
gg = reshape(gg, size(bok_rg,1), size(bok_rg,2)); 
% Logisk operation. Pixlar med värden mindre än noll blir ett. 
% Pixlar med värden större än eller lika med noll blir noll. 
mask = gg < 0; 
mask3D(:,:,1) = mask; 
mask3D(:,:,2) = mask; 
mask3D(:,:,3) = mask;

Applicera masken över originalet

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.

%% Applicera masken på bilden 
bi_med_mask = uint8(double(bok) .* mask3D); 
figure; 
imagesc(bi_med_mask);
Handen är borttagen från originalbilden.
Handen är borttagen från originalbilden.

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