On the sparse estimation

ATR Computational Neuroscience
Laboratories
Masa-aki SatoContents
1. Why sparse estimation is necessary?
Generalization ability for ill posed problem
2. Why sparse estimation can be achieved?
Role of Bayesian estimation
3. Example of sparse estimation for realproblem

Ill-posed problem
Large number of parameters are estimatedfrom small number of data
• Maximum Likelihood (Minimum Squared Error)– Estimate optimal parameter which maximize likelihood– Overfitting:Complex models with many adjustable parameters tend tofit noise in training data and degrade generalization ability• Sparse estimation
Extract relevant features and discard irrelevant features
to attain good generalization ability

Function approximation by polynomial
y = w 0 + w1x + w2x 2 + … + wN x N=W ⋅ X

Linear parameter model

X = ⎡⎢ 1, x , x 2, …, x N ⎤⎥⎣⎦Input (feature) variableW = ⎡⎢ w 0, w1, w2, …, wN ⎤⎥ Weight parameter vector⎣⎦

50 data points are
randomly generated
from quadratic function

y = 2x − x 2 + noiseMaximum likelihood (Quadratic function)
Minimize Squared Error
Terror = ∑ ( y ( t ) − W ⋅ X ( t ) )2t =1

Find optimal W

Maximum likelihood (20 degree polynomial)
Overfitting : Optimal W fits noise in training data
Generalization is not good

Regularization method (20 degree polynomial)
Terror = ∑ ( y ( t ) − W ⋅ X ( t ) )2 + α ⋅ W 2
t =1(1Prior : P (W ) ∝ exp − α ⋅ W 22Minimization)

Model selection•

Search best model which gives best generalization error
by changing number pf parameters (polynomial degree)• Combinatorial serach is almost impossiblefor large degree of freedom
Training error & Generalization error

Number pf parameters (Polynomial degree)

Sparse estimation by Bayesian method• Parameters are considered as random variable• Posterior probability is calculated for possible parameter value• Estimation is done by integrated over possible value
according to posterior probability distribution

Sparse estimation (20 degree polynomial)• Precision parameter αn is introduced
for each weight component wn and estimated from observed data1Prior P ( wn ) ∝ exp − αn ⋅ wn 2 , αn = 不定2()

Posterior for 2nd order weight

Posterior for 3rd order weightSparse Estimation
Prunes irrelevant features in the modeland increase generalization ability

MAP / ML Estimation(Maximum a Posteriori / Maximum Likelihood)
Liklihood• Posteriorprior

P ( X | θ ) P0 ( θ )P (θ | X ) =P (X )Marginal likelihood• Estimate optimal parameter

θMAP = arg max log ( P ( X | θ ) P0 ( θ ) )P (θ | X )θ2Regular Modelθ1Full Bayesian Estimation
Liklihood• Posteriorprior

P ( X | θ ) P0 ( θ )P (θ | X ) =P (X )Marginal likelihood• Estimate posterior parameter distribution
and integrate over parameters according to the posterior.
Marginal likelihood

P ( X ) = ∫ dθ P ( X | θ ) P0 ( θ )Estimated parameterθ = ∫ dθ P ( θ | X ) θModel reduction
by Bayesian method
Mixture of Gaussian example

Redundant Model (ill-posed problem)
Estimation model is a Mixture of two Gaussian units

P ( x | θ ) = g 0 ⋅ N ( x | θ1 ) + ( 1 − g 0 ) ⋅ N ( x | θ2 )Assume data is generated by a single GaussianSingle unit model correspond to three cases :P ( x | θ ) = N ( x | θ1 ), g 0 = 1 , θ2 = arbitrary
P ( x | θ ) = N ( x | θ2 ), g 0 = 0 , θ1 = arbitrary
P ( x | θ ) = N ( x | θ1 ), θ1 = θ2 , g 0 = arbitrary

Posterior distribution for redundant modelg0 = 1

g0 = 0P (θ | X )θ2P (θ | X )θ1

θ2

