Partially observable stochastic games (POSGs) provide a rich mathematical framework for planning under uncertainty by a group of agents. However, this modeling advantage comes with a price, namely computation cost. Solving POSGs optimally quickly becomes intractable after a few decision cycles. Our main contribution is to provide bounded approximation techniques which enable us to scale POSG algorithms by several orders of magnitude. We study both the general POSGs and its cooperative counterpart DEC-POMDPs. Experiments on a number of problems confirm the scalability of our approach while still providing useful policies.

This paper focuses on the identification of human activity patterns in SecondLife (SL), a user-constructed virtual environment.SecondLife allows the users to create a virtual avatar,explore areas constructed by other users, socialize, and conduct financial transactions just as one would in the real world.However unlike the real world, new attractions can be constructed within hours and previous ones often fall into disuse rapidly. Without current information about the state of regions in the virtual world, it is difficult to infer the purpose of the user’s actions from location information. In this paper,we present an approach for gathering data on users’ activities and building a map of SecondLife annotated with information about activities that the users were able to perform in each region. Using this map, a recommender agent built into the user’s heads-up display can present suggestions of other areas to visit based on data collected from previous users. We discuss the the use of five supervised classifiers and report classification results for the map construction portion of the agent.

In this paper, we put forth the first join tree propagation algorithm  that selectively applies either arc reversal (AR) or variable elimination (VE) to build the propagated messages. Our approach utilizes a recent method for identifying the propagated join tree messages \`{a} priori. When it is determined that precisely one message is to be constructed at a join tree node, VE is utilized to build this distribution; otherwise, AR is applied as it is better suited to construct multiple distributions passed between  neighboring join tree nodes. Experimental results, involving evidence processing in  seven real-world and one benchmark Bayesian network,  empirically demonstrate that selectively applying VE and AR is faster than applying one of these methods exclusively on the entire network.

This paper extends the concept of trust modeling within a multi-agent environment.  Trust modeling often focuses on identifying the appropriate trust level for the other agents in the environment and then using these levels to determine how to interact with each agent.  However, this type of modeling does not account for sneaky agents who are willing to cooperate when the stakes are low and take selfish, greedy actions when the rewards rise.  Adding trust to an interactive partially observable Markov decision process (I-POMDP) allows trust levels to be continuously monitored and corrected enabling agents to make better decisions.  The addition of trust modeling increases the decision process calculations, but solves more complex trust problems that are representative of the human world.  The modified I-POMDP reward function and belief models can be used to accurately track the trust levels of agents with hidden agendas.  Testing demonstrates that agents quickly identify the hidden trust levels to mitigate the impact of a deceitful agent.

We compare two approaches to Bayesian network inference, called variable elimination (VE) and arc reversal (AR). It is established that VE never requires more space than AR, and never requires more computation (multiplications and additions) than AR.

The main task of part-of-speech (PoS) tagging is to assign the appropriate morphosyntactic category to each word in a sentence. A combination of different PoS taggers usually results in higher tagging accuracy than obtained by the use of only a single tagger. We present a new language and tagset independent system, CombiTagger, which combines automatically the output of several taggers. The system, which is open source, provides algorithms for simple and weighted voting, but it is extensible so that other combination algorithms can be added easily. We demonstrate the functionality of CombiTagger by using it to develop and evaluate combined taggers for Icelandic. The most accurate individual tagger obtains an accuracy of 91.83%. CombiTagger achieves 93.09%-93.41% accuracy by combining the output of five or six taggers using simple and weighted voting.

This paper introduces an information theoretic approach to verification of modular causal probabilistic models. We assume systems which are gradually extended by adding new functional modules, each having a limited domain knowledge captured by a local Bayesian network. Different modules originate from independent design processes. We assume that the local models are correct, which, however does not guarantee globally coherent inference in composed systems. The introduced method supports discovery of significant inter module dependencies which are ignored in the assembled Bayesian network.

While team action recognition has a relatively extended literature, less attention has been given to the detailed realtime analysis of the internal structure of the team actions.  This includes recognizing the current state of the action, predicting the next state, recognizing deviations from the standard action model, and handling ambiguous cases. The underlying probabilistic reasoning model has a major impact on the type of data it can extract, its accuracy, and the computational cost of the reasoning process. In this paper we are using Cascading Hidden Markov Models (CHMM) to analyze Bounding Overwatch, an important team action in military tactics. The team action is represented in the CHMM as a plan tree. Starting from real-world recorded data, we identify the subteams through clustering and extract team oriented discrete features. In an experimental study, we investigate whether the better scalability and the more structured information provided by the CHMM comes with an unacceptable cost in accuracy. We find the a properly parametrized CHMM estimating the current goal chain of the Bounding Overwatch plan tree comes very close to a flat HMM estimating only the overall Bounding Overwatch state (a subset of the goal chain) at a respective overall state accuracy of 95% vs 98%, making the CHMM a good candidate for deployed systems.

A discriminative large margin classifier based approach to anaphora resolution for neuroscience abstracts is presented. The system employs both syntactic and semantic features. A support vector machine based word sense disambiguation method combining evidence from three methods, that use WordNet and Wikipedia, is also introduced and used for semantic features. The support vector machine anaphora resolution classifier with probabilistic outputs achieved almost four-fold improvement in accuracy over the baseline method.

The increase in the number of complex temporal datasets collected today has prompted the development of methods that extend classical machine learning and data mining methods to time-series data.  This work focuses on methods for multivariate time-series classification. Time series classification is a challenging problem mostly because the number of temporal features that describe the data and are potentially useful for classification is enormous. We study and develop a temporal abstraction framework for generating multivariate time series features suitable for classification tasks. We propose the STF-Mine algorithm that automatically mines discriminative temporal abstraction patterns from the time series data and uses them to learn a classification model. Our experimental evaluations, carried out on both synthetic and real world medical data, demonstrate the benefit of our approach in learning accurate classifiers for time-series datasets.