Machine Learning

Machine Learning research at York focuses on statistical relational learning, reinforcement learning, Bayesian networks and other graphical models and natural language learning.

Graphical models use graphs to represent probabilistic interactions between variables modelling a given situation. The most popular sort of graphical model is a Bayesian network which uses a directed graph; in certain circumstances Bayesian networks can represent causal relations between variables. A key problem is to how to get hold of a graphical model in the first place. Machine learning offers a solution where graphical models are inferred from data drawn from the situation being modelled. For this task we have developed the GOBNILP software for exact Bayesian network learning.

- Nuala Sheehan, Mark Bartlett and James Cussens. Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees. Theoretical Population Biology, 97:11-19, 2014.
- Chris J. Oates, Jim Q. Smith, Sach Mukherjee and James Cussens. Exact Estimation of Multiple Directed Acyclic Graphs. Arkiv 1404.1238, April 2014.
- Lilia Costa, Jim Smith, Thomas Nichols, James Cussens, Eugene P. Duff and Tamar R. Makin. Searching Multiregression Dynamic Models of Resting-State fMRI Networks using Integer Programming. Bayesian Analysis. Posted online 2014-10-28.
- James Cussens. Integer Programming for Bayesian Network Structure Learning. Quality Technology and Quantitative Management, 11(1):99-110, March 2014.
- Mark Barlett and James Cussens. Advances in Bayesian Network Learning using Integer Programming. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013). 182-191, 2013.
- James Cussens, Mark Bartlett, Elinor M. Jones and Nuala A. Sheehan. Maximum Likelihood Pedigree Reconstruction using Integer Linear Programming. Genetic Epidemiology, 37(1):69-83, Janary 2013.
- James Cussens. Bayesian network learning with cutting planes. In Fabio G. Cozman and Avi Pfeffer, editors, Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), pages 153-160, Barcelona, 2011. AUAI Press.
- Mark Bartlett, Iain Bate, James Cussens and Dimitar Kazakov. Probabilistic Instruction Cache Analysis using Bayesian Networks. Proceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011)
- Mark Bartlett, Iain Bate, and James Cussens. Instruction cache prediction using Bayesian networks. In Proc. ECAI 2010 - 19th European Conference on Artificial Intelligence, pages 1099-1100, 2010. Short paper.
- Mark Bartlett, Iain Bate, and James Cussens. Learning Bayesian networks for improved instruction cache analysis. In Proceedings of the Ninth International Conference on Machine Learning and Applications (ICMLA 2010), pages 417-423. IEEE, 2010.
- James Cussens. Maximum likelihood pedigree reconstruction using integer programming. In Proceedings of the Workshop on Constraint Based Methods for Bioinformatics (WCB-10), Edinburgh, July 2010.
- James Cussens. Bayesian network learning by compiling to weighted MAX-SAT. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI 2008), Helsinki, 2008.
- Nicos Angelopoulos and James Cussens. Bayesian learning of Bayesian networks with informative priors. Annals of Mathematics and Artificial Intelligence, 54(1):53-98, 2008.

A common approach to graphical model learning is to define a score
measuring how well any given graphical model is
supported by observed data. The problem then reduces to
finding a graphical model with the highest
score. Finding such a model is known to be an NP-hard
problem. This motivates using optimisation approaches
such as integer linear programming or weighted MAX-SAT
solvers to do the searching. An MRC project *A
graphical model approach to pedigree construction using
constrained optimisation* started Oct 2011. This is a
joint project with Leicester and Bristol which uses
integer linear programming to induce Bayesian networks
representing 'pedigrees' (family trees).

- Nuala Sheehan, Mark Bartlett and James Cussens. Improved Maximum Likelihood Reconstruction of Complex Multi-generational Pedigrees. Theoretical Population Biology, 97:11-19, 2014.
- Chris J. Oates, Jim Q. Smith, Sach Mukherjee and James Cussens. Exact Estimation of Multiple Directed Acyclic Graphs. Arkiv 1404.1238, April 2014.
- Lilia Costa, Jim Smith, Thomas Nichols, James Cussens, Eugene P. Duff and Tamar R. Makin. Searching Multiregression Dynamic Models of Resting-State fMRI Networks using Integer Programming. Bayesian Analysis. Posted online 2014-10-28.
- James Cussens. Integer Programming for Bayesian Network Structure Learning. Quality Technology and Quantitative Management, 11(1):99-110, March 2014.
- Mark Barlett and James Cussens. Advances in Bayesian Network Learning using Integer Programming. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013). 182-191, 2013.
- James Cussens, Mark Bartlett, Elinor M. Jones and Nuala A. Sheehan. Maximum Likelihood Pedigree Reconstruction using Integer Linear Programming. Genetic Epidemiology, 37(1):69-83, Janary 2013.
- James Cussens. Bayesian network learning with cutting planes. In Fabio G. Cozman and Avi Pfeffer, editors, Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), pages 153-160, Barcelona, 2011. AUAI Press.
- James Cussens. Maximum likelihood pedigree reconstruction using integer programming. In Proceedings of the Workshop on Constraint Based Methods for Bioinformatics (WCB-10), Edinburgh, July 2010.
- James Cussens. Bayesian network learning by compiling to weighted MAX-SAT. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI 2008), Helsinki, 2008.

In collaborative with the Real-time systems group, we have been learning BNs to model worst-case execution times. A particular focus has been on modelling cache hits and misses.

- Mark Bartlett, Iain Bate, James Cussens and Dimitar Kazakov. Probabilistic Instruction Cache Analysis using Bayesian Networks. Proceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2011)
- Mark Bartlett, Iain Bate, and James Cussens. Instruction cache prediction using Bayesian networks. In Proc. ECAI 2010 - 19th European Conference on Artificial Intelligence, pages 1099-1100, 2010. Short paper.
- Mark Bartlett, Iain Bate, and James Cussens. Learning Bayesian networks for improved instruction cache analysis. In Proceedings of the Ninth International Conference on Machine Learning and Applications (ICMLA 2010), pages 417-423. IEEE, 2010.

Statistical relational learning (SRL) is a branch of machine
learning which aims to combine the strengths of probabilistic
and relational representations. At York the focus is on
*first-order logic* to represent relations, and so our
brand of SRL is *probabilistic inductive logic programming (PILP)*.

Despite the current great interest in SRL, there remains considerable debate about how best to achieve this integration. One useful avenue of research is to approach this from a Bayesian point of view, since this reduces statistical inference to probabilistic inference.

- James Cussens. Approximate Bayesian computation for the parameters of PRISM programs. In P. Frasconi and F.A. Lisi (Eds.): ILP 2010, LNAI 6489, pp. 38--46. Springer, Heidelberg (2011).
- James Cussens. On generative parameterisations of Markov logic networks. In Proc. SRL 09, Leuven, July 2009.
- Vítor Santos Costa, David Page, and James Cussens. CLP(BN): Constraint logic programming for probabilistic knowledge. In Luc De Raedt, Paolo Frasconi, Kristian Kersting, and Stephen Muggleton, editors, Probabilistic Inductive Logic Programming, volume 4911 of Lectures Notes in Computer Science, pages 156-188. Springer, Berlin, 2008.
- James Cussens. Logic-based formalisms for statistical relational learning. In Lise Getoor and Ben Taskar, editors, Introduction to Statistical Relational Learning. pages 269-290, MIT Press, Cambridge, MA, 2007.
- James Cussens. Model equivalence of PRISM programs. In Proceedings of the Dagstuhl seminar: Probabilistic, Logical and Relational Learning - A Further Synthesis, 2007. (Associated talk given at CS Dept, KU Leuven, Belgium.)
- James Cussens. Individuals, relations and structures in probabilistic models. In Lise Getoor and David Jensen, editors, IJCAI Workshop on Learning Statistical Models from Relational Data (SRL2003), pages 32-36, Acapulco, Mexico, August 2003.
- James Cussens. Attribute-value and relational learning: A statistical viewpoint. In Luc De Raedt and Stefan Kramer, editors, Proceedings of the ICML-2000 Workshop on Attribute-Value and Relational Learning: Crossing the Boundaries, pages 35-39, 2000.

Graphical models such as Bayesian networks represent relations of conditional independence via the structure of a graph. SRL formalisms, such as the PRISM system, are capable of representing more complex conditional independence relations, and so graphs aren't enough. One promising avenue is to use algebraic statistics to analyse these more complex relations. Algebraic statistics is a sub-branch of algebraic geometry, so a nice bonus is the geometrical intuitions which it provides.

- James Cussens. Model equivalence of PRISM programs. In Proceedings of the Dagstuhl seminar: Probabilistic, Logical and Relational Learning - A Further Synthesis, 2007. (Associated talk given at CS Dept, KU Leuven, Belgium.)

SRL is a computationally demanding form of machine learning requiring both symbolic and numerical computation. An interesting route would be to implement SRL algorithms in the Mercury language. Roughly speaking, Mercury is strongly-typed Prolog which compiles to C (and thus to native code). Encouraging results have already been achieved for non-probabilistic ILP.

- James Cussens. Approximate Bayesian computation for the parameters of PRISM programs. In P. Frasconi and F.A. Lisi (Eds.): ILP 2010, LNAI 6489, pp. 38--46. Springer, Heidelberg (2011).
- Barnaby Fisher and James Cussens. Inductive Mercury programming. In Stephen Muggleton and Ramon Otero, editors, Inductive Logic Programming: Proceedings of the 16th International Conference (ILP-06), Santiago de Compostela, 2007. Springer.

- S. Devlin, M. Grzes, and D. Kudenko (2011): An Empirical Study of Potential-Based Reward Shaping and Advice in Complex, Multi-Agent Systems. In Advances in Complex Systems (ACS) 14(2).
- S. Devlin and D. Kudenko (2011): "Theoretical Considerations of Potential-Based Reward Shaping for Multi-Agent Systems", Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
- M. Grzes, D. Kudenko (2010): "PAC-MDP Learning with Knowledge-based Admissible Models", Ninth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).
- M. Grzes, D. Kudenko (2010): "Online Learning of Shaping Rewards in Reinforcement Learning", Neural Networks, 23(4).
- M. Grzes and D. Kudenko (2009). â€śReinforcement Learning with Reward Shaping and Mixed Resolution Function Approximationâ€ť. International Journal of Agent Technologies and Systems (IJATS), 1(2):36-54.
- M. Grzes, D. Kudenko (2008): "Plan-based reward shaping for reinforcement learning", Fourth IEEE International Conference on Intelligent Systems (IS).

Please see our page on natural language processing for information on machine learning of natural language.