COMPLETE STATISTICAL THEORY OF
LEARNING
LEARNING USING STATISTICALINVARIANTS

Vladimir Vapnik
1PART I
VC THEORY OF GENERALIZATION

2

THE MAIN QUESTION OF LEARNING
THEORYQUESTION:
When in set of functions {f (x)} we can minimize functionalZ
R(f ) = L(y, f (x))dP(x, y),f (x) ∈ {f (x)},if measure P(x, y) is unknown but we are given ` iid pairs(x1, y1), ..., (x`, y`).

ANSWER:We can minimize functional R(f ) using data if and only if
the VC-dimension h of set {f (x)} is finite.

3

DEFINITION OF VC DIMENSION

Let {θ(f (x))} be a set of indicator functions(here θ(u) = 1 if u ≥ 0 and θ(u) = 0 if u < 0).
• VC-dimension of set of indicator functions {θ(f (x))} isequal h if h is the maximal number of vectors x1, ..., xh thatcan be shattered (separated into all 2h possible subsets) using indicator functions from {θ(f (x))}. If such vectors exist
for any number h the VC dimension of the set is infinite.
• VC-dimension of set of real valued functions {f (x)} is the
VC-dimension of the set of indicator functions {θ(f (x) + b)}

4

TWO THEOREMS OF VC THEORY

Theorem 1. If set {f (x)} has VC dimension h, then withprobability 1 − η for all functions f (x) the boundq
R(f ) ≤ R`emp(f ) + e2 + 4eR`emp(f ),holds true, whereR`emp(f ) =

`
1X

`


L(yi, f (xi)),

e=O

i=1



h − ln η.
`

Theorem 2. Let x, w ∈ Rn. The VC dimension h of set of
linear indicator functions {θ(xTw) : ||x||2 ≤ 1, ||w||2 ≤ C} ish ≤ min(C, n) + 1

5

STRUCTURAL RISK MINIMIZATION
PRINCIPLE

To find the desired approximation f`(x) in a set {f (x)}:FIRST, introduce a structure on a set of functions {f (x)}{f (x)}1 ⊂ {f (x)}2 ⊂ · · · {f (x)}m ⊂ {f (x)}with corresponding VC-dimension hk
h1 ≤ h2 ≤ · · · ≤ hm ≤ ∞.
SECOND, chose the function f`(x) that minimizes the boundqhk − ln ηR(f ) ≤ R`emp(f ) + e2 + 4eR`emp(f ), e = O.
`
1. over elements {f (x)}k (with VC dimension hk) and2. the function f`(x) (with the smallest in {f (x)}k loss R`emp(f ).

6

FOUR QUESTIONS TO COMPLETELEARNING THEORY

1. How to choose loss function L(y, f ) in functional R(f )?
2. How to select an admissible set of functions {f (x)}?
3. How to construct structure on admissible set?
4. How to minimize functional on constructed structure?

The talk answers these questions for pattern recognition
problem.

7

PART IITARGET FUNCTIONAL FOR MINIMIZATION

8SETTING OF PROBLEM: GOD PLAYS DICE

Object𝑦𝑖𝑦𝑖

