Calculation of the output of a neural network

Artificial Neural Networks

(abbrev. ANNs, or simply NNs)

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.

Calculation of the output of a neural network

made of threshold perceptrons

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

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 (x₀ = 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 x₁ ¸si x₂. 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 x₁ ¸si x₂ iau valori ˆın mult¸imea {−1,1}.

x₁

x₂

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

R˘ aspuns

a.

o

(x

, x

) = sign (x

+ x

− 1), o

(x

, x

) = sign (x

− x

− 1), o

(x

, x

) = sign ( − x

+ x

− 1), o

(x

, x

) = sign ( − x

− x

− 1),

o(x

, x

) = sign (o

(x

, x

) − o

(x

, x

) − o

(x

, x

) + o

(x

, x

)).

b. x

x

o

o

o

o

o

1 1 1 − 1 − 1 − 1 1 1 − 1 − 1 1 − 1 − 1 − 1

− 1 1 − 1 − 1 1 − 1 − 1

− 1 − 1 − 1 − 1 − 1 1 1

c. Indicat¸i funct¸iile boolene reprezentate de c˘ atre uit˘ at¸ile de pe nivelul ascuns (1, 2, 3 ¸si 4) atunci cˆ and x

, x

∈ {− 1, 1 } . Procedat¸i similar pentru ie¸sirea o.

R˘ aspuns:

Din tabelul obt¸inut la punctul precedent este imediat c˘ a, atunci cˆ and x

, x

∈ {− 1, 1 } , ie¸sirile calculate de c˘ atre unit˘ at¸ile 1, 2, 3 ¸si 4 corespund conceptelor/funct¸iilor x

∧ x

, x

∧¬ x

, ¬ x

∧ x

¸si respectiv

¬ x

∧ ¬ x

. Ie¸sirea ret¸elei, o, corespunde conceptului ¬ (x

xor x

).

Observat¸ie : Se poate remarca faptul c˘ a ˆın aceast˘ a ret¸ea un neu-

ron (¸si doar unul!) de pe nivelul ascuns este activat la fiecare

combinat¸ie de valori (din cele 4 posibile) pentru x

, x

∈ {− 1, 1 } .

d. Specificat¸i cum anume ar putea fi modificat˘ a ret¸eaua dat˘ a astfel ˆıncˆ at noua variant˘ a s˘ a calculeze funct¸ia de variabile reale (nu boolene ca mai ˆınainte!) x

¸si x

, a c˘ arei relat¸ie de definit¸ie este: f (x

, x

) = 1 dac˘ a x

, x

≥ 0 sau x

, x

< 0, ¸si − 1 ˆın caz contrar.

R˘ aspuns:

Este imediat c˘ a funct¸ia indicat˘ a ˆın enunt¸ se poate scrie sub forma

f (x

, x

) =

1 dac˘ a sign (x

) · sign (x

) ≥ 0

− 1 dac˘ a sign (x

) · sign (x

) < 0.

Se observ˘ a imediat c˘ a aceasta coincide cu funct¸ia

¬ (sign (x

) xor sign (x

)). Prin urmare, este suficient s˘ a ad˘ aug˘ am

la ret¸eaua dat˘ a ˆın enunt¸ un nivel ascuns suplimentar, format din

dou˘ a unit˘ at¸i cu funct¸ie de activare de tip prag, care s˘ a transforme

intr˘ arile x

¸si x

ˆın sign (x

) ¸si respectiv sign (x

). Vom obt¸ine ca

rezultat ret¸eaua din slide-ul urm˘ ator.

x₂ x₁

x0=1

x0=1

o₁

o₂ 1

0 0

1

o

−1

−1

−1

−1 1

1

−1

1

−1

−1

−1

−1

−1 1

1 1

Expressivity of neural networks:

boolean functions

CMU, 2010 fall, Aarti Singh, HW5, pr. 4.3

Consider the set of binary functions over d Boolean (binary) vari- ables: F = { f : { 0, 1 }

→ { 0, 1 }} . Show that any function in F can be represented by a neural network with a single hidden layer.

Note : You can work with values other than { 0, 1 } , such as { 1, − 1 } ,

as long as the function is still binary.

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.

Exemplification:

CMU, 2011 spring, Roni Rosenfeld, HW4, pr. 1.c A neural network with only one hidden layer that

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

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.

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

A negative expressivity result

concerning networks of threshold perceptrons

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

Consider the function f : R → R defined as f(x1, x2) = 1 for x1, x2 ≥ 0 or x₁, x₂ < 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?

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

Nε = {(x₁, x₂)| q

x²₁ +x²₂ ≤ ε},

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

x2

x₁

−1

+1 −1

+1

O

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 = (p₁, p₂) 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^′ = (−p₁,−p₂), 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

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)

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 w₀ (corresponding to x₀ = 1) for the output unit of the neural net must satisfy the inequalities

