×

zbMATH — the first resource for mathematics

Relational linear programming. (English) Zbl 1404.68109
Summary: We propose relational linear programming, a simple framework for combining linear programs (LPs) and logic programs. A relational linear program (RLP) is a declarative LP template defining the objective and the constraints through the logical concepts of objects, relations, and quantified variables. This allows one to express the LP objective and constraints relationally for a varying number of individuals and relations among them without enumerating them. Together with a logical knowledge base, effectively a logic program consisting of logical facts and rules, it induces a ground LP. This ground LP is solved using lifted linear programming. That is, symmetries within the ground LP are employed to reduce its dimensionality, if possible, and the reduced program is solved using any off-the-shelf LP solver. In contrast to mainstream LP template languages such as AMPL, which features a mixture of declarative and imperative programming styles, RLP’s relational nature allows a more intuitive representation of optimization problems, in particular over relational domains. We illustrate this empirically by experiments on approximate inference in Markov logic networks using LP relaxations, on solving Markov decision processes, and on collective inference using LP support vector machines.
MSC:
68T05 Learning and adaptive systems in artificial intelligence
68N17 Logic programming
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] (Getoor, L.; Taskar, B., Introduction to Statistical Relational Learning, (2007), MIT Press Cambridge, MA) · Zbl 1141.68054
[2] De Raedt, L., Logical and relational learning, (2008), Springer · Zbl 1203.68145
[3] (De Raedt, L.; Frasconi, P.; Kersting, K.; Muggleton, S. H., Probabilistic Inductive Logic Programming, (2008), Springer) · Zbl 1132.68007
[4] Raedt, L. D.; Kersting, K., Statistical relational learning, (Sammut, G. W.C., Encyclopedia of Machine Learning, (2010), Springer Heidelberg), 916-924
[5] Nilsson, N., Probabilistic logic, Artif. Intell., 28, 1, 71-87, (1986) · Zbl 0589.03007
[6] Geffner, H., Artificial intelligence: from programs to solvers, AI Commun., 27, 1, 45-51, (2014)
[7] Rush, A.; Collins, M., A tutorial on dual decomposition and Lagrangian relaxation for inference in natural language processing, J. Artif. Intell. Res., 45, 305-362, (2012) · Zbl 1280.68272
[8] (Sra, S.; Nowozin, S.; Wright, S., Optimization for Machine Learning, (2011), MIT Press)
[9] Guns, T.; Nijssen, S.; De Raedt, L., Itemset mining: a constraint programming perspective, Artif. Intell., 175, 12-13, 1951-1983, (2011) · Zbl 1353.68233
[10] Atserias, A.; Maneva, E., Sherali-Adams relaxations and indistinguishability in counting logics, SIAM J. Comput., 42, 1, 112-137, (2013) · Zbl 1286.68175
[11] Littman, M.; Dean, T.; Pack Kaelbling, L., On the complexity of solving Markov decision problems, (Proceedings of the 11th Annual Conference on Uncertainty in Artificial Intelligence, UAI-95, (1995)), 394-402
[12] Richardson, M.; Domingos, P., Markov logic networks, Mach. Learn., 62, 1-2, 107-136, (2006)
[13] Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Gallagher, B.; Eliassi-Rad, T., Collective classification in network data, AI Mag., 29, 3, 93-106, (2008)
[14] Mladenov, M.; Ahmadi, B.; Kersting, K., Lifted linear programming, (Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, AISTATS, J. Mach. Learn. Res. Workshop Conf. Proc., vol. 22, (2012)), 788-797
[15] Dantzig, G.; Thapa, M., Linear programming 2: theory and extensions, (2003), Springer
[16] Zhou, W.; Zhang, L.; Jiao, L., Linear programming support vector machines, Pattern Recognit., 35, 12, 2927-2936, (2002) · Zbl 1010.68108
[17] Demiriz, A.; Bennett, K. P.; Shawe-Taylor, J., Linear programming boosting via column generation, Mach. Learn., 46, 1-3, 225-254, (2002) · Zbl 0998.68105
[18] Ataman, K.; Street, W.; Zhang, Y., Learning to rank by maximizing auc with linear programming, (Proceedings of the International Joint Conference on Neural Networks, IJCNN, (2006)), 123-129
[19] Wang, Z.; Shawe-Taylor, J., Large-margin structured prediction via linear programming, (Proceedings of the 12th International Conference on Artificial Intelligence and Statistics, AISTATS, (2009)), 599-606
[20] Klein, T.; Brefeld, U.; Scheffer, T., Exact and approximate inference for annotating graphs with structural svms, (Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Part 1, ECML PKDD-08, (2008)), 611-623
[21] Torkamani, M.; Lowd, D., Convex adversarial collective classification, (Proceedings of the 30th International Conference on Machine Learning, ICML, (2013)), 642-650
[22] Wainwright, M. J.; Jordan, M. I., Graphical models, exponential families, and variational inference, Found. Trends Mach. Learn., 1, 1-2, 1-305, (2008) · Zbl 1193.62107
[23] Syed, U.; Bowling, M.; Schapire, R. E., Apprenticeship learning using linear programming, (Proceedings of the 25th International Conference on Machine Learning, ICML, (2008), ACM), 1032-1039
[24] Sanner, S.; Boutilier, C., Practical solution techniques for first-order mdps, Artif. Intell., 173, 5-6, 748-788, (2009) · Zbl 1191.68641
[25] Ng, A. Y.; Russell, S. J., Algorithms for inverse reinforcement learning, (Proceedings of the 17th International Conference on Machine Learning, ICML, (2000)), 663-670
[26] Komodakis, N.; Paragios, N.; Tziritas, G., Clustering via LP-based stabilities, (Proceedings of the 21st Conference on Neural Information Processing Systems, NIPS, (2008)), 865-872
[27] Sandler, M., On the use of linear programming for unsupervised text classification, (Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, (2005), ACM), 256-264
[28] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows: theory, algorithms, and applications, (1993), Prentice Hall · Zbl 1201.90001
[29] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A mathematical programming language, (1993), The Scientific Press San Francisco, CA
[30] Fourer, R.; Gay, D.; Kernighan, B., AMPL: A modeling language for mathematical programming, (2002), Duxbury Press/Brooks/Cole Publishing Company
[31] Lloyd, J., Foundations of logic programming, (1987), Springer-Verlag Berlin · Zbl 0668.68004
[32] Flach, P., Simply logical - intelligent reasoning by example, Wiley Professional Computing, (1994), Wiley · Zbl 0817.68049
[33] Niu, F.; Ré, C.; Doan, A.; Shavlik, J., Tuffy: scaling up statistical inference in Markov logic networks using an RDBMS, Proc. VLDB Endow., 4, 6, 373-384, (2011)
[34] Singla, P.; Domingos, P., Lifted first-order belief propagation, (Proceedings of the 23rd AAAI Conference on Artificial Intelligence, AAAI, Chicago, IL, USA, (2008)), 1094-1099
[35] Kersting, K.; Ahmadi, B.; Natarajan, S., Counting belief propagation, (Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, UAI, (2009))
[36] Ahmadi, B.; Kersting, K.; Mladenov, M.; Natarajan, S., Exploiting symmetries for scaling loopy belief propagation and relational training, Mach. Learn., 92, 91-132, (2013) · Zbl 1273.68293
[37] Godsil, C.; Royle, G., Algebraic graph theory, (2001), Springer · Zbl 0968.05002
[38] Ramana, M.; Scheinerman, E.; Ullman, D., Fractional isomorphism of graphs, Discrete Math., 132, 247-265, (1994) · Zbl 0808.05077
[39] Grohe, M.; Kersting, K.; Mladenov, M.; Selman, E., Dimension reduction via colour refinement, (Proceedings of the 22th Annual European Symposium, ESA-14, (2014)), 505-516 · Zbl 1425.68313
[40] Godsil, C., Compact graphs and equitable partitions, Linear Algebra Appl., 255, 259-266, (1997) · Zbl 0872.05033
[41] Berkholz, C.; Bonsma, P.; Grohe, M., Tight lower and upper bounds for the complexity of canonical colour refinement, (Proceedings of the 21st Annual European Symposium on Algorithms, ESA, (2013)), 145-156 · Zbl 1362.68097
[42] Apsel, U.; Kersting, K.; Mladenov, M., Lifting relational MAP-LPs using cluster signatures, (Proceedings of the 28th AAAI Conference on Artificial Intelligence, AAAI, (2014))
[43] Bui, H.; Huynh, T.; Riedel, S., Automorphism groups of graphical models and lifted variational inference, (Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, UAI, (2013))
[44] Bödi, R.; Herr, K.; Joswig, M., Algorithms for highly symmetric linear and integer programs, Math. Program., Ser. A, 137, 1-2, 65-90, (2013) · Zbl 1262.90101
[45] Littman, M.; Dean, T.; Kaelbling, L. P., On the complexity of solving Markov decision problems, (Proceedings of the 11th International Conference on Uncertainty in Artificial Intelligence, UAI, (1995)), 394-402
[46] Sutton, R.; Barto, A., Reinforcement learning: an introduction, (1998), The MIT Press
[47] Narayanamurthy, S.; Ravindran, B., On the hardness of finding symmetries in Markov decision processes, (Proceedings of the 25th International Conference on Machine Learning, ICML, (2008)), 688-695
[48] Ravindran, B.; Barto, A., Symmetries and model minimization in Markov decision processes, (2001), University of Massachusetts Amherst, MA, USA, Tech. Rep. 01-43
[49] Dean, T.; Givan, R., Model minimization in Markov decision processes, (Proceedings of the 14th National Conference on Artificial Intelligence, AAAI, (1997)), 106-111
[50] Chakrabarti, S.; Dom, B.; Indyk, P., Enhanced hypertext categorization using hyperlinks, (Proceedings of ACM SIGMOD International Conference on Management of Data, SIGMOD, (1998)), 307-318
[51] Neville, J.; Jensen, D., Iterative classification in relational data, (Proceedings of the AAAI-2000 Workshop on Learning Statistical Models from Relational Data, (2000)), 13-20
[52] Neville, J.; Jensen, D., Collective classification with relational dependency networks, (Proceedings of the 2nd International Workshop on Multi-Relational Data Mining, (2003)), 77-91
[53] Neville, J.; Jensen, D., Relational dependency networks, J. Mach. Learn. Res., 8, 653-692, (2007) · Zbl 1222.68274
[54] Vapnik, V. N., Statistical learning theory, Adaptive and Learning Systems for Signal Processing, Communications and Control Series, (1998), John Wiley & Sons New York, A Wiley-Interscience Publication · Zbl 0934.62009
[55] Sen, P.; Namata, G. M.; Bilgic, M.; Getoor, L.; Gallagher, B.; Eliassi-Rad, T., Collective classification in network data, AI Mag., 29, 3, 93-106, (2008)
[56] Macskassy, S. A.; Provost, F., Classification in networked data: a toolkit and a univariate case study, J. Mach. Learn. Res., 8, 935-983, (2007)
[57] Lu, Q.; Getoor, L., Link-based classification, (Proceedings of the 20th International Conference on Machine Learning, ICML, (2003)), 496-503
[58] Brooke, A.; Kendrick, D.; Meeraus, A., GAMS: A User’s guide, (1992), The Scientific Press Redwood City, CA
[59] J. Bisschop, P. Lindberg, AIMMS the Modeling System, Paragon Decision Technology, 1993.
[60] Ciriani, T.; Colombani, Y.; Heipcke, S., Embedding optimisation algorithms with mosel, 4OR, 1, 2, 155-167, (2003) · Zbl 1097.90036
[61] Kuip, C., Algebraic languages for mathematical programming, Eur. J. Oper. Res., 67, 25-51, (1993) · Zbl 0776.90087
[62] Fragniere, E.; Gondzio, J., Optimization modeling languages, (Pardalos, P.; Resende, M., Handbook of Applied Optimization, (2002), Oxford University Press New York), 993-1007
[63] (Wallace, S.; Ziemba, W., Applications of Stochastic Programming, (2005), SIAM Philadelphia) · Zbl 1068.90002
[64] Mitra, G.; Luca, C.; Moody, S.; Kristjanssonl, B., Sets and indices in linear programming modelling and their integration with relational data models, Comput. Optim. Appl., 4, 263-283, (1995) · Zbl 0826.90086
[65] Atamtürk, A.; Johnson, E.; Linderoth, J.; Savelsbergh, M., A relational modeling system for linear and integer programming, Oper. Res., 48, 6, 846-857, (2000)
[66] Farrell, R.; Maness, T., A relational database approach to a linear programming-based decision support system for production planning in secondary wood product manufacturing, Decis. Support Syst., 40, 2, 183-196, (2005)
[67] Yih, W.; Roth, D., Global inference for entity and relation identification via a linear programming formulation, (Getoor, L.; Taskar, B., An Introduction to Statistical Relational Learning, (2007), MIT Press)
[68] Riedel, S.; Clarke, J., Incremental integer linear programming for non-projective dependency parsing, (Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP, (2006)), 129-137
[69] Clarke, J.; Lapata, M., Global inference for sentence compression: an integer linear programming approach, J. Artif. Intell. Res., 31, 399-429, (2008) · Zbl 1182.68286
[70] Martins, A.; Smith, N.; Xing, E., Concise integer linear programming formulations for dependency parsing, (Proceedings of the 47th Annual Meeting of the Association for Computational Linguistics, ACL, (2009)), 342-350
[71] Riedel, S.; Smith, D.; McCallum, A., Parse, price and cut—delayed column and row generation for graph based parsers, (Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP-CoNLL, (2012)), 732-743
[72] Cheng, X.; Roth, D., Relational inference for wikification, (Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP, (2013)), 1787-1796
[73] Kabjan, D.; Fourer, R.; Ma, J., Algebraic modeling in a deductive database language, (2009), presented at the 11th INFORMS Computing Society (ICS) Conference 2009, but not published
[74] Eisner, J.; Filardo, N., Dyna: extending Datalog for modern AI, (de Moor, O.; Gottlob, G.; Furche, T.; Sellers, A., Datalog Reloaded - 1st International Workshop, Datalog 2010, Oxford, UK, March 16-19, 2010, Lect. Notes Comput. Sci., vol. 6702, (2011), Springer), 181-220, Revised Selected Papers
[75] Mattingley, J.; Boyd, S., CVXGEN: a code generator for embedded convex optimization, Optim. Eng., 12, 1, 1-27, (2012) · Zbl 1293.65095
[76] Hart, W.; Watson, J.-P.; Woodruff, D., Pyomo: modeling and solving mathematical programs in python, Math. Program. Comput., 3, 219-260, (2011)
[77] Diamond, S.; Chu, E.; Boyd, S., CVXPY: a python-embedded modeling language for convex optimization, (May 2014), version 0.2
[78] Rizzolo, N.; Roth, D., Modeling discriminative global inference, (Proceedings of the IEEE International Conference on Semantic Computing, ICSC, (2007)), 597-604
[79] Gordon, G.; Hong, S.; Dudík, M., First-order mixed integer linear programming, (Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, UAI, (2009)), 213-222
[80] Zawadzki, E.; Gordon, G.; Platzer, A., An instantiation-based theorem prover for first-order programming, (Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, AISTATS, vol. 15, (2011)), 855-863
[81] Margot, F., Symmetry in integer linear programming, (Jünger, M.; Liebling, T.; Naddef, D.; Nemhauser, G.; Pulleyblank, W.; Reinelt, G.; Rinaldi, G.; Wolsey, L., 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, (2010), Springer), 1-40
[82] Achterberg, T.; Wunderling, R., Mixed integer programming: analysing 12 years of progress, (Jünger, M.; Reinelt, G., Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, (2002), Springer), 449-481 · Zbl 1317.90206
[83] Gurobi Optimization, Inc., Gurobi optimizer reference manual, http://www.gurobi.com, 2014.
[84] Sellmann, M.; Van Hentenryck, P., Structural symmetry breaking, (Proceedings of 19th International Joint Conference on Artificial Intelligence, IJCAI, (2005)), 298-303
[85] Bödi, R.; Grundhöfer, T.; Herr, K., Symmetries of linear programs, Note Mat., 30, 1, 129-132, (2010)
[86] T. Berthold, M. Pfetsch, Detecting orbitopal symmetries, 2009. · Zbl 1209.90260
[87] Noessner, J.; Niepert, M.; Stuckenschmidt Rockit, H., Exploiting parallelism and symmetry for map inference in statistical relational models, (Proceedings of the 27th AAAI Conference on Artificial Intelligence, AAAI, (2013))
[88] Mladenov, M.; Globerson, A.; Kersting, K., Efficient lifting of MAP LP relaxations using k-locality, (Proceedings of the 17th Int. Conf. on Artificial Intelligence and Statistics, AISTATS, J. Mach. Learn. Res. Workshop Conf. Proc., vol. 33, (2014))
[89] Mladenov, M.; Globerson, A.; Kersting, K., Lifted message passing as reparametrization of graphical models, (Proceedings of the 30th Int. Conf. on Uncertainty in Artificial Intelligence, UAI, (2014))
[90] Lu, T.; Boutilier, C., Value-directed compression of large-scale assignment problems, (Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI, (2015))
[91] Bi, J.; Bennett, K.; Embrechts, M.; Breneman, C.; Song, M., Dimensionality reduction via sparse support vector machines, J. Mach. Learn. Res., 3, 1229-1243, (2003) · Zbl 1102.68531
[92] Demiriz, A.; Bennett, K.; Shawe-Taylor, J., Linear programming boosting via column generation, Mach. Learn., 46, 1-3, 225-254, (2002) · Zbl 0998.68105
[93] Conitzer, V.; Sandholm, T., Computing the optimal strategy to commit to, (Proceedings 7th ACM Conference on Electronic Commerce, EC, (2006)), 82-90
[94] Saraswat, V.; Gupta, V.; Jagadeesan, R.; Panangaden, P.; Precup, D.; Rossi, F.; Sen, P., Probabilistic constraint programming, (Working Notes of the 2014 NIPS Workshop on Probabilistic Programming, (2014))
[95] Bach, S.; Broecheler, M.; Getoor, L.; O’leary, D., Scaling MPE inference for constrained continuous Markov random fields with consensus optimization, (Proceedings of the International Conference on Neural Information Processing Systems, NIPS, (2012)), 2654-2662
[96] Airola, A.; Pyysalo, S.; Björne, J.; Pahikkala, T.; Ginter, F.; Salakoski, T., All-paths graph kernel for protein-protein interaction extraction with evaluation of cross-corpus learning, BMC Bioinform., 9, Suppl. 11, S2, (2008)
[97] Suzuki, J.; Hirao, T.; Sasaki, Y.; Maeda, E., Hierarchical directed acyclic graph kernel: methods for structured natural language data, (Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, ACL, (2003)), 32-39
[98] Haussler, D., Convolution kernels on discrete structures, (1999), UC Santa Cruz, Tech. rep., UCSC-CRL-99-10
[99] Gärtner, T., Exponential and geometric kernels for graphs, (Working Notes of the NIPS Workshop on Unreal Data: Principles of Modeling Nonvectorial Data, (2002)), 49-58
[100] Horváth, T.; Gärtner, T.; Wrobel, S., Cyclic pattern kernels for predictive graph mining, (Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, (2004)), 158-167
[101] Borgwardt, K. M.; Kriegel, H.-P., Shortest-path kernels on graphs, (Proceedings of the 5th IEEE International Conference on Data Mining, ICDM, (2005))
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.