Welcome to this AI 101 video on Case Based Reasoning. I'm Tommy Thompson and this is
AI and Games. In this video we're going to give a brief overview of case based reasoning
as a methodology; How does it work? Where and why is it used? As well as give you a
bit of an understanding of where the interesting problems exist when building a system of your
own.
First up, let's explain what Case Based Reasoning is. Case Based Reasoning is an automated reasoning
and decision making process whereby we solve new problems through the experiences we've
accumulated in solving previous ones. This is achieved by accumulating data to build
a model of understanding of a problem we're trying to solve. By storing the conditions
of the problem and the actions taken at that time, we establish a collection of rules that
dictate when in a given situation, we have one or more actions to resolve it. The system
is then focussed on recognising the similarity of new problems to existing ones, but also
how to manage that collection of accumulated data.
While we're interested in the AI methodology, Case Based Reasoning stems largely from the
manner in which humans conduct problem solving and has correlations within cognitive science.
We face a variety of decision problems in every day of our lives, but seldom worry about
how to resolve them unless they are entirely new to us. If we're entering a coffee shop,
we know how to get inside the building by opening the door. You don't question it given
you learned at an early age how to open doors and as such, getting into the shop doesn't
prove a problem: you just open the door and go in and order your coffee. The door might
not look the same as other doors you've opened, but you understand that it's a door and know
how a door works. Even if you're in a foreign country and don't know the language, you will
approach the ordering of a coffee in much the same way you would do in your homeland.
Given the way in which a barista and customer interact during the transaction doesn't really
change when ordering in a different country. The hard part is overcoming the language barrier
at specific moments. In this case, you made a judgement based on prior knowledge to order
your coffee in Paris, Rome or Berlin in much the same way you would do if you were in your
favourite coffee shop in London. I have solved this problem before, so I will do roughly
the same thing as last time and try to work around the language barrier.
The same principle often applies in video games: with specific tropes established throughout
games such that we repeat actions in the same or different games with an intended outcome.
If we have an enemy moving towards us in a platforming game, we'll often jump over or
onto it. We build an understanding of when jumping on an enemy proves to be the best
outcome versus jumping over it. When we meet similar situations again in the future, we
know how to tackle it. This is a critical aspect of how games are designed: we want
players to memorise patterns of behaviour that yield positive outcomes and make them
repeat those patterns throughout the game in similar or different contexts. If this
isn't properly established, the game can become confusing as we try to solve a puzzle that
we're simply not prepared to deal with as we've not had prior experience that reinforces
our understanding of it.
Case Based reasoning is a good to apply when you have a situation that requires diagnosis,
prediction, classification or recommendation. As such it has assumed a role in industries
that was previously covered by rule-based expert systems: a more rigid approach to the
same problem that proved popular in the 1970s and 1980s. However, as we'll discuss later,
CBR has effectively replaced it given it's ability to adapt and change its knowledge
base over time, meaning its learning. In addition, expert systems typically have a domain model:
where some high-level language is used to express data terminology in a set-theoretic
language. Whereas CBR doesn't require data to be modelled in such a way and can be far
more coarse and data-driven, ultimately being reduced to a bunch of numbers.
As such, there are applications of CBR in situations such as medical diagnosis, vehicle
fault diagnosis and repair and anticipating court case outcomes based on legal precedents
and even fraud detection given that in each case there is existing data that would allow
us to identify what to do in a given situation. Though perhaps the most common applications
that people are familiar with is recommendation systems you see in the likes of Amazon and
Netflix.
In practice, CBR is focussed on the management of cases: a set of of pairings of a given
situation or state x, with action or decision y. These cases are collated and stored over
time, typically with the collection growing in size and scale over time. This collection
of cases allow for us to build up more options for making decisions in given situations.
We can then in practice use that collection to find actions to make by finding previously
recording situations that are similar to one we're in now.
So for this to work, case based reasoning is structured as a four-step process, sometimes
referred to as the 4R's: retrieval, reuse, revision and retention. Each of these phases
either interacts with the collection of cases: either editing this collection or retrieving
actions from it to make. This means that the case collection is constantly being edited
as the system is being searched for appropriate actions based on current situations, combined
with updating it to highlight whether a particular case proved useful in a given context as well
as adding new cases when it seems clear that the current situation has very little relation
to anything we've already stored.
So to cover the 4R's in a little more detail, let's walk through each of them:
Retrieval is the process of finding a case that is similar to our current situation or
state. This relies on an ability to assess any two states based on their applicability.
Reuse is when we retrieve a case and propose it as a valid action to apply in our current
state.
Revision is when we evaluate through a series of metrics or simulations how well the proposed
action will perform and whether it is practical to apply it in the particular case we're in.
This sometimes results in some revision of the action to fit the current context.
Then lastly, retention is applied after a successful execution by storing the result
of this experience in memory. This is useful when you've revised the proposed solution,
given it's now clearly an individual case.
These 4R methods provide a decision making system that can generalise its previous experiences:
allowing you to apply decisions made in similar but not identical circumstances to new situations.
Coming back to the coffee shop example, you can continue to open that door and order your
coffee irrespective of where the door is and the layout of the coffee shop because it's
roughly the same problem each time. Even when the situation differs, like you're baking
different types of cake, you can often apply the same rules to get your desired outcome.
The secret sauce is how the model is stored and your metrics for comparing cases in the
system, as well as comparing cases to the current state of your problem. We would typically
store the states of our case bases as n-dimensional real vectors: or rather one or more collection
of real numbers. This is useful given it allows you to quickly run 'similarity measures' across
two distinct cases to check whether they're compatible with one another. These similarity
measures often act like heuristics in classic AI search: given they're applying expert knowledge
against the dataset to infer some understanding of their similarity in a given problem.
But even with the similarity measures there are still lots of small, nuanced issues that
need to be addressed: how to tweak cases that are not 100% fit for the task at hand, when
to add new cases or delete old ones and tweaking the similarity measures being used. This is
where machine learning approaches can be applied to automate that process and save the life
and soul of a poor subject expert, who would otherwise have to do it all by themselves.
As such, you could craft an ever growing and adapting system that learns from it experiences
over time.
And that's it for our AI 101 on Case Based Reasoning. If you'd keen to see how this can
be applied, check out my case study on how Killer Instinct's shadow AI clones a players
behaviour and replicates in a non-player character. I've Tommy Thompson and you've been watching
AI and Games: a series on artificial intelligence supported on patreon.com. If you found this
video useful, head on over to patreon.com and find out more about our content. Thanks
for watching.