X

h

whyh(P) ≥ −w₀ , X

h

whyh(P^′) ≥ −w₀ ⁽1⁾

⇒ X

h6∈O

whyh(P^′) ≥ −w₀, X

h

whyh(Q) < −w₀ , X

h

whyh(Q^′) < −w₀ ⁽2)

⇒ X

h6∈O

whyh(Q^′) < −w₀, 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.

Expressivity of neural networks:

Any Lipschitz continuous function defined on a bounded interval from R can be approximated by a neural network

with a single hidden layer

CMU, 2011 fall, Tom Mitchell, Aarti Singh, HW5, pr. 2.3

Let f (x) be any function whose domain is [C, D), for real values C < D . Suppose that the function is Lipschitz continuous, that is,

∀ x, x

∈ [C, D), | f (x

) − f (x) | ≤ L | x

− x | , for some constant L ≥ 0.

Construct a neural network with one hidden layer that approxi- mates this function within ε > 0, that is, ∀ x ∈ [C, D), | f (x) − out (x) | ≤ ε, where out (x) is the output of your neural network given the in- put x.

Hint : You may use as building blocks the network(s) designed at CMU, 2007 fall, Carlos Guestrin, HW2, pr. 4.

Note : Your network should use only the activation functions g

and g

(the identity and respectively the step function) mentioned

at above referred problem.

You need to specify the number K of hidden units, the activation function for each unit, and a formula for calculating each weight w

, w

, w

, and w

, for each k ∈ { 1, 2, . . . , K } . These weights may be specified in terms of C , D, L and ε, as well as the values of f (x) evaluated at a finite number of x values of your choosing (you need to explicitly specify which x values you use). You do not need to explicitly write the out (x) function.

Why does your network attain the given accuracy?

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

2ε

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 = (αi +βi)/2, pentru cu i = 1, . . . , K, unde K ^not.=

(D−C) L 2ε

,

α₁ = C, β₁ = α₂ = 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).

ˆ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.

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

o_i ξ_i

f( ) gS

ξ _i

−f( ) gI

x₀= 1

1

1 1

x

ξ_i

) [ )

