The Problem
- 格式:pdf
- 大小:2.49 MB
- 文档页数:35
Classifying Matrices with a Spectral Regularization
Ryota Tomioka & Kazuyuki Aihara University of Tokyo / Fraunhofer FIRST 2007/06/23
Logit-loss Matrix Scalar Dual Interiorpoint
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Summary
• Proposed the Matrix Classifier that factorizes using the Spectral -regularization.
Single-trial EEG Classification
The Covariance EEG signal Class Label
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Single-trial EEG Classification
The Covariance EEG signal Class Label
• Implementation
– Dual formulation. – Linear Matrix Inequality. – Interior point method.
• Application
– Motor-imagery EEG classification.
• Summary
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
LASSO:
Ridge penalty:
Spectral
-regularization:
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
The Problem
Lagrange multipliers
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
MTFL
[Argyriou et al. 07]
Uncovering Shared Structure
[Amit et al. 07]
Classifying Matrices
[this talk]
Application
Matrix Factorization
Multi-ouput Regression
6 4 2 0 t=1 t=4
0
0.5
1
Original problem!
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Good News for IP optimization
• Obtaining the Primal Variable:
: solution at barrier parameter t
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Extracted Features (2/2) Eigenvectors
10 5 0 −5 −10 −15 0 10 20 30 40 Eigencomponents 50 0.01 0.48329 3.3598 8.8587 (selected)
– Two steps:
• Feature Extraction: Find a low-dimensional decomposition. • Classify: linear classifier on the log-power feature.
• LR (L2)
– (Frobenius norm)-regularized logistic regression.
Implementation
- Dual Formulation - Linear Matrix Inequality - Interior Point Method
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
The First Trick: The Dual Optimization Problem
The fit must be simple (large entropy)
Residual of the fit must be small
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
The Second Trick: Using Linear Matrix Inequality
Eigenvalues
5 0 −5 −10
0.01 0.48329 3.3598 8.8587 (selected)
Smaller #components
Stronger Regularization
0 0.01 0.1 1 10 100 Regularization constant (λ) −15 0 10 20 30 40 Eigencomponents 50
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Extracted Features (1/2) Model Selection and Eigenvalues
Test Model Selection
(a) 60
50
(b) 15
10
Error (%)
40 30 20 10
Works on Spectral (Trace-norm) Regularization
• Prior work by Fazel, Hindi, and Boyd (2001) • Related work by Abernethy et al. (2006)
MMMF
[Srebro et al. 05]
• Quality guarantee:
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Application: Motor-imagery EEG Classification
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
• LR (rank=2)
– Rank=2 constrained logistic regression (nonconvex!)
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Results: Classification Errors
• Low-ranked ( -regularized) solution performs better. • Fixed rank performs suboptimal.
Using the singular-value decomposition:
The classifier can be written as:
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Interpreting the Model
Using the singular-value decomposition:
– Single convex optimization problem. – Dual formulation and Linear Matrix Inequality for efficient optimization. – Sparseness: interpretable solution.
Multi-class Classification
Matrix Classification
Loss Function Input Output Optimization
Hinge-loss Scalar Matrix SDP
Quad-loss Vector Vector Iterative
Hinge-loss Vector Vector Primal Gradient
ERD/ERS Lateralized modulation of rhythmic activity Left Right
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Conventional Methods
• Common Spatial Pattern (CSP) [Koles 1991; Ramoser 2000] (State of the art)
Ryota Tomioka at ICML 2007 Corvallis, OR, USA
Outline
• Method
– Discriminative model that factorizes using the spectral -regularization. – Penalized empirical loss minimization (convex!).
Examples of Matrix Inputs
• Multivariate Time Series
Sensors Time
• Second order statistics
Sensors
Sensors
Hale Waihona Puke 51015
20
25
30
35
40
45
5
10
15
20
25
30
35
40
45
Ryota Tomioka at ICML 2007 Corvallis, OR, USA