𝑃(𝑦|𝑥 ሻLearning Machine

𝑓 𝑥, 𝛼 , 𝛼𝜖Λ𝑦Nature

𝑥𝑖

𝑃(𝑥 ሻ

𝑥𝑖
𝑥
𝑥1 , 𝑦1 , … , 𝑥𝓁 , 𝑦𝓁

Given ` i.i.d. observations(x1, y1), ..., (x`, y`),x ∈ X, y ⊂ {0, 1}

generated by unknown P(x, y) = P(y|x)P(x) find the ruler(x) = θ(f0(x)),
which minimizes in a set {f (x)} probability of misclassification
ZRθ (f ) = |y − θ(f (x))|dP(x, y)
9STANDARD REPLACEMENT OF BASIC
SETTING

Using data(x1, y1), ..., (x`, y`),x ∈ X, y ⊂ {0, 1}

minimize in the set of functions {f (x)} the functionalZ
R(f ) = (y − f (x))2dP(x, y)R(instead of functional RIθ(f ) = |y − θ(f (x))|dP(x, y)).
Minimizer f0(x) of R(f ) estimates condition probability
function f0(x) = P(y = 1|x). Use the classification ruler(x) = θ(f0(x) − 0.5) = θ(P(y = 1|x) − 0.5).

10PROBLEM WITH STANDARD
REPLACEMENT

Minimization of functional R(f ) in the set {f (x)} is equivalent to minimization of the expression
Z
Z
R(f ) = (y − f (x))2dP(x, y) = [(y − f0(x)) + (f0(x) − f (x))]2dP(x, y)
where f0(x) minimizes R(f ). This is equivalent to minimization
Z
R(f ) = (y − f0(x))2dP(x, y)+ZZ(f0(x) − f (x))2dP(x) + 2 (y − f0(x))(f0(x) − f (x))dP(x, y).

ACTUAL GOAL IS: USING ` OBSERVATIONS TOMINIMIZE THE SECOND INTEGRAL, NOT SUM OF
LAST TWO INTEGRALS.
11

DIRECT ESTIMATION OF CONDITIONALPROBABILITY
1. When y ⊂ {0, 1} the conditional probability P(y = 1|x) is
defined by some real valued function 0 ≤ f (x) ≤ 1.
2. From Bayesian formulaP(y = 1|x)p(x) = p(y = 1, x)
follows that any function G(x − x0) ∈ L2 defines equationZ

G(x − x0)f (x0)dP(x0) =Z

G(x − x0)dP(y = 1, x0)(∗)

which solution is conditional probability f (x) = P(y = 1|x).
3. To estimate conditional probability means to solve theequation (*) when P(x) and P(y = 1, x) are unknown but data,(x1, y1), ..., (x`, y`)generated according to P(y, x), are given.
12

4. Solution of equation (*) is ill-posed problem.

MAIN INDUCTIVE STEP IN STATISTICS

Replace the unknown Cumulative Distribution Function (CDF)
P(x), x = (x1, ..., xn))T ∈ Rn with it estimate P`(x): The Empirical Cumulative Distribution Function (ECDF)`

1X
P`(x) =
θ{x − xi},`i=1

θ{x − xi} =nY

θ{xk − xki}

k=1

obtained from data
x1, ..., x`,xi = (x1i, ..., xni)T,The main theorem of statistics claims that ECDF converges
to actual CDF uniformly with fast rate of convergence. The
following inequality holds true
P{sup |P(x) − P`(x)| > ε} < 2 exp{−2ε2`},

∀ε.

x

13

TWO CONSTRUCTIVE SETTINGS OF
CLASSIFICATION PROBLEM
1.Standard constructive setting: Minimization of functionalZ
Remp(f ) = (y − f (x))2dP`(x, y),in a set {f (x)} using data (x1, y1), ..., (x`, y`) leads to`

1X(yi − f (xi))2,
Remp(f ) =`f (x) ∈ {f (x)}.

i=1

•••
2. New constructive setting: Solution of equationZ
Z
G(x − x0)f (x0)dP`(x0) = G(x − x0)dP`(y = 1, x0),
using data leads to solution in {f (x)} the equation
`

`

1X
1X
G(x − xi)f (xi) =yjG(x − xj),``
i=1

f (x) ∈ {f (x)}.

j=1

14

NADARAYA-WATSON ESTIMATOR OF
CONDITIONAL PROBABILITY

It is known Nadaraya-Watson estimator of P(y = 1|x):P`
i=1 yi G(x − xi )f (x) = P`,
i=1 G(x − xi )where special kernels G(x − xi) (say, Gaussian) are used.
This estimator is the solution of ”corrupted” equation
`

`

i=1

i=1

1X
1X
G(x − xi)f (x) =yiG(x − xi)``(which uses special kernel) rather than the obtained equation
`

`

i=1

j=1

1X
1X
G(x − xi)f (xi) =yjG(x − xj).
``
(which is defined for any kernel G(x − x0) from L2).
15

WHAT MEANS TO SOLVE THE EQUATION
To solve the equation
`

`

i=1

j=1

1X
1X
G(x − xi)f (xi) =yjG(x − xj)``means to find the function in {f (x)} minimizing L2-distance

2
Z X
`
`
X
G(x − xi)f (xi) −yjG(x − xj) dµ(x).
R(f ) = i=1

j=1

Simple algebra leads to expression
RV (f ) =`X

(yi − f (xi))(yj − f (xj))v(xi, xj),

i,j=1

where values v(xi, xj) areZv(xi, xj) = G(x − xi)G(x − xj)dµ(x),i, j = 1, ..., `.

Values v(xi, xj) form V-matrix.
16

THE V-MATRIX ESTIMATE

1. For µ(x) = P(x) elements v(xi, xj) of V-matrix areZv(xi, xj) = G(x − xi)G(x − xj)dP(x).
Using empirical estimate P`(x) instead of P(x) we obtainthe following estimates of elements of V-matrix`

1X
v(xi, xj) =G(xs − xi)G(xs − xj).
` s=1
2. For µ(x) = x, x ∈ (−1, 1) and G(x − x0) = exp{−0.5δ 2(x − x0)2},v(xi, xj) =exp{−δ 2(xi − xj)2}{erf [δ(1 + 0.5(xi + xj))] + erf {δ(1 − 0.5(xi + xj))]}.

17

LEAST V-QUADRATIC FORM METHOD AND
LEAST SQUARES METHOD

Let (x1, y1), ..., (x`, b`) be training data. Using notations:
Y = (y1, ..., y`)T,

F(f ) = (f (x1), ..., f (x`))T,

V = ||v(xi, xj)||

we can rewrite functional`X
RV (f ) =(yi − f (xi))(yj − f (xj))v(xi, xj),
i,j=1

in matrix form
RV (f ) = (Y − F(f ))TV(Y − F(f )),We call this functional Least V-quadratic functional.
Identity matrix I instead of V forms Least Squares functional
RI(f ) = (Y − F(f ))T(Y − F(f )),18

PART III
SELECTION OF ADMISSIBLE SET OF FUNCTIONS

19

STRONG AND WEAK CONVERGENCE

Functions f`(x) ∈ L2 have two modes of convergence:
1. Strong mode of convergence (convergence of functions)Zlim (f`(x) − f0(x))2dµ(x) = 0.
`→∞

2. Weak mode of convergence (convergence of functionals)
ZZlimf`(x)φ(x)dµ(x) = f0(x)φ(x)dµ(x), ∀φ(x) ∈ L2`→∞

(convergence for all possible functions φ(x) ∈ L2.)
• Strong mode of convergence implies weak convergence:
Z
2 Z
Z
(f`(x) − f0(x))φ(x)dµ(x) ≤ (f`(x) − f0(x))2dµ(x) φ2(x)µ(x).
• For functions f`(x) belonging to compact weak mode of
convergence implies strong mode of convergence.
20

WEAK CONVERGENCE TO CONDITIONALPROBABILITY FUNCTIONS P(y = 1|x)

Weak mode convergence of sequence of functions f`(x) tofunction f0(x) = P(y = 1|x) means equalities
Z
Z
Z
lim
φ(x)f`(x)dP(x) = φ(x)P(y = 1|x)dP(x) = φ(x)dP(y = 1, x)`→∞

for all φ(x) ∈ L2.
Let us call set of m functions φ1(x), ..., φm(x) from L2 thechosen predicates. Let us call the subset of functions {f (x)}for which the following m equalities hold trueZZ
φk(x)f (x)dP(x) = φk(x)dP(y = 1, x), k = 1, ..., m.
the admissible set of functions (defined by the predicates).

21

ADMISSIBLE SUBSETS FOR ESTIMATIONCONDITIONAL PROBABILITY FUNCTION

Replacing P(x), P(y = 1, x) with P`(x), P`(y = 1, x) we obtain
`

`

1X
1X
φk(xi)f (xi) =yiφk(xi),``i=1

k = 1, ..., m.

i=1

In the matrix notations
Y = (y1, ..., y`)T, F(f ) = (f (x1), ..., f (x`))T, Φk = (φk(x1), ...φk(x`))T
we obtain that:
The admissible set of functions {f (x)} satisfies equalitiesTΦT
k F(f ) = Φk Y,

k = 1, ..., m.

We call these equalities statistical invariants for P(y = 1|x).

22

DUCK TEST, STATISTICAL INVARIANTS,
PREDICATES, AND FEATURESTHE DUCK TEST LOGIC”If it looks like a duck, swims like a duck, and quacks like a
duck , then it probably is a duck”. (English proverb.)
STATISTICAL INVARIANTS
`
`
1X
1X
φk(xi)f (xi) =yiφk(xi), k = 1, ..., m
`
`
i=1