[β

α_{i i}

0 x

y

c = f( )

,,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(ξ₁) pt. x ∈ [α₁ = C, β₁) f(ξ₂) pt. x ∈ [α₂ = β₁, β₂) . . . .

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

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

gI

−β₁

−β₂

−α₂

gS

gS

gI

−α_K

−β_K gS

S

gI

gS

gS

gI

ξ₁ f( )

ξ₁

−f( )

ξ₂ f( )

ξ₂

−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

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( ) ξ₂ f( )

ξ₁

−f( )

ξ₂

−f( )

De asemenea, datorit˘a faptului c˘a β₁ = α₂, β₂ = α₃, . . . , β_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.

−α₁

gS

gS

gS

gS

−β_K

−α_K

−α₂

ξ₁ f( )

ξ₂

f( )−f( )ξ₁

ξ_K−1

−f( ) ξ_K

f( )

ξ_K

−f( )

x0= 1 o

level 1

1

1

x

1 1

K

level 2 gI

The sigmoidal / logistic perceptron:

Exemplification: setting up its weights so as to represent a given boolean expression

CMU, 2003 fall, T. Mitchell, A. Moore, midterm, pr. 6.a

w1 w2

wn

w0 x1

x2

xn

x0 = 1

AA AA AA AA

. .

.

Σ

net = Σ_{wi xi}

i=0 n

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

Consider a single sigmoid threshold unit with three inputs, x

, x

, and x

.

y = σ(w

+ w

x

+ w

x

+ w

x

) where σ(z) = 1 1 + e

.

We input values of either 0 or 1 for each of these inputs. Assign

values to weights w

, w

, w

and w

so that the output of the

sigmoid unit is greater than 0.5 if an only if (x

and x

) or x

is

true.

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 w₀+w₁x₁+w₂x₂+w₃x₃ — adic˘a, argumentul pe care-l va lua funct¸ia sigmoidal˘a (σ) — pentru fiecare combinat¸ie de valori ale variabilelor x₁, x₂, x₃. ˆ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

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

tabelului al˘aturat.

ˆIn vederea g˘asirii unei solut¸ii pentru acest sistem, putem observa c˘a ˆın expresia (x₁∧x₂)∨x₃ variabilele logice x₁ ¸si x₂ 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 w₁ = w₂, sistemul (5) va deveni cel scris ˆın dreapta.

















w₀ < 0

w₀ +w₃ > 0 w₀ +w₁ < 0

w₀ +w₁ +w₃ > 0 w₀ + 2w₁ > 0

w0 + 2w1+w3 > 0

(6)

Mai departe, analizˆand din nou expresia (x₁∧x₂)∨x₃, este natural s˘a gˆandim c˘a, ˆın raport cu operatorul

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













w₀ < 0

w₀ + 2w₁ > 0 w₀ +w₁ < 0 w₀ + 3w₁ > 0 w₀ + 4w₁ > 0

(7)

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 w₁ > 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

w₁ < −w₀ < 2w₁. (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: w₁ = 1

2 ¸si w₀ = −3

4. Prin urmare, w₂ = 1

2 ¸si w₃ = 1.

Observat¸ie (1)

De fapt, dac˘ a lucr˘ am ˆıntr-un reper de coordonate w

Ow

, orice punct (w

, w

) din cadranul al doilea [¸si]

care este situat ˆıntre dreptele de ecuat¸ii w

= − w

¸si respectiv w

=

− 1

2 w

este o solut¸ie a inecuat¸iei duble (8), deci ¸si a sistemului de inecuat¸ii (5), la care, a¸sa cum am v˘ azut, au fost ad˘ augate restrict¸iile w

= w

=

1 2 w

.

w =−w

1 0

w

1

w = − 0.5 w

0

w

−1/2 0

−3/4

−1

1/2

(Invers, adic˘ a a preciza care este ˆıntreg spat¸iul de solut¸ii al sis-

temului (5) este mult ˆın afara obiectivului acestui exercit¸iu.)

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.

Rosenblatt’s Perceptron Algorithm:

some simple properties

CMU, 2015 spring, Tom Mitchell, Nina Balcan, HW6, pr 3.ab

CMU, 2017 spring, Barnabas Poczos, HW3, pr. 1.bc

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

Let S

be the same set of examples as S , but presented in a different order.

a. Does the Perceptron algorithm necessarily make the same num- ber of mistakes on S as it does on S

?

If so, why? If not, show such an S and S

where the Perceptron

algorithm makes a different number of mistakes on S

than it does

on S .

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 (x₁, x₂) (−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” (w₀), 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 x₂ = 0.5x₁ 2 (1,0) +1 1 > 0 (1,−2) nu x₂ = 0.5x₁ 3 (1,1) +1 −1 ≤ 0 (2,−1) da x₂ = 2x₁ 4 (−1,0) −1 2 > 0 (2,−1) nu x₂ = 2x₁ 5 (−1,−2) −1 0 ≤ 0 (3,1) da x₂ = −3x₁ 6 (1,−1) +1 2 > 0 (3,1) nu x2 = −3x1

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

x₁ x₂

x₁ x₂

x₂ x₁

−2

−3 2

1

−1 1

−1

3

=2

−1 1

−2

−3 2 3

1

−1

=−3

x₁ x₂

x₂ x₁

x₁ x₂

x₂ x₁

−2

−3 2

1

−1 1

−1

3

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¯₁ ¸si x¯₂. 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 x₁ = 0, adic˘a axa Ox₁. 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.

Observat¸ie important˘ a

De¸si ˆın ambele cazuri de mai sus (S ¸si S

) algoritmul Perceptron

g˘ ase¸ste un separator liniar pentru datele de intrare, acest fapt nu

este garantat ˆın gazul general, chiar dac˘ a datele sunt liniar sepa-

rabile. Vezi de exemplu problema CMU, 2015 spring, Alex Smola,

midterm, pr. 4. (Motivele sunt: rata de ˆınv˘ at¸are (implicit˘ a) prea

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

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¯₁ ¸si x¯₂ dou˘a astfel de puncte, diferent¸a lor, x¯₁−x¯₂, va fi un vector care are direct¸ia dreptei-separator.

Din relat¸iile w¯·x¯₁ = 0 ¸si w¯·x¯₂ = 0 rezult˘a w¯·(¯x₁−x¯₂) = 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.

A¸sadar, r˘aspunsul este Adev˘arat.

Rosenblatt’ Perceptron Algorithm:

Convergence / Mistake bounds

MIT, 2009 fall, Tommy Jaakkola, lecture notes 2

ˆınv˘at¸˘am un concept, folosind instant¸ele de antrenament x₁, . . . , xn, . . . ∈ R^d ˆı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 x₁, . . . , 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^∗ ∈ R^d astfel ˆıncˆat ytw^∗ ·xt ≥ γ pentru t = 1, . . . , n, . . ..

ii. Toate instant¸ele x₁, . . . , xn, . . . sunt cont¸inute ˆıntr-o sfer˘a din R^d 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) +yt_kxt_k pentru un tk ∈ {1, . . . , n, . . .} a.ˆı. yt_kw^(k) ·xt_k ≤ 0, (9) ceea ce ˆınseamn˘a c˘a instant¸a xt_k este clasificat˘a eronat de c˘atre perceptron la iterat¸ia k.

iv. Startarea procesului de ˆınv˘at¸are se face cu w⁽⁰⁾ = 0 ∈ R^d.

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)||² ≤ kR²;

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.

Observat¸ia 1: Notˆand cu θt unghiul format de vectorii xt ¸si w^∗ ˆın R^d ¸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 R^d 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.

Solution (in Romanian)

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^∗||.

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) +yt_kxt_k)· w^∗ = w^(k) ·w^∗ +yt_kxt_k ·w^∗.

ˆIntrucˆat yt_kxt_k·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 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.

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) +yt_kxt_k) ·(w^(k) +yt_kxt_k)

= w^(k) ·w^(k) + 2yt_kw^(k) ·xt_k +y_t²_kxt_k ·xt_k

= ||w^(k)||² + 2yt_kw^(k) · xt_k +y_t²_k||xt_k||²

= ||w^(k)||² + 2yt_kw^(k) · xt_k +||xt_k||²

≤ ||w^(k)||² +R².

Inegalitatea de mai sus deriv˘a din faptul c˘a yt_kw^(k) · xt_k ≤ 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 R^d, conform condit¸iei ii. Cum w⁽⁰⁾ = 0, este imediat c˘a ||w^(k)||² ≤ k R², deci ||w^(k)|| ≤ √

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

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.

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

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

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

Nici restrict¸ia iv (w⁽⁰⁾ = 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 x₁, . . . , xn, . . . trebuie s˘a aib˘a centrul ˆın originea lui R^d (vezi condit¸ia ii, partea a doua) poate fi eliminat˘a f˘ar˘a ca rezultatul de convergent¸˘a s˘a fie afectat.

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).

Theoretical foundations for the perceptron training algorithm

Liviu Ciortuz, 2017

following Tom Mitchell, Machine Learning book, 1997, p. 89-93

ˆIn acest exercit¸iu vom elab- ora/reda [mai ˆıntˆ ai] partea de fundamentare teoretic˘ a pentru antrenarea percep- tronului liniar, date fiind instant¸ele (¯ x

, t

), . . . , (¯ x

, t

), cu x ¯

∈ R

¸si t

∈ R pentru i = 1, . . . , n.

A¸sadar, vom considera perceptronul liniar avˆ and intr˘ arile x

= 1, x

, . . . , x

¸si ponderile w

, w

, . . . , w

.

x

w

x

w

x

=1 w

w

.. .

x

Σ

P

wixi

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)².

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

renot.

= (x₀ = 1, x_i,1, . . . , xi,d), adic˘a oi = w₀ +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 : R^d+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

∇^w¯f( ¯w) este vectorul gradient, adic˘a

∂

∂w₀f( ¯w), ∂

∂w₁f( ¯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 —,

¯

w_ML = arg min

¯

w E( ¯w) = arg min

¯ w

1 2

Xn

i=1

(ti −w¯ ·x¯_i)².

Answer

∂E

∂w

= ∂

∂w

1 2

X

j=1

(t

− o

)

= 1 2

X

j=1

∂

∂w

(t

− o

)

= 1 2

X

j=1

2(t

− o

) ∂

∂w

(t

− o

) = X

j=1

(t

− o

) ∂

∂w

(t

− w ¯ · x ¯

)

= X

d

(t

− o

)( − x

)

Therefore,

∆w

= η X

j=1

(t

− o

)x