crawled the Web.
The web site itself may have changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
Dynamic Re nement of Feature Weights Using Quantitative Introspective Learning
Dynamic Re nement of Feature Weights Using Quantitative
Introspective Learning
Zhong Zhang
and
Qiang Yang
School of Computing Science
Simon Fraser University
Burnaby B C
Canada V A S
Abstract
Recently more and more researchers have been
supporting the view that learning is a goal
driven process One of the key properties of
a goal driven learner is introspectiveness the
ability to notice the gaps in its knowledge and
to reason about the information required to
ll in those gaps In this paper we introduce
a quantitative introspective learning paradigm
into case based reasoning CBR The result is
an integrated problem solving model which will
learn introspectively feature weights in a case
base in order to be responsive dynamically to
its users In contrast to the existing qualitative
methods for introspective learning our model
has the advantage of being able to capture ac
curate learning information in the interactions
with its users A CBR system equipped with
quantitative introspective learning ability can
allow the feature weights to be captured auto
matically and to track its users changing pref
erences continuously In such a system while
the reasoning part is still case based the learn
ing part is shouldered by a quantitative in
trospective learning model Weight learning
and evolution are accomplished in the back
ground The e ectiveness of this integration
will be demonstrated through a series of em
pirical experiments
Introduction
Case based reasoning CBR is a problem solving strat
egy which uses stored previous cases to solve current
problems Kolodner
It has enjoyed tremen
dous success for solving problems related to knowledge
reuse Leake and Ram
Usually in a case base
a case s index is a set of important descriptors of the
case It can be used to distinguish a case from others
In many implementations these descriptors are repre
sented as feature value pairs and usually a feature is as
sociated with an importance value called
feature weight
to indicate how important it is in the case retrieval pro
cess When a new problem is presented its index will be
extracted and used to trigger a search in the case base
The cases with the most similar indices will be retrieved
for further consideration Kolodner
The performance of a CBR system depends on how to
use appropriate features to index cases and how to ob
tain an accurate measurement of the similarity between
cases in the case retrieval process Therefore the feature
weights play an important role in determining the suc
cess of CBR applications How to choose and maintain
an appropriate set of feature weights in a case base is a
non trivial problem in CBR research In addition the
relative importance of the cases is changing with time
partly due to the uneven and changing distribution of the
inherent problem space also partly due to the changing
interests of its users How to evolve a case base con
tinuously in an automated manner is also becoming an
urgent task of the knowledge base industry
One approach to tackling this problem is to use in
trospective learning which has a representation of its
own process in order to detect deviations that show
when the learning is needed as well as what the learning
needs Leake
et al
Ram and Cox
In the
past various introspective learning methods have been
employed in feature weighting in CBR systems Fox and
Leake
Leake
et al
Wettschereck
et al
Bonzano
et al
A main theme is to learn through
qualitative
introspective learning whereby the feature
weights are adjusted based on a rough estimate of the
direction
for a change if the weights are too high then
adjust them so that they become lower and vice versa
But how much has to be changed quantitatively is not
su ciently determined In this work we extend qual
itative introspective learning to quantitative introspec
tive learning within CBR With the quantitative learn
ing methods we can adjust the weights not only in the
right
direction
but also in the right
amount
We claim
that such an extension provides a sound and promising
continual weight introspective learning method in CBR
This paper is organized as follows In Section we
introduce some related work on the application of intro
spective learning to feature weighting Section presents
a novel quantitative introspective learning model inte
grated into case based reasoning In Section we demon
strate the experimental results for evaluating the perfor mance of our integrated model And also there we cross
validate our work with others Section concludes our
discussion where we will also explore our future work
Qualitative Introspective Learning
Methods
Leake et al Leake and Ram
summarize in a sym
posium report the goal driven learning process from var
ious aspects They indicate that one of the three key
properties of a goal driven learner is its
introspectiveness
an ability to notice the gaps in its knowledge and to rea
son about the information needed to ll in those gaps
They also pinpoint that introspective learning acquires
problem solving knowledge by monitoring its run time
performance seeking chances in this process to learn by
itself
In Fox and Leake
Fox et al describe their ex
periences with introspective learning in CBR The ROB
BIE system described is an application of an introspec
tive model to the task of re ning indexes used to retrieve
cases Its goal is to improve reasoning process when en
countering failures in its reasoning The introspective
learning component in the system monitors its reasoning
process by comparing it with a declarative model which
is used to describe the system s ideal reasoning process
Once a failure is found the model is used to create an
explanation of the failure in terms of other failed asser
tions and to suggest a repair The authors claim that
even under knowledge poor initial conditions the intro
spective learning of new feature indexes improves the
success rate of the system But they still indicate that
there exists a problem with the ordering of the presenta
tion of training cases to the system due to the inherent
shortcoming of their learning mechanism
As a variation of a model that is introduced in Munoz
Avilz and Huellen
Bonzano et al Bonzano
et al
also propose introspective learning as an approach
to feature weighting in CBR demonstrating their system
which combines introspective learning with CBR They
rst pose the problem with their experience in construct
ing a CBR system for Air Tra c Control The problem
encountered is that it is di cult to determine the impor
tant features and adjust their relative importance The
situation is further complicated by the fact that the fea
tures are highly context sensitive the predictiveness of
a feature depends heavily on the current context They
use so called
pulling
and
pushing
techniques to adjust
the feature weights Given a target T and two cases
A
and
B
if it is judged that
A
is a correct solution to T but
B
is not the learning method will
push
B
away from T
and
pull
A
closer to T As to its weight updating pol
icy their introspective learning method uses a decaying
learning process as shown in the following two formulae
increase
W
i
t
W
i
t
i
F
c
K
c
decrease
W
i
t
W
i
t
;
i
F
c
K
c
where K
c
represents the number of times that a case
has been
correctly
retrieved F
c
represents the number
of times that a case has been
incorrectly
retrieved and
i
determines the initial weight change The ratio be
tween F
c
and K
c
is used to reduce the in uence of the
weight update as the number of successful retrievals in
creases We can observe that the timing of triggering
the adjustment process is very important when to trig
ger the adjustment of the weights using the above two
formulae is a crucial issue yet to be further addressed
in the work This limitation makes it necessary to in
volve a human user in the learning process In contrast
instead of relying on a domain independent decaying fac
tor what we propose in this paper is a continual learning
process in the
lifetime
of the case based reasoner This
extension releases the human manager of the decision to
explicitly trigger a learning process
The second limitation of the work by Bonzano et al
is that it is qualitative in nature While the direction of
change in feature weights is indicated in the above two
formulae the amount of change is only in uenced by
the frequency of successes and failures and the decaying
factor A quantitative change would be needed to re ect
the amount of adjustment in proportion to the error
The third limitation reported by the authors is that
the learning method does not work well for pivotal cases
as the redundancy in a case base is essential in such a
learning process A pivotal case is the one that pro
vides coverage not provided by the other cases in a case
base Smyth and Keane
In contrast the quantita
tive introspective learning paradigm that we will present
in this paper will allow not only pairs of cases to be com
pared but also any number of cases to participate in the
learning process This is achieved through a process in
which a user can provide feedback at any time to all top
ranking cases not just to a few selected In Section
we will provide experimental comparisons between the
quantitative and q