Learning to Act in Relational Markov Decision Processes ( Khardon, Wang, Joshi )
Markov decision processes give a mathematical model for agents acting
in a dynamic environment. The agent's actions affect the world, it own
state, and whether it is "rewarded" or not. However, the results of
actions are not deterministic. In relational models, the state of the
world is best described by referring to objects and relations among
them. This is a very intuitive setting that matches many problems.
Our main interest is in developing agents that learn to act in a
useful way by utilizing various sources of information: examples from
a teacher, exploration by trial and error, utilizing a model of the
world etc. In previous work we have developed a theoretical model for
learning from examples, developed algorithms and analyzed them, and
developed a system L2Act for solving AI planning problem using this
framework. Our current work is focused on developing useful knowledge
representations for agents' internal representations (e.g. policies)
that lead to efficient and robust learning to act.
See the following papers (and publications page):
First Order Decision Diagrams for Relational MDPs
,
Proceedings of IJCAI 2007
Learning Action Strategies for Planning Domains
,
Artificial Intelligence Vol 113, 1999, pages 125-148.
Kernel Methods: robustness and applications to logic learning ( Khardon, Wachman, )
Kernel Methods give a generic way to apply certain learning methods
(maximum margin, perceptron, nearest neighbors) to domains with any
structure. The main tool is a kernel function which computes inner
products in some space, which serves as a virtual representation
space for examples. This amazing idea (known since 60s) is being
intensively investigated in the machine learning community.
Our previous work investigated the
scope and limitations of using kernel methods for logic learning.
This issue turns out to be tricky since there are nice kernel
constructions but they do not necessarily lead to successful
learning. Our current focus is on two issues:
kernel learning with relational data, and
identifying learning algorithms which
are robust to "noise" - a small amount of wrong annotation on training
data.
See the following papers (and publications page):
Learning from Interpretations: A Rooted Kernel for Ordered Hypergraphs
Proceedings of ICML 2007.
Noise Tolerant Variants of the Perceptron Algorithm
,
Journal of Machine Learning Research (JMLR)
8(Feb):227--248, 2007.
Efficiency versus Convergence of Boolean Kernels for On-Line
Learning Algorithms
,
Journal of AI Research (JAIR) 24(2005):341-356.
Automatic Classification of Stars in Astronomical Surveys ( Khardon, Wachman, Protopapas )
Huge amounts of data are now available from astronomy surveys where telescopes take measurements of the sky over a long period of time. This information is processed by experts as well as computers to provide high-level classifications and measurements of importance for astronomy. Our project aims to provide automatic methods for classifying astronomical measurements of stars using luminosity time-series measurements and other measurable properties of the stars. Such classification systems can save many expert-human-years and allow for faster paced scientific investigation. Our research develops and applies machine learning techniques for this project including combining multiple forms of data (including time-series measurements), work on kernels (related to the previous project since the data is structured), and providing interpretable results in an end to end prediction system. This work is done in collaboration with the Time Series Center at Harvard.
Mining Frequent Patterns (collaborators listed in articles)
The problem of ``mining frequent patterns'' is one of the most widely
studied problems in data mining. Here, given a database capturing some
activities (e.g. shopping lists in supermarkets) one searches for
patterns of activities (e.g. sets of items bought together) which
occur with sufficiently high frequency. This idea has been applied
in a variety of real world problems. Our previous work developed
formal complexity results for itemset mining, by showing an equivalence
to some problems of learning by asking questions, and developed a
new algorithm which is particularly efficient when
patterns sought are large.
Current work is focused on mining in
relational data. For example given a set of molecules described by
graphs (capturing a family of interest e.g. "high solubility", or
"effective drug") one would like to find frequent substructures in this
family.
See the following papers:
On Mining Closed Sets in Multi-Relational Data
,
Proceedings of IJCAI 2007
Discovering All Most Specific Sentences
,
ACM Transactions on Database Systems , Vol 28, pages
140-174, June 2003.
Learning Expressions in First Order Logic ( Khardon, Arias )
We are studying problems where a machine learning system sees examples
and produces hypotheses which are represented by logical
formulae. This generic framework fits many applications from learning
moves for Chess to identifying whether molecules will work well as
drugs. Our theoretical work aims to characterize the computational
complexity of these problems, i.e. how easy or hard they are to solve.
The work includes developing
algorithms which are provably correct and
efficient, and proving lower bounds that show limitations on the
efficiency of any algorithm for such problems.
See the following papers:
Learning Closed Horn Expressions,
Information and Computation Vol 178, 2002, pages 214-240.
The Subsumption Lattice and Query Learning
,
Journal of Computer and System Sciences Volume 72, Issue 1, Pages
72-94 (February 2006)
LogAn-H: a system for learning from relational data ( Khardon, Arias )
We have developed a system for learning from relational data
(e.g. from graphs). The system is pretty efficient, gives a non
traditional type of algorithm ("bottom up") based on the theoretical
results, and is a state of the art Inductive Logic Programming (ILP)
system. Current work is focused on solving large scale problems
involving classification of molecules. For an introduction see
links to the system below as well as:
Learning Horn Expressions with LogAn-H,
Journal of Machine Learning Research (JMLR)
8(Mar):549--587, 2007.
Grants:
The following grants supported this work in the UK:
EPSRC grant GR/M21409
Learning Approximation and Reasoning
EPSRC grant GR/N03167
Learning Relational Expressions for Natural Language Applications
Current Grants:
NSF grant IIS-0099446:
Learning and Reasoning with Relational Structures