Description

7. Statistical estimation
• maximum likelihood estimation
• optimal detector design
• experiment design
Parametric distribution estimation
• distribution estimation problem: estimate probability density p(y) of a random variable from observed values
• parametric distribution estimation: choose from a family of densities px(y), indexed by a parameter x maximum likelihood estimation
maximize (over x) logpx(y)
• y is observed value
• l(x) = logpx(y) is called log-likelihood function
• can add constraints x ∈ C explicitly, or define px(y) = 0 for x 6∈ C
• a convex optimization problem if logpx(y) is concave in x for fixed y
Linear measurements with IID noise
linear measurement model

• x ∈ Rn is vector of unknown parameters
• vi is IID measurement noise, with density p(z)
• yi is measurement: y ∈ Rm has density
maximum likelihood estimate: any solution x of
maximize
(y is observed value)
examples
• Gaussian noise N(0,σ2): p(z) = (2πσ2)−1/2e−z2/(2σ2),

ML estimate is LS solution
• Laplacian noise: p(z) = (1/(2a))e−|z|/a,

ML estimate is ℓ1-norm solution
• uniform noise on [−a,a]:

ML estimate is any x with
Logistic regression
random variable y ∈ {0,1} with distribution
p = prob
• a, b are parameters; u ∈ Rn are (observable) explanatory variables
• estimation problem: estimate a, b from m observations (ui,yi) log-likelihood function (for y1 = ··· = yk = 1, yk+1 = ··· = ym = 0):

concave in a, b
example (n = 1, m = 50 measurements)

• circles show 50 points (ui,yi)
• solid curve is ML estimate of p = exp(au + b)/(1 + exp(au + b))
(Binary) hypothesis testing
detection (hypothesis testing) problem given observation of a random variable X ∈ {1,…,n}, choose between:
• hypothesis 1: X was generated by distribution p = (p1,…,pn)
• hypothesis 2: X was generated by distribution q = (q1,…,qn)
randomized detector
• a nonnegative matrix T ∈ R2×n, with 1TT = 1T
• if we observe X = k, we choose hypothesis 1 with probability t1k, hypothesis 2 with probability t2k
• if all elements of T are 0 or 1, it is called a deterministic detector detection probability matrix:

• Pfp is probability of selecting hypothesis 2 if X is generated by distribution 1 (false positive)
• Pfn is probability of selecting hypothesis 1 if X is generated by distribution 2 (false negative) multicriterion formulation of detector design
minimize (w.r.t. R
subject to t1k + t2k = 1, k = 1,…,n
tik ≥ 0, i = 1,2, k = 1,…,n
variable T ∈ R2×n
scalarization (with weight λ > 0)
minimize (Tp)2 + λ(Tq)1
subject to t1k + t2k = 1, tik ≥ 0, i = 1,2, k = 1,…,n
an LP with a simple analytical solution

• a deterministic detector, given by a likelihood ratio test
• if pk = λqk for some k, any value 0 ≤ t1k ≤ 1, t1k = 1 − t2k is optimal
(i.e., Pareto-optimal detectors include non-deterministic detectors) minimax detector
minimize max{Pfp,Pfn} = max{(Tp)2,(Tq)1} subject to t1k + t2k = 1, tik ≥ 0, i = 1,2, k = 1,…,n
an LP; solution is usually not deterministic
example
0.70 0.10
 0.20 0.10
P =
 0.05 0.70
0.05 0.10

solutions 1, 2, 3 (and endpoints) are deterministic; 4 is minimax detector
Experiment design
m linear measurements of unknown x ∈ Rn
• measurement errors wi are IID N(0,1)
• ML (least-squares) estimate is

• error e = xˆ − x has zero mean and covariance

confidence ellipsoids are given by {x | (x − xˆ)TE−1(x − xˆ) ≤ β}
experiment design: choose ai ∈ {v1,…,vp} (a set of possible test vectors) to make E ‘small’
vector optimization formulation
minimize (w.r.t. S
subject to mk ≥ 0, m1 + ··· + mp = m mk ∈ Z
• variables are mk (# vectors ai equal to vk)
assume m ≫ p, use λk = mk/m as (continuous) real variable
minimize (w.r.t. S subject to
• common scalarizations: minimize logdetE, trE, λmax(E), . . .
• can add other convex constraints, e.g., bound experiment cost cTλ ≤ B D-optimal design
minimize subject to
interpretation: minimizes volume of confidence ellipsoids
dual problem
maximize logdetW + nlogn subject to
interpretation: {x | xTWx ≤ 1} is minimum volume ellipsoid centered at origin, that includes all test vectors vk
complementary slackness: for λ, W primal and dual optimal

optimal experiment uses vectors vk on boundary of ellipsoid defined by W
λ2 =0.5
design uses two vectors, on boundary of ellipse defined by optimal W
derivation of dual of page 1–13
first reformulate primal problem with new variable X:
minimize logdetX−1
subject to

• minimize over X by setting gradient to zero: −X−1 + Z = 0
• minimum over λk is −∞ unless dual problem
maximize n + logdetZ − ν
subject to
change variable W = Z/ν, and optimize over ν to get dual of page 1–13