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 (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
R˘ aspuns
a.
o
1(x
1, x
2) = sign (x
1+ x
2− 1), o
2(x
1, x
2) = sign (x
1− x
2− 1), o
3(x
1, x
2) = sign ( − x
1+ x
2− 1), o
4(x
1, x
2) = sign ( − x
1− x
2− 1),
o(x
1, x
2) = sign (o
1(x
1, x
2) − o
2(x
1, x
2) − o
3(x
1, x
2) + o
4(x
1, x
2)).
b. x
1x
2o
1o
2o
3o
4o
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
1, x
2∈ {− 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
1, x
2∈ {− 1, 1 } , ie¸sirile calculate de c˘ atre unit˘ at¸ile 1, 2, 3 ¸si 4 corespund conceptelor/funct¸iilor x
1∧ x
2, x
1∧¬ x
2, ¬ x
1∧ x
2¸si respectiv
¬ x
1∧ ¬ x
2. Ie¸sirea ret¸elei, o, corespunde conceptului ¬ (x
1xor x
2).
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
1, x
2∈ {− 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
1¸si x
2, a c˘ arei relat¸ie de definit¸ie este: f (x
1, x
2) = 1 dac˘ a x
1, x
2≥ 0 sau x
1, x
2< 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
1, x
2) =
1 dac˘ a sign (x
1) · sign (x
2) ≥ 0
− 1 dac˘ a sign (x
1) · sign (x
2) < 0.
Se observ˘ a imediat c˘ a aceasta coincide cu funct¸ia
¬ (sign (x
1) xor sign (x
2)). 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
1¸si x
2ˆın sign (x
1) ¸si respectiv sign (x
2). Vom obt¸ine ca
rezultat ret¸eaua din slide-ul urm˘ ator.
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
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 }
d→ { 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 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?
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
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)
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.
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
Iand g
S(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
0, w
k, w
0(k), and w
1(k), 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ε
,
α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).
ˆ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
oi ξi
f( ) gS
ξ i
−f( ) gI
x0= 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(ξ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
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( )
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
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
1, x
2, and x
3.
y = σ(w
0+ w
1x
1+ w
2x
2+ w
3x
3) where σ(z) = 1 1 + e
−z.
We input values of either 0 or 1 for each of these inputs. Assign
values to weights w
0, w
1, w
2and w
3so that the output of the
sigmoid unit is greater than 0.5 if an only if (x
1and x
2) or x
3is
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 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
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 (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)
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.
Observat¸ie (1)
De fapt, dac˘ a lucr˘ am ˆıntr-un reper de coordonate w
0Ow
1, orice punct (w
0, w
1) din cadranul al doilea [¸si]
care este situat ˆıntre dreptele de ecuat¸ii w
1= − w
0¸si respectiv w
1=
− 1
2 w
0este 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
1= w
2=
1 2 w
3.
w =−w
1 0
w
11
w = − 0.5 w
0
w
0−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 (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
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
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.
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¯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.
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 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.
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.
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.
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) +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.
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.
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“
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: x′k = (x0t, x1t, . . . , xdt), cu x0t = 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) = 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.
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
1, t
1), . . . , (¯ x
n, t
n), cu x ¯
i∈ R
d¸si t
i∈ R pentru i = 1, . . . , n.
A¸sadar, vom considera perceptronul liniar avˆ and intr˘ arile x
0= 1, x
1, . . . , x
d¸si ponderile w
0, w
1, . . . , w
d.
x
1w
2x
2w
0x
0=1 w
1w
d.. .
x
dΣ
o =P
d i=0wixi
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
∇w¯f( ¯w) este vectorul gradient, adic˘a
∂
∂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.
Answer
∂E
∂w
i= ∂
∂w
i1 2
X
nj=1
(t
j− o
j)
2= 1 2
X
nj=1
∂
∂w
i(t
j− o
j)
2= 1 2
X
nj=1
2(t
j− o
j) ∂
∂w
i(t
j− o
j) = X
nj=1
(t
j− o
j) ∂
∂w
i(t
j− w ¯ · x ¯
j)
= X
d
(t
j− o
j)( − x
j,i)
Therefore,
∆w
i= η X
nj=1