University:
University of Michigan
Course:
STATS 250 | Introduction to Statistics and Data Analysis
Academic year:

2022
Views:

339

Pages:

20
Author:

Tatum B

Surrogate loss functions, divergences and decentralized detection 1 Talk outline • nonparametric decentralized detection algorithm – use of surrogate loss functions and marginalized kernels – use of convex analysis • study of surrogate loss functions and divergence functionals – correspondence of losses and divergences – M-estimator of divergences (e.g., Kullback-Leibler divergence) 2 Decentralized decision-making problem learning both classifier and experiment • covariate vector X and hypothesis (label) Y = ±1 • we do not have access directly to X in order to determine Y • learn jointly the mapping (Q, γ) Q γ X −→ Z −→ Y 3 Decentralized decision-making problem learning both classifier and experiment • covariate vector X and hypothesis (label) Y = ±1 • we do not have access directly to X in order to determine Y • learn jointly the mapping (Q, γ) Q γ X −→ Z −→ Y • roles of “experiment” Q: – due to data collection constraints (e.g., decentralization) – data transmission constraints – choice of variates (feature selection) – dimensionality reduction scheme 3-a A decentralized detection system ... Sensors Communication channel Fusion center Decision rule • Decentralized setting: Communication constraints between sensors and fusion center (e.g., bit constraints) • Goal: Design decision rules for sensors and fusion center • Criterion: Minimize probability of incorrect detection 4 Concrete example – wireless sensor network Light source ... ... ... ... sensors Set-up: • wireless network of tiny sensor motes, each equiped with light/ humidity/ temperature sensing capabilities • measurement of signal strength ([0–1024] in magnitude, or 10 bits) Goal: is there a forest fire in a certain region? 5 Related work • Classical work on classification/detection: – completely centralized – no consideration of communication-theoretic infrastructure 6 Related work • Classical work on classification/detection: – completely centralized – no consideration of communication-theoretic infrastructure • Decentralized detection in signal processing (e.g., Tsitsiklis, 1993) – joint distribution assumed to be known – locally-optimal rules under conditional independence assumptions (i.e., Naive Bayes) 6-a Overview of our approach • Treat as a nonparametric estimation (learning) problem – under constraints from a distributed system • Use kernel methods and convex surrogate loss functions – tools from convex optimization to derive an efficient algorithm 7 Problem set-up Y ∈ {±1} X1 γ1 X2 γ2 X3 γ3 . . .X S . . . γS X ∈ {1, . . . , M }S Z1 Z2 Z3 . . .Z S Z ∈ {1, . . . , L}S ; L ¿ M γ(Z 1 , . . . , Z S ) Problem: Given training data (xi , yi )ni=1 , find the decision rules (γ 1 , . . . , γ s ; γ) so as to minimize the detection error probability: P (Y 6= γ(Z 1 , . . . , Z s )). 8 Kernel methods for classification • Classification: Learn γ(z) that predicts label y • K(z, z 0 ) is a symmetric positive semidefinite kernel function • feature space H in which K acts as an inner product, i.e., K(z, z 0 ) = hΨ(z), Ψ(z 0 )i • Kernel-based algorithm finds linear function in H, i.e. γ(z) = hw, Ψ(z)i = n X αi K(zi , z) i=1 • Advantages: – kernel function classes are sufficiently rich for many applications – optimizing over kernel function classes is computionally efficient 9 Convex surrogate loss function φ to 0-1 loss 3 Zero−one Hinge Logistic Exponential Surrogate loss 2.5 2 1.5 1 0.5 0 −1 −0.5 0 0.5 Margin value 1 1.5 2 • minimizing (regularized) empirical φ-risk Êφ(Y γ(Z)): n X λ φ(yi γ(zi )) + kγk2 , min γ∈H 2 i=1 • (zi , yi )ni=1 are training data in Z × {±1} • φ is a convex loss function (surrogate to non-convex 0-1 loss) 10 Stochastic decision rules at each sensor Y X1 X2 X3 . . .X S ... Z1 Z2 Z3 Q(Z|X) . . .Z S Kz (z, z 0 ) = hΨ(z), Ψ(z 0 )i γ(Z) γ(z) = hw, Ψ(z)i • Approximate deterministic sensor decisions by stochastic rules Q(Z|X) • Sensors do not communicate directly =⇒ factorization: QS Q(Z|X) = t=1 Qt (Z t |X t )  Q = Q Qt , • The overall decision rule is represented by γ(z) = hw, Ψ(z)i 11 High-level strategy: Joint optimization • Minimize over (Q, γ) an empirical version of Eφ(Y γ(Z)) • Joint minimization: – fix Q, optimize over γ: A simple convex problem – fix γ, perform a gradient update for Q, sensor by sensor 12 Approximating empirical φ-risk • The regularized empirical φ-risk Êφ(Y γ(Z)) has the form: G0 = n XX z λ φ(yi γ(z))Q(z|xi ) + ||w||2 2 i=1 • Challenge: even evaluating G0 at a single point is intractable Requires summing over LS possible values for z • Idea: – approximate G0 by another objective function G – G is φ-risk of a “marginalized” feature space – G0 ≡ G for deterministic Q 13 “Marginalizing” over feature space z2 x2 γ(z) = hw, Ψ(z)i fQ (x) = hw, ΨQ (x)i Q(z | x) z1 x1 Quantized: Z−space Original: X −space Stochastic decision rule Q(z | x): • maps between X and Z • induces marginalized feature map ΨQ from base map Ψ (or marginalized kernel KQ from base kernel K) 14 Marginalized feature space {ΨQ (x)} 15 Marginalized feature space {ΨQ (x)} • Define a new feature space ΨQ (x) and a linear function over ΨQ (x):  Ψ (x) = P Q(z|x)Ψ(z) ⇐= Marginalization over z Q z fQ (x) = hw, ΨQ (x)i 15-a Marginalized feature space {ΨQ (x)} • Define a new feature space ΨQ (x) and a linear function over ΨQ (x):  Ψ (x) = P Q(z|x)Ψ(z) ⇐= Marginalization over z Q z fQ (x) = hw, ΨQ (x)i • The alternative objective function G is the φ-risk for fQ : G= n X φ(yi fQ (xi )) + i=1 15-b λ kwk2 2 Marginalized feature space {ΨQ (x)} • Define a new feature space ΨQ (x) and a linear function over ΨQ (x):  Ψ (x) = P Q(z|x)Ψ(z) ⇐= Marginalization over z Q z fQ (x) = hw, ΨQ (x)i • The alternative objective function G is the φ-risk for fQ : G= n X φ(yi fQ (xi )) + i=1 λ kwk2 2 • ΨQ (x) induces a marginalized kernel over X : X 0 0 Q(z|x)Q(z 0 |x0 ) Kz (z, z 0 ) KQ (x, x ) := hΨQ (x), ΨQ (x )i = z,z 0 ⇒ Marginalization taken over message z conditioned on sensor signal x 15-c

Surrogate Loss Functions, Divergences and Decentralized Detection

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock