Justin Lloyd's Thinkering

Today I read a paper titled “Towards Flexible Teamwork”

The abstract is:
Many AI researchers are today striving to build agent teams for complex, dynamic multi-agent domains, with intended applications in arenas such as education, training, entertainment, information integration, and collective robotics.

Unfortunately, uncertainties in these complex, dynamic domains obstruct coherent teamwork.

In particular, team members often encounter differing, incomplete, and possibly inconsistent views of their environment.

Furthermore, team members can unexpectedly fail in fulfilling responsibilities or discover unexpected opportunities.

Highly flexible coordination and communication is key in addressing such uncertainties.

Simply fitting individual agents with precomputed coordination plans will not do, for their inflexibility can cause severe failures in teamwork, and their domain-specificity hinders reusability.

Our central hypothesis is that the key to such flexibility and reusability is providing agents with general models of teamwork.

Agents exploit such models to autonomously reason about coordination and communication, providing requisite flexibility.

Furthermore, the models enable reuse across domains, both saving implementation effort and enforcing consistency.

This article presents one general, implemented model of teamwork, called STEAM.

The basic building block of teamwork in STEAM is joint intentions (Cohen & Levesque, 1991b); teamwork in STEAM is based on agents’ building up a (partial) hierarchy of joint intentions (this hierarchy is seen to parallel Grosz & Kraus’s partial SharedPlans, 1996).

Furthermore, in STEAM, team members monitor the team’s and individual members’ performance, reorganizing the team as necessary.

Finally, decision-theoretic communication selectivity in STEAM ensures reduction in communication overheads of teamwork, with appropriate sensitivity to the environmental conditions.

This article describes STEAM’s application in three different complex domains, and presents detailed empirical results.

Today I read a paper titled “Boosting the Differences: A fast Bayesian classifier neural network”

The abstract is:
A Bayesian classifier that up-weights the differences in the attribute values is discussed.

Using four popular datasets from the UCI repository, some interesting features of the network are illustrated.

The network is suitable for classification problems.

Today I read a paper titled “Orderly Spanning Trees with Applications”

The abstract is:
We introduce and study the {\em orderly spanning trees} of plane graphs.

This algorithmic tool generalizes {\em canonical orderings}, which exist only for triconnected plane graphs.

Although not every plane graph admits an orderly spanning tree, we provide an algorithm to compute an {\em orderly pair} for any connected planar graph $G$, consisting of a plane graph $H$ of $G$, and an orderly spanning tree of $H$.

We also present several applications of orderly spanning trees: (1) a new constructive proof for Schnyder’s Realizer Theorem, (2) the first area-optimal 2-visibility drawing of $G$, and (3) the best known encodings of $G$ with O(1)-time query support.

All algorithms in this paper run in linear time.

Today I read a paper titled “Best-first Model Merging for Hidden Markov Model Induction”

The abstract is:
This report describes a new technique for inducing the structure of Hidden Markov Models from data which is based on the general `model merging’ strategy (Omohundro 1992).

The process begins with a maximum likelihood HMM that directly encodes the training data.

Successively more general models are produced by merging HMM states.

A Bayesian posterior probability criterion is used to determine which states to merge and when to stop generalizing.

The procedure may be considered a heuristic search for the HMM structure with the highest posterior probability.

We discuss a variety of possible priors for HMMs, as well as a number of approximations which improve the computational efficiency of the algorithm.

We studied three applications to evaluate the procedure.

The first compares the merging algorithm with the standard Baum-Welch approach in inducing simple finite-state languages from small, positive-only training samples.

We found that the merging procedure is more robust and accurate, particularly with a small amount of training data.

The second application uses labelled speech data from the TIMIT database to build compact, multiple-pronunciation word models that can be used in speech recognition.

Finally, we describe how the algorithm was incorporated in an operational speech understanding system, where it is combined with neural network acoustic likelihood estimators to improve performance over single-pronunciation word models..