What is supervised learning?

Given (X_i,Y_i) pairs with neither F_Y nor F_Y degenerate, supervised learning is the estimation of any given functional of F_X|Y

What is supervised learning?

Given (X_i,Y_i) pairs with neither F_Y nor F_Y degenerate, supervised learning is the estimation of any given functional of F_X|Y

Examples

• Classification
• Regression
• 2-sample testing
• K-sample testing

Classification and Fisher's LDA

• Given F_X|Y = N(μ_y,Σ) and F_Y = B(π),
• where X ϵ R^p
• Bayes optimal classifier is x' Σ^-1 δ > t, where δ=μ₀-μ₁

Classification and Fisher's LDA

• Given F_X|Y = N(μ_y,Σ) and F_Y = B(π),
• where X ϵ R^p
• Bayes optimal classifier is x' Σ^-1 δ > t, where δ=μ₀-μ₁

Properties

• simple
• multiclass generalizations
• plug-in estimate converges to Bayes optimal
• algorithmic efficiency

But...

• When n < p, our estimate of Σ is singular
• Cannot use Fisher's LDA
• What to do?

But...

• When n < p, our estimate of Σ is singular
• Cannot use Fisher's LDA
• What to do?

• Manifold learning
• Spare modeling (is secretly also manifold learning)

Manifold Learning for Subsequent Inference

Limitations of existing approaches

• Manifold learing
  • is typically unsupervised
  • out of sample embedding is icky
  • do not scale to terabytes (often require n³ operations)
  • who says directions of variance are near directions of discrimination?

Limitations of existing approaches

• Manifold learing
  • is typically unsupervised
  • out of sample embedding is icky
  • do not scale to terabytes (often require n³ operations)
  • who says directions of variance are near directions of discrimination?

• Sparse modeling (is supervised, but...)
  • NP-hard (feature screening), or
  • approximations do not scale to terabytes (Lasso), or
  • non-convex (Dictionary learning),
  • with icky hyperparameters (elastic net & dictionary learning)

Linear Projections

• PCA: eig({x_i - μ})
• PCA': eig({x_i - μ_j})
• LOL: [δ, eig({x_i - μ_j})]

"Linear Optimal Low-Rank"

Linear Projections

• PCA: eig({x_i - μ})
• PCA': eig({x_i - μ_j})
• LOL: [δ, eig({x_i - μ_j})]

"Linear Optimal Low-Rank"

Notes

• Fisher's LDA uses δ and {x_i - μ_j}
• PCA' removes δ
• PCA kind of accidentally includes δ, Σ + π(1-π) δ δ', but weights it suboptimally
• LOL uses both terms explicitly, weighting δ more
• For each we compose with LDA on low-d estimates

LOL Gaussian Intuition

LOL > PCA Theory

Unpacking the theory: Chernoff Information

• C(F,G) = sup _t [ -log ∫ f^t(x) g^1-t(x) dx], for 0 < t < 1
• the exponential rate at which the Bayes error decreases
• it is the tightest possible bound on performance
• if F=N(μ₀,Σ₀) and G=N(μ₁,Σ₁)
• C(F,G)= 0.5 sup_t t(1-t) δ' Σ^-1 δ + log |Σ_t| / (|Σ₀|^t |Σ₁|^1-t)

Unpacking the theory: Chernoff Information

• C(F,G) = sup _t [ -log ∫ f^t(x) g^1-t(x) dx], for 0 < t < 1
• the exponential rate at which the Bayes error decreases
• it is the tightest possible bound on performance
• if F=N(μ₀,Σ₀) and G=N(μ₁,Σ₁)
• C(F,G)= 0.5 sup_t t(1-t) δ' Σ^-1 δ + log |Σ_t| / (|Σ₀|^t |Σ₁|^1-t)

Chernoff on Projected Data

• let F & G be Gaussian with same covariance (LDA model)
• let A be any linear transformation
• C(F^A, G^A) = 1/8 * || P_Z Σ^-1/2 δ ||_F²
• P_Z = Z (Z' Z)^-1 Z', and Z = Σ^1/2A'
• let C^A := C(F^A, G^A)

"Thm A: LOL > PCA'"

• let F & G be Gaussian with same covariance
• C^LOL ≥ C^PCA'
• inequality is strict whenever δ' (I - U_dU_d' ) δ ≥ 0.

"Thm B: LOL > PCA"

• C^PCA = 4K / (4 - K), where
• K = δ' Σ^t_d δ
• so when δ is in the space spanned by the smaller eigenvectors, PCA discards nearly all the info

"Thm B: LOL > PCA"

• C^PCA = 4K / (4 - K), where
• K = δ' Σ^t_d δ
• so when δ is in the space spanned by the smaller eigenvectors, PCA discards nearly all the info

Simple Example

• if Σ is diagonal with decreasing λ's,
• δ=(0,...,0,s),
• λ_p + s²/4 < λ_d
• C^PCA = 0
• C^LOL = s² / λ_p

"Thm C: [δ, U_d] > U_d"

• let U_d be any matrix in R^{p x d} with U_d U_d' = I
• arthimetic is messier
• nearly the same result as PCA
• basically, when δ and U_d are nearly orthogonal, adding delta helps

"Thm D: LOL > PCA as p increases"

• let γ = λ_d - λ_d+1
• let δ be sparse with probabilty ε an element is 0,
• o.w. it is Gaussian
• let p(1-ε) → θ
• then with probability at least ε^d, C^PCA = 0 < C^LOL
• and this probability can be made arbitrarily close to 1

"Thm E: LOL > PCA as n & p increases"

• when n/p → 0, all results trivially hold

• Suppose Σ is low rank + σ²I
• Suppose that: M log p ≤ log n ≤ M' log λ,
• provided M & M' are large enough
• estimates of C converge, so
• E [ C^LOL ] > E[ C^PCA]

LOL > PCA Simulations

LOL is fast

• utilize FlashX semi-external memory (SEM) computing
• optimal (linear) scale up and out
• SEM speed ≈ internal memory speed
• swap random projections (RP) with SVD for 10x speed improvement
• RP error rate ≈ SVD error rate
• ~3 minutes for a 2 terabyte dataset

LOL > PCA Data

LOL Hypothesis Testing & Regression

Discussion

• simple supervised inference for wide data
• big data tools (eg, Spark, H20, VW) typically focus on large n
• algorithmic and theoretical generalizations straightforward
• open source implementations