A Brief Introduction to Artificial Intelligence
Yukihiko Yamasita
Dept. of International Development Engineering
Tokyo Institute of Technology

Contents
1. Fields of AI
2. Statistical learning theory
3. Neural networks
4. Deep learning11 Fields of AI
AI stands on many fields.
Application• Expert system– A computer system that emulates the decision-making ability ofa human expert.
– Prediction, diagnosis, design, planning, monitoring, debugging,repair, instruction, control, etc.
• Natural language processing– Understand and generate sentences to communicate between human and computer– Language translation– Speech recognition and generation• Pattern recognition– Optical character recognition (OCT): Postal number reader– Computer vision, face detection and recognition.
2• Autonomous vehicle and robots• Art (music and painting) generation• Games (chess and Go)• Big Data
– Extract information from a huge amount of data (The history of
web accesses, tweets, positions, texts, and so on)– Marketing– Diagnostics : Building, bridge, etc. Airplane, train, etc.
Hardware• General purpose computer– ENIAC : Electronic Numerical Integrator and Computer, 1945
– IBM System 360, i386, Core, ARM, ...
• LISP machine (1973)– LISP (List Processor) : Programming language to handle symbols
easily3• PSI (Personal Sequential inference Machine),
PIM (Parallel Inference Machine)– Prolog : Programming language for logical inference• GPGPU (General Purpose Graphic Processing Unit)– NVidia TESLA V100: Over 5,000 calculation cores.
7 TFlops (FP64), 28 TFlops (FP16),– Deep learning and image processing (Linear algebra).
– CUDA : Compute Unified Device Architecture
Methods• Symbol processing• Logic inference• Statistical learning• Neural networks• Deep learning4