i=1

T
(or ΦTk F(f ) = Φk Y, k = 1, ..., m in vector notations)collect set of admissible functions {f (x)} which ”identify” animal as a duck if it ”looks, swims, and quacks like a duck”.
PREDICATES AND FEATURES
Concepts of predicates and features are very different:

23• With increasing number of predicates the VC dimensionof admissible set of functions {f (x)} DECREASES.
• With increasing number of features the VC dimensionof admissible set of functions {f (x)} INCREASES.

EXACT SETTING OF COMPLETE LEARNING
PROBLEM• The complete solution of classification problem requires:
In a given set of functions {f (x)} to minimize functional
RV (f ) = (Y − F(f ))TV(Y − F(f )),subject to constraints (statistical invariants)TΦTk F(f ) = Φk Y,

k = 1, ..., m.

We call this conditional minimization model of learning
Learning Using Statistical Invariants (LUSI).
• Classical methods require in a given (specially constructed)
subset of functions {f (x)} to minimize the functional
RI(f ) = (Y − F(f ))T(Y − F(f )).
24

APPROXIMATE SETTING OF COMPLETELEARNING PROBLEM
In this setting minimization of the functional
RV (f ) = (Y − F(f ))TV(Y − F(f )),on the set of functions {f (x)} satisfying m constraintsTΦTs F(f ) = Φs Y,

s = 1, ..., mis replaced with minimization of the functional
m
X
2
τ
T
T
T
Φs F(f ) − Φs Y ,RVP (f ) = τb(Y − F(f )) V(Y − F(f )) +m s=1
where τb, τ ≥ 0, τb + τ = 1. This functional can be rewritten as
RVP (f ) = (Y − F(f ))T(bτ V + τ P)(Y − F(f )),where (` × `) matrix P defines predicates covariance
m
1 X
P=
ΦsΦT
s.
m s=1
25

PART IVCOMPLETE SOLUTION IN REPRODUCING KERNELHILBERT SPACE (RKHS)

26

IMPORTANT FACTS FROM RKHS 1.

1. RKHS is set of functions {f (x)} for which(K(x, x0), f (x0)) = f (x),(K(x, x0) is Mercer kernel).

2. Mercer kernel is defined by orthonormal functions ψk(x)∞X
K(x, x0) =λiψi(x)ψi(x0), λi > 0, λt −→t→∞= 0.
i=1

3. Set of functions
fc(x) =∞
Xciψi(x)i=1with inner product (and norm)(fc(x), fc∗ (x)) =

∞
X
i=1

cic∗i
λi

||fc(x)||2 =

∞
X
i=1

c2i

!

λi

forms RKHS of kernel K(x, x0).
27

