Mellouk A., Chebira A. (eds.) Machine Learning
Подождите немного. Документ загружается.
Implicit Estimation of Another’s Intention Based on Modular Reinforcement Learning
393
The agents can carry the truck to a certain goal by cooperatively controlling Ω. The main
state variables are shown in Fig. 8. Internal reward function G
m
is defined as
(19)
where C is the position of the truck, and Goal
m
is the position of the m-th goal.
Fig. 7. Simple truck-pushing task by pair of agents
Fig. 8. State variables and parameters in task environment
5.2 Experiment 1: implicit estimation of another’s intention
Wwe fisrt conducted an experiment in which the Follower estimated the Leader’s goal,
where the Leader selected one of three sub-goals, and learned how to achieve the
collaborative task (Fig. 9, top). There were three goals, and the Leader changed its goals
from G
1
− > G
2
− > G
3
alternately every 1000 trials.
In contrast to simple reinforcement learning, the Follower agent not only has to learn the
policies for the goals but also the state for predictors the relationship between the current
situation and the internal goal by updating these parameters.
Machine Learning
394
The 1000 trajectories of the truck corresponding to all 1000 trials in this experiment are
shown in Figs. 10 and 11. Simple Q-learning with explicitly given internal goals and SSRL
are compared. Fig. 10 shows the results obtained from the experiment using Q-learning, and
Fig. 11 shows those from the experiment using SSRL. The task success rate is indicated in
each figure. The red curves represent the trajectories for the team that reached the goal, and
the gray curves represent the trajectories for the team that did not reach the goal. This shows
that simple Q-learning achieves a single task. However, the Follower could not coordinate
with the Leader agent after it had changed its goal because it could not discover the Leader
agent’s intentions. SSRL performs better when the Leader changes its intentions. Fig.13
shows that three predictors were generated that discover the Leader’s intentions.
Furthermore, Fig. 12 shows that appropriate internal goals were selected inside the Follower
agent.
Fig. 9. Top: cooperative action is acquired by Follower, bottom: plan toward the goal is
acquired by Leader
Fig. 10. Behaviors of truck at Follower’s learning stage with single Q-table and internal goal-
switching module without state predictors
Implicit Estimation of Another’s Intention Based on Modular Reinforcement Learning
395
Fig. 11. Behaviors of truck at Follower’s learning stage with SSRL
Fig. 12. Time course of probabilities where m-th internal goal is selected
Fig. 13. Time course of probabilities that environment being faced is the i-th situation
Machine Learning
396
Fig. 14. Reward function for Follower’s internal goals
These results show that SSRL enabled the Follower to implicitly estimate the Leader’s
intention.
5.3 Experiment 2: sequential collaborative task
After the follower had acquired the ability to implicitly estimate the leader’s intentions, the
next experiment was carried out. The experimental environment is shown at the bottom of
Fig. 9. The task required the agents to go through several checkpoints (sub-goals), and reach
the final goal. The Follower in the next experiment exploited the SSRL acquired through
Experiment 1, and the Leader explored and planed the path to the final goal. The Leader
agent can chose the next sub-goal out of three check points that correspond to three goals in
Experiment 1, i.e., “up,” “upper right,” and “right,” from the current checkpoint as shown in
Fig. 9. There are also two “cliffs” in this task environment. If the truck enters the cliffs, it can
no longer move. The Leader learned the path to the final goal by using a simple Q-learning.
The reward function for the Leader is shown in Fig. 15. Two kinds of Follower agents are
compared in this experiment. The first has a single Q-learning architecture and a perfect
internal goal switch. The second has SSRL.
Fig. 16 shows the results for the experiment using simple Q-learning. Fig. 17 shows the
results for the experiment using SSRL. Fig. 18 shows the success rate representing the
probability that the team will finally reach the final goal. The results reveal that the team
whose Follower agent could not discriminate the Leader’s intentions performed worse than
the team whose Follower agent could distinguish the Leader’s intentions. Without such a
distributed memory system like SSRL, the Follower would not be able to up with in the
Leader’s intentions. In addition to disadvantage, the poor performance of the Follower
agent adversely affects the Leader’s learning process. However, the Follower with SSRL
could estimate the Leader’s intentions and keep up with the Leader’s plans although there
was no explicit communication between the two agents.
Implicit Estimation of Another’s Intention Based on Modular Reinforcement Learning
397
Fig. 15. Reward function for Leader agent for planning path
Fig. 16. Behaviors of truck at Leader’s learning stage with single Q-table and internal goal
switching module without Situation Recognizer
However, the success rate for the collaborative task saturated at about 40%. The reason for
this is that the Follower notices changes in the Leader’s intentions after these changes have
sufficiently affected the state variables. The delay until the Follower becomes aware of the
changes is sometimes critical, and the truck occasionally fell into the cliffs. To estimate the
other’s intentions without any explicit signs outside the state variables, the information has
Machine Learning
398
Fig. 17. Behaviors of truck at Leader’s learning stage with SSRL
Fig. 18. Success rate for cooperative task
to be embedded in the state variables, which are the objectives of the team’s control task.
Our results suggest that it is not impossible to implicitly estimate the other’s intentions, but
it is important to have a communication channel whose variables are not related to the state
variables, which are the objectives of the task, e.g., voice, colar sign, or marker. This must be
the reason why we use explicit sign in collaborative tasks. As we mentioned, the “implicit
estimation” must back up and complement “explicit estimation.” “Explicit estimation” must
be faster and better than “implicit estimation” as far as a code table was shared in a team.
However, this does not mean “explicit estimation” is superior to“implicit estimation.” They
are complementary architectures.
Implicit Estimation of Another’s Intention Based on Modular Reinforcement Learning
399
6. Conclusion
We described a framework for implicitly estimating another’s intentions based on modular
reinforcement learning. We applied the framework to a truckpushing task by two agents as
a concrete example. In the experiment, the Follower agent could perceive changes in the
Leader’s intentions and estimate his intentions without observing any explicit signs on any
action outputs from the Leader. This demonstrated that autonomous agents can
cooperatively achieve a task without any explicit communication. Self-enclosed autonomous
agents can indirectly perceive the other’s changes in intentions from changes in their
surrounding environment. It is revealed that multiple internal models help an autonomous
agent to achieve collaborative task.
In the context of artificial intelligence, “symbol grounding problem” is considered as an
important problem. The problem deals with how robots and people can relate their
symbolic system to their physical and embodied experiences. The symbolic system
mentioned here is also used in communication, usually. Takamuku et al. presented a system
for lexicon acquisition through behavior learning which is based on a modified multi-
module reinforcement. The robot in their work is able to automatically associate words to
objects with various visual features based on similarities in features of dynamics[8]. At the
same time, Taniguchi et al. described an integrative learning architecture for spike timing-
dependent plasticity (STDP) and the reinforcement learning schemata model (RLSM) [12,
11]. The learning architecture enables an autonomous robot to acquire behavioral concepts
and signs representing the situation where the robot should initiate the behavior. They
called this process “symbol emergence.” The symbolic system plays a important role in
human social communication.They also utilize modular learning architecture to describe the
process of symbol organization. However, they treat bottomup organization of “explicit
symbols,” which is assumed to be used explicit communication.
In many researches, “symbolic communication” means exchanging discrete signals.
However, the essential point of symbolic communication is not such an externalized signs,
but an adaptive formation of “interpretant” from the viewpoint of Peirce’s semiotics.
Therefore, we focus on the implicit communication and its bottom-up process of
organization.
However, the system we treated in this chapter is constrained to some extent. This
framework for implicit estimates does not always work well. If the system does not satisfy
the assumptions made in Section 4, the framework is not guaranteed to work. The Leader’s
policies are fixed when the Follower agent is learning its policies, predictors, and network
connections in our framework. The model described in this chapter may not work in the
simultaneous multi-agent reinforcement learning environment. We intend to take these into
account in future work.
7. References
[1] K. Doya, N. Sugimoto, D. Wolpert, and M. Kawato. Selecting optimal behaviors based on
context. International symposium on emergent mechanisms of communication, 2003.
[2] Charles Hartshorne, Paul Weiss, and Arthur W. Burks, editors. Collected Papers of Charles
Sanders Peirce. Thoemmes Pr, 4 1997.
[3] M. Haruno, D.M.Wolpert, and M. Kawato. Mosaic model for sensorimotor learning and
control. Neural Computation, 13:2201–2220, 2001.
Machine Learning
400
[4] K. Murphy. Learning switching kalman-filter models. Compaq Cambridge Research Lab
Tech Report, pages 98–10, 1998.
[5] C.E. Shannon. A mathematical theory of communication. Bell System Technical Journal,,
27:379–423, and 623–656, 1948.
[6] R. Sutton and A.G. Barto. Reinforcement Learning : An Introduction. The MIT Press, 1998.
[7] Y. Takahashi et al. Modular learning syatem and scheduling for behavior acquisition in
multi-agent environment. In RoboCup 2004 Symposium papers and team description
papers, CD-ROM, 2004.
[8] Shinya Takamuku, Yasutake Takahashi, and Minoru Asada. Lexicon acquisition based
on object-oriented behavior learning. Advanced Robotics, 20(10):1127–1145, 2006.
[9] J. Tani, M. Ito, and Y. Sugita. Seif-organization of distributedly represented mulyiple
behavior schemata in a mirror system:reviews of robots using rnnpb. Neural
Networks,, 17:1273–1289, 2004.
[10] J. Tani and S. Nolfi. Learning to perceive the world as articulated: an approach for
hierarchical learning in sensory-motor systems. Neural Networks, 12:1131–1141,
1999.
[11] T. Taniguchi and T. Sawaragi. Symbol emergence by combining a reinforcement
learning schema model with asymmetric synaptic plasticity. In 5th International
Conference on Development and Learning, 2006.
[12] T. Taniguchi and T. Sawaragi. Incremental acquisition of behaviors and signs based on a
reinforcement learning schemata model and a spike timing-dependent plasticity
network. Advanced Robotics, 21(10):1177–1199, 2007.
[13] T. Taniguchi and T. Sawaragi. Incremental acquisition of multiple nonlinear forward
models based on differentiation process of schema model. Neural Networks,
21(1):13–27, 2008.
[14] C. Watkins and P. Dayan. Technical note: Q-learning. Machine Learning, 8:279–292, 1992.
[15] D.M. Wolpert, K. Doya, and M. Kawato. A unifying comuputational framework for
motor control and social interaction. Phil Trans R Soc Lond B, 358:593–602, 2003.
[16] D.M. Wolpert, Z. Ghahramani, and M. I. Jordan. An internal model for sensorimotor
integration. science, 269:1880–1882, 1995.
[17] D.M. Wolpert and M. Kawato. Multiple paired forward and inverse models for motor
control. Neural Networks, 11:1317–1329, 1998.
20
Machine Learning for Sequential Behavior
Modeling and Prediction
Xin Xu
Institute of Automation, National University of Defense Technology,
Changsha, 410073, China
1. Introduction
In the information era, as computer networks and related applications become more and
more popular, security problems are more and more serious in global information
infrastructure. It was reported that in the past two years, large amounts of network attacks
and computer viruses caused great damages to global economy and the potential threats to
the global information infrastructure have increased a lot. To defend various cyber attacks
and computer viruses, lots of computer security techniques have been studied, which
include cryptography, firewalls and intrusion detection, etc. As an important computer
security technique, intrusion detection [1,2] has been considered to be more promising for
defending complex computer attacks than other techniques such as cryptography, firewalls,
etc. The aim of intrusion detection is to find cyber attacks or non-permitted deviations of the
characteristic properties in a computer system or monitored networks. Thus, one of the
central problems for intrusion detection systems (IDSs) is to build effective behavior models
or patterns to distinguish normal behaviors from abnormal behaviors by observing collected
audit data. To solve this problem, earlier IDSs usually rely on security experts to analyze the
audit data and construct intrusion detection rules manually [2]. However, since the amount
of audit data, including network data, process execution traces and user command data, etc.,
increases vary fast, it becomes a time-consuming, tedious and even impossible work for
human experts to analyze dynamic, huge volumes of audit data and extract attack
signatures or detection rules. Furthermore, detection rules constructed by human experts
are usually based on fixed features or signatures of existing attacks, so it will be very
difficult for these rules to detect deformed or even completely new attacks.
According to the differences in the monitored data, IDSs can be mainly classified into two
categories, i.e., network-based intrusion detection and host-based intrusion detection.
Network-based intrusion detection observes data from network packets and extracts various
features from them, which usually include connection features, traffic features, and content
features. A systematic discussion on feature representation in network-based intrusion
detection can be found in [3]. For host-based intrusion detection, various observation data
from the corresponding operation systems are collected, which mainly include system call
data and shell command data [4], etc. Despite of having different observation data, both
host-based and network-based intrusion detection need to improve the detection accuracy
for large volumes and variability of normal and attack behaviors. Aiming at this problem,
Machine Learning
402
lots of research work has been devoted to develop intrusion detection systems (IDSs) using
various artificial intelligence (AI) methods and tools [3-5]. Thus, the motivations for
applying AI techniques in IDSs are due to large amounts of dynamic behaviors and the lack
of a priori knowledge for unknown attacks. How to establish appropriate behavior models
has been a central problem in the development of IDSs since the distinctions between
normal behaviors and computer attacks are usually very vague. In earlier research on IDSs,
it was very popular to separately construct behavior models either for normal usages or
attacks. To model intrusion behaviors alone is called misuse detection and anomaly
detection refers to establish profiles of normal usages. In misuse detection, behavior patterns
or models of known attacks are constructed and alarms are raised when the patterns of
observation data match the attack models. On the other hand, anomaly detection only
models the patterns of normal behaviors and detects any possible attacks as deviations from
the normal behavior model. Until now, although there have been many advances in misuse
detection and anomaly detection, some significant challenges still exist to meet the
requirements of defending computer systems from attacks with increasing complexity,
intelligence, and variability. For misuse detection, the inability of detecting new attacks is its
inevitable weakness and it is very hard to improve the performance of pure misuse
detection systems for the sake of increasing amounts of novel attacks. Although anomaly
detection has the ability of detecting new attacks, it usually suffers from high rates of false
alarms since it is very difficult to obtain a complete model of normal behaviors.
To solve the above problems in IDSs, machine learning and data mining methods for
intrusion detection have received a lot of research interests in recent years [4-10]. One
motivation for applying machine learning and data mining techniques in IDSs is to
construct and optimize detection models automatically, which will eliminate the tedious
work of human experts for data analysis and model building in earlier IDSs. To detect novel
attacks, several adaptive anomaly detection methods were proposed by employing data
mining methods based on statistics [7], or clustering techniques [10]. Recently, there have
been several efforts in designing anomaly detection algorithms using supervised learning
algorithms, such as neural networks [8], support vector machines [11], etc. In addition to
supervised or inductive learning methods for misuse and anomaly detection, another
approach to adaptive intrusion detection is to use unsupervised learning methods. Unlike
supervised learning methods, where detection models are constructed by careful labeling of
normal behaviors, unsupervised anomaly detection tries to detect anomalous behaviors
with very little a priori knowledge about the training data. However, as studied in [12], the
performance of pure unsupervised anomaly detection approaches is usually unsatisfactory,
e.g., it was demonstrated in [12] that supervised learning methods significantly outperform
the unsupervised ones if the test data contains no unknown attacks.
Despite of many advances that have been achieved, existing IDSs still have some difficulties
in improving their performance to meet the needs of detecting increasing types of attacks in
high-speed networks. One difficulty is to improve detection abilities for complex or new
attacks without increasing false alarms. Since misuse IDSs employ signatures of known
attacks, it is hard for them to detect deformed attacks, notwithstanding completely new
attacks. On the other hand, although anomaly detection can detect new types of attacks by
constructing a model of normal behaviors, the false alarm rates in anomaly-based IDSs are
usually high. How to increase the detecting ability while maintaining low false alarms is still
an open problem of IDS research.