nips nips2012 nips2012-206 knowledge-graph by maker-knowledge-mining

206 nips-2012-Majorization for CRFs and Latent Likelihoods

Source: pdf

Author: Tony Jebara, Anna Choromanska

Abstract: The partition function plays a key role in probabilistic modeling including conditional random ﬁelds, graphical models, and maximum likelihood estimation. To optimize partition functions, this article introduces a quadratic variational upper bound. This inequality facilitates majorization methods: optimization of complicated functions through the iterative solution of simpler sub-problems. Such bounds remain efﬁcient to compute even when the partition function involves a graphical model (with small tree-width) or in latent likelihood settings. For large-scale problems, low-rank versions of the bound are provided and outperform LBFGS as well as ﬁrst-order methods. Several learning applications are shown and reduce to fast and convergent update rules. Experimental results show advantages over state-of-the-art optimization methods. This supplement presents additional details in support of the full article. These include the application of the majorization method to maximum entropy problems. It also contains proofs of the various theorems, in particular, a guarantee that the bound majorizes the partition function. In addition, a proof is provided guaranteeing convergence on (non-latent) maximum conditional likelihood problems. The supplement also contains supporting lemmas that show the bound remains applicable in constrained optimization problems. The supplement then proves the soundness of the junction tree implementation of the bound for graphical models with large n. It also proves the soundness of the low-rank implementation of the bound for problems with large d. Finally, the supplement contains additional experiments and ﬁgures to provide further empirical support for the majorization methodology. Supplement for Section 2 Proof of Theorem 1 Rewrite the partition function as a sum over the integer index j = 1, . . . , n under the random ordering π : Ω → {1, . . . , n}. This deﬁnes j∑ π(y) and associates h and f with = n hj = h(π −1 (j)) and fj = f (π −1 (j)). Next, write Z(θ) = j=1 αj exp(λ⊤ fj ) by introducing ˜ ˜ λ = θ − θ and αj = hj exp(θ ⊤ fj ). Deﬁne the partition function over only the ﬁrst i components ∑i as Zi (θ) = j=1 αj exp(λ⊤ fj ). When i = 0, a trivial quadratic upper bound holds ( ) Z0 (θ) ≤ z0 exp 1 λ⊤ Σ0 λ + λ⊤ µ0 2 with the parameters z0 → 0+ , µ0 = 0, and Σ0 = z0 I. Next, add one term to the current partition function Z1 (θ) = Z0 (θ) + α1 exp(λ⊤ f1 ). Apply the current bound Z0 (θ) to obtain 1 Z1 (θ) ≤ z0 exp( 2 λ⊤ Σ0 λ + λ⊤ µ0 ) + α1 exp(λ⊤ f1 ). Consider the following change of variables u γ 1/2 −1/2 = Σ0 λ − Σ0 = α1 z0 exp( 1 (f1 2 (f1 − µ0 )) − µ0 )⊤ Σ−1 (f1 − µ0 )) 0 and rewrite the logarithm of the bound as log Z1 (θ) ( ) 1 ≤ log z0 − 1 (f1 − µ0 )⊤ Σ−1 (f1 − µ0 ) + λ⊤ f1 + log exp( 2 ∥u∥2 ) + γ . 0 2 Apply Lemma 1 (cf. [32] p. 100) to the last term to get ( (1 ) ) log Z1 (θ) ≤ log z0 − 1 (f1 − µ0 )⊤ Σ−1 (f1 − µ0 ) + λ⊤ f1 + log exp 2 ∥v∥2 +γ 0 2 ( ) v⊤ (u − v) 1 + + (u − v)⊤ I + Γvv⊤ (u − v) 1+γ exp(− 1 ∥v∥2 ) 2 2 10 where Γ = 1 1 tanh( 2 log(γ exp(− 2 ∥v∥2 ))) . 1 2 log(γ exp(− 2 ∥v∥2 )) The bound in [32] is tight when u = v. To achieve tightness −1/2 ˜ when θ = θ or, equivalently, λ = 0, we choose v = Σ0 (µ0 − f1 ) yielding ( ) Z1 (θ) ≤ z1 exp 1 λ⊤ Σ1 λ + λ⊤ µ1 2 where we have z1 = z0 + α1 z0 α1 = µ0 + f1 z0 + α1 z0 + α1 1 tanh( 2 log(α1 /z0 )) = Σ0 + (µ0 − f1 )(µ0 − f1 )⊤ . 2 log(α1 /z0 ) µ1 Σ1 This rule updates the bound parameters z0 , µ0 , Σ0 to incorporate an extra term in the sum over i in Z(θ). The process is iterated n times (replacing 1 with i and 0 with i − 1) to produce an overall bound on all terms. Lemma 1 (See [32] p. 100) ( ( ) ) For all u ∈ Rd , any v ∈ Rd and any γ ≥ 0, the bound log exp 1 ∥u∥2 + γ ≤ 2 ( ( ) ) log exp 1 ∥v∥2 + γ + 2 ( ) v⊤ (u − v) 1 + (u − v)⊤ I + Γvv⊤ (u − v) 1 1 + γ exp(− 2 ∥v∥2 ) 2 holds when the scalar term Γ = 1 tanh( 2 log(γ exp(−∥v∥2 /2))) . 2 log(γ exp(−∥v∥2 /2)) Equality is achieved when u = v. Proof of Lemma 1 The proof is provided in [32]. Supplement for Section 3 Maximum entropy problem We show here that partition functions arise naturally in maximum ∑ p(y) entropy estimation or minimum relative entropy RE(p∥h) = y p(y) log h(y) estimation. Consider the following problem: ∑ ∑ min RE(p∥h) s.t. p(y)f (y) = 0, p(y)g(y) ≥ 0. p y y d′ Here, assume that f : Ω → R and g : Ω → R are arbitrary (non-constant) vector-valued functions ( ) over the sample space. The solution distribution p(y) = h(y) exp θ ⊤ f (y) + ϑ⊤ g(y) /Z(θ, ϑ) is recovered by the dual optimization ∑ ( ) arg θ, ϑ = max − log h(y) exp θ ⊤ f (y) + ϑ⊤ g(y) d ϑ≥0,θ y ′ where θ ∈ Rd and ϑ ∈ Rd . These are obtained by minimizing Z(θ, ϑ) or equivalently by maximizing its negative logarithm. Algorithm 1 permits variational maximization of the dual via the quadratic program min 1 (β ϑ≥0,θ 2 ˜ ˜ − β)⊤ Σ(β − β) + β ⊤ µ ′ where β ⊤ = [θ ⊤ ϑ⊤ ]. Note that any general convex hull of constraints β ∈ Λ ⊆ Rd+d could be imposed without loss of generality. Proof of Theorem 2 We begin by proving a lemma that will be useful later. Lemma 2 If κΨ ≽ Φ ≻ 0 for Φ, Ψ ∈ Rd×d , then 1 ˜ ˜ ˜ L(θ) = − 2 (θ − θ)⊤ Φ(θ − θ) − (θ − θ)⊤ µ ˜ ˜ ˜ U (θ) = − 1 (θ − θ)⊤ Ψ(θ − θ) − (θ − θ)⊤ µ 2 satisfy supθ∈Λ L(θ) ≥ 1 κ ˜ supθ∈Λ U (θ) for any convex Λ ⊆ Rd , θ ∈ Λ, µ ∈ Rd and κ ∈ R+ . 11 Proof of Lemma 2 Deﬁne the primal problems of interest as PL = supθ∈Λ L(θ) and PU = supθ∈Λ U (θ). The constraints θ ∈ Λ can be summarized by a set of linear inequalities Aθ ≤ b where A ∈ Rk×d and b ∈ Rk for some (possibly inﬁnite) k ∈ Z. Apply the change of variables ˜ ˜ ˜ ˜ ˜ ˜ z = θ− θ. The constraint A(z+ θ) ≤ b simpliﬁes into Az ≤ b where b = b−Aθ. Since θ ∈ Λ, it 1 ⊤ ˜ ≥ 0. We obtain the equivalent primal problems PL = sup is easy to show that b ˜ − z Φz − Az≤b z⊤ µ and PU = supAz≤b − 1 z⊤ Ψz − z⊤ µ. The corresponding dual problems are ˜ 2 2 ⊤ −1 y⊤AΦ−1A⊤y ˜ µ Φ µ +y⊤AΦ−1µ+y⊤b+ y≥0 2 2 y⊤AΨ−1 A⊤y µ⊤Ψ−1µ ˜ DU = inf +y⊤AΨ−1µ+y⊤b+ . y≥0 2 2 DL = inf ˜ Due to strong duality, PL = DL and PU = DU . Apply the inequalities Φ ≼ κΨ and y⊤ b > 0 as ⊤ −1 y⊤AΨ−1 A⊤y y⊤AΨ−1 µ κ ˜ µΨ µ + + y⊤b + PL ≥ sup − z⊤ Ψz − z⊤ µ = inf y≥0 2 2κ κ 2κ ˜ Az≤b 1 1 ≥ DU = PU . κ κ 1 This proves that PL ≥ κ PU . We will use the above to prove Theorem 2. First, we will upper-bound (in the Loewner ordering sense) the matrices Σj in Algorithm 2. Since ∥fxj (y)∥2 ≤ r for all y ∈ Ωj and since µj in Algorithm 1 is a convex combination of fxj (y), the outer-product terms in the update for Σj satisfy (fxj (y) − µ)(fxj (y) − µ)⊤ ≼ 4r2 I. Thus, Σj ≼ F(α1 , . . . , αn )4r2 I holds where α 1 F(α1 , . . . , αn ) = i n ∑ tanh( 2 log( ∑i−1 αk )) k=1 αi 2 log( ∑i−1 α ) i=2 k k=1 using the deﬁnition of α1 , . . . , αn in the proof of Theorem 1. The formula for F starts at i = 2 since z0 → 0+ . Assume permutation π is sampled uniformly at random. The expected value of F is then α π(i) 1 n 1 ∑ ∑ tanh( 2 log( ∑i−1 απ(k) )) k=1 . Eπ [F(α1 , . . . , αn )] = απ(i) n! π i=2 ) 2 log( ∑i−1 k=1 απ(k) We claim that the expectation is maximized when all αi = 1 or any positive constant. Also, F is invariant under uniform scaling of its arguments. Write the expected value of F as E for short. ∂E ∂E ∂E Next, consider ∂αl at the setting αi = 1, ∀i. Due to the expectation over π, we have ∂αl = ∂αo for any l, o. Therefore, the gradient vector is constant when all αi = 1. Since F(α1 , . . . , αn ) is invariant to scaling, the gradient vector must therefore be the all zeros vector. Thus, the point ∂ ∂E when all αi = 1 is an extremum or a saddle. Next, consider ∂αo ∂αl for any l, o. At the setting 2 ∂ ∂E αi = 1, ∂ E = −c(n) and, ∂αo ∂αl = c(n)/(n − 1) for some non-negative constant function ∂α2 l c(n). Thus, the αi = 1 extremum is locally concave and is a maximum. This establishes that Eπ [F(α1 , . . . , αn )] ≤ Eπ [F(1, . . . , 1)] and yields the Loewner bound ) ( n−1 ∑ tanh(log(i)/2) 2 I = ωI. Σj ≼ 2r log(i) i=1 Apply this bound to each Σj in the lower bound on J(θ) and also note a corresponding upper bound ∑ ˜ ˜ ˜ J(θ) ≥ J(θ)−tω+tλ ∥θ − θ∥2− (θ − θ)⊤(µj −fxj (yj )) 2 j ∑ ˜ ˜ ˜ J(θ) ≤ J(θ)−tλ ∥θ − θ∥2− (θ − θ)⊤(µj −fxj (yj )) 2 j 12 ˜ which follows from Jensen’s inequality. Deﬁne the current θ at time τ as θτ and denote by Lτ (θ) the above lower bound and by Uτ (θ) the above upper bound at time τ . Clearly, Lτ (θ) ≤ J(θ) ≤ Uτ (θ) with equality when θ = θτ . Algorithm 2 maximizes J(θ) after initializing at θ0 and performing an update by maximizing a lower bound based on Σj . Since Lτ (θ) replaces the deﬁnition of Σj with ωI ≽ Σj , Lτ (θ) is a looser bound than the one used by Algorithm 2. Thus, performing θτ +1 = arg maxθ∈Λ Lτ (θ) makes less progress than a step of Algorithm 1. Consider computing the slower update at each iteration τ and returning θτ +1 = arg maxθ∈Λ Lτ (θ). Setting Φ = (tω +tλ)I, Ψ = tλI and κ = ω+λ allows us to apply Lemma 2 as follows λ sup Lτ (θ) − Lτ (θτ ) = θ∈Λ 1 sup Uτ (θ) − Uτ (θτ ). κ θ∈Λ Since Lτ (θτ ) = J(θτ ) = Uτ (θτ ), J(θτ +1 ) ≥ supθ∈Λ Lτ (θ) and supθ∈Λ Uτ (θ) ≥ J(θ ∗ ), we obtain ( ) 1 J(θτ +1 ) − J(θ ∗ ) ≥ 1− (J(θτ ) − J(θ ∗ )) . κ Iterate the above inequality starting at t = 0 to obtain ( )τ 1 ∗ J(θτ ) − J(θ ) ≥ 1− (J(θ0 ) − J(θ ∗ )) . κ ( ) 1 τ κ A solution within a multiplicative factor of ϵ implies that ϵ = 1 − κ or log(1/ϵ) = τ log κ−1 . ⌉ ⌈ Inserting the deﬁnition for κ shows that the number of iterations τ is at most log(1/ϵ) or κ log κ−1 ⌉ ⌈ log(1/ϵ) log(1+λ/ω) . Inserting the deﬁnition for ω gives the bound. Y12,0 Y11,1 Y21,1 Y31,1 ··· 1,1 Ym1,1 Figure 3: Junction tree of depth 2. Algorithm 5 SmallJunctionTree ˜ Input Parameters θ and h(u), f (u) ∀u ∈ Y12,0 and zi , Σi , µi ∀i = 1, . . . , m1,1 + Initialize z → 0 , µ = 0, Σ = zI For each conﬁguration u ∈ Y12,0 { ∏m1,1 ∑m1,1 ∏m1,1 ˜ ˜ ˜ α = h(u)( ∑ zi exp(−θ ⊤ µi )) exp(θ ⊤ (f (u) + i=1 µi )) = h(u) exp(θ ⊤ f (u)) i=1 zi i=1 m1,1 l = f (u) + i=1 µi − µ 1 ∑m1,1 tanh( 2 log(α/z)) ⊤ Σ + = i=1 Σi + ll 2 log(α/z) α µ + = z+α l z += α } Output z, µ, Σ Supplement for Section 5 Proof of correctness for Algorithm 3 Consider a simple junction tree of depth 2 shown on Figure 3. The notation Yca,b refers to the cth tree node located at tree level a (ﬁrst level is considered as the one with∑ leaves) whose parent is the bth from the higher tree level (the root has no parent so b = 0). tree ∑ Let Y a1 ,b1 refer to the sum over all conﬁgurations of variables in Yca1 ,b1 and Y a1 ,b1 \Y a2 ,b2 1 c1 c1 c2 refers to the sum over all conﬁgurations of variables that are in Yca1 ,b1 but not in Yca2 ,b2 . Let ma,b 1 2 denote the number of children of the bth node located at tree level a + 1. For short-hand, use ψ(Y ) = h(Y ) exp(θ ⊤ f (Y )). The partition function can be expressed as: 13 Y13,0 Y12,1 ··· Y11,1 Y21,1 ··· Y22,1 1,1 Ym1,1 ··· Y11,2 Y21,2 1,2 Ym1,2 2,1 Ym2,1 1,m2,1 Y1 ··· 1,m2,1 Y2 1,m 2,1 Ym1,m2,1 Figure 4: Junction tree of depth 3. Z(θ) = ∑ 2,0 u∈Y1 ≤ ∑ 2,0 u∈Y1 = ∑  ψ(u) ∏ m1,1 i=1 [ ∏ m1,1 ψ(u) i=1 [    ∑ ψ(v) 2,0 v∈Yi1,1 \Y1 ) 1( ˜ ˜ ˜ zi exp( θ − θ)⊤ Σi (θ − θ) + (θ − θ)⊤ µi 2 ∏ ( m1,1 ⊤ h(u) exp(θ f (u)) 2,0 u∈Y1 zi exp i=1 ] 1 ˜ ˜ ˜ (θ − θ)⊤ Σi (θ − θ) + (θ − θ)⊤ µi 2 )] ∑ where the upper-bound is obtained by applying Theorem 1 to each of the terms v∈Y 1,1 \Y 2,0 ψ(v). 1 i By simply rearranging terms we get: ) ( ( [ (m1,1 )) m1,1 ∏ ∑ ∑ ˜ zi exp(−θ ⊤ µi ) exp θ ⊤ f (u) + µi h(u) Z(θ) ≤ 2,0 u∈Y1 i=1 ( exp 1 ˜ (θ − θ)⊤ 2 (m1,1 ∑ ) Σi i=1 ˜ (θ − θ) )] . i=1 One ( can prove that this ) expression can be upper-bounded by 1 ˆ ⊤ Σ(θ − θ) + (θ − θ)⊤ µ where z, Σ and µ can be computed using Algoˆ ˆ z exp 2 (θ − θ) rithm 5 (a simpliﬁcation of Algorithm 3). We will call this result Lemma A. The proof is similar to the proof of Theorem 1 so is not repeated here. Consider enlarging the tree to a depth 3 as shown on Figure 4. The partition function is now      m2,1 m1,i ∑  ∏ ∑ ∏ ∑   Z(θ) = ψ(w) . ψ(u)  ψ(v)  3,0 u∈Y1 i=1 3,0 v∈Yi2,1 \Y1 j=1 w∈Yj1,i \Yi2,1 ( )) ∏m1,i (∑ ∑ term By Lemma A we can upper bound each v∈Y 2,1 \Y 3,0 ψ(v) j=1 w∈Yj1,i \Yi2,1 ψ(w) 1 i ( ) ˆ ˆ ˆ by the expression zi exp 1 (θ − θ)⊤ Σi (θ − θ) + (θ − θ)⊤ µi . This yields 2 [ )] ( m2,1 ∑ ∏ 1 ˜ ˜ ˜ Z(θ) ≤ ψ(u) (θ − θ)⊤ Σi (θ − θ) + (θ − θ)⊤ µi . zi exp 2 3,0 i=1 u∈Y1 2,1 2,1 2,1 This process can be viewed as collapsing the sub-trees S1 , S2 , . . ., Sm2,1 to super-nodes that are represented by bound parameters, zi , Σi and µi , i = {1, 2, · · · , m2,1 }, where the sub-trees are 14 deﬁned as: 2,1 S1 = 1,1 {Y12,1 , Y11,1 , Y21,1 , Y31,1 , . . . , Ym1,1 } 2,1 S2 = 1,2 {Y22,1 , Y11,2 , Y21,2 , Y31,2 , . . . , Ym1,2 } = 2,1 {Ym2,1 , Y1 . . . 2,1 Sm2,1 1,m2,1 1,m2,1 , Y2 1,m2,1 , Y3 1,m2,1 , . . . , Ym1,m2,1 }. Notice that the obtained expression can be further upper bounded using again Lemma A (induction) ( ) ˆ ˆ ˆ yielding a bound of the form: z exp 1 (θ − θ)⊤ Σ(θ − θ) + (θ − θ)⊤ µ . 2 Finally, for a general tree, follow the same steps described above, starting from leaves and collapsing nodes to super-nodes, each represented by bound parameters. This procedure effectively yields Algorithm 3 for the junction tree under consideration. Supplement for Section 6 Proof of correctness for Algorithm 4 We begin by proving a lemma that will be useful later. Lemma 3 For all x ∈ Rd and for all l ∈ Rd , 2  d d 2 ∑ ∑ l(i)  . x(i)2 l(i)2 ≥  x(i) √∑ d l(j)2 i=1 i=1 j=1 Proof of Lemma 3 By Jensen’s inequality, 2  ( d )2 d d ∑ x(i)l(i)2 ∑ ∑ x(i)l(i)2  . √∑ x(i)2 ∑d ⇐⇒ x(i)2 l(i)2 ≥  ≥ ∑d d l(j)2 l(j)2 l(j)2 j=1 j=1 i=1 i=1 i=1 i=1 d ∑ l(i)2 j=1 Now we prove the correctness of Algorithm 4. At the ith iteration, the algorithm stores Σi using ⊤ a low-rank representation Vi Si Vi + Di where Vi ∈ Rk×d is orthonormal, Si ∈ Rk×k positive d×d semi-deﬁnite and Di ∈ R is non-negative diagonal. The diagonal terms D are initialized to tλI where λ is the regularization term. To mimic Algorithm 1 we must increment the Σ matrix by a rank one update of the form Σi = Σi−1 + ri r⊤ . By projecting ri onto each eigenvector in V, we i ∑k ⊤ can decompose it as ri = j=1 Vi−1 (j, ·)ri Vi−1 (j, ·)⊤ + g = Vi−1 Vi−1 ri + g where g is the remaining residue. Thus the update rule can be rewritten as: Σi ⊤ ⊤ ⊤ = Σi−1 + ri r⊤ = Vi−1 Si−1 Vi−1 + Di−1 + (Vi−1 Vi−1 ri + g)(Vi−1 Vi−1 ri + g)⊤ i ′ ′ ′ ⊤ ⊤ ⊤ = Vi−1 (Si−1 + Vi−1 ri r⊤ Vi−1 )Vi−1 + Di−1 + gg⊤ = Vi−1 Si−1 Vi−1 + gg⊤ + Di−1 i ′ where we deﬁne Vi−1 = Qi−1 Vi−1 and deﬁned Qi−1 in terms of the singular value decomposition, ′ ′ ⊤ Q⊤ Si−1 Qi−1 = svd(Si−1 + Vi−1 ri r⊤ Vi−1 ). Note that Si−1 is diagonal and nonnegative by i−1 i construction. The current formula for Σi shows that we have a rank (k + 1) system (plus diagonal term) which needs to be converted back to a rank k system (plus diagonal term) which we denote by ′ Σi . We have two options as follows. Case 1) Remove g from Σi to obtain ′ ′ ′ ′ ⊤ Σi = Vi−1 Si−1 Vi−1 + Di−1 = Σi − gg⊤ = Σi − cvv⊤ 1 where c = ∥g∥2 and v = ∥g∥ g. th Case 2) Remove the m (smallest) eigenvalue in S′ and its corresponding eigenvector: i−1 ′ Σi ′ ′ ′ ′ ′ ′ ⊤ = Vi−1 Si−1 Vi−1 + Di−1 + gg⊤ − S (m, m)V (m, ·)⊤ V (m, ·) = Σi − cvv⊤ ′ ′ where c = S (m, m) and v = V(m, ·) . 15 ′ Clearly, both cases can be written as an update of the form Σi = Σi + cvv⊤ where c ≥ 0 and v⊤ v = 1. We choose the case with smaller c value to minimize the change as we drop from a system of order (k + 1) to order k. Discarding the smallest singular value and its corresponding eigenvector would violate the bound. Instead, consider absorbing this term into the diagonal component to ′′ ′ preserve the bound. Formally, we look for a diagonal matrix F such that Σi = Σi + F which also ′′ maintains x⊤ Σi x ≥ x⊤ Σi x for all x ∈ Rd . Thus, we want to satisfy: ( d )2 d ∑ ∑ ⊤ ′′ ⊤ ⊤ ⊤ ⊤ x Σi x ≥ x Σi x ⇐⇒ x cvv x ≤ x Fx ⇐⇒ c x(i)v(i) ≤ x(i)2 F(i) i=1 i=1 where, for ease of notation, we take F(i) = F(i, i). ′ where w = v⊤ 1. Consider the case where v ≥ 0 though we will soon get rid of (∑ )2 ∑d d this assumption. We need an F such that i=1 x(i)2 F(i) ≥ c i=1 x(i)v(i) . Equivalently, we (∑ ) ∑d ′ 2 ′ d need i=1 x(i)2 F(i) ≥ . Deﬁne F(i) = F(i) for all i = 1, . . . , d. So, we need 2 i=1 x(i)v(i) cw cw2 (∑ ) ∑d ′ ′ ′ 2 d an F such that i=1 x(i)2 F(i) ≥ . Using Lemma 3 it is easy to show that we i=1 x(i)v(i) Deﬁne v = 1 wv ′ ′ ′ may choose F (i) = v(i) . Thus, we obtain F(i) = cw2 F(i) = cwv(i). Therefore, for all x ∈ Rd , ∑d all v ≥ 0, and for F(i) = cv(i) j=1 v(j) we have d ∑ ( x(i) F(i) ≥ c 2 i=1 d ∑ )2 x(i)v(i) . (3) i=1 To generalize the inequality to hold for all vectors v ∈ Rd with potentially negative entries, it is ∑d sufﬁcient to set F(i) = c|v(i)| j=1 |v(j)|. To verify this, consider ﬂipping the sign of any v(i). The left side of the Inequality 3 does not change. For the right side of this inequality, ﬂipping the sign of v(i) is equivalent to ﬂipping the sign of x(i) and not changing the sign of v(i). However, in this case the inequality holds as shown before (it holds for any x ∈ Rd ). Thus for all x, v ∈ Rd and ∑d for F(i) = c|v(i)| j=1 |v(j)|, Inequality 3 holds. Supplement for Section 7 Small scale experiments In additional small-scale experiments, we compared Algorithm 2 with steepest descent (SD), conjugate gradient (CG), BFGS and Newton-Raphson. Small-scale problems may be interesting in real-time learning settings, for example, when a website has to learn from a user’s uploaded labeled data in a split second to perform real-time retrieval. We considered logistic regression on ﬁve UCI data sets where missing values were handled via mean-imputation. A range of regularization settings λ ∈ {100 , 102 , 104 } was explored and all algorithms were initialized from the same ten random start-points. Table 3 shows the average number of seconds each algorithm needed to achieve the same solution that BFGS converged to (all algorithms achieve the same solution due to concavity). The bound is the fastest algorithm as indicated in bold. data|λ BFGS SD CG Newton Bound a|100 1.90 1.74 0.78 0.31 0.01 a|102 0.89 0.92 0.83 0.25 0.01 a|104 2.45 1.60 0.85 0.22 0.01 b|100 3.14 2.18 0.70 0.43 0.07 b|102 2.00 6.17 0.67 0.37 0.04 b|104 1.60 5.83 0.83 0.35 0.04 c|100 4.09 1.92 0.65 0.39 0.07 c|102 1.03 0.64 0.64 0.34 0.02 c|104 1.90 0.56 0.72 0.32 0.02 d|100 5.62 12.04 1.36 0.92 0.16 d|102 2.88 1.27 1.21 0.63 0.09 d|104 3.28 1.94 1.23 0.60 0.07 e|100 2.63 2.68 0.48 0.35 0.03 e|102 2.01 2.49 0.55 0.26 0.03 e|104 1.49 1.54 0.43 0.20 0.03 Table 3: Convergence time in seconds under various regularization levels for a) Bupa (t = 345, dim = 7), b) Wine (t = 178, dim = 14), c) Heart (t = 187, dim = 23), d) Ion (t = 351, dim = 34), and e) Hepatitis (t = 155, dim = 20) data sets. Inﬂuence of rank k on bound performance in large scale experiments We also examined the inﬂuence of k on bound performance and compared it with LBFGS, SD and CG. Several choices 16 of k were explored. Table 4 shows results for the SRBCT data-set. In general, the bound performs best but slows down for superﬂuously large values of k. Steepest descent and conjugate gradient are slow yet obviously do not vary with k. Note that each iteration takes less time with smaller k for the bound. However, we are reporting overall runtime which is also a function of the number of iterations. Therefore, total runtime (a function of both) may not always decrease/increase with k. k LBFGS SD CG Bound 1 1.37 8.80 4.39 0.56 2 1.32 8.80 4.39 0.56 4 1.39 8.80 4.39 0.67 8 1.35 8.80 4.39 0.96 16 1.46 8.80 4.39 1.34 32 1.40 8.80 4.39 2.11 64 1.54 8.80 4.39 4.57 Table 4: Convergence time in seconds as a function of k. Additional latent-likelihood results For completeness, Figure 5 depicts two additional data-sets to complement Figure 2. Similarly, Table 5 shows all experimental settings explored in order to provide the summary Table 2 in the main article. bupa wine −19 0 −5 −log(J(θ)) −log(J(θ)) −20 −21 −22 Bound Newton BFGS Conjugate gradient Steepest descent −15 −23 −24 −5 −10 0 5 log(Time) [sec] 10 −20 −4 −2 0 2 4 log(Time) [sec] 6 8 Figure 5: Convergence of test latent log-likelihood for bupa and wine data-sets. Data-set Algorithm BFGS SD CG Newton Bound ion m=1 m=2m=3m=4 -4.96 -5.55 -5.88 -5.79 -11.80 -9.92 -5.56 -8.59 -5.47 -5.81 -5.57 -5.22 -5.95 -5.95 -5.95 -5.95 -6.08 -4.84 -4.18 -5.17 Data-set Algorithm BFGS SD CG Newton Bound bupa m=1 m=2 m=3 m=4 -22.07 -21.78 -21.92 -21.87 -21.76 -21.74 -21.73 -21.83 -21.81 -21.81 -21.81 -21.81 -21.85 -21.85 -21.85 -21.85 -21.85 -19.95 -20.01 -19.97 wine m=1m=2m=3m=4 -0.90 -0.91 -1.79 -1.35 -1.61 -1.60 -1.37 -1.63 -0.51 -0.78 -0.95 -0.51 -0.71 -0.71 -0.71 -0.71 -0.51 -0.51 -0.48 -0.51 hepatitis m=1m=2m=3m=4 -4.42 -5.28 -4.95 -4.93 -4.93 -5.14 -5.01 -5.20 -4.84 -4.84 -4.84 -4.84 -5.50 -5.50 -5.50 -4.50 -5.47 -4.40 -4.75 -4.92 SRBCT m=1m=2m=3m=4 -5.99 -6.17 -6.09 -6.06 -5.61 -5.62 -5.62 -5.61 -5.62 -5.49 -5.36 -5.76 -5.54 -5.54 -5.54 -5.54 -5.31 -5.31 -4.90 -0.11 Table 5: Test latent log-likelihood at convergence for different values of m ∈ {1, 2, 3, 4} on ion, bupa, hepatitis, wine and SRBCT data-sets. 17

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract The partition function plays a key role in probabilistic modeling including conditional random ﬁelds, graphical models, and maximum likelihood estimation. [sent-4, score-0.327]

2 To optimize partition functions, this article introduces a quadratic variational upper bound. [sent-5, score-0.221]

3 This inequality facilitates majorization methods: optimization of complicated functions through the iterative solution of simpler sub-problems. [sent-6, score-0.28]

4 Such bounds remain efﬁcient to compute even when the partition function involves a graphical model (with small tree-width) or in latent likelihood settings. [sent-7, score-0.295]

5 For large-scale problems, low-rank versions of the bound are provided and outperform LBFGS as well as ﬁrst-order methods. [sent-8, score-0.152]

6 Estimation often requires minimizing the partition function as is the case in conditional random ﬁelds (CRFs) and log-linear models [1, 2]. [sent-12, score-0.206]

7 This article revisits majorization and repairs its slow convergence by proposing a tighter bound on the log-partition function. [sent-15, score-0.421]

8 The improved majorization outperforms state-of-the-art optimization tools and admits multiple versatile extensions. [sent-16, score-0.205]

9 A tighter bound provides convergent monotonic minimization while outperforming ﬁrst- and second-order methods in practice1 . [sent-19, score-0.192]

10 The bound applies to graphical models [18], latent variable situations [17, 19, 20, 21] as well as high-dimensional settings [10]. [sent-20, score-0.283]

11 Section 2 presents the bound and Section 3 uses it for majorization in CRFs. [sent-23, score-0.357]

12 The bound is extended to graphical models in Section 5 and high dimensional problems in Section 6. [sent-25, score-0.217]

13 This article contributes an analogous quadratic upper-bound on the partition function. [sent-37, score-0.221]

14 Proof 1 (Sketch, See Supplement for Formal Proof) Recall the bound log(eθ + e−θ ) ≤ cθ2 [22]. [sent-47, score-0.152]

15 Tilt the bound to handle log(h1 eθ f1 + h2 eθ f2 ). [sent-49, score-0.152]

16 The bound improves previous inequalities and its proof is in the Supplement. [sent-52, score-0.199]

17 It tightens [4, 19] since it avoids wasteful curvature tests (it uses duality theory to compare the bound and the optimized function rather than compare their Hessians). [sent-53, score-0.152]

18 The bound is computed using Algorithm 1 by iterating over the y variables (“for each y ∈ Ω”) according to an arbitrary ordering via the bijective function π : Ω → {1, . [sent-55, score-0.152]

19 Algorithm 1 replaces a sum of log-linear models with a single log-quadratic model which makes monotonic majorization straightforward. [sent-62, score-0.245]

20 The ﬁgure inside Algorithm 1 depicts the bound on ˜ log Z(θ) for various choices of θ. [sent-63, score-0.26]

21 This update rule is interleaved with the bound computation. [sent-68, score-0.19]

22 3 Conditional Random Fields and Log-Linear Models The partition function arises naturally in maximum entropy estimation or minimum relative entropy estimation (cf. [sent-69, score-0.206]

23 A CRF deﬁnes a distribution over all y ∈ Ωj (of which yj is a single element) as the log-linear model p(y|xj , θ) = 1 hx (y) exp(θ ⊤ fxj (y)) Zxj (θ) j ∑ ⊤ where Zxj (θ) = y∈Ωj hxj (y) exp(θ fxj (y)). [sent-79, score-0.787]

24 For the j’th training pair, we are given a nonnegative function hxj (y) ∈ R+ and a vector-valued function fxj (y) ∈ Rd deﬁned over the domain y ∈ Ωj . [sent-80, score-0.388]

25 The parameter θ∑ CRFs is estimated by maximizing the regularized conditional for t log-likelihood4 or log-posterior: j=1 log p(yj |xj , θ) − tλ ∥θ∥2 where λ ∈ R+ is a regularizer set 2 using prior knowledge or cross-validation. [sent-83, score-0.206]

26 Rewriting gives the objective of interest J(θ) = t ∑ j=1 log hxj (yj ) + θ ⊤ fxj (yj ) − Zxj (θ) 2 tλ 2 ∥θ∥ . [sent-84, score-0.496]

27 Algorithm 2 proposes a method for maximizing the regularized conditional likelihood J(θ) or, equivalently minimizing the partition function Z(θ). [sent-86, score-0.262]

28 It solves the problem in Equation 1 subject to convex constraints by interleaving the quadratic bound with a quadratic programming procedure. [sent-87, score-0.25]

29 Algorithm 2 ConstrainedMaximization 0: Input xj , yj and functions hxj , fxj for j = 1, . [sent-89, score-0.545]

30 4 Latent Conditional Likelihood Section 3 showed how the partition function is useful for maximum conditional likelihood problems involving CRFs. [sent-98, score-0.262]

31 In this section, maximum conditional likelihood is extended to the setting where some variables are latent. [sent-99, score-0.154]

32 Therefore, we aim to estimate a conditional distribution p(y|x) from some set of hypotheses that achieves high conditional likelihood given the data-set D = {(x1 , y1 ), . [sent-113, score-0.252]

33 3 We will select this conditional distribution by assuming it emerges from a conditioned joint distribution over x and y as well as a hidden variable m which is being marginalized as p(y|x, Θ) = ∑ p(x,y,m|Θ) ∑ m . [sent-119, score-0.174]

34 The latent likelihood of the data L(Θ) = p(D|Θ) subsumes Equation 1 and is the new objective of interest t t ∏ ∑ p(xj , yj , m|Θ) ∏ ∑m L(Θ) = p(yj |xj , Θ) = . [sent-122, score-0.23]

35 (2) y,m p(xj , y, m|Θ) j=1 j=1 A good choice of the parameters is one that achieves a large conditional likelihood value (or posterior) on the data set D. [sent-123, score-0.154]

36 Next, assume that each p(x|y, m, Θ) is an exponential family distribution ( ⊤ ) p(x|y, m, Θ) = h(x) exp θy,m ϕ(x) − a(θy,m ) where each conditional is speciﬁed by a function h : Ωx → R+ and a feature mapping ϕ : Ωx → Rd which are then used to derive the normalizer a : Rd → R+ . [sent-124, score-0.237]

37 Thus, we have the complete likelihood p(x, y, m|Θ) = ( ) π ∑y,m h(x) exp θ ⊤ ϕ(x) − a(θy,m ) . [sent-129, score-0.195]

38 Apply the change of variables exp(νy,m ) = πy,m exp(−a(θy,m )) and rewrite the objective as a function5 of a vector θ: ( ) ∑ ( ⊤ ) ⊤ t t ∑ ∏ m exp θyj ,m ϕ(xj ) + νyj ,m ∏ m exp θ fj,yj ,m ( ) = ∑ ∑ L(Θ) = . [sent-131, score-0.278]

39 Apply Jensen’s inequality to lower bound each numerator term as ∑ ∑ ( ) ⊤∑ m ηj,m fj,yj ,m − m ηj,m log ηj,m exp θ ⊤ fj,yj ,m ≥ eθ m ˜⊤ where ηj,m = (eθ fj,yj ,m ∑ ∑ ˜ θ⊤ f ′ )/( m′ e j,yj ,m ). [sent-138, score-0.438]

40 y,m The overall lower bound on the likelihood is then 1 ˜ ⊤˜ ˜ ˜ ⊤˜ ˜ ˜ Q(θ, θ) = L(θ)e− 2 (θ−θ) Σ(θ−θ)−(θ−θ) µ ∑t ∑t ∑ ˜ ˜ where Σ = j=1 Σj and µ = j=1 (µj − m ηj,m fj,yj ,m ). [sent-140, score-0.208]

41 This yields an iterative scheme similar to Algorithm 2 for monotonically maximizing latent conditional likelihood. [sent-142, score-0.2]

42 2 4 that recover the bound efﬁciently for graphical models of bounded tree-width. [sent-146, score-0.217]

43 Consider a log-linear model (a function class) indexed by a parameter θ ∈ Λ in a convex hull Λ ⊆ Rd as follows ( ) 1 ∏ p(Y |θ) = hc (Yc ) exp θ ⊤ fc (Yc ) Z(θ) c∈W ( ⊤ ) where Z(θ) = Y c∈W hc (Yc ) exp θ fc (Yc ) . [sent-170, score-0.613]

44 Instead, consider a more efﬁcient surrogate algorithm which computes the same bound parameters by efﬁciently exploiting the factorization of the graphical model. [sent-174, score-0.217]

45 This is possible since exponentiated quadratics are closed under multiplication and the required bound computations distribute nicely across decomposable graphical models. [sent-175, score-0.256]

46 In Algorithm 3 (the Supplement provides a proof of its correctness), take ch(c) to be the set of children-cliques of clique c and pa(c) to be the parent of c. [sent-183, score-0.164]

47 The algorithm stores a quadratic bound for each conﬁguration of u (where u is the set of variables in common across both clique c and its parent). [sent-185, score-0.276]

48 It then forms the bound by summing over v ∈ Yc \ Ypa(c) , each conﬁguration of each variable a clique c has that is not shared with its parent clique. [sent-186, score-0.269]

49 Note that w is used to query the children b ∈ ch(c) of a clique c to report their bound parameters zb|w , µb|w , Σb|w . [sent-190, score-0.227]

50 Algorithm 3 is efﬁcient in the sense that computations involve enumerating over all conﬁgurations of each clique in the junction tree rather than over all conﬁgurations of Y . [sent-193, score-0.232]

51 Thus, in addition to the Σ matrix which represents the curvature of the bound, Algorithm 3 is recovering the partition function value z and the gradient since µ = ∂ log Z(θ) . [sent-197, score-0.216]

52 Instead, the new algorithm provides a low-rank version of the bound which still majorizes the log-partition function but re˜ quires only O(tnd) complexity (putting it on par with LBFGS). [sent-202, score-0.191]

53 Rather than increment the matrix by a rank one update of the √ tanh( 1 log(α/z)) 2 form Σi = Σi−1 + ri r⊤ where ri = (fi − µi ), simply project ri onto each i 2 log(α/z) eigenvector in V and update matrix S and V via a singular value decomposition (O(k 3 ) work). [sent-225, score-0.445]

54 After removing k such projections, the remaining residual from ri forms a new eigenvector ek+1 and its magnitude forms a new singular value. [sent-226, score-0.197]

55 7 Experiments We ﬁrst focus on the logistic regression task and compare the performance of the bound (using the low-rank Algorithm 2) with ﬁrst-order and second order methods such as LBFGS, conjugate gradient (CG) and steepest descent (SD). [sent-233, score-0.241]

56 Data-set Size Algorithm LBFGS SD CG Bound SRBCT Tumors Text SecStr n=4 n = 26 n=2 n=2 t = 83 t = 308 t = 1500 t = 83679 d = 9236 d = 390260 d = 23922 d = 632 λ = 101 λ = 101 λ = 102 λ = 101 time iter time iter time iter time iter 6. [sent-247, score-0.324]

57 97 9 CoNLL PennTree m=9 m = 45 t = 1000 t = 1000 d = 33615 d = 14175 λ = 101 λ = 101 time iter time iter 25661. [sent-263, score-0.162]

58 Data−set Bound EM 5 5 5 0 0 0 −5 −5 −5 −10 −10 −10 −15 −15 −15 −20 −20 −20 −25 −5 0 5 10 15 20 −25 25 −5 0 5 10 15 20 25 −25 −5 0 5 10 15 20 25 Figure 1: Classiﬁcation boundaries using the bound and EM for a toy latent likelihood problem. [sent-283, score-0.274]

59 We next performed experiments with maximum latent conditional likelihood problems. [sent-284, score-0.22]

60 7 We next compared the algorithms (the bound, Newton-Raphson, BFGS, CG and SD) in maximum latent conditional likelihood problems on ﬁve benchmark data-sets. [sent-294, score-0.22]

61 These included four UCI datasets6 (ion, bupa, hepatitis and wine) and the previously used SRBCT data-set. [sent-295, score-0.174]

62 Figure 2 depicts the convergence on ion, hepatitis and SRBCT data sets. [sent-302, score-0.174]

63 18 bupa hepatitis wine SRBCT m=2 m=2 m=3 m=4 -21. [sent-308, score-0.433]

64 8 Discussion A simple quadratic upper bound for the partition function of log-linear models was proposed and makes majorization approaches competitive with state-of-the-art ﬁrst- and second-order optimization methods. [sent-330, score-0.514]

65 The bound is efﬁciently recoverable for graphical models and admits low-rank variants for high-dimensional data. [sent-331, score-0.217]

66 It allows faster and monotonically convergent majorization in CRF learning and maximum latent conditional likelihood problems (where it also ﬁnds better local maxima). [sent-332, score-0.425]

67 Future work will explore intractable partition functions where likelihood evaluation is hard but bound maximization may remain feasible. [sent-333, score-0.316]

68 Furthermore, the majorization approach will be applied in stochastic [31] and distributed optimization settings. [sent-334, score-0.205]

69 These include the application of the majorization method to maximum entropy problems. [sent-531, score-0.254]

70 It also contains proofs of the various theorems, in particular, a guarantee that the bound majorizes the partition function. [sent-532, score-0.299]

71 In addition, a proof is provided guaranteeing convergence on (non-latent) maximum conditional likelihood problems. [sent-533, score-0.201]

72 The supplement also contains supporting lemmas that show the bound remains applicable in constrained optimization problems. [sent-534, score-0.283]

73 The supplement then proves the soundness of the junction tree implementation of the bound for graphical models with large n. [sent-535, score-0.544]

74 It also proves the soundness of the low-rank implementation of the bound for problems with large d. [sent-536, score-0.191]

75 Finally, the supplement contains additional experiments and ﬁgures to provide further empirical support for the majorization methodology. [sent-537, score-0.336]

76 Deﬁne the partition function over only the ﬁrst i components ∑i as Zi (θ) = j=1 αj exp(λ⊤ fj ). [sent-547, score-0.162]

77 When i = 0, a trivial quadratic upper bound holds ( ) Z0 (θ) ≤ z0 exp 1 λ⊤ Σ0 λ + λ⊤ µ0 2 with the parameters z0 → 0+ , µ0 = 0, and Σ0 = z0 I. [sent-548, score-0.34]

78 Consider the following change of variables u γ 1/2 −1/2 = Σ0 λ − Σ0 = α1 z0 exp( 1 (f1 2 (f1 − µ0 )) − µ0 )⊤ Σ−1 (f1 − µ0 )) 0 and rewrite the logarithm of the bound as log Z1 (θ) ( ) 1 ≤ log z0 − 1 (f1 − µ0 )⊤ Σ−1 (f1 − µ0 ) + λ⊤ f1 + log exp( 2 ∥u∥2 ) + γ . [sent-551, score-0.476]

79 100) to the last term to get ( (1 ) ) log Z1 (θ) ≤ log z0 − 1 (f1 − µ0 )⊤ Σ−1 (f1 − µ0 ) + λ⊤ f1 + log exp 2 ∥v∥2 +γ 0 2 ( ) v⊤ (u − v) 1 + + (u − v)⊤ I + Γvv⊤ (u − v) 1+γ exp(− 1 ∥v∥2 ) 2 2 10 where Γ = 1 1 tanh( 2 log(γ exp(− 2 ∥v∥2 ))) . [sent-554, score-0.463]

80 100) ( ( ) ) For all u ∈ Rd , any v ∈ Rd and any γ ≥ 0, the bound log exp 1 ∥u∥2 + γ ≤ 2 ( ( ) ) log exp 1 ∥v∥2 + γ + 2 ( ) v⊤ (u − v) 1 + (u − v)⊤ I + Γvv⊤ (u − v) 1 1 + γ exp(− 2 ∥v∥2 ) 2 holds when the scalar term Γ = 1 tanh( 2 log(γ exp(−∥v∥2 /2))) . [sent-560, score-0.646]

81 Supplement for Section 3 Maximum entropy problem We show here that partition functions arise naturally in maximum ∑ p(y) entropy estimation or minimum relative entropy RE(p∥h) = y p(y) log h(y) estimation. [sent-563, score-0.363]

82 The solution distribution p(y) = h(y) exp θ ⊤ f (y) + ϑ⊤ g(y) /Z(θ, ϑ) is recovered by the dual optimization ∑ ( ) arg θ, ϑ = max − log h(y) exp θ ⊤ f (y) + ϑ⊤ g(y) d ϑ≥0,θ y ′ where θ ∈ Rd and ϑ ∈ Rd . [sent-568, score-0.386]

83 Since ∥fxj (y)∥2 ≤ r for all y ∈ Ωj and since µj in Algorithm 1 is a convex combination of fxj (y), the outer-product terms in the update for Σj satisfy (fxj (y) − µ)(fxj (y) − µ)⊤ ≼ 4r2 I. [sent-586, score-0.329]

84 Σj ≼ 2r log(i) i=1 Apply this bound to each Σj in the lower bound on J(θ) and also note a corresponding upper bound ∑ ˜ ˜ ˜ J(θ) ≥ J(θ)−tω+tλ ∥θ − θ∥2− (θ − θ)⊤(µj −fxj (yj )) 2 j ∑ ˜ ˜ ˜ J(θ) ≤ J(θ)−tλ ∥θ − θ∥2− (θ − θ)⊤(µj −fxj (yj )) 2 j 12 ˜ which follows from Jensen’s inequality. [sent-625, score-0.456]

85 Deﬁne the current θ at time τ as θτ and denote by Lτ (θ) the above lower bound and by Uτ (θ) the above upper bound at time τ . [sent-626, score-0.304]

86 Algorithm 2 maximizes J(θ) after initializing at θ0 and performing an update by maximizing a lower bound based on Σj . [sent-628, score-0.19]

87 The notation Yca,b refers to the cth tree node located at tree level a (ﬁrst level is considered as the one with∑ leaves) whose parent is the bth from the higher tree level (the root has no parent so b = 0). [sent-643, score-0.357]

88 The partition function can be expressed as: 13 Y13,0 Y12,1 ··· Y11,1 Y21,1 ··· Y22,1 1,1 Ym1,1 ··· Y11,2 Y21,2 1,2 Ym1,2 2,1 Ym2,1 1,m2,1 Y1 ··· 1,m2,1 Y2 1,m 2,1 Ym1,m2,1 Figure 4: Junction tree of depth 3. [sent-647, score-0.186]

89 1 i By simply rearranging terms we get: ) ( ( [ (m1,1 )) m1,1 ∏ ∑ ∑ ˜ zi exp(−θ ⊤ µi ) exp θ ⊤ f (u) + µi h(u) Z(θ) ≤ 2,0 u∈Y1 i=1 ( exp 1 ˜ (θ − θ)⊤ 2 (m1,1 ∑ ) Σi i=1 ˜ (θ − θ) )] . [sent-649, score-0.348]

90 ψ(u)  ψ(v)  3,0 u∈Y1 i=1 3,0 v∈Yi2,1 \Y1 j=1 w∈Yj1,i \Yi2,1 ( )) ∏m1,i (∑ ∑ term By Lemma A we can upper bound each v∈Y 2,1 \Y 3,0 ψ(v) j=1 w∈Yj1,i \Yi2,1 ψ(w) 1 i ( ) ˆ ˆ ˆ by the expression zi exp 1 (θ − θ)⊤ Σi (θ − θ) + (θ − θ)⊤ µi . [sent-655, score-0.361]

91 zi exp 2 3,0 i=1 u∈Y1 2,1 2,1 2,1 This process can be viewed as collapsing the sub-trees S1 , S2 , . [sent-657, score-0.209]

92 , Sm2,1 to super-nodes that are represented by bound parameters, zi , Σi and µi , i = {1, 2, · · · , m2,1 }, where the sub-trees are 14 deﬁned as: 2,1 S1 = 1,1 {Y12,1 , Y11,1 , Y21,1 , Y31,1 , . [sent-660, score-0.222]

93 Notice that the obtained expression can be further upper bounded using again Lemma A (induction) ( ) ˆ ˆ ˆ yielding a bound of the form: z exp 1 (θ − θ)⊤ Σ(θ − θ) + (θ − θ)⊤ µ . [sent-673, score-0.291]

94 This procedure effectively yields Algorithm 3 for the junction tree under consideration. [sent-675, score-0.157]

95 By projecting ri onto each eigenvector in V, we i ∑k ⊤ can decompose it as ri = j=1 Vi−1 (j, ·)ri Vi−1 (j, ·)⊤ + g = Vi−1 Vi−1 ri + g where g is the remaining residue. [sent-683, score-0.32]

96 03 Table 3: Convergence time in seconds under various regularization levels for a) Bupa (t = 345, dim = 7), b) Wine (t = 178, dim = 14), c) Heart (t = 187, dim = 23), d) Ion (t = 351, dim = 34), and e) Hepatitis (t = 155, dim = 20) data sets. [sent-795, score-0.305]

97 Inﬂuence of rank k on bound performance in large scale experiments We also examined the inﬂuence of k on bound performance and compared it with LBFGS, SD and CG. [sent-796, score-0.304]

98 bupa wine −19 0 −5 −log(J(θ)) −log(J(θ)) −20 −21 −22 Bound Newton BFGS Conjugate gradient Steepest descent −15 −23 −24 −5 −10 0 5 log(Time) [sec] 10 −20 −4 −2 0 2 4 log(Time) [sec] 6 8 Figure 5: Convergence of test latent log-likelihood for bupa and wine data-sets. [sent-835, score-0.584]

99 17 Data-set Algorithm BFGS SD CG Newton Bound bupa m=1 m=2 m=3 m=4 -22. [sent-856, score-0.155]

100 11 Table 5: Test latent log-likelihood at convergence for different values of m ∈ {1, 2, 3, 4} on ion, bupa, hepatitis, wine and SRBCT data-sets. [sent-936, score-0.17]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('yc', 0.359), ('fxj', 0.291), ('srbct', 0.233), ('majorization', 0.205), ('tanh', 0.177), ('hepatitis', 0.174), ('lbfgs', 0.171), ('bupa', 0.155), ('bound', 0.152), ('vi', 0.148), ('exp', 0.139), ('ion', 0.133), ('rd', 0.132), ('supplement', 0.131), ('log', 0.108), ('partition', 0.108), ('yj', 0.108), ('bfgs', 0.106), ('cg', 0.106), ('wine', 0.104), ('conditional', 0.098), ('hxj', 0.097), ('sd', 0.092), ('ri', 0.086), ('ypa', 0.086), ('fc', 0.081), ('iter', 0.081), ('junction', 0.079), ('tree', 0.078), ('zxj', 0.078), ('clique', 0.075), ('pu', 0.074), ('rk', 0.07), ('zi', 0.07), ('cvv', 0.068), ('conll', 0.068), ('hc', 0.067), ('latent', 0.066), ('sup', 0.065), ('graphical', 0.065), ('crfs', 0.065), ('jebara', 0.065), ('article', 0.064), ('gg', 0.063), ('gurations', 0.063), ('eigenvector', 0.062), ('newton', 0.062), ('ch', 0.061), ('dim', 0.061), ('penntree', 0.058), ('secstr', 0.058), ('tumors', 0.058), ('yboth', 0.058), ('ysolo', 0.058), ('zb', 0.056), ('zc', 0.056), ('likelihood', 0.056), ('si', 0.055), ('steepest', 0.055), ('fj', 0.054), ('sec', 0.054), ('elds', 0.052), ('tnd', 0.051), ('lw', 0.051), ('pl', 0.05), ('lemma', 0.05), ('xj', 0.049), ('quadratic', 0.049), ('entropy', 0.049), ('singular', 0.049), ('jensen', 0.048), ('proof', 0.047), ('correctness', 0.045), ('di', 0.044), ('az', 0.042), ('parent', 0.042), ('columbia', 0.041), ('hidden', 0.04), ('monotonic', 0.04), ('exponentiated', 0.039), ('inequality', 0.039), ('hull', 0.039), ('bth', 0.039), ('choromanska', 0.039), ('extremum', 0.039), ('loewner', 0.039), ('majorizes', 0.039), ('soundness', 0.039), ('update', 0.038), ('ft', 0.038), ('emerges', 0.036), ('iterative', 0.036), ('orthonormal', 0.036), ('em', 0.035), ('ipping', 0.035), ('conjugate', 0.034), ('pietra', 0.034), ('hinges', 0.034), ('tony', 0.034), ('qi', 0.033)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999988 206 nips-2012-Majorization for CRFs and Latent Likelihoods

Author: Tony Jebara, Anna Choromanska

2 0.11872713 96 nips-2012-Density Propagation and Improved Bounds on the Partition Function

Author: Stefano Ermon, Ashish Sabharwal, Bart Selman, Carla P. Gomes

Abstract: Given a probabilistic graphical model, its density of states is a distribution that, for any likelihood value, gives the number of conﬁgurations with that probability. We introduce a novel message-passing algorithm called Density Propagation (DP) for estimating this distribution. We show that DP is exact for tree-structured graphical models and is, in general, a strict generalization of both sum-product and max-product algorithms. Further, we use density of states and tree decomposition to introduce a new family of upper and lower bounds on the partition function. For any tree decomposition, the new upper bound based on ﬁner-grained density of state information is provably at least as tight as previously known bounds based on convexity of the log-partition function, and strictly stronger if a general condition holds. We conclude with empirical evidence of improvement over convex relaxations and mean-ﬁeld based bounds. 1

3 0.10275952 335 nips-2012-The Bethe Partition Function of Log-supermodular Graphical Models

Author: Nicholas Ruozzi

Abstract: Sudderth, Wainwright, and Willsky conjectured that the Bethe approximation corresponding to any ﬁxed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound on the true partition function. In this work, we resolve this conjecture in the afﬁrmative by demonstrating that, for any graphical model with binary variables whose potential functions (not necessarily pairwise) are all log-supermodular, the Bethe partition function always lower bounds the true partition function. The proof of this result follows from a new variant of the “four functions” theorem that may be of independent interest. 1

4 0.098911889 325 nips-2012-Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions

Author: Alekh Agarwal, Sahand Negahban, Martin J. Wainwright

Abstract: We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding a O(d/T ) convergence rate for strongly convex objectives in d dimensions and O( s(log d)/T ) convergence rate when the optimum is s-sparse. Our algorithm is based on successively solving a series of ℓ1 -regularized optimization problems using Nesterov’s dual averaging algorithm. We establish that the error of our solution after T iterations is at most O(s(log d)/T ), with natural extensions to approximate sparsity. Our results apply to locally Lipschitz losses including the logistic, exponential, hinge and least-squares losses. By recourse to statistical minimax results, we show that our convergence rates are optimal up to constants. The effectiveness of our approach is also conﬁrmed in numerical simulations where we compare to several baselines on a least-squares regression problem.

5 0.096103735 301 nips-2012-Scaled Gradients on Grassmann Manifolds for Matrix Completion

Author: Thanh Ngo, Yousef Saad

Abstract: This paper describes gradient methods based on a scaled metric on the Grassmann manifold for low-rank matrix completion. The proposed methods signiﬁcantly improve canonical gradient methods, especially on ill-conditioned matrices, while maintaining established global convegence and exact recovery guarantees. A connection between a form of subspace iteration for matrix completion and the scaled gradient descent procedure is also established. The proposed conjugate gradient method based on the scaled gradient outperforms several existing algorithms for matrix completion and is competitive with recently proposed methods. 1

6 0.094423793 186 nips-2012-Learning as MAP Inference in Discrete Graphical Models

7 0.093650773 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

8 0.091097079 180 nips-2012-Learning Mixtures of Tree Graphical Models

9 0.088638797 27 nips-2012-A quasi-Newton proximal splitting method

10 0.086832799 127 nips-2012-Fast Bayesian Inference for Non-Conjugate Gaussian Process Regression

11 0.081844099 134 nips-2012-Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods

12 0.081544384 115 nips-2012-Efficient high dimensional maximum entropy modeling via symmetric partition functions

13 0.080979362 326 nips-2012-Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses

14 0.078673683 138 nips-2012-Fully Bayesian inference for neural models with negative-binomial spiking

15 0.078292347 21 nips-2012-A Unifying Perspective of Parametric Policy Search Methods for Markov Decision Processes

16 0.077287711 247 nips-2012-Nonparametric Reduced Rank Regression

17 0.076532483 199 nips-2012-Link Prediction in Graphs with Autoregressive Features

18 0.076218374 334 nips-2012-Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

19 0.075617 355 nips-2012-Truncation-free Online Variational Inference for Bayesian Nonparametric Models

20 0.07473065 169 nips-2012-Label Ranking with Partial Abstention based on Thresholded Probabilistic Models

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.247), (1, 0.043), (2, 0.102), (3, -0.042), (4, -0.039), (5, -0.01), (6, -0.019), (7, -0.035), (8, -0.046), (9, 0.004), (10, 0.005), (11, 0.036), (12, 0.008), (13, 0.035), (14, -0.046), (15, 0.015), (16, 0.017), (17, -0.032), (18, 0.049), (19, 0.025), (20, -0.039), (21, 0.005), (22, 0.03), (23, 0.045), (24, -0.09), (25, 0.047), (26, 0.016), (27, -0.061), (28, -0.03), (29, 0.036), (30, 0.036), (31, -0.036), (32, -0.036), (33, 0.014), (34, -0.005), (35, -0.022), (36, -0.024), (37, -0.084), (38, -0.034), (39, 0.089), (40, 0.021), (41, -0.055), (42, 0.012), (43, 0.049), (44, 0.077), (45, 0.015), (46, -0.144), (47, -0.077), (48, -0.035), (49, -0.024)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93320912 206 nips-2012-Majorization for CRFs and Latent Likelihoods

Author: Tony Jebara, Anna Choromanska

2 0.77911198 96 nips-2012-Density Propagation and Improved Bounds on the Partition Function

Author: Stefano Ermon, Ashish Sabharwal, Bart Selman, Carla P. Gomes

3 0.6731106 44 nips-2012-Approximating Concavely Parameterized Optimization Problems

Author: Joachim Giesen, Jens Mueller, Soeren Laue, Sascha Swiercy

Abstract: We consider an abstract class of optimization problems that are parameterized concavely in a single parameter, and show that the solution path along the √ parameter can always be approximated with accuracy ε > 0 by a set of size O(1/ ε). A √ lower bound of size Ω(1/ ε) shows that the upper bound is tight up to a constant factor. We also devise an algorithm that calls a step-size oracle and computes an √ approximate path of size O(1/ ε). Finally, we provide an implementation of the oracle for soft-margin support vector machines, and a parameterized semi-deﬁnite program for matrix completion. 1

4 0.65318239 85 nips-2012-Convergence and Energy Landscape for Cheeger Cut Clustering

Author: Xavier Bresson, Thomas Laurent, David Uminsky, James V. Brecht

Abstract: This paper provides both theoretical and algorithmic results for the 1 -relaxation of the Cheeger cut problem. The 2 -relaxation, known as spectral clustering, only loosely relates to the Cheeger cut; however, it is convex and leads to a simple optimization problem. The 1 -relaxation, in contrast, is non-convex but is provably equivalent to the original problem. The 1 -relaxation therefore trades convexity for exactness, yielding improved clustering results at the cost of a more challenging optimization. The ﬁrst challenge is understanding convergence of algorithms. This paper provides the ﬁrst complete proof of convergence for algorithms that minimize the 1 -relaxation. The second challenge entails comprehending the 1 energy landscape, i.e. the set of possible points to which an algorithm might converge. We show that 1 -algorithms can get trapped in local minima that are not globally optimal and we provide a classiﬁcation theorem to interpret these local minima. This classiﬁcation gives meaning to these suboptimal solutions and helps to explain, in terms of graph structure, when the 1 -relaxation provides the solution of the original Cheeger cut problem. 1

5 0.63796175 232 nips-2012-Multiplicative Forests for Continuous-Time Processes

Author: Jeremy Weiss, Sriraam Natarajan, David Page

Abstract: Learning temporal dependencies between variables over continuous time is an important and challenging task. Continuous-time Bayesian networks effectively model such processes but are limited by the number of conditional intensity matrices, which grows exponentially in the number of parents per variable. We develop a partition-based representation using regression trees and forests whose parameter spaces grow linearly in the number of node splits. Using a multiplicative assumption we show how to update the forest likelihood in closed form, producing efﬁcient model updates. Our results show multiplicative forests can be learned from few temporal trajectories with large gains in performance and scalability.

6 0.63480884 334 nips-2012-Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

7 0.62032408 115 nips-2012-Efficient high dimensional maximum entropy modeling via symmetric partition functions

8 0.6150105 127 nips-2012-Fast Bayesian Inference for Non-Conjugate Gaussian Process Regression

9 0.61225289 359 nips-2012-Variational Inference for Crowdsourcing

10 0.61103213 37 nips-2012-Affine Independent Variational Inference

11 0.6109063 301 nips-2012-Scaled Gradients on Grassmann Manifolds for Matrix Completion

12 0.60497558 267 nips-2012-Perceptron Learning of SAT

13 0.60178876 335 nips-2012-The Bethe Partition Function of Log-supermodular Graphical Models

14 0.59106565 320 nips-2012-Spectral Learning of General Weighted Automata via Constrained Matrix Completion

15 0.5865441 248 nips-2012-Nonparanormal Belief Propagation (NPNBP)

16 0.57559019 321 nips-2012-Spectral learning of linear dynamics from generalised-linear observations with application to neural population data

17 0.57036543 129 nips-2012-Fast Variational Inference in the Conjugate Exponential Family

18 0.56977892 180 nips-2012-Learning Mixtures of Tree Graphical Models

19 0.56786996 53 nips-2012-Bayesian Pedigree Analysis using Measure Factorization

20 0.5643971 325 nips-2012-Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.05), (21, 0.021), (38, 0.165), (39, 0.01), (42, 0.033), (54, 0.019), (55, 0.019), (74, 0.053), (76, 0.143), (80, 0.133), (92, 0.044), (96, 0.223)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.90563589 66 nips-2012-Causal discovery with scale-mixture model for spatiotemporal variance dependencies

Author: Zhitang Chen, Kun Zhang, Laiwan Chan

Abstract: In conventional causal discovery, structural equation models (SEM) are directly applied to the observed variables, meaning that the causal effect can be represented as a function of the direct causes themselves. However, in many real world problems, there are signiﬁcant dependencies in the variances or energies, which indicates that causality may possibly take place at the level of variances or energies. In this paper, we propose a probabilistic causal scale-mixture model with spatiotemporal variance dependencies to represent a speciﬁc type of generating mechanism of the observations. In particular, the causal mechanism including contemporaneous and temporal causal relations in variances or energies is represented by a Structural Vector AutoRegressive model (SVAR). We prove the identiﬁability of this model under the non-Gaussian assumption on the innovation processes. We also propose algorithms to estimate the involved parameters and discover the contemporaneous causal structure. Experiments on synthetic and real world data are conducted to show the applicability of the proposed model and algorithms.

2 0.87831444 157 nips-2012-Identification of Recurrent Patterns in the Activation of Brain Networks

Author: Firdaus Janoos, Weichang Li, Niranjan Subrahmanya, Istvan Morocz, William Wells

Abstract: Identifying patterns from the neuroimaging recordings of brain activity related to the unobservable psychological or mental state of an individual can be treated as a unsupervised pattern recognition problem. The main challenges, however, for such an analysis of fMRI data are: a) deďŹ ning a physiologically meaningful feature-space for representing the spatial patterns across time; b) dealing with the high-dimensionality of the data; and c) robustness to the various artifacts and confounds in the fMRI time-series. In this paper, we present a network-aware feature-space to represent the states of a general network, that enables comparing and clustering such states in a manner that is a) meaningful in terms of the network connectivity structure; b)computationally efďŹ cient; c) low-dimensional; and d) relatively robust to structured and random noise artifacts. This feature-space is obtained from a spherical relaxation of the transportation distance metric which measures the cost of transporting â€œmassâ€? over the network to transform one function into another. Through theoretical and empirical assessments, we demonstrate the accuracy and efďŹ ciency of the approximation, especially for large problems. 1

same-paper 3 0.83371335 206 nips-2012-Majorization for CRFs and Latent Likelihoods

Author: Tony Jebara, Anna Choromanska

4 0.79701608 197 nips-2012-Learning with Recursive Perceptual Representations

Author: Oriol Vinyals, Yangqing Jia, Li Deng, Trevor Darrell

Abstract: Linear Support Vector Machines (SVMs) have become very popular in vision as part of state-of-the-art object recognition and other classiﬁcation tasks but require high dimensional feature spaces for good performance. Deep learning methods can ﬁnd more compact representations but current methods employ multilayer perceptrons that require solving a difﬁcult, non-convex optimization problem. We propose a deep non-linear classiﬁer whose layers are SVMs and which incorporates random projection as its core stacking element. Our method learns layers of linear SVMs recursively transforming the original data manifold through a random projection of the weak prediction computed from each layer. Our method scales as linear SVMs, does not rely on any kernel computations or nonconvex optimization, and exhibits better generalization ability than kernel-based SVMs. This is especially true when the number of training samples is smaller than the dimensionality of data, a common scenario in many real-world applications. The use of random projections is key to our method, as we show in the experiments section, in which we observe a consistent improvement over previous –often more complicated– methods on several vision and speech benchmarks. 1

5 0.7662648 355 nips-2012-Truncation-free Online Variational Inference for Bayesian Nonparametric Models

Author: Chong Wang, David M. Blei

Abstract: We present a truncation-free stochastic variational inference algorithm for Bayesian nonparametric models. While traditional variational inference algorithms require truncations for the model or the variational distribution, our method adapts model complexity on the ﬂy. We studied our method with Dirichlet process mixture models and hierarchical Dirichlet process topic models on two large data sets. Our method performs better than previous stochastic variational inference algorithms. 1

6 0.76413429 172 nips-2012-Latent Graphical Model Selection: Efficient Methods for Locally Tree-like Graphs

7 0.76380742 83 nips-2012-Controlled Recognition Bounds for Visual Learning and Exploration

8 0.76179403 200 nips-2012-Local Supervised Learning through Space Partitioning

9 0.76136827 252 nips-2012-On Multilabel Classification and Ranking with Partial Feedback

10 0.76049572 65 nips-2012-Cardinality Restricted Boltzmann Machines

11 0.76034236 56 nips-2012-Bayesian active learning with localized priors for fast receptive field characterization

12 0.76021522 281 nips-2012-Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders

13 0.76006222 316 nips-2012-Small-Variance Asymptotics for Exponential Family Dirichlet Process Mixture Models

14 0.76004004 104 nips-2012-Dual-Space Analysis of the Sparse Linear Model

15 0.75972319 186 nips-2012-Learning as MAP Inference in Discrete Graphical Models

16 0.75859344 292 nips-2012-Regularized Off-Policy TD-Learning

17 0.75802875 16 nips-2012-A Polynomial-time Form of Robust Regression

18 0.757626 199 nips-2012-Link Prediction in Graphs with Autoregressive Features

19 0.75688356 330 nips-2012-Supervised Learning with Similarity Functions

20 0.75555176 227 nips-2012-Multiclass Learning with Simplex Coding