IMPORTANT FACTS FROM RKHS 2.
4. REPRESENTER THEOREM. Minimum of functional
RV (f ) = (F(f ) − Y)TV(F(f ) − Y)in subset of RKHS with ||f (x)||2 ≤ C has representation
f0(x) =`X

atK(xi, x) = ATK(x),

(∗)

i=1

where we denoted A = (a1, ..., a`)T, K(x) = (K(x1, x), ..., K(x`, x))T
5. Square of norm of function f (x) in form (*) is||f (x)||2 = ATKA,

K = ||K(xi, xj)||,F(f ) = KA.

6. Subset of functions from RKHS with bounded norm
ATKA ≤ C has finite VC dimension (the smaller C, the smaller
is VC dimension). By controlling C, one controls both: the
VC dimension of subset of functions and their smoothness.
Structure defined by C is the key in implementation SRM
principle for functions belonging to RKHS.
28

CONDITIONAL MINIMIZATION IN RKHS:
EXACT LUSI SOLUTION
For RKHS we have F(f ) = KA. Minimum of the functional
RV (f ) = (KA − Y)TV(KA − Y),subject to m constraints
TΦTk KA = Φk Y,

k = 1, ..., mand constraint
ATKA ≤ C
has unique solution of the formf`(x) = AT
LUSI K(x),where
ALUSI = AV −m
X

µs A s ,s=1

AV = (VK + γcI)−1VY, As = (VK + γcI)−1Φs
Parameters µs are solution of linear equationsmX
Tµs A T
KΦ
=
(KA
−
Y)
Φs,
s = 1, ..., m.
s
V
s
s=1
29

UNCONDITIONAL MINIMIZATION IN RKHS(SOLUTION OF APPROXIMATE SETTING).

Minimum of functional
RVV w (f ) = (KA − Y)T(bτ V + τ P)(KA − Y)in the set of functions {f (x)} belonging to RKHS of kernel
K(x,x0) with bounded norm
ATKA ≤ C
has unique solution of the form
f0(x) = AT
VP K(x),where
AVP = ((bτ V + τ P)K + γcI)−1(bτ V + τ P)Y.

30

SVM AND LUSI-SVM ESTIMATIONS IN
RKHS• SVM: Given data(x1, y1), ..., (x`, y`)find in RKHS the function f (x) = ATK(x) with norm||f (x)||2 = ATKA ≤ C(∗)

that minimizes losses
L(A) =`
Xyi − ATK(xi)i=1• LUSI-SVM: Given data find in RKHS the function
f (x) = ATK(x) with bounded norm (*) that minimizes
L(A) = τm
X

ATKΦs − YTΦs + τb

s=1

yi − ATK(xi) ,i=m+1

τ > 0, τb > 0.

31

where τ + τb = 1,m+`
X

LUSI-SVM RSTIMATOR
LUSI-SVM method selects in set ATKA ≤ C the function
f (x) =`X

aiK(xi, x) = ATK(x),

where

i=1

A=

m
X

δtΦt +

t=1

m+`
X

δtΦt.

t=m+1

To find δt one has to maximize the functional
R(δ) =

m+`
X
i=1

m+`

1X
T
δiΦs Y −δrΦTr KΦs δs
2 r,s=1

subject to constraints−bτ γc∗ ≤ δt ≤ τbγc∗,t = (m + 1), ..., (m + `),−τ γc∗ ≤ δt ≤ τ γc∗,where we denotedt = 1, ..., m, τb + τ = 1,

Φm+t = (0, ..., 1, ..., 0))T,t = m + 1, ..., m + `.
32

LEARNING DOES NOT REQUIRE BIG DATA

According to Representer Theorem, the optimal solutionof learning problem in RKHS have properties:
1. It is defined by linear parametric functions in form of expansion on kernel functions (i.e optimal solution belongs
to one layer network, not multi-layers network).
2. Observation vectors x1, .., x` and kernel K(x, x0) define basisof linear expansion for optimal ` parametric solution.
3. SVM: to control VC dimension uses data to find both thebasis of expansion and the parameters of solution.
4. LUSI-SVM: to estimate unknown parameters of solution,
adds to ` training pairs m pairs (KΦs, YTΦs) obtained using
predicates. When τ ≈ 1 it uses just these m pairs.
5. Since any functions from Hilbert space can be used as
predicates φs(x), there exist one or several ”smart” predicates defining pairs (KΦs, YTΦs) to form optimal solution.
—
33

ILLUSTRATION

I:
0.3756
I&I: 0,2166

V:
0.1432
V &I: 0.1017
34

ILLUSTRATION

I:
0.3212
I&I: 0.1808

V:
0.1207
V &I: 0.0778
35

ILLUSTRATION

I:
0.1672
I&I: 0.1072

V:
0.0689V &I: 0.0609
36

MULTIDIMENSIONAL EXAMPLESTABLE 1
Data set
Training Features SVM
V&I
Diabetes
562
8
25.94% 22.73%
MAGIC
1005
10
19.03% 15.10%
WPBC
134
33
25.48% 23.02%
Bank Marketing445
16
12.06% 10.58%
TABLE 2Diabetes
MAGIC
Training SVM V&I9 Training SVM
V&I
71
28.42 27.52%
242
20.51 17.35%
151
26.97% 24.56%
491
20.93% 15.91%
304
26.35% 23.78%
955
18.89% 15.19%
612
25.43% 22.60%
1903
18.03% 14.25%

37

NEW INVARIANT FOR DIABETESψ∗(x) =

1, if x ∈ B (selected box)
0, otherwise

GlucosesickhealthyBMI

I&I(+∗) decreases errors rate from 22.73% to 22.07%.
38

WAY TO FIND NEW INVARIANT

Find a situation (the box B in Fig.), where the existing
solution (the approximation P`(y = 1|x)) contradicts the evidence (contradicts invariant for predicate φ(x) = 1 inside
the box) and then modify the solution (obtain a new approximation P(n+1)(y = 1|x)) which resolves this contradiction.
This is the same principle that is used in physics to discover the laws of Nature. To discover laws of the Naturephysicists first trying to find a situation where existing theory contradicts observations (The invariants fail. Theoreticalpredictions do not supported by experiments). Then they
trying to reconstruct theory to remove the contradictions.
They construct a new approximation of theory which does
not contradict the observed reality – keeps all invariants.
The most important (and most difficult) part in scientificdiscovery is to find contradictive situation.
39

PART V
LUSI APPROACH IN NEURAL NETWORKS

40

VP-BACK PROPAGATION ALGORITHM• Neural Networks searching for minimum of functional
RI(f ) = (F(f ) − Y)T(F(f ) − Y),in the set of piece-wise linear functions {f } realized by neuralnetwork. It uses gradient descent procedure of minimization(called Back Propagation). Procedure has three steps:
1. Forward propagation. 2. Backward propagation. 3. Updates of parameters.
• To minimize in the same set of functions the VP-form
RVP (f ) = (F(f ) − Y)T(bτ V + τ P)(F(f ) − Y),using back propagation technique, one has to modify justbackward step: instead of vector E = ((y1 − u1), ..., (y` − u`))T,(where u1, ..., u` are outputs of the last layer (last unit) on
vectors x1, ..., x`) one has back propagate modified vectorb = (bE
τ V + τ P)E.
41

SCHEME OF VP-BACK PROPAGATIONALGORITHM

1. Forward propagation step. Given initial weights w of Net,
propagate training vectors xi through all hidden layers.
2. Border conditions for back propagation. Let ui be value
corresponding to vector xi propagated on the last layer(unit) and ei = (yi − ui) be difference between target value
yi and obtained value ui. Consider vector E = (e1, ..., e`)T.
3. Back propagation step. Back propagate vectorb = (bE
τ V + τ P)E, where E = (e1, ..., e`)T.
4. Weights updating step. Compute gradient of weights andupdate the weights of the network.

42

EXAMPLE: MNIST DIGIT RECOGNITION
Minimization of R(f ) = (Y − F(f ))T(bτ V + τ P)(Y − F(f )).
2D image of digit ui(x1, x2). Predicate: φ(ui) = 1.
Experiment settings: V = I, ` = 1, 000 (100 per class). Batch 6.
5

T=0, 96.9%
T=0.05, 97.1%

4

3

2

0

10

20

30

40

50

Error rate: DNNet – 3.1%,

60

70

80

90

100

VP-NNet – 2.9%
43

EXAMPLE: MNIST DIGIT RECOGNITIONTMinimization of R(f
)
=
(Y
−
F(f
))
(b
τ V + τ P)(Y − F(f )).
R1
Predicate: φ(ui) = 0 ui(x1, x2) cos 2πx1dx1dx2, (u(x1, x2) is a digit).

Experiment settings: V = I, ` = 1, 000 (100 per class). Batch 6.
6

avg-grad(6)Tau(10)*P[cos 2*Pi*x*pca[0] ]

5

4

3

0

20

40

60

Error rate: DNNet – 3.4%,

80

100

120

140

VP-NNet – 3.3%
44

EXAMPLE: MNIST DIGIT RECOGNITION
Minimization of R(f ) = (Y − F(f ))T(bτ V + τ P)(Y − F(f )).
Z 1
φm,n(ui) =ui(x1, x2) cos mπx1 cos nπx2dx1dx2, m, n = 1, 2, 3, 4.
0

Experiment settings: V = I, ` = 1, 000 (100 per class). Batch 6.
10

avg-grad(6)Tau(10)*P[FFT 4x4]

9
8
7
6
5
4

3

2

0

20

40

60

Error rate: DNNet – 3.4%,

80

100

120

140

VP-NNet – 2.8%
45

STATISTICAL PART OF LEARNING THEORYIS COMPLETED
Theory found that:
1. The functional for minimization defines V-quadratic formR(f ) = (Y − F(f ))TV(Y − f (f )).

(1)

2. In RKHS, where F(f ) = KA, the admissible set of functions
is defined by invariants for given m predicate functions φk:
T
ΦT
KA
=
Φ
k
k Y, k = 1, ..., m.

(2)

3. For RKHS the structure in SRM method is defined by thevalues of norm of functions from RKHSATKA ≤ C,(3)

which satisfies (2).
4. There exist unique (closed form) solution for the problemof minimization (1) subject to constraints (2) and (3).

46

The only question left is ”How to choose set of predicates”?
Answer to this question forms intelligent content of learning.

PART VI
EXAMPLES OF PREDICATES

47

EXAMPLES OF GENERAL TYPE
PREDICATES`X

P`(y = 1|xi)φ(xi) =

i=1

`
X

yiφ(xi)

(∗).

i=1

•••
1. Predicate φ(x) = 1 in (*) collects functions for which
Expected number of elements of class y = 1 computed
using P`(y = 1|x) equal to the number of training
examples of the first class.
2. Predicate φ(x) = x in (*) collects functions for which
Expected center of mass of vectors x of class y = 1
computed using P`(y = 1|x) coincides with center ofmass of training examples of the first class.
3. Predicate φ(x) = xxT, x ∈ Rn collects functions for which
Expected 0.5n(n + 1) values of covariance matrix
computed using P`(y = 1|x) coincide with values ofcovariance matrix computed for vectors x of the firstclass.
48

EXAMPLES OF PREDICATES FOR 2D
IMAGES {u(x1, x2)}
Let 2D functionsu(x1, x2), 0 ≤ x1, x2 ≤ πdescribe images and let ` pairs(u1(x1, x2), y1), ..., (u`(x1, x2), y`),form the training set.
1. Predicates
Z πZ πφr,s(ui) =ui(x1, x2) cos rx1 cos sx2dx1dx2,
0r, s = 1, ..., N0define coefficients ar,s of cosines expansion of image ui(x1, x2).
2. For a given function g(x1, x2) predicate
Z ∞Z ∞
φ(ui, xµ, xν ) =ui(x1, x2)g(x1 − x1µ, x2 − x2ν )dx1dx2,−∞−∞

defines value of convolution at point (x1µ, x2ν ).
49

INSTRUMENTS FOR SPECIAL PREDICATES

LIE DERIVATIVES
Let image is defined by differentiable 2D function u(x1, x2).
Consider small linear transformations of 2D space (x1, x2) ∈ R2:
 1
 1

1
2
x
x + a1x + a2x + a3tα=⇒x2x2 + a4x2 + a5x1 + a6
For small ak function u(ta(x1, x2) in space t(x1, x2) has thefollowing representation in non-transformed space (x1, x2)u(tα(x1, x2)) ≈ u(x1, x2) +6
X

akLku(x1, x2),

k=1

where Lku(x1, x2) are the so-called Lie derivatives.

50

ILLUSTRATION

Digit 2 in transformed space and in original space correctedby Lie operator of rotation

From paper by P. Simard et al. ”Transformation
invariance...”51

LIE OPERATORS

1. Horizontal translation ta(x1, x2) −→ (x1 + a, x2)
Lie operator is L1 = ∂x∂ 1
2. Vertical translation ta(x1, x2) −→ (x1, x2 + a)
Lie operator is L2 = ∂x∂ 2
3. Rotation tα(x1, x2) −→ (x1 cos α − x2 sin α, x1 sin α + x2 cos α)
Lie operator is L3 = x2 ∂x∂ 1 − x1 ∂x∂ 2
4. Scaling ta(x1, x2) −→ (x1 + ax1, x2 + ax2).
Lie operator is L4 = x1 ∂x∂ 1 + x2 ∂x∂ 2
5. Parallel hyperbolic ta(x1, x2) −→ (x1 + ax1, x2 − ax2)
Lie operator is L5 = x1 ∂x∂ 1 − x2 ∂x∂ 2
6. Diagonal hyperbolic ta(x1, x2) −→ (x1 + ax2, x2 + ax1)
Lie operator is L6 = x2 ∂x∂ 1 + x1 ∂x∂ 2
52

ILLUSTRATION
Digit 3 and it transformations using 5 Lie operators(scaling, rotation, expansion-compression, diagonal
expansion-compression, thickening)

From paper by P. Simard et al. ”Transformation
invariance...”53

INVARIANTS WITH RESPECT TO LINEAR
TRANSFORMATIONS.

Let ui(x1, x2i) be an image ((n × n) matrix in pixel space(x1.x2)). Consider six predicate matrixes
φk(ui) = Lkui(x1, x2),

k = 1, ..., 6

and corresponding six sets of invariants`X
i=1

φk(ui)P`(y = 1|xi) =`X

yiφk(ui),k = 1, ..., 6.

i=1

Adding these equalities to LUSI constraints one tries toestimate rule P`(y = 1|x) which keeps invariants with respect
to Lie transformations.

54

TANGENT DISTANCE

Consider two image functions u1(x1, x2) and u2(x1, x2).
Let us introduce two six parametric sets of functions{u1(x1, x2)}a = u1(x1, x2) +6
X

akLku1(x1, x2)

k=1{u2(x1, x2)}b = u2(x1, x2) +6
X

bkLku2(x1, x2)

k=1

defined by small parameters ak and bk k = 1, ..., 6.
Tangent distance between functions u1 and u2 is the value
dtang (u1, u2) = min||{u1(x1, x2)}a − {u2(x1, x2)}b|| =a,b

min u1(x1, x2) +
a,b

6
X
k=1

akLku1(x1, x2) − u2(x1, x2) −6
X

bkLku2(x1, x2) .

k=1• Predicate dtang (u, u0) defines tangent distance from u to u0.
55

EXAMPLES OF PREDICATES THAT DEFINE
DEGREE OF SYMMETRIES
1. Predicate defining degree of vertical symmetry f (x)
xn1 · · · xnn
x11 · · · x1nu(x) =  .. . . . ..  ,uT1 (x) =  .. . . . ..  .
x11 · · · x1nxn1 · · · xnn
Predicate defines tangent distance dtang (f , fT1 ).
2. Predicate defining degree of horizontal symmetry f (x)
x1n · · · x11x11 · · · x1n
uT2 (x) =  .. . . . ..  .
u(x) =  .. . . . ..  ,xnn · · · xn1
xn1 · · · xnn
Predicate defines tangent distance dtang (u, uT2 ).

56

3. Predicate defining degree of horizontal antisymmetry f (x)
x11 · · · x1nxnn · · · xn1
u(x) =  .. . . . ..  ,uT3 (x) =  .. . . . ..  .
xn1 · · · xnn
x1n · · · x11
Predicate defines tangent distance dtang (u, uT3 ).

CONCLUSIVE REMARKS• Complete statistical methods of learning require, using
structural risk minimization principle, in a given set of functions {f (x)} minimize functional
RV (f ) = (Y − F(f ))TV(Y − F(f ))subject to invariant constraints
T
ΦT
F(f
)
=
Φ
s
s Y.

• LUSI method provides unique solution of this problem forfunctions from RKHS and approximation for Neural Nets.
• Further progress in learning theory goes beyond statisticalreasoning. It goes in the direction of search of predicates
which form basis for understanding of problems existing in
the World (see Plato–Hegel–Wigner line of philosophy).
• Predicates are abstract ideas, while invariants that arebuilded using them form elements of solution. These twoconcepts reflect essence of intelligence, not just its imitation.
57

THE CHALLENGE

Using 60,000 training examples of MNIST digit recognition
problem (6,000 per/class) DNN achieved ≈ 0.5% test error.
1. Find predicates which will allow you to achieve the samelevel of test error using just 600 examples (60/per class).
2. Find a small set of basic predicates to achieve this goal.

58

PLATO-HEGEL-WIGNER LINE OF
PHILOSOPHY

In 1928 Vladimir Propp published book ”Morphology of
the Folktale” where he described 31 predicates that allow
to synthesize Russian folk tales. Later his morphology has
been successfully applied to other types of narrative, be it inliterature, theater, film, television series, games, etc. (although Propp applied it only to the wonder or fairy tale).
(See Wikipedia: Vladimir Propp.)
The idea is that World of Ideas contains small amount ofideas (predicates) that can be translated in World of Things
by many different invariants.
Propp found 31 predicates which describe different actionsof people in Real World. Probably there exist a small amountof predicates that describe 2D Real World images. The challenge is to find them (to understand World of 2D images).
59