Creating the whole story from bits and pieces
Eyal Amir
Eyal Amir creates theories about representing and using partial information. Partial information may range from observations of people's actions to the behavior of agents on the Web. "We live in a partially observable world," he said. "We can't see everything at every point in time. We have to make decisions based on what we know." What kind of knowledge can be gained from subsets of information? How can the information be better organized such that conclusions can be drawn? Amir is studying ways to represent information in such a way that computations can be performed on them to answer these kinds of questions.
One partial information system that Amir is modeling is a
variant of chess called Kriegspiel, or partially observable
chess. As if chess is not difficult enough, the player of
partially observable chess cannot see what her opponent is doing.
One can only draw conclusions from what the referee says, and
based on those one must guess where her opponent's pieces are
(especially the king!). For instance, the referee will let her
know if her opponent has attempted an illegal move, if she has
captured a piece, or if her king is in check. To study this
chess game, Amir's approach is to use some of the game's known
structure and which actions may be performed. "Encoding the game
explicitly is unfeasible because there are an essentially
infinite number of possible board positions, but we are using
some logical tools to represent what we know. Theoretically, the
first time you look at the problem, it looks impossible to
solve." All states with nonzero probability must be represented.
The first task is to detect which states are possible. "If you
start out with a piece of knowledge," he said, "the way that your
knowledge changes over time is not infinite. We can introduce
variables for pieces or positions whose identity we do not know,
and have the updated knowledge dependent on them. When we apply
automated reasoning tools to this information, we can conclude
that the positions possible for our opponent's pieces." In this
way, it can already be concluded that the problem is solvable for
some cases (e.g., a number of time steps is less than thirty,
starting from a full board) and that more information is needed
for strong answers to position queries. An important application
of this work is for tracking people and commodities. For
example, the locations of people after hurricane Katrina or the
recent tsunami in India, could be tracked using this
technique.
Making better decisions with the information you've got
Amir is also applying his theories to searching the Web. Any search engine must rely heavily on partial information. It constantly needs to update its crawl of Web pages, but cannot update all of them at the same time. It needs to decide, on the basis of only a subset of knowable information, which pages to refresh when. Currently, crawling models use a very simplistic model for updating Web pages, he explained. The Web pages are assumed independent, and there is a different probabilistic change frequency associated with every Web page.
A better model is needed to help predict when a Web page will change-one that uses the relationships among pages. "We want to absorb a lot of information and do some reasoning with it in such a way that the user can trust the process," said Amir. "What I do is use logical and probabilistic presentations to encode the knowledge before using it. The same techniques apply to formal verification of software and hardware as well as speech recognition and HCI (human-computer interaction) and machine learning."
Theories of partial knowledge are used by a variety of engineering disciplines. How to rout information reliably on a sensor network involves predicting reliability and security using partial information. The network might be detecting conversations among people, it might be seeing if there are tanks driving by, it might be monitoring the weather, or it might be all of these. "The reasoning about all of those sensors together is a probabilistic reasoning task," said Amir. "Is there rain or snow? Is the area blocked from movement? Can we send some trucks through that area? We can apply our technology to answer these questions."
In a consumer-oriented example, if you are a
price-conscious shopper at the Gap, you don't go in every day and
look for the best prices before buying. You have to decide when
to go and look. You may know when sales are going to happen from
advertising, or you might go on a certain day because it is
convenient. Maybe they'll have a sale that day, or maybe they
won't. But perhaps experience has told you that because the
Banana Republic store across the street is having a sale, the Gap
will have a sale the following week. "This is the kind of
information we get from a variety of sources, which provides us
with pieces of information that we need to make decisions," said
Amir. "My goal is to help people make better decisions, with
accuracy and speed."
Written by Judy Tolliver,
April 10, 2006
--
Last Modified August 07 2006 08:58:45.
