2015

Hinge-Loss Markov Random Fields and Probabilistic Soft Logic

Bach, Stephen H., Broecheler, Matthias, Huang, Bert et al.

Understand

A fundamental challenge in developing high-impact machine learning technologies is balancing the need to model rich, structured domains with the ability to scale to big data.

Many important problem areas are both richly structured and large scale, from social and biological networks, to knowledge graphs and the Web, to images, video, and natural language.
In this paper, we introduce two new formalisms for modeling structured data, and show that they can both capture rich structure and scale to big data.
The first, hinge-loss Markov random fields (HL-MRFs), is a new kind of probabilistic graphical model that generalizes different approaches to convex inference.

Built on

Minima of Functions of Several Variables with Inequalities as Side Constraints
W. Karush · 1939
Earlier work this paper cites.
Nonlinear programming
H. W. Kuhn and A. W. Tucker · 1951
Earlier work this paper cites.
Record linkage: Making maximum use of the discriminating power of identifying information
H. B. Newcombe and J. M. Kennedy · 1962
Earlier work this paper cites.
Statistical analysis of non-lattice data
J. Besag · 1975
Earlier work this paper cites.
Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires
R. Glowinski and A. Marrocco · 1975
Earlier work this paper cites.
A dual algorithm for the solution of nonlinear variational problems via finite element approximation
D. Gabay and B. Mercier · 1976
Earlier work this paper cites.
Some simplified NP-complete graph problems
M. R. Garey, D. S. Johnson, and L. Stockmeyer · 1976
Earlier work this paper cites.
Learning relations by pathfinding
B. L. Richards and R. J. Mooney · 1992
Earlier work this paper cites.
New 3/4-approximation algorithms for the maximum satisfiability problem
M. X. Goemans and D. P. Williamson · 1994
Earlier work this paper cites.
Inductive logic programming: Theory and methods
S. Muggleton and L. De Raedt · 1994
Earlier work this paper cites.
Interior-Point Polynomial Algorithms in Convex Programming
Y. Nesterov and A. Nemirovskii · 1994
Earlier work this paper cites.
Finding MAPs for belief networks is NP-hard
S. E. Shimony · 1994
Earlier work this paper cites.
Fuzzy Sets and Fuzzy Logic: Theory and Applications
G. J. Klir and B. Yuan · 1995
Earlier work this paper cites.
Clausal discovery
L. De Raedt and L. Dehaspe · 1996
Earlier work this paper cites.
Object-oriented Bayesian networks
D. Koller and A. Pfeffer · 1997
Earlier work this paper cites.
Discrete Lagrangian-based search for solving MAX-SAT problems
B. W. Wah and Y. Shang · 1997
Earlier work this paper cites.
Approximating MAPs for belief networks is NP-hard and other theorems
A. Abdelbar and S. Hedetniemi · 1998
Earlier work this paper cites.
Learning probabilistic relational models
N. Friedman, L. Getoor, D. Koller, and A. Pfeffer · 1999
Earlier work this paper cites.
SPOOK: A system for probabilistic object-oriented knowledge representation
A. Pfeffer, D. Koller, B. Milch, and K. T. Takusagawa · 1999
Earlier work this paper cites.
Efficient clustering of high-dimensional data sets with application to reference matching
A. McCallum, K. Nigam, and L. H. Ungar · 2000
Earlier work this paper cites.
Guided local search for solving SAT and weighted MAX-SAT problems
P. Mills and E. Tsang · 2000
Earlier work this paper cites.
The Nature of Statistical Learning Theory
V. Vapnik · 2000
Earlier work this paper cites.
Eigentaste: A constant time collaborative filtering algorithm
K. Goldberg, T. Roeder, D. Gupta, and C. Perkins · 2001
Earlier work this paper cites.
IBAL: A probabilistic rational programming language
A. Pfeffer · 2001
Earlier work this paper cites.
Improved approximation algorithms for MAX SAT
T. Asano and D. P. Williamson · 2002
Earlier work this paper cites.
Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms
M. Collins · 2002
Earlier work this paper cites.
Learning probabilistic models of link structure
L. Getoor, N. Friedman, D. Koller, and B. Taskar · 2002
Earlier work this paper cites.
Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields
J. Kleinberg and É. Tardos · 2002
Earlier work this paper cites.
Using weighted MAX-SAT engines to solve MPE
J. D. Park · 2002
Earlier work this paper cites.
The eigentrust algorithm for reputation management in P2P networks
S. Kamvar, M. Schlosser, and H. Garcia-Molina · 2003
Earlier work this paper cites.
Grafting: Fast, incremental feature selection by gradient descent in function space
S. Perkins, K. Lacker, and J. Theiler · 2003
Earlier work this paper cites.
Trust management for the semantic web
M. Richardson, R. Agrawal, and P. Domingos · 2003
Earlier work this paper cites.
Combinatorial Optimization: Polyhedra and Efficiency
A. Schrijver · 2003
Earlier work this paper cites.
Incremental parsing with the perceptron algorithm
M. Collins and B. Roark · 2004
Earlier work this paper cites.
Max-margin Markov networks
B. Taskar, C. Guestrin, and D. Koller · 2004
Earlier work this paper cites.
The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems
L. An and P. Tao · 2005
Earlier work this paper cites.
A linear programming formulation and approximation algorithms for the metric labeling problem
C. Chekuri, S. Khanna, J. Naor, and L. Zosin · 2005
Earlier work this paper cites.
Using linear programming to decode binary linear codes
J. Feldman, M. J. Wainwright, and D. R. Karger · 2005
Earlier work this paper cites.
Computing and Applying Trust in Web-based Social Networks
J. Golbeck · 2005
Earlier work this paper cites.
Learning the structure of Markov logic networks
S. Kok and P. Domingos · 2005
Earlier work this paper cites.
BLOG: Probabilistic models with unknown objects
B. Milch, B. Marthi, S. Russell, D. Sontag, D. L. Ong, and A. Kolobov · 2005
Earlier work this paper cites.
Discriminative training of Markov logic networks
P. Singla and P. Domingos · 2005
Earlier work this paper cites.
Learning structured prediction models: A large margin approach
B. Taskar, V. Chatalbashev, D. Koller, and C. Guestrin · 2005
Earlier work this paper cites.
Large margin methods for structured and interdependent output variables
I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun · 2005
Earlier work this paper cites.
The interior-point revolution in optimization: History, recent developments, and lasting consequences
M. Wright · 2005
Earlier work this paper cites.

Similar

Reducing the dimensionality of data with neural networks
G. Hinton and R. Salakhutdinov · 2006
Cited alongside, same era.
Convergent tree-reweighted message passing for energy minimization
V. Kolmogorov · 2006
Cited alongside, same era.
Solving Markov random fields using second order cone programming relaxations
M. P. Kumar, P. H. S. Torr, and A. Zisserman · 2006
Cited alongside, same era.
Quadratic programming relaxations for metric labeling and Markov random field MAP estimation
P. Ravikumar and J. Lafferty · 2006
Cited alongside, same era.
Markov logic networks
M. Richardson and P. Domingos · 2006
Cited alongside, same era.
Linear programming relaxations and belief propagation – An empirical study
C. Yanover, T. Meltzer, and Y. Weiss · 2006
Cited alongside, same era.
Predicting Structured Data
G. Bakir, T. Hofmann, B. Schölkopf, A. J. Smola, B. Taskar, and S. V. N. Vishwanathan, editors · 2007
Cited alongside, same era.
ProbLog: A probabilistic Prolog and its application in link discovery
L. De Raedt, A. Kimmig, and H. Toivonen · 2007
Cited alongside, same era.
Lifted first-order probabilistic inference
R. de Salvo Braz, E. Amir, and D. Roth · 2007
Cited alongside, same era.
Introduction to statistical relational learning
L. Getoor and B. Taskar, editors · 2007
Cited alongside, same era.
Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations
A. Globerson and T. Jaakkola · 2007
Cited alongside, same era.
Template based inference in symmetric relational Markov random fields
A. Jaimovich, O. Meshi, and N. Friedman · 2007
Cited alongside, same era.

Then

MRF energy minimization and beyond via dual decomposition
N. Komodakis, N. Paragios, and G. Tziritas · 2011
Later among the works it cites.
An alternating direction method for dual MAP LP relaxation
O. Meshi and A. Globerson · 2011
Later among the works it cites.
Sum-product networks: A new deep architecture
H. Poon and P. Domingos · 2011
Later among the works it cites.
The PITA system: Tabling and answer subsumption for reasoning under uncertainty
F. Riguzzi and T. Swift · 2011
Later among the works it cites.
A reduction of imitation learning and structured prediction to no-regret online learning
S. Ross, G. J. Gordon, and J. A. Bagnell · 2011
Later among the works it cites.
Introduction to dual decomposition for inference
D. Sontag, A. Globerson, and T. Jaakkola · 2011
Later among the works it cites.
Scaling MPE inference for constrained continuous Markov random fields
S. H. Bach, M. Broecheler, L. Getoor, and D. P. O’Leary · 2012
Later among the works it cites.
Lifted probabilistic inference
K. Kersting · 2012
Later among the works it cites.
Lifted linear programming
M. Mladenov, B. Ahmadi, and K. Kersting · 2012
Later among the works it cites.
Globally convergent dual MAP LP relaxation solvers using Fenchel-Young margins
A. G. Schwing, T. Hazan, M. Pollefeys, and R. Urtasun · 2012
Later among the works it cites.
Efficiently searching for frustrated cycles in MAP inference
D. Sontag, D. K. Choe, and Y. Li · 2012
Later among the works it cites.
On lifting the Gibbs sampling algorithm
D. Venugopal and V. Gogate · 2012
Later among the works it cites.
Hinge-loss Markov random fields: Convex inference for structured prediction
S. H. Bach, B. Huang, B. London, and L. Getoor · 2013
Later among the works it cites.
Exploiting the power of MIP solvers in MAXSAT
J. Davies and F. Bacchus · 2013
Later among the works it cites.
A flexible framework for probabilistic models of social trust
B. Huang, A. Kimmig, L. Getoor, and J. Golbeck · 2013
Later among the works it cites.
Collective activity detection using hinge-loss Markov random fields
B. London, S. Khamis, S. H. Bach, B. Huang, L. Getoor, and L. Davis · 2013
Later among the works it cites.
Tighter linear program relaxations for high order graphical models
E. Mezuman, D. Tarlow, A. Globerson, and Y. Weiss · 2013
Later among the works it cites.
A hypergraph-partitioned vertex programming approach for large-scale consensus optimization
H. Miao, X. Liu, B. Huang, and L. Getoor · 2013
Later among the works it cites.
Knowledge graph identification
J. Pujara, H. Miao, L. Getoor, and W. Cohen · 2013
Later among the works it cites.
Probabilistic soft logic for semantic textual similarity
I. Beltagy, K. Erk, and R. J. Mooney · 2014
Later among the works it cites.
Road traffic congestion monitoring in social media with hinge-loss Markov random fields
P. Chen, F. Chen, and Z. Qian · 2014
Later among the works it cites.
Network-based drug-target interaction prediction with probabilistic soft logic
S. Fakhraei, B. Huang, L. Raschid, and L. Getoor · 2014
Later among the works it cites.
Probabilistic programming
A. D. Gordon, T. A. Henzinger, A. V. Nori, and S. K. Rajamani · 2014
Later among the works it cites.
Inferring user preferences by probabilistic logical reasoning over social networks
Original
J. Li, A. Ritter, and D. Jurafsky · 2014
Later among the works it cites.
Learning latent engagement patterns of students in online courses
A. Ramesh, D. Goldwasser, B. Huang, H. Daumé III, and L. Getoor · 2014
Later among the works it cites.
Reinforcement and Imitation Learning via Interactive No-Regret Learning, 2014
S. Ross and J. A. Bagnell · 2014
Later among the works it cites.
Exploiting social network structure for person-to-person sentiment analysis
R. West, H. S. Paskov, J. Leskovec, and C. Potts · 2014
Later among the works it cites.
A new approach to probabilistic programming inference
F. Wood, J. W. van de Meent, and V. Mansinghka · 2014
Later among the works it cites.
Joint prediction for entity/event-level sentiment analysis using probabilistic soft logic models
L. Deng and J. Wiebe · 2015
Closest in time.
Latent topic networks: A versatile probabilistic programming framework for topic models
J. Foulds, S. Kumar, and L. Getoor · 2015
Closest in time.
Lifted graphical models: A survey
A. Kimmig, L. Mihalkova, and L. Getoor · 2015
Closest in time.
HyPER: A flexible and extensible probabilistic framework for hybrid recommender systems
P. Kouki, S. Fakhraei, J. Foulds, M. Eirinaki, and L. Getoor · 2015
Closest in time.
FoxPSL: An extended and scalable PSL implementation
S. Magliacane, P. Stutz, P. Groth, and A. Bernstein · 2015
Closest in time.
AD 3 : Alternating Directions Dual Decomposition for MAP Inference in Graphical Models
A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar, N. A. Smith, and E. P. Xing · 2015
Closest in time.
Weakly supervised models of aspect-sentiment for online course discussion forums
A. Ramesh, S. Kumar, J. Foulds, and L. Getoor · 2015
Closest in time.
Joint models of disagreement and stance in online debate
D. Sridhar, J. Foulds, M. Walker, B. Huang, and L. Getoor · 2015
Closest in time.
Structuring linked data search results using probabilistic soft logic
D. Alshukaili, A. A. A. Fernandes, and N. W. Paton · 2016
Closest in time.
Weakly supervised tweet stance classification by relational bootstrapping
J. Ebrahimi, D. Dou, and D. Lowd · 2016
Closest in time.
Algebraic model counting
A. Kimmig, G. Van den Broeck, and L. De Raedt · 2016
Closest in time.
A probabilistic soft logic based approach to exploiting latent and global information in event classification
S. Liu, K. Liu, S. He, and J. Zhao · 2016
Closest in time.
Stability and generalization in structured prediction
B. London, B. Huang, and L. Getoor · 2016
Closest in time.
Advanced Structured Prediction
S. Nowozin, P. V. Gehler, J. Jancsary, and C. H. Lampert, editors · 2016
Closest in time.
ClaimEval: Integrated and flexible framework for claim evaluation using credibility of sources
M. Samadi, P. Talukdar, M. Veloso, and M. Blum · 2016
Closest in time.
A probabilistic approach for collective similarity-based drug-drug interaction prediction
D. Sridhar, S. Fakhraei, and L. Getoor · 2016
Closest in time.
Edward: A library for probabilistic modeling, inference, and criticism
Original
D. Tran, A. Kucukelbir, A. B. Dieng, M. Rudolph, D. Liang, and D. M. Blei · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…