# Calculation of the output of a neural network

(1)

## Artificial Neural Networks

### Contains:

ex. 1, 5, 31, 7, 9, 17, 18, 36, 14, 20, 21, 22, 15, 26, 19

from the 2022f version of the ML exercise book by L. Ciortuz et al.

(2)

### CMU, 2010 fall, Aarti Singh, HW5, pr. 4.1.1

(3)

Consider˘am ret¸eaua neuronal˘a din figura al˘aturat˘a. Toate unit˘at¸ile acestei ret¸ele neu- ronale sunt de tip prag, adic˘a folosesc pentru activare funct¸ia sign definit˘a prin sign(z) = 1 dac˘a z ≥ 0 ¸si −1ˆın rest. Pentru unitatea de pe nivelul de ie¸sire (l˘asat˘a nenumerotat˘a), pon- derea corespunz˘atoare termenului liber (x0 = 1) este 0.

a. Scriet¸i funct¸ia matematic˘a calculat˘a de fiecare dintre unit˘at¸ile ret¸elei, ˆın raport cu intr˘arile x1 ¸si x2. Vet¸i nota cu oi (unde i = 1, . . . ,4) ie¸sirile unit˘at¸ilor de pe nivelul ascuns

¸si cu o ie¸sirea ret¸elei, adic˘a valoarea produs˘a de c˘atre unitatea de pe nivelul de ie¸sire.

b. Calculat¸i output-ul ret¸elei atunci cˆand intr˘arile x1 ¸si x2 iau valori ˆın mult¸imea {−1,1}.

x1

x2

x0=1

x0=1

o

−1

−1

−1

−1 1

1

−1

1

−1

−1

−1

−1

−1 1 1

1

2

3

4 1

(4)

1

1

2

1

2

2

1

2

1

2

3

1

2

1

2

4

1

2

1

2

1

2

1

1

2

2

1

2

3

1

2

4

1

2

1

2

1

2

3

4

(5)

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

(6)

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

1

2

(7)

x2 x1

x0=1

x0=1

o1

o2 1

0 0

1

o

−1

−1

−1

−1 1

1

−1

1

−1

−1

−1

−1

−1 1

1 1

(8)

(9)

d

### as long as the function is still binary.

(10)

Let S denote the set of all possible d-bit binary vectors. For any function f ∈ F, define Tf = {b ∈ {0,1}d|f(b) = 1}. We construct a neural network with one hidden layer to represent f as follows:

The neural network has |Tf| hidden units, each of which corresponds to a distinct binary vector in Tf. The weights from the input layer to the i-th hidden unit are determined by the values of the corresponding binary vector bi: the j-th weight is 1 if bij is 1 and −1 otherwise. The activation functions in the hidden units are threshold functions:

hi(v) =

1 if v ≥ Pd

j=1 bij, 0 otherwise.

It is easy to see that hi outputs 1 if and only if the input is bi. The weights from all hidden units to the output layer are 1, and the activation function in the output unit is the identity function.

To show that the above neural network represents f, we first note that for every b in Tf exactly one hidden unit, the one corresponding to b, outputs 1, and therefore the neural net outputs 1. For any b 6∈ Tf, all hidden units output 0, and the neural network outputs 0. This completes of the proof.

(11)

### implements (A ∨ ¬ B) xor ( ¬ C ∨ D).

(12)

Explicitˆand definit¸ia funct¸iei logice xor ¸si apoi aplicˆand regulile lui DeMorgan, expresia boolean˘a din enunt¸ devine:

(A∨ ¬B) xor (¬C ∨D) = [(A ∨ ¬B) ∧ ¬(¬C ∨D)]∨[¬(A∨ ¬B) ∧(¬C ∨ D)]

= [(A ∨ ¬B) ∧(C ∧ ¬D)] ∨[(¬A ∧B) ∧(¬C ∨D)]

ˆIntrucˆat operatorii logici ∨ ¸si ∧ sunt distributivi unul fat¸˘a de cel˘alalt, rezult˘a c˘a:

(A∨ ¬B) xor (¬C∨D) = (A∧C ∧ ¬D)∨(¬B∧C∧ ¬D)∨(¬A∧B∧ ¬C)∨(¬A∧B∧D) Fiecare din cele patru paranteze din partea dreapt˘a a egalit˘at¸ii de mai sus poate fi reprezentat˘a cu ajutorul unui perceptron-prag cu patru intr˘ari, ¸si anume cˆate o intrare pentru fiecare din cele trei variabile boolene din paran- tez˘a, plus o intrare pentru termenul liber.

De exemplu, conjunct¸iei A∧C ∧ ¬D ˆıi putem asocia inegalitatea x+z−t > 5/2, deci ponderile intr˘arilor perceptronului corespunz˘ator vor fi −5/2, 1, 1 ¸si −1.) Cei patru perceptroni vor fi plasat¸i pe primul nivel ascuns al ret¸elei pe care o construim.

(13)

Apoi, ie¸sirile acestor patru perceptroni vor consti- tui intr˘ari pentru un alt perceptron-prag, care s˘a reprezinte disjunct¸ia a patru variabile boolene. (Acestui perceptron, situat pe nivelul de ie¸sire, ˆıi putem asocia, de exemplu, inegalitatea x+y +z +t > −7/2.)

Ret¸eaua neuronal˘a rezultat˘a este cea din figura al˘aturat˘a.

1 1

1

1 1 1

1 1

1 1

1

−1

−1

1

1

A

B

D C

−5/2

−5/2

−1 1 1 7/2

−5/2

−5/2

−1

−1

−1

(14)

### CMU, 2010 fall, Aarti Singh, HW5, pr. 4.1.2

(15)

Consider the function f : R → R defined as f(x1, x2) = 1 for x1, x2 ≥ 0 or x1, x2 < 0, and −1 otherwise. It was shwown (see CMU, 2010 fall, Aarti Singh, HW5, pr. 4.1.1) that it can be represented using a network of threshold perceptrons with two hidden layers.

Show that no neural network made of threshold units, with only one hidden layer, can represent f. For simplicity, you shall assume that the number of hidden units in a hidden layer is finite, but it can be arbitrarily large.

### Hint

When there is only one hidden layer, the separating border corresponding to each hidden unit is a line in the 2-d plane such that the hidden unit outputs +1 on one side of the line and −1 on the other.

Consider a circular neighborhood (V) of the origin such that if a separating line determined by a hidden unit that crosses the neighborhood V , then it passes through the origin. (Since the number of hidden units is finite, we can always find such a neighborhood.)

Can any neural network made only of threshold units, with one hidden layer, represent f in the neighborhood V?

(16)

Given any neural network with one hidden layer of finite hidden units, we will consider a circular neighborhood of the origin

Nε = {(x1, x2)| q

x21 +x22 ≤ ε},

with ε being [less then] the minimum of the distances from the origin to the separating lines (hidden units) which do not pass through the origin.

We will consider two cases:

### Case 1

: No line crosses the neighborhood. In this case, the neural network must output the same value in this neighborhood, but f outputs 1 or −1. Therefore, neural networks in this case cannot represent f.

x2

x1

−1

+1 −1

+1

O

(17)

these lines must all pass through the origin. Denote the set of the hidden units corresponding to these lines as O. Let us consider a point P = (p1, p2) situated in this neighborhood and in the first quadrant, that does not fall on any line (see the figure). We can always find such a point because the number of the hidden units, hence the number of lines, is finite. By symmetry, the point P = (−p1,−p2), also in the neighborhood, does not fall on any line either, and f(P) = f(P) = 1. Let yh(P) ∈ {1,−1} denote the output of the hidden unit h on P.

### x

1

−1

+1 −1

+1

O Q’

Q P’

P

It is easy to see the following:

yh(P) = −yh(P) ∀h ∈ O, and yh(P) = yh(P) ∀h 6∈ O.

Let wh denote the weight from the hidden unit h to the output unit. We thus have X

h

whyh(P) = X

h∈O

whyh(P) + X

h6∈O

whyh(P) = − X

h∈O

whyh(P) + X

h6∈O

whyh(P)

= −X

h

whyh(P) + 2 X

h6∈O

whyh(P). (1)

(18)

Similarly, we can pick Q and Q = −Q in the fourth and the second quadrantal parts of the neighborhood, and have that

X

h

whyh(Q) = −X

h

whyh(Q) + 2 X

h6∈O

whyh(Q). (2) Since f(P) = f(P) = 1 and f(Q) = f(Q) = −1, in order to represent f, the free weight w0 (corresponding to x0 = 1) for the output unit of the neural net must satisfy the inequalities

X

h

whyh(P) ≥ −w0 , X

h

whyh(P) ≥ −w0 (1)

⇒ X

h6∈O

whyh(P) ≥ −w0, X

h

whyh(Q) < −w0 , X

h

whyh(Q) < −w0 (2)

⇒ X

h6∈O

whyh(Q) < −w0, which cannot happen because P

h6∈Owhyh(P) = P

h6∈Owhyh(Q), since yh(P) = yh(Q) for every h 6∈ O. This completes the proof.

(19)

(20)

I

S

(21)

0

k

0(k)

1(k)

(22)

### R˘ aspuns

Este imediat c˘a din ipoteza |f(x)−f(x)| ≤ L|x−x|, ˆın cazul ˆın care |x−x| ≤ ε L, rezult˘a

|f(x) −f(x)| ≤ ε (3) A¸sadar, este de dorit s˘a ,,acoperim“ intervalul [C, D) cu intervale de lungime

L (sau mai mic˘a):

[C, C + 2ε

L ), [C + 2ε

L , C + 22ε

L ), . . . , [C + (K −1)2ε

L , D))

¸si s˘a lu˘am punctele x de forma ξi = (αii)/2, pentru cu i = 1, . . . , K, unde K not.=

(D−C) L 2ε

,

α1 = C, β1 = α2 = C + 2ε

L , . . . , βK−1 = αK = C + (K −1)2ε

L , βK = D.

A¸sadar, prin ξi am notat mijlocul intervalului i de mai sus, [αi, βi).

(23)

ˆIn continuare, vom ar˘ata c˘a putem construi o ret¸ea neuronal˘a cu un singur nivel ascuns ¸si care folose¸ste doar unit˘at¸i de tip liniar sau de tip prag, astfel ˆıncˆat

pentru ∀x ∈ [C, D), dac˘a x ∈ [αi, βi), atunci out(x) def.= f(ξi). (4) ˆIn consecint¸˘a, dac˘a ˆın relat¸ia (3) vom ˆınlocui x cu ξi, va rezulta imediat c˘a

|f(x) −out(x)| ≤ ε.

Revenind acum la proprietatea (4), vom ar˘ata c˘a exist˘a o ret¸ea avˆand K unit˘at¸i pe nivelul ascuns (¸si o singur˘a unitate de ie¸sire), astfel ˆıncˆat, dac˘a x ∈ [αi, βi), atunci unitatea i de pe nivelul ascuns se activeaz˘a (producˆand valoarea f(ξi), iar toate celelalte unit˘at¸i de pe nivelul ascuns r˘amˆan neactivate (adic˘a produc output 0). Prin urmare, rezultatul va fi exact cel dorit.

(24)

Conform problemei CMU, 2007 fall, Carlos Guestrin, HW2, pr. 4.b, exist˘a o ret¸ea neuronal˘a care produce valoarea c = f(ξi) pentru orice input x ∈ [αi, βi)

¸si 0 ˆın rest, ¸si care folose¸ste funct¸ii de activare gS pe nivelul ascuns ¸si gI pe nivelul de ie¸sire:

gS

−βi

−αi

oi ξi

f( ) gS

ξ i

−f( ) gI

x0= 1

1

1 1

x

ξi

) [ )

[β

αi i

0 x

y

c = f( )

(25)

,,Ansamblˆand“ K astfel de ret¸ele, vom obt¸ine ret¸eaua din figura al˘aturat˘a.

Output-ul acestei ret¸ele este exact cel dorit (deci satisface condit¸ia din enunt¸):

out(x) =







f(ξ1) pt. x ∈ [α1 = C, β1) f(ξ2) pt. x ∈ [α2 = β1, β2) . . . .

f(ξK) pt. x ∈ [αK = βK−1, βK = D)

⇒ |f(x) −out(x)| ≤ ε, ∀x ∈ [C, D).

gI

−β1

−β2

−α2

gS

gS

gI

−αK

−βK gS

S

gI

gS

gS

gI

ξ1 f( )

ξ1

−f( )

ξ2 f( )

ξ2

−f( )

ξK f( )

ξK

−f( )

1

2

K 0= 1

x

level 1 level 2 level 3

o 1

1

1

x

1

x

1

1

1

1 1

x

(26)

Neajunsul este c˘a ret¸eaua aceasta are dou˘a niveluri as- cunse, ˆın loc de unul singur, a¸sa cum se cere ˆın enunt¸.

Totu¸si, el poate fi ,,corectat“ imediat, comasˆand nivelurile 2 ¸si 3 — formate doar din unit˘at¸i liniare — ˆıntr-o singur˘a unitate liniar˘a (care va constitui nivelul

de ie¸sire al noii ret¸ele), ca ˆın figura al˘aturat˘a.

gI

gS

gS

gS

gS

gS

gS

gS

ξK−1 f( )

ξK−1

−f( )

ξK f( )

ξK

−f( ) ξ2 f( )

ξ1

−f( )

ξ2

−f( )

(27)

De asemenea, datorit˘a faptului c˘a β1 = α2, β2 = α3, . . . , βK−1 = αK, nivelul ascuns (al acestei noi ret¸ele), format din cele 2K unit˘at¸i de tip prag, poate fi echivalat cu un altul, compus din doar K + 1 unit˘at¸i de tip prag. La final, obt¸inem ret¸eaua din figura al˘aturat˘a.

−α1

gS

gS

gS

gS

−βK

−αK

−α2

ξ1 f( )

ξ2

f( )−f( )ξ1

ξK−1

−f( ) ξK

f( )

ξK

−f( )

x0= 1 o

level 1

1

1

x

1 1

K

level 2 gI

(28)

(29)

w1 w2

wn

w0 x1

x2

xn

x0 = 1

. .

.

### Σ

net = Σwi xi

i=0 n

1 1 + e-net o = σ(net) =

1

2

3

0

1

1

2

2

3

3

z

0

1

2

3

1

2

3

(30)

### Solution (in Romanian)

Vom scrie mai ˆıntˆai tabela de valori a funct¸iei / expresiei boolene date. Vom ad˘auga ˆın aceast˘a tabel˘a o coloan˘a care va cont¸ine forma [particular˘a a] sumei ponderate w0+w1x1+w2x2+w3x3 — adic˘a, argumentul pe care-l va lua funct¸ia sigmoidal˘a (σ) — pentru fiecare combinat¸ie de valori ale variabilelor x1, x2, x3. ˆIn plus, la fiecare linie vom preciza ¸si condit¸ia care trebuie s˘a fie satisf˘acut˘a de c˘atre suma ponderat˘a de pe linia respectiv˘a, ˆın a¸sa fel ˆıncˆat perceptronul s˘a realizeze codificarea cerut˘a ˆın enunt¸.

x1 x2 x3 (x1 x2)x3 w0 +w1x1 +w2x2 +w3x3 ... 0

0 0 0 0 w0 < 0

0 0 1 1 w0 +w3 > 0

0 1 0 0 w0 +w2 < 0

0 1 1 1 w0 +w2 +w3 > 0

1 0 0 0 w0 +w1 < 0

1 0 1 1 w0 +w1 +w3 > 0

1 1 0 1 w0 +w1 +w2 > 0

1 1 1 1 w0 +w1 +w2+ w3 > 0

(5)

A¸sadar, rezumˆand, pentru ca uni- tatea sigmoidal˘a s˘a codifice expresia boolean˘a dat˘a, tre- buie ca ponderile wi

a satisfac˘a sistemul de inecuat¸ii scrise ˆın ultima coloan˘a a

tabelului al˘aturat.

(31)

ˆIn vederea g˘asirii unei solut¸ii pentru acest sistem, putem observa c˘a ˆın expresia (x1∧x2)∨x3 variabilele logice x1 ¸si x2 joac˘a rol simetric ˆın raport cu opera- torul ∧. Deci este natural s˘a consider˘am c˘a ponder- ile alocate lui x1 ¸si x2 [ca input-uri] ˆın perceptronul sigmoidal pot fi egale. Introducˆand deci restrict¸ia w1 = w2, sistemul (5) va deveni cel scris ˆın dreapta.















w0 < 0

w0 +w3 > 0 w0 +w1 < 0

w0 +w1 +w3 > 0 w0 + 2w1 > 0

w0 + 2w1+w3 > 0

(6)

Mai departe, analizˆand din nou expresia (x1∧x2)∨x3, este natural s˘a gˆandim c˘a, ˆın raport cu operatorul

∨, ponderea variabilei x3 ar trebui s˘a fie aceea¸si cu ponderile ,,cumulate“ ale variabilelor x1 ¸si x2. Prin urmare, ,,injectˆand“ ¸si restrict¸ia w3 = w1 + w2 = 2w1, sistemul de inecuat¸ii (6) va deveni cel scris ˆın dreapta.











w0 < 0

w0 + 2w1 > 0 w0 +w1 < 0 w0 + 3w1 > 0 w0 + 4w1 > 0

(7)

(32)

Din forma sistemului (7), apare natural s˘a explor˘am ce anume se ˆıntˆampl˘a dac˘a restrict¸ion˘am spat¸iul de solut¸ii inpunˆand condit¸ia w1 > 0. ˆIn aceast˘a ipotez˘a, sistemul (7) va avea aceea¸si solut¸ie ca ¸si inecuat¸ia dubl˘a

w0 +w1 < 0 < w0 + 2w1, care este echivalent˘a cu

w1 < −w0 < 2w1. (8)

Pentru aceast˘a ultim˘a inecuat¸ie dubl˘a este foarte u¸sor s˘a indic˘am solut¸ii. Iat˘a una dintre ele: w1 = 1

2 ¸si w0 = −3

4. Prin urmare, w2 = 1

2 ¸si w3 = 1.

(33)

0

1

0

1

1

0

1

0

1

2

3

1 0

1

1

0

0

−1/2 0

−3/4

−1

1/2

(34)

### Observat¸ie (2)

Rostul acestui [tip de] exercit¸iu este s˘a arate c˘a pentru a g˘asi valori corespunz˘atoare ponderilor unui perceptron ˆın a¸sa fel ˆıncˆat el s˘a reprez- inte/codifice o anumit˘a funct¸ie, putem apela la [rezolvarea de] sisteme de restrict¸ii / inecuat¸ii.

Mai general, a¸sa cum precizeaz˘a ¸si Tom Mitchell ˆın Machine Learning la pag.

95, putem folosi metode de programare liniar˘a sau ne-liniar˘a.

Pe de alt˘a parte, acest exercit¸iu pune ˆın evident¸˘a ˆın mod indirect faptul c˘a ar fi de dorit ca (alternativ) s˘a dispunem de o procedur˘a de calcul general˘a, cˆat mai simpl˘a, prin care s˘a atingem obiectivul ment¸ionat anterior.

O astfel de procedur˘a — bazat˘a pe metoda gradientului descendent — va face obiectul problemelor urm˘atoare. ˆIn raport cu programarea lininiar˘a sau cea ne-liniar˘a, aceast˘a procedur˘a are avantajul c˘a se scaleaz˘a ˆın mod elegant/convenabil la nivel de ret¸ea neuronal˘a.

(35)

(36)

### Consider running the Perceptron algorithm (see the nearby pseudo-code) on some se- quence of examples S . (Remember that an example is a data point and its label.)

initialize w¯ ¯0 for i = 1, . . . , n do

if yi( ¯w ·x¯i) 0 then

¯

w w¯ +yix¯i

end if end for

(37)

### Solution (in Romanian)

a. Consider˘am urm˘atorul set de exemple (S), ˆın ordinea indicat˘a:

Exemplul 1 2 3 4 5 6

Instant¸a (x1, x2) (−1,2) (1,0) (1,1) (−1,0) (−1,−2) (1,−1)

Eticheta y −1 +1 +1 −1 −1 +1

Sintetiz˘am execut¸ia algoritmului Perceptron pe aceste date, f˘ar˘a a folosi ter- menul “bias” (w0), alc˘atuind tabelul urm˘ator:

Iterat¸ia(i) x¯i yi yiw¯ ·x¯i w¯ gre¸seal˘a ec. separatorului

init¸ializare – – (0,0) – –

1 (−1,2) −1 0 ≤ 0 (1,−2) da x2 = 0.5x1 2 (1,0) +1 1 > 0 (1,−2) nu x2 = 0.5x1 3 (1,1) +1 −1 ≤ 0 (2,−1) da x2 = 2x1 4 (−1,0) −1 2 > 0 (2,−1) nu x2 = 2x1 5 (−1,−2) −1 0 ≤ 0 (3,1) da x2 = −3x1 6 (1,−1) +1 2 > 0 (3,1) nu x2 = −3x1

(38)

A¸sadar, algoritmul a comis trei gre¸seli. Cei trei separatori obt¸inut¸i ˆın cursul aplic˘arii algoritmului Perceptron pe ¸sirul de exemple S sunt prezentat¸i ˆın figura de mai jos.

−1 1

−2

−3 2 3

1

−1

=1/2

x1 x2

x1 x2

x2 x1

−2

−3 2

1

−1 1

−1

3

=2

−1 1

−2

−3 2 3

1

−1

=−3

x1 x2

x2 x1

x1 x2

x2 x1

−2

−3 2

1

−1 1

−1

3

(39)

Este imediat c˘a modul ˆın care se construie¸ste separatorul — a c˘arui expresie analitic˘a este o combinat¸ie liniar˘a de instant¸e gre¸sit catalogate — este depen- dent de exemplele prezentate. ˆIntrebarea care a fost pus˘a ˆın enunt¸ este dac˘a pentru dou˘a succesiuni/ordini diferite, rezultatele finale (i.e., expresiile sepa- ratorilor obt¸inut¸i) coincid (ˆıntotdeuna) sau nu. ˆIn continuare vom ar˘ata c˘a ˆın mod obi¸snuit rezultatele finale (i.e., pozit¸iile finale ale separatorilor obt¸inut¸i) nu coincid.

Consider˘am S secvent¸a de exemple obt¸inut˘a din S prin inversarea [ordinii]

exemplelor x¯1 ¸si x¯2. Este imediat c˘a la prima iterat¸ie perceptronul gre¸se¸ste ¸si apoi calculeaz˘a w¯ = (1,0), ceea ce conduce la ecuat¸ia separatorului x1 = 0, adic˘a axa Ox1. Evident, aceasta dreapt˘a este un separator perfect pentru ˆıntregul set de exemple, deci algoritmul nu va mai comite pˆan˘a la final nicio [alt˘a]

gre¸seal˘a. Concluzia este c˘a, pe un acela¸si set de exemple de antrenament, algoritmul Perceptron poate comite un num˘ar diferit de gre¸seli (¸si, de aseme- nea, un alt separator) dac˘a exemplele ˆıi sunt prezentate ˆın dou˘a seccesiuni diferite.

(40)

### mare ¸si/sau ne-parcurgerea setului de date decˆ at o singur˘ a dat˘ a.)

(41)

to a hyper-plane. The weight vector, w, learned by Perceptron will be normal¯ to this hyperplane? (True or False?)

R˘aspuns:

Cunoa¸stem din geometria analitic˘a faptul c˘a orice doi vectori w¯ ¸si x¯ pentru care are loc relat¸ia w¯ · x¯ = 0 sunt ortogonali (adic˘a, perpendiculari unul pe cel˘alalt).

ˆIn cazul perceptronilor (de tip liniar, prag sau sigmoidal), ecuat¸ia separatoru- lui este tocmai de forma w¯·x¯ = 0, unde x¯ este un punct arbitrar de pe dreapta [sau, ˆın general, hiper-planul] separator. Considerˆand x¯1 ¸si x¯2 dou˘a astfel de puncte, diferent¸a lor, x¯1−x¯2, va fi un vector care are direct¸ia dreptei-separator.

Din relat¸iile w¯·x¯1 = 0 ¸si w¯·x¯2 = 0 rezult˘a w¯·(¯x1−x¯2) = 0. Prin urmare, vectorul de ponderi w¯ este perpendicular pe direct¸ia dreptei-separator.

Proprietatea aceasta se poate verifica ¸si ˆın mod direct/particular pe datele de la punctele precedente. De exemplu, la punctul a, pe ¸sirul de exemple S, la iterat¸ia 1 avem w¯ = (1,−2) ¸si se poate observa direct pe grafic c˘a acest vector este perpendicular pe direct¸ia dreptei y = 1

2x.

(42)

### MIT, 2009 fall, Tommy Jaakkola, lecture notes 2

(43)

ˆınv˘at¸˘am un concept, folosind instant¸ele de antrenament x1, . . . , xn, . . . ∈ Rd ˆımpreun˘a cu etichetele corespunz˘atoare y1, . . . , yn, . . . ∈ {−1,1}.

Demonstrat¸i c˘a ˆın cazul ˆın care sunt ˆındeplinite condit¸iile i-iv de mai jos, algoritmul de actualizare a ponderilor perceptronului termin˘a ˆıntr-un num˘ar finit de pa¸si. Formal, exprim˘am acest fapt astfel: ∃m ∈ N astfel ˆıncˆat ytw(m)·xt ≥ 0 pentru orice t ∈ {1, . . . , n, . . .}, unde w(m) este vectorul de ponderi obt¸inut de perceptron la iterat¸ia m.

Iat˘a acum condit¸iile ment¸ionate mai sus:

i. Instant¸ele x1, . . . , xn, . . . sunt separabile liniar prin originea sistemului de coordonate, cu o margine finit˘a γ > 0. Din punct de vedere formal, aceasta ˆınseamn˘a c˘a exist˘a w ∈ Rd astfel ˆıncˆat ytw ·xt ≥ γ pentru t = 1, . . . , n, . . ..

ii. Toate instant¸ele x1, . . . , xn, . . . sunt cont¸inute ˆıntr-o sfer˘a din Rd cu centrul ˆın origine, adic˘a ∃R > 0 astfel ˆıncˆat ||xt|| def.= √xt ·xt ≤ R pentru orice t.

iii. ˆInv˘at¸area se face ˆın manier˘a incremental˘a, folosind urm˘atoarea regul˘a de actualizare a ponderilor:

w(k+1) = w(k) +ytkxtk pentru un tk ∈ {1, . . . , n, . . .} a.ˆı. ytkw(k) ·xtk ≤ 0, (9) ceea ce ˆınseamn˘a c˘a instant¸a xtk este clasificat˘a eronat de c˘atre perceptron la iterat¸ia k.

iv. Startarea procesului de ˆınv˘at¸are se face cu w(0) = 0 ∈ Rd.

(44)

Indicat¸ie: Ar˘atat¸i c˘a la fiecare iterat¸ie (k) a algoritmului, sunt satisf˘acute urm˘atoarele propriet˘at¸i:

a. w ·w(k) ≥ kγ; b. ||w(k)||2 ≤ kR2;

c. k ≤

||w||

γ R

2

.

Ultima inegalitate indic˘a [o margine superioar˘a pentru] num˘arul maxim de iterat¸ii executate de c˘atre perceptron.

(45)

Observat¸ia 1: Notˆand cu θt unghiul format de vectorii xt ¸si w ˆın Rd ¸si t¸inˆand cont de faptul c˘a

cosθt = cos(xt, w) = xt ·w

||xt|| ||w||, deci

ytw ·xt = yt||w|| ||xt||cosθt,

ceea ce, coroborat cu condit¸ia i, implic˘a yt||xt||cosθt||w|| ≥ γ, adic˘a yt ||xt||cosθt ≥ γ

||w||. Din punct de vedere geometric, aceasta ˆınseamn˘a c˘a ˆın spat¸iul Rd distant¸a de la orice instant¸˘a xt la vectorul w (care trece prin

originea sistemului de coordonate) este mai mare sau egal˘a cu γ

||w||.

Observat¸ia 2: Separatorul w(k) este o combinat¸ie liniar˘a de instant¸ele xi, ˆıntrucˆat regula de actualizare este w(k+1) = w(k)+yixi. Observat¸ia aceasta este

valabil˘a ¸si la antrenarea perceptronului-prag clasic, bazat pe regula delta.

(46)

### Ideea de baz˘ a

Algoritmul de actualizare a ponderilor perceptronului determin˘a schimbarea pozit¸iei separatorului la fiecare iterat¸ie (k) la care avem de a face cu un ex- emplu clasificat gre¸sit.

Intuitiv, ne a¸stept˘am ca pozit¸ia separatorului la iterat¸ia k + 1 (adic˘a hiper- planul de ecuat¸ie w(k+1) ·x = 0) s˘a se apropie de pozit¸ia separatorului w care define¸ste conceptul de ˆınv˘at¸at.

ˆIn consecint¸˘a, cosinusul unghiului dintre w(k) ¸si w ar trebui s˘a creasc˘a de la o iterat¸ie la alta.

Pentru a dovedi/verifica ˆın mod riguros aceasta, vom t¸ine cont c˘a, prin definit¸ie,

cos(w(k), w) = w(k) ·w

||w(k)|| ||w||.

(47)

Mai ˆıntˆai vom compara valorile produsului scalar de la num˘ar˘atorul fract¸iei de mai sus, la dou˘a iterat¸ii succesive. Folosind regula (9), putem scrie:

w(k+1) ·w = (w(k) +ytkxtk)· w = w(k) ·w +ytkxtk ·w.

ˆIntrucˆat ytkxtk·w ≥ γ (vezi condit¸ia i din enunt¸), rezult˘a c˘a valoarea produsu- lui scalar w(k) ·w cre¸ste la fiecare iterat¸ie cu o cantitate cel put¸in egal˘a cu γ. Cum w(0) = 0 conform restrict¸iei iv, este imediat c˘a w(k) ·w ≥ kγ la iterat¸ia k.

A¸sadar, num˘ar˘atorul fract¸iei care define¸ste cos(w(k), w) cre¸ste cel put¸in liniar ˆın raport cu k. Cu aceasta, tocmai am demonstrat relat¸ia a.

(48)

A analiza evolut¸ia numitorului fract¸iei care define¸ste cos(w(k), w) revine la a compara ||w(k+1)|| cu ||w(k)||, ˆıntrucˆat ||w|| este constant ˆın raport cu k.

||w(k+1)||2 def.= w(k+1) ·w(k+1) (9)

= (w(k) +ytkxtk) ·(w(k) +ytkxtk)

= w(k) ·w(k) + 2ytkw(k) ·xtk +yt2kxtk ·xtk

= ||w(k)||2 + 2ytkw(k) · xtk +yt2k||xtk||2

= ||w(k)||2 + 2ytkw(k) · xtk +||xtk||2

≤ ||w(k)||2 +R2.

Inegalitatea de mai sus deriv˘a din faptul c˘a ytkw(k) · xtk ≤ 0 (i.e., exemplul tk este clasificat gre¸sit la iterat¸ia k, conform condit¸iei iii din enunt¸) ¸si din ipoteza c˘a orice instant¸˘a de antrenament este cont¸inut˘a ˆın sfera de raz˘a R

¸si avˆand centrul ˆın originea spat¸iului Rd, conform condit¸iei ii. Cum w(0) = 0, este imediat c˘a ||w(k)||2 ≤ k R2, deci ||w(k)|| ≤ √

k R la iterat¸ia k. Cu aceasta, am demonstrat relat¸ia b.

(49)

Acum, combinˆand rezultatele a ¸si b, obt¸inem urm˘atoarea inegalitate:

cos(w(k), w) = w(k) ·w

||w(k)|| ||w|| ≥ kγ

√k R||w|| = √

k γ

R||w||.

S¸tim c˘a valoarea funct¸iei cos este ˆıntotdeauna cel mult egal˘a cu 1. ˆIn consecint¸˘a,

1 ≥ cos(w(k), w) ≥ √

k γ

R||w|| ⇒ k ≤

R||w||

γ

2

, deci am demonstrat relat¸ia c.

Aceasta ˆınseamn˘a c˘a ˆın condit¸iile specificate ˆın enunt¸, antrenarea perceptronului-prag se va face ˆın cel mult R||w||

γ

2

iterat¸ii, unde perechea de simboluri ⌊ ⌋ desemneaz˘a funct¸ia parte ˆıntreag˘a inferioar˘a.

Observat¸ia 3: Marginea superioar˘a calculat˘a mai sus este remarcabil˘a, ˆıntrucˆat ea nu depinde nici de instant¸ele xi ¸si nici de dimensiunea (d) a

spat¸iului din care sunt selectate aceste instant¸e.

(50)

Restrict¸ia referitoare la separabilitatea prin origine a instant¸elor de antre- nament (vezi condit¸ia i, prima parte) — ¸si anume, componenta ,,liber˘a“

w0 asociat˘a separatorului w trebuie s˘a fie 0 — nu este de fapt limitativ˘a.

Cazul general al separabilit˘at¸ii liniare ˆın Rd, adic˘a yt(w0 + w · xt) ≥ 0 pen- tru orice t ∈ {1,2, . . . , n . . .}, poate fi redus la cazul particular al separabilit˘at¸ii prin origine ˆın Rd+1 dac˘a pe de o parte se consider˘a w = (w0, w1, . . . , wd), cu w = (w1, . . . , wd), iar pe de alt˘a parte se mapeaz˘a toate instant¸ele de antre- nament xt = (x1t, . . . , xdt) din Rd ˆın Rd+1 astfel: xk = (x0t, x1t, . . . , xdt), cu x0t = 1 pentru orice t. Cu aceast˘a mapare, rezult˘a ytw · xt ≥ 0 pentru orice t (re- spectiv ytw ·xt ≥ γ cˆand se lucreaz˘a cu margine finit˘a, ca ˆın enunt¸ul acestei probleme).

Nici restrict¸ia iv (w(0) = 0) nu este cu adev˘arat limitativ˘a; ˆın general algorit- mii de antrenare a unit˘at¸ilor / ret¸elelor neuronale init¸ializeaz˘a ponderile w la valori mici (ˆın modul).

Similar, este imediat c˘a restrict¸ia potrivit c˘areia sfera ˆın care sunt cont¸inute instant¸ele x1, . . . , xn, . . . trebuie s˘a aib˘a centrul ˆın originea lui Rd (vezi condit¸ia ii, partea a doua) poate fi eliminat˘a f˘ar˘a ca rezultatul de convergent¸˘a s˘a fie afectat.

(51)

### Observat¸ia 5

Deducerea marginii superioare de la punctul c de mai sus ˆın cazul ˆın care se folose¸ste o rat˘a de ˆınv˘at¸are oarecare η > 0 se face extinzˆand ˆın mod natural demonstrat¸ia de mai sus (vezi CMU, 2013 spring, A. Smola, B. Poczos, HW2, pr. 2.a).

ˆIn concluzie, mai r˘amˆan de examinat dou˘a condit¸ii: separabilitatea liniar˘a cu margine γ > 0 ¸si cont¸inerea instant¸elor de antrenament ˆıntr-o sfer˘a de raz˘a finit˘a. Se poate demonstra c˘a ambele condit¸ii sunt esent¸iale pentru convergent¸a perceptronului Rosenblatt ˆın regim de ˆınv˘at¸are online (vezi prob- lema CMU, 2008 fall, Eric Xing, midterm exam, pr. 3.2).

(52)

(53)

1

1

n

n

i

d

i

0

1

d

0

1

d

1

2

2

0

0

1

d

d

o =

### P

d i=0

wixi

(54)

regulilor de actualizare a ponderilor wi, cu i = 0, . . . , d) pentru g˘asirea acelei valori care minimizeaz˘a semi-suma p˘atratelor erorilor comise de perceptron,a adic˘a

E( ¯w) def.= 1 2

Xn

i=1

(ti −oi)2.

ˆIn aceast˘a ultim˘a expresie, oi este output-ul perceptronului liniar pentru in- trarea x¯i

renot.

= (x0 = 1, xi,1, . . . , xi,d), adic˘a oi = w0 +Pd

j=1wjxi,j.

V˘a reamintim c˘a la aplicarea metodei gradientului descendent pentru g˘asirea unui punct de minim al unei funct¸ii derivabile f : Rd+1 → R, regula de ac- tualizare a parametrilor w¯ ai funct¸iei f are forma w¯ ← w¯ + ∆ ¯w, cu ∆ ¯w def.=

−η∇w¯f( ¯w), unde η > 0 este un num˘ar real mic, numit rata de ˆınv˘at¸are, iar

∂w0f( ¯w), ∂

∂w1f( ¯w), . . .

.

a Conform problemei CMU, 2001 fall, T. Mitchell, A. Moore, final exam, pr. 10.2, am putea scrie — ˆın ipoteza c˘a datele au fost generate probabilist, cu o component˘a ,,zgomot“ urmˆand o distribut¸ie gaussian˘a uni-variat˘a de medie 0, a¸sa cum s-a precizat acolo —,

¯

wML = arg min

¯

w E( ¯w) = arg min

¯ w

1 2

Xn

i=1

(ti w¯ ·x¯i)2.

(55)

i

i

n

j=1

j

j

2

n

j=1

i

j

j

2

n

j=1

j

j

i

j

j

n

j=1

j

j

i

j

j

d

j

j

j,i

i

n

j=1

j

j

j,i

Updating...

## References

Related subjects :