Show description

Then a simple telescope sum yields n n n E χ(yfψ,F ) ≤E χ(yfχ∗ ) + 4 E ψ(yfψ,F ) − Eemp ψ(yfψ,F ) ∗ ∗ ) − E ψ(yfψ,F ) + δ(F, ψ) + 4 Eemp ψ(yfψ,F RW γ ≤E χ(yfχ∗ ) + δ(F, ψ) + 4 √ −2 log δ + r/R + n 8 log 2 . 28) Here γ is the effective margin of the soft-margin loss max(0, 1 − γyf (x)), W is an upper bound on w , R ≥ x , r is the average radius, as defined in the previous section, and we assumed that b is bounded by the largest value of w, x . A similar reasoning for logistic and exponential loss is given in Boucheron et al.

4 Margin-Based Loss Functions 35 edge (vi , vj ) ∈ E is assigned a nonnegative weight w(vi , vj ) ∈ R+ . A path from v1 ∈ V to vn ∈ V is a sequence of nodes v1 v2 . . vn such that (vi , vi+1 ) ∈ E. The weight of a path is the sum of the weights on the edges. For an undirected graph, (vi , vj ) ∈ E =⇒ (vj , vi ) ∈ E ∧ w(vi , vj ) = w(vj , vi ). A graph is said to be connected if every pair of nodes in the graph is connected by a path. , minimum weight) path from vi to vj . If the output labels are nodes in a graph G, the following loss function takes the structure of G into account: y , y) + f (x, y˜)] − f (x, y)}.

Although the focus of this chapter is on graphical models, we also briefly review models that capture recursive dependency structure in syntactic natural language constructions. 2 Conditional Independence types of independence In defining probabilistic models, conditional independence is a concept of fundamental importance that also underpins the theory of graphical models. If one wants to model domains with a potentially large number of variables among which complex dependencies exist, as is typical in many real-world applications, everything may depend on everything else and it is crucial to make appropriate assumptions about the ways variables do not depend on each other.