Fisher Information matrix becomes singularθ1

Pruning of redundant parameters• Complex models explain a given data better
than simpler models and give higher posterior value• Then all parameters are used for prediction

MAP
Full Bayesian• Reduced simpler model dominates
by integration over parameters

Posterior distribution for 100 sample data generated by a single Gaussian model
MAP optimal

Reduced model

Reduced model

P (θ | X )g0 = 0g0 = 1

θ2

θ1

Parameter pruningin Sparse Estimation

Prior in Sparse Estimation Model
αn controles a precision (width) ofweight parameter distribution
1P ( wn | αn ) ∝ αn ⋅ exp − αn ⋅ wn 22PriorP ( log ( αn ) ) = const . （Non-informative prior）
wn = 0 , αn = Arbitrary()

Posterior parameter distribution for ( wn , αn )Other parameters are integrated out
And their effects are taken into account
Posterior for relevant parameter

Posterior for irrelevant parameter

wn = 0αn = arbitraryCalculation of posterior distributionLiklihood• Posterior

P (J , α B ) =P (B J )P0 (J α )P0 (α )J = ∫ J P (J , α B )d J d αFree energy maximization(Hierarhical) prior

P (B )

Marginal likelihood

Posterior calculation

Distance between trial posterior Q(J,α) and true posterior P(J,α|B)[]

F [Q(J, α )] = ln P(B ) − KL Q(J, α ) P(J, α B )Log marginal likelihood (Evidence)Variational Bayesian (VB) method
Factorization assumption ： Q ( J , α ) = QJ ( J )Qα ( α )Maximization of F(Q) w.r.t. Qα ( α )Maximization of F(Q)Maximization of F(Q) w.r.t. QJ(J)
Repeated until convergence

Posterior distribution

P ( J | B ) ≈ QJ ( J ) at the maximum

Log marginal likelihood log ( P ( B ) ) ≈ maximized F (Q )Free energy
Free energy after integration of current distribution
1⎡−1⋅ B ⋅ B ′ ) + log ΣVB ⎤⎥F = − ⎢ Tr ( ΣVB⎦
2⎣
B ⋅ B ′ = G ⋅ J 0 ⋅ J 0′ ⋅ G ′ + σ0I

MEG covariance matrix
Estimated MEG covarianceΣVB = G ⋅ W ⋅ α ⋅ W ′ ⋅ G ′ + σI

Optimal condition (Free energy maximum)

J ⋅ J′α (n ) =GVB ( n )Estimation gainVariational Bayesian method
Posterior calculation is converted tofree energy maximization
Free energy = (Likelihood)+ (Model complexity)
Likelihood
1L = − ⎢⎡ (Y − W ⋅ X )2 + W ′ ⋅ α ⋅ W ⎥⎤Error⎦2⎣Decreasing
1⎡−1 ⎤
2
2= − ⎢ (Y ) − (Y ⋅ X ) ⋅ ( X ⋅ X ′ + α ) ⎥ function of α⎦2⎣Model complexity

1
H = − log X ⋅ X ′ ⋅ α−1 + 1
2
1→ − N ⋅ log (T ) for finite α ,T ≫ 1
2Increasing
function of αBIC

One dimensional case1
H = − log X ⋅ X ′ ⋅ α−1 + 1
2
as α → ∞→0Genaral dimension

1H = − log X ⋅ X ′ ⋅ α−1 + 1
2
1→ − Neff ⋅ log (T )2
Neff Number of finite

α,T ≫ 1

Example of sparse estimation
for real problem
I Nambu, R Osu, M Sato, S Ando, M Kawato, E Naito
Single-trial reconstruction of !nger-pinch forces fromhuman motor-cortical activation measured by nearinfrared spectroscopy (NIRS)
NeuroImage 47 (2009) 628.637

Sparse estimation

forceForce

Estimate pinching force
from 24ch x 21 (sec) NIRS data
(Nambu et al)
time

Estimated weightby brute force model search

Estimated weightby sparse estimation

Estimated force from NIRS data