2 Statistical learning theory
2.1 Framework• z: pattern• Pattern are observed randomly.
• F(z): cumulative probability distribution function• Assumption: each pattern has its category.
• Assumption: a family of (classification) functions dα(z) (α ∈Λ) that
returns a category for an input pattern z.
• We define a function Q(α, z) with a classification function dα(z).
{0 (the result of dα(z) is correct)
Q(α, z) ≡.
1 (the result of dα(z) is incorrect)• R(α) : the expectation of the risk of a classification function dα.
( ∫)∫R(α) = Ez Q(α, z) =Q(α, z)dF(z) =Q(α, z) f (z)dz .
The problem is to obtain the classification function dα that minimizes R(α).
5• For learning, we can use only finite number of patterns.
• K : the number of learning patterns.
z1, z2, . . . , zK .
• Assumption: we know the category of each learning patterns.
• The risk of a classification function for learning patterns is calculated byK
1∑Q(α, zk ).
Remp(α) =K
k=1

We call it the empirical risk.
• The diﬀerence between two risks is evaluated in statistical learningtheory.
∫R(α) =Q(α, z)dF(z),Remp(α) =

K
∑
1

K
6

k=1

Q(α, zk ).

Definition 1. ERM (empirical risk minimization) principle
Use dα that minimized Remp(α) instead of R(α).

• Learning patterns appear according to a p.d.f. f (z).
• Estimate the expectation of Q(α, z) from Q(α, zk ) for learning patterns zk .
7

2.2 Entropy, annealed entropy, growth function• N Λ(z1, z2, . . . , zK ) : the number of diﬀerent (Q(α, z1), Q(α, z2), . . . ,Q(α, zK )) when we fix (z1, z2, . . . , zK ) and vary α ∈ Λ.
• That is the number of diﬀerent types of risk array of classification
functions for a fixed set of input patterns.
• Entropy :H Λ(K) = Ez1,z2,...,zK ln N Λ(z1, z2, . . . , zK )• Annealed entropy :Λ (K) = ln EΛHann
z1,z2,...,zK N (z1, z2, . . . , zK )• Growth function :GΛ(K) = ln

max

z1,z2,...,zKN Λ(z1, z2, . . . , zK )• We have following relation.
Λ (K) ≤ GΛ(K)H Λ(K) ≤ Hann
82.3 Basic inequality
The following theorem is one of the most important theorems for statistical learning theory.
Theorem 1. We have following relation. (Basic inequality)

)2 
(
{
}
Λ



1   Hann(2K).
− ε−P sup |R(α) − Remp(α)| > ε < 4 exp  K 




K
K
α∈Λ
• The left hand side is the probability that learning patterns (z1, z2, . . . , zK )appears, with which the maximum absolute diﬀerence between theensemble risk and the empirical risk among all α ∈ Λ is larger thanε.
Λ (2K) < GΛ(2K),• Since Hann

 
{
}
(
)
2



1  GΛ(2K)P sup |R(α) − Remp(α)| > ε < 4 exp − ε−.
 K 


 K

K
α∈Λ

9

2.4 VC (Vapnik-Chervonenkis) dimension
Theorem 2. For any integer K, we have GΛ(K) = K ln 2 or there exists
an integer h (VC dimension) such that
GΛ(K) = K ln(∑2
) (K ≤ h)
GΛ(K) ≤ ln hi=0 K Ci (K > h)
• When the number of samples is less than or equal to h, there exists an classifier that splits all samples correctly for any labeling ofsamples.
Theorem 3.

{}

P sup |R(α) − Remp(α)| > ε
α∈Λ

 
(
)
2



1   h(1 + ln(2L/h))< 4 exp − ε−.
 K 




K
K

10

2.5

VC dimension and risk

Corollary 1. With probability 1 − η the following relation holds.
√h(1 + ln(2K/h)) − ln(η/4).
R(α) − Remp(α) ≤
K
11

2.6

Linear classifier and VC dimension

12

2.7 Support vector machine (SVM)• A linear classifier (of two-class problem):d(x) = ⟨w, x⟩ + θ.
• (xk , yk ): a pair of sample xk and its label yk (= ±1) (k = 1, 2 . . . , K)

Maximize margin
13

2.8

Margin and VC dimension• Assume that the norm of patterns are upper bounded. The larger
margin the fewer VC dimension is.
14

2.9 Soft margin• Soft margin : Some errors are allowed.

1+ C (Sum of errors) → min.
Margin15

2.10 Solution of linear SVM
Lagrange’s method :Subject to0 ≤ αk ≤ C, (k = 1, 2, . . . K)K∑

αk y k = 0

(1)

l=1

Maximize
LD =

K
∑
k=1

αk −

K ∑
K
∑
1

2

αk αlyk yl⟨zk , zl⟩(2)

k=1 l=1• Variables for optimization problem are only αl.
• The dimension of this problem is the number of samples.
• The classification function can be calculated by∑d(x) =
αlyl⟨zl, x⟩ + θzl∈S V• θ is obtained by using KKT condition.
16(3)

2.11 Kernel method for nonlinear SVM• Patterns are mapped by a nonlinear function Φ.
√
√
√
2
2
Example: Φ(x1, x2) = (x1, x2, 2x1 x2, 2x1, 2x2, 1)

Kernel function : k(x, z) ≡ ⟨Φ(x), Φ(z)⟩ = ⟨x, z⟩2 + 1
17

2.12 Nonlinear SVM• Classification function and its criterion of linear SVM are expressed
only by inner products. (Kernel method)• Classification function∑
d(x) =
αlylk(zl, x) + θ(4)zl∈S V• The optimization problem for learning is given as
Subject toK∑
0 ≤ αk ≤ C, (l = 1, 2, . . . K),
αk yk = 0(5)
k=1minimize
LD =

K
∑
k

αk −

K ∑
K
∑
1

2

k=1 l=1

with respect to αk .
18

αk αlyk ylk(zk , zl)(6)

3 Neural networks
3.1 Perceptron• An imitation of a biological neuron– xi : inputs to a perceptron. (i = 1, 2, · · · , N).
– wi : weights (i = 1, 2, · · · , N).
– θ : threshold.
• We extend an input vector and a weight as x0 = 1 and w0 = θ,then we haveNN∑∑
wi x i + θ =wi x ii=1

i=0• The output f (x1, . . . , xN ) of perceptron is given by.
 (∑)

N wx >01i=0 i if (x1, . . . , xN ) = .
 0 (otherwise)19Perceptron
Training algorithm(k) (k)(k)• (xi , y ) : a pair of sample data xi and its label y(k)(= ±1) (l =1, 2 . . . , K)
• Update rule:(k)wi ⇐ wi − µ( f (x0, . . . , xN ) − y(k))xi
20

3.2 Neural network
Artificial neuron
f (x) = ϕ(z), z = ⟨w, x⟩ =

N
∑

wn xn

n=1

• ϕ(z) is the activation function.
Example: sigmoid function
1
ϕ(z) =
1 + eγz

https://upload.wikimedia.org/wikipedia/commons/a/ac/Logistic-curve.png

21

Multi-layer network• L : the number of layers.
• Nl : the number of neurons in the l-th layer.
• ϕl(z) : the activation function in the l-th layer.
• xi, l : the i-th input of a neuron in the l-th layer.
• wi, j, l : the weight from the ouptput of the j-th neurons in the (l − 1)th layer to the i-th neurons in the l-th layer.
(The thresholds are included in weights.)
zi, l =

N∑(l−1)

wi, j, l x j, l

(7)

j=1

xi, (l+1) = ϕl(zi, l)• x j, 1 is the input of the network.
• x j, (L+1) is the output of the network.

22

(8)

Example: 4-layer neural network





N3
N2
N1
∑
∑

∑
w j, n, 2 xn
ym =wm, i, 4ϕ3  wi, j, 3ϕ2 


i=1

j=1

n=1

23

3.3 Back propagation
Training algorithm for multi-layer network.
• Neural network: ym = fm(x0, . . . , xN1 ; {wi, j, l}).
(k)(k) (k)(k)(k)• (x0 , . . . , xN ; y1 , . . . , yN ) : a pair of sample xn and its target
(k)

L

1

output ym (= ±1) (k = 1, 2 . . . , K)
• Minimum squared error (MSE)
argminwi, j, l

NL
K ∑
∑
k=1 m=1

(k)
(k)
(k) 2
fm(x0 , . . . , xN ; {wi, j, l}) − ym
1

• Maximum gradient method is applied for each sample point.
Update rule:∂wi, j, l ⇐ wi, j, l − µ∂wi, j, l

NL
∑

(k)
(k)
(k) 2
fm(x0 , . . . , xN ; {wi, j, l}) − ym
1

m=1

24

Update rule:∂wi, j, l ⇐ wi, j, l − µ∂wi, j, l

NL
∑

(k)
(k)
(k) 2
fm(x0 , . . . , xN ; {wi, j, l}) − ym1

m=1

• In the L-th layer, the errors of outputs is defined by
(k)

(k)

(k)

εm, L = fm(x0 , . . . , xN ; {wi, j, l}) − ym . (m = 1, 2, . . . , NL)
1• Then, the update rule of wi, j, l is given by,wi, j, l ⇐ wi, j, l − 2µ

NL
∑
m=1

∂
fm(x0, . . . , xN1 ; {wi, j, l}).
εm, L∂wi, j, l• We describe the derivative of ϕl(z) asdϕl′ϕl (z) =
dz z

25

∂
fm(x0, . . . , xN1 ; {wi, j, l})∂wi, j, l
N∑
NL
L−1
∑
=
ϕ′L(ziL, L)wiL, iL−1, L ·ϕ′L−1(ziL−1, (L−1))wiL−1, iL−2, (L−1)
iL=0
N
l+1
∑

···

il+1=0iL−1=0ϕ′l+1(zil+1, (l+1))wil+1, i, (l+1)ϕ′l (zi, l)x j, l

(9)

• The update rule can be described aswi, j, l ⇐ wi, j, l − 2µϕ′l (zi, l)x j, l εi, l,
where εi, l is the errors of outputs to be reduced in the l-th layer:
εil, l =N
l+1∑
il+1=0ϕ′l (zil+1, l)wil+1, il, (l+1) εil+1, (l+1).

This can be calculated layer by layer from the end to the beginning.
⇒ Back propagation.
26

εil, l =N
l+1∑
il+1=0ϕ′l (zil+1, l)wil+1, il, (l+1) εil+1, (l+1).
27

3.4 Hopfield network
Traveling Salesman Problem (TSP)• Cm : city m. (m = 1, 2, . . . , M).
• dmn : the distance between Cm and Cn.
• Search a path of the minimum length that go through all cities andreturn to the start city.
• Its computational complexity is NP-complete (even if the distances
are given by Euclidean distance on a plane).

URL: https://jp.mathworks.com/help/optim/ug/travelling-salesman-problem.html
28

Hopfield network• A recurrent network.
• si(= 0, 1) : the state of the i-th unit (neuron) (i = 1, 2, . . . , N).
• wi j : the strength of connection between the i-th and the j-th units.
• θi : the threshold of the i-th unit.
• wi j = w ji

Hopfield network29• Update rule:

 (
)
∑


N w s −θ ≥01i
j=1 i j jsi ⇐ .

 0 (otherwise)• Energy function:
E=−

N
N
∑
∑
1

2

i=1 j=1, j,iwi j si s j +

N
∑

θi si

i=1

• From such a quadratic energy function, we can construct a Hopfield
network.
• The energy is not increased by the update.
• At first they consider the Hopfield network can provide the solutionof energy minimization problem (such as TSP) quickly.
• However, it is not true. the Hopfield network cannot give the global
optimum solution in many cases.
• The decreasing will stop at a local minimum point.
30

TSP by Hopfield network• For m = 1, 2 . . . , M and n = 0, 1 . . . , M, we define a mapping as{
m + Mn (n < M)
i(m, n) =.
m(n = M)• The states are defined by{
1 (if the path reaches city m after n moves)si(m, n) =.
0 (otherwise)• Energy function:
E =

M−1
M ∑
M
∑∑

dm,l si(m, n) si(l, n+1)

n=0 m l
M  ∑
M
∑

+α




n=1 m=1

2

2
M ∑
M


∑



si(m, n) − 1 + βs−1i(m, n)
m=1 n=1• TSP can be expressed by a Hopfield network.
31

3.5 Boltzmann machine• To solve the problem of local minimum points, the probability is
introduced to the Hopfield network.
• T : temperature∑N• ∆Ei = j=1 wi j s j − θi : the diﬀerence of energy• Probability si = 1 at the next stage is given by
1()∆E
1 + exp − T i• There is a possibility to escape from a local minimum point.
• The probability of the set of states of which energy is the minimum
is higher than the other sets.
• The temperature T is set to a high value and is decreased gradually
to make the convergence faster with a more precise solution.
⇒ Simulated annealing.
32

Restricted Boltzmann machine (RBM)• Two types of units : Visible and Hidden (Latent) units.
• Weights wi, j are zero between units of the same type.
• RBM is used in the training of Deep learning.
⇒ Weights wi, j are trained.

Restricted Boltzmann machine (RBM)
URL: https://en.wikipedia.org/wiki/Boltzmann_machine#/media/File:Restricted_Boltzmann_machine.svg

33

3.6 Deep learning• Three layers used be standard for neural network when BP is used.
• Even if the number of layers is increased, the information for learning is dispersed so that it does not transfer properly between lower
and upper layers and PB does not work well.
• Deep learning is proposed for ’autoencoder’ (automatically tuned
encoder for data compression) by a neural network. (G. E. Hinton
and R. R. Salakhutdinov, “Reducing the dimensionality of data withneural networks,” Science, vol.313, July 2006.)• Encoder and decoder are joined. (Input and output are the same.)• A intermediate layer of which the number of neuron is smaller thanthat of input/output layer expresses features of patterns• The deep learning for the autoencoder consists of– Pretraining by restricted Boltzmann machine for each layer– Unrolling by BP– Fine-tuning
34

Pretraining by Restricted Boltzmann machine (RBM)• The network for the encoder is trained layer bylayer.
• vi : i-th component of visible unit
(0 or 1, binary pixel)– Input image for the first layer.
– The output of the (l−1)-th layer for l-th layer.
• h j : j-th component of hidden unit
(0 or 1, binary feature)35

Training of RBM• Repeat the following steps– Obtain h j from vi by the following probability1

P(h j = 1) =∑P(ṽ j = 1) =1

1 + e i wi, jv j
– Obtain the confabulation ṽ j from hi by the following probability∑

1 + e j wi, jhi• Calculate ⟨hi v j⟩ that is the fraction of times when v j and hi are on
together.
• Calculate ⟨hi ṽ j⟩ similarly.
• Update the weight :wi, j ⇐ wi, j + λ(⟨hi v j⟩ − ⟨hi ṽ j⟩),where λ(> 0) is a learning rate.
36

Unrolling by BP

Fine-tuning• The transposition of weight inl-th layer is used for (L − l + 1)

• Standard BP is used for the
final tuning.

37

Data compression of MNIST handwritten numeral images• Nine-layer network (784(= 28 × 28) − 1000 − 500 − 250 − 2)BP

Deep learning38

3.7 Convolutional Neural Network (CNN)
CNN consists of• Convolutional layer– A data in a region is mapped to a node of the upper layer similarly
to convolution so the weights are sift invariant.
– Several types of convolutions are applied.
– Consider 1D case. Let wi, j be the weight of the t-th type fromj-th node to i-th node of the upper layer. Then for any k, we havew(i−k),( j−k),t = wi, j,t• Pooling layer : the amount of date is reduced.

By Aphex34 - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=45673581
39• Fully connected layer (for the last layer)
Activation function f (x)• ReLU : rectified linear units (= hinge loss) : max(0, x)• Sigmoid function : 1/(1 + e−x)
∑ yjyi
• Softmax : e / j e : activation values in other units are used.

S. Albelwi and A. Mahmood, “A Framework for Designing the Architectures of Deep Convolutional Neural Networks,” Entropy, 2017.
40

Features in CNN
Daniel Jeﬀries, “Learning AI if You Suck at Math - P5 -ŁDeep Learning and Convolutional Neural Nets in Plain English!,”https://hackernoon.com/learning-ai-if-you-suck-at-math-p5-deep-learning-and-convolutional-neural-netsin-plain-english-cda79679bbe3

41

3.8 Long Short Term Memory (LSTM)• A type of recurrent networks.
• S. Hochreiter and J. Schmidhuber, “Long Short-term Memory,”NeuralComputation 1997.
• Alex Graves, et al. ”Speech recognition with deep recurrent neuralnetworks,” ICASSP 2013.

42• xt : input vector• ct : state vector• f t : forget gate vector• it : input gate vector• ot : output gate Vector• ht : output vector• W f , W i, W o, W c, U f , Ui, Uo, Uc, b f , bi, bo, bc : parameters• σh : activate function for state• σg : activate function for state, input gate, and output gate
• σh : activate function for output
Update rule:(◦ : Hadamard product (element-wise product))• f t = σg(W f xt + U f ct−1 + b f )• it = σg(W i xt + Ui ct−1 + bi)• ot = σg(W o xt + Uo ct−1 + bo)• ct = f t ◦ ct−1 + it ◦ σc(W c xt + Uc ct−1 + bc)• ht = ot ◦ σh(ct )43

3.9 Generative Adversarial Network (GAN)• Ian J. Goodfellow, et al. ”Generative Adversarial Nets,” NIPS, 2014.
• Two types of networks.
– Discriminative network : D(x)The probability that x came from the data rather than Generator.
– Generative network : G(z):The generated pattern from a noize z.

Modified from https://skymind.ai/wiki/generative-adversarial-network-gan

44• Criterion:
min max E x≃pdata( x)[log D(x)] + E z≃p z( z)[log(1 − D(G(z)))].
G D– D(x) to discriminate precisely.
– G(z) to generate patterns that cause misclassification of D(x).
– Its original purpose is precise discrimination.
– But the trained G(z) is used as a pattern generator.

Hunter Heidenreich, “What is a Generative Adversarial Network?,”
URL:https://towardsdatascience.com/what-is-a-generative-adversarial-network-76898dd7ea65

45

4 Conclusion• AI stands on many fields– Linear algebra– Statistical learning– Logic inference– Image and signal processing– Natural language processing– Parallel computing.
• Many applications– Pattern recognition∗ Character recognition∗ Computer vision (face detection and recognition))– Decision making (diagnostics and AlphaGO)– Natural language processing (for communication)– Big data (marketing and data scientists)– Autonomous vehicle and robot46

• Week points– Logical thinking and integration of information.
– AlphaGo : strong in earlier and last stages but weak in middle.
– For autonomous vehicle, a range finder (can measure distance) is
necessary although a human can drive a car with only an eye.
• Future– Precise recognition– Practical autonomous vehicle and robot– Language translation– Artificial general intelligence.
Instead of human, machines do everything.

Thank you very much for listening.

47