Skip to main content
Loading Explore guides…
Rule-Based Machine Learning · Acedra
Home
Explore
Computer Science
Rule-Based Machine Learning
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
69 segments
Copy
Hide video
0:00
[Music] Hi I'm Ryan Urbanowicz and this is Part 7 of “Machine Learning Essentials for Biomedical Data Science”. In this video we'll take a look at how “rule-based” machine learning algorithms work. Here's a quick reminder of the parts making up this video series. In the last two videos, we covered specific machine learning algorithms including a variety of tree-based algorithms and neural network algorithms. Again we start by revisiting this diagram of better known
0:32
machine learning algorithms that can be applied or adapted to supervised learning problems. In the following slides we'll be learning about rule-based algorithms with a particular focus on learning classifier systems. While variations of these algorithms have been around since the 70s, it would be no surprise if you've never heard of them. Like all machine learning algorithms the ones I'll discuss in this video have distinct advantages and disadvantages. But the main reason
0:59
to consider including rule-based machine learning algorithms in your machine learning toolkit is because they offer an enticing combination of effective and interpretable modeling. In discussing rule-based machine learning and learning classifier system algorithms in this video, we will also briefly touch on “genetic algorithms” which we included in our other algorithms group here. “Evolutionary algorithms”, such as “genetic algorithms” and “genetic
1:25
programming” offer very flexible and open-ended framework for model discovery making them well suited to minimizing assumptions made during modeling. So let's dive into rule-based machine learning. Rule-based machine learning is in many ways an alternative paradigm of modeling where the problem space is modeled in a piecewise manner. Each piece of the model (in this case) is made up of individual rules and the model as a whole is a rule set. To visualize this, here on the right
1:56
we have some data points in a data set each with either class X or class O and we want to generate a model that correctly classifies instances. Instead of generating a single model capturing a decision boundary, or (as in the case with random forests) training an ensemble of complete models that could be combined with the vote, we will train a rule set where each rule represents a conditional piece of the overall model. In other words, each rule is only applicable to
2:26
making predictions on the instances in the data set that satisfies its conditions. So let's take a look at rules being discovered that capture this particular problem space in in a piecewise manner. Here, each box represents the piece of the problem space covered by a single discovered rule. Ideally in classification, each box will capture all (or mostly) just one of two classes. Ultimately,
2:53
this set of rules here identifies regions of the problem space that are predicted to be one class or the other. So what is the rule? As we saw in part 5 of this video series in our discussion of linearizing decision trees for interpretation, a rule is simply an IF:THEN expression that captures a conditional mapping between features and their values and the target outcome. So another super simple example of a rule might be something like: If the feature color is red and the feature
3:26
shape is octagon then a rule might predict stop sign when modeling traffic sign classification. This rule is considered conditional since the prediction “stop sign” is only asserted when a given instance has the feature values that match the “IF” part of the given rule. A number of machine learning algorithms exist that can all be grouped into what we call rule-based machine learning including “association rule mining”, popular in consumer analytics, “artificial immune
3:57
systems”, popular for anomaly detection, and “learning classifier systems”, focused on standard classification problems, which would be the focus of the rest of this video. First off, I'll be the first to admit that the name “Learning Classifier Systems”, abbreviated as “LCS”, which has been in use for over 40 years, does little to convey what these algorithms actually do. A better name might be something like; “evolutionary rule set learner”. But for this video we'll stick to the
4:26
traditional name of LCS. Let's start a discussion of LCS by looking at a really simple example rule set that might be trained on some biomedical data with both genetic and clinical features in it. Here we're trying to classify cases from control outcomes. This first rule indicates that; “IF” a genetic feature labeled as “SNP A” has a value of 0 and the body mass index of a patient is less
4:51
than 20, they are predicted to be a control. The next indicates that if a “SNP X” has a value of 1, then they are predicted to be a case. And the third rule, indicates that if a patient's BMI is between 30 and 40, then they are predicted to be a case as well. And so on. Note here that no single rule can be used as a model in itself and only when they are brought together as a rule set do
5:15
they form a model. Another thing to note, is that rules are not mutually exclusive. The parts of the problem space that each rule covers can overlap with other rules in the set allowing the model to more generalizably deal with ambiguous parts of the problem space. Some distinguishing aspects of LCS’s include that model (or in this case rule) discovery, is typically driven by an evolutionary
5:40
algorithm such as a basic genetic algorithm. If you're not familiar with evolutionary algorithms, these are algorithms directly inspired by the concepts of neo-Darwinian evolution where candidate models or in this case rules are akin to biological organisms that have a chance to survive and mate based on their fitness. And the mating of more fit individuals produces offspring models (or rules) that are ideally even more fit than their parents. These algorithms borrow concepts from
6:10
biological evolution, including the selection of more fit parents for the opportunity to reproduce, the genetic operators of recombination (in other words crossover and mutation), and survival of the fittest where in an environment with some maximum allowable population, the fit survive and the less fit are likely to die off. Another characteristic that is unlike other algorithms we've discussed,
6:36
is that LCS’s employ population-based search, meaning that a population of candidate solutions are explored, but only one model (or in the case of LCS’s), one subset of rules, will make up the final model. So what are the advantages of LCS’s as a machine learning modeling algorithm? As I already mentioned, compared to most popular machine learning algorithms to date, they are in many cases much more interpretable and explainable. However, it's fair to point
7:04
out that while some LCS variants are just as interpretable as decision trees, others are a bit less so. However what makes LCS’s really stand out in contrast with decision trees is that they are very well suited to modeling complex multivariate feature interactions as well as heterogeneous associations (as we talked about in our second video) Heterogeneous associations is a type of complexity that many machine learning algorithms struggle with. Furthermore, LCS’s are model free
7:33
which means that they avoid major assumptions of linearity or any other classification boundary shape assumptions, as well as not assuming that all features should be included in the final model. Furthermore, LCS has conveniently utilized both implicit and explicit generalization pressures to help avoid overfitting. And they're also regarded as an adaptable and updatable family of algorithms. Meaning that it's easy to improve the model with the addition of new data, without
8:04
having to train the model again from scratch. And lastly, these algorithms are extremely flexible in that they can be tweaked to handle all sorts of unique problems effectively. However, on the downside, as I've already indicated LCS’s are not widely known which unfortunately means there are very few people out there that use them or compare them to other machine learning algorithms in practice. Second, to date, there are relatively few LCS implementations available as software or
8:32
in machine learning packages such as scikit-learn. However, this is something that has been slowly changing as myself and other researchers in the field have been developing LCS implementations for easier use. Third, LCS’s like any evolutionary or stochastic open-ended algorithm, can be computationally expensive in contrast with many other algorithms. This can make conducting a hyper-parameter sweep quite expensive. But fortunately, LCS’s have only a couple key
9:00
hyper-parameters that we typically have to worry about. Fourth, if you're coming from a mathematics background you might be concerned with the fact that there is little theoretical work on LCS algorithms or evolutionary algorithms in general. This is kind of a catch-22 for LCS’s since the open-endedness of these algorithms is both what makes them effective for finding complex patterns
9:21
(other algorithms might miss) but also at the same time makes it almost impossible to mathematically prove if or when they will converge on an optimal solution. As such, the success of LCS to date comes primarily from empirical evidence applying them to both simulated and real-world data. Fifth, as mentioned some implementations of LCS aren't quite as interpretable as decision trees if that is your most important objective. And sixth, like many machine learning algorithms,
9:51
LCS’s are still vulnerable at least to some level of overfitting. So now let's explore the basics of how an LCS algorithm works starting with this overview schematic. As a quick note in this video we are focusing on what would technically be known as Michigan-style Learning classifier Systems: the most iconic and best studied LCS is to date. Okay, so LCS’s are an iterative algorithm, learning over
10:15
the course of many iteration cycles. The numbered black circles in the schematic trace the key steps comprising a single iteration. In the schematic all rectangles represent rule sets: here, here, here, and here. Ovals represent different components of the algorithms each responsible for different aspects of a learning cycle. Shapes in yellow denote data as either a data set or a single data instance. Ovals in green identify algorithm components responsible for discovering
10:47
new rules to add to the evolving rule population. Ovals in purple, denote other non-rule discovery components. And pink ovals, which will appear in a bit, will denote algorithmic components that play a role outside of the training cycle. So now let's quickly walk through the algorithm steps at a high level and then we'll talk about each more detail in subsequent slides. First in this yellow box we have our training data. Since LCS algorithms were originally designed to tackle
11:15
reinforcement learning problems, the data sources are commonly referred to (in the field) as the environment. Unlike most other machine learning algorithms, LCS is typically conduct a training iteration focused on one data point at a time. So before training it's important to shuffle the instances of the data to avoid potential biases and how the data was arranged. In step one of the learning iteration we grab the first instance from our training data. Step two passes
11:41
this training instance to the “rule population” which is the set of all rules currently included in our strengthening model. Typically, this rule population actually starts off empty and I'll explain how we get some initial rules in there in just a moment. For now just assume that our population already includes a bunch of rules. Step three is “matching” where we identify any rules in the current population that have a condition (in other words the “IF” part of the rule) that is
12:09
satisfied by the values of the current training instance. In step four, this subset of matching rules forms what we call the “match set” or set “M”. In step 5 we separate our match set into rules that predicted the correct class (of the current training instance) from those that are making an incorrect classification putting rules into either set “C” or set “I”, respectively. Now at this point, if no rules made it into our “correct set”, that means that there are no rules
12:38
in our population that covers that part of the problem space with an accurate prediction. As a result, step 6 activates a “covering” mechanism which basically randomly generates a new rule that both matches the current training instance and has the correct class prediction. This new rule is added both to the population and to our current correct set. However, since this randomly generated rule is just a guess, it's up to the downstream parts of the algorithm to decide if
13:07
this rule will be worth keeping or not. Covering is also how LCS initializes its rule population when starting out with an empty population. Early training iterations will activate covering frequently explicitly trying out rules that are relevant to instances in our training data. As a mechanism, covering is important because if we simply randomly initialize our rule population many of the rules might end up not matching any of the instances in our data set, thus being useless.
13:36
Next we move on to step 7 where we update the parameters of all rules that made it either into our correct or incorrect sets. With correct rules getting a boost in the parameters that control the rules fitness and incorrect rules being penalized. This constitutes “rule evaluation” which (of note) is different than “model evaluation” as we previously discussed in part 4 of this video series. Next, in step 8, LCS activates an explicit generalization mechanism that helps to
14:07
minimize overfitting. And then in Step 9, we have our most important rule discovery mechanism which is commonly driven by a simple genetic algorithm. This step involves picking two parent rules from the correct set where rules with a higher fitness have a better chance of being selected. Parent rules are then mated using crossover and mutation mechanisms to yield two new offspring rules which
14:31
have their parameters initialized before they're added to the rule population. The last step, is the deletion mechanism. This mechanism importantly selects rules from the population to be deleted where the least fit rules have the greatest chance of being deleted. This mechanism is activated whenever the size of the rule population is bigger than a user-specified maximum. This is an important LCS hyper-parameter that prevents the population from getting so
14:59
large that the algorithm slows down from the computational burden. At this point this learning cycle continues, again and again, picking the next instance from the data set each time. When it reaches the end of the data set the algorithm goes back to the top and cycles through the instances, again and again, until some algorithm stop criteria are met. The typical stop criteria is some maximum number of training iterations which is another key hyper-parameter of LCS’s. Once LCS
15:28
stops training, it's common to apply some post processing to the rule population called “rule compaction” which seeks to limit the final rule set down to some smaller yet still effective set of rules. Furthermore, once we have our final LCS model (being comprised of some subset of rules), we'll want to apply this model to be able to make predictions on new data. And for this we'll need a “prediction array”. Our new data might be some testing data to evaluate our model. And so now,
15:56
as before, the algorithm takes a testing instance from the data and passes it to the final rule population. Then as before, we employ matching to find our match set of rules. But now we pass this match set to a prediction array which chooses the predicted class based on the amount of rules that support one outcome or the other. Over the following slides I'll look at each of these steps in a little more detail to hopefully make this process a little clearer. So first let's look at
16:26
the training data and a visual representation of instances that I’ve assembled to better explain how LCS’s work. In this yellow box, each of these little cartoons represent individual instances in the data and each of the blue or orange half circles in each cartoon represent a feature in the data. So in this simple example we have 22 instances and 8 features. Let's look more closely at one of these instances. Again features in the data are ordered from left to right where each
16:56
feature can have a value of 0 or 1, illustrated by the colors orange and blue in this cartoon. Notably, in practice, the data doesn't have to include binary features like in this illustration. They can be categorical, with many possible values, or they can be quantitative. But for this explanation of LCS’s we'll make this simplifying assumption that all variables are binary. Attached to this cartoon representation of an instance is the outcome label, given as a hexagon,
17:24
where a white hexagon indicates a class of 0 and a black hexagon indicates a class of 1. In general, LCS algorithms are best suited to binary and multi-class classification. However, they have been extended to regression problems as well. Moving on to step two, we have our rule population. Let's zoom in on one of the cartoon representations of an individual rule. The first thing to reiterate here, is that in an LCS a single rule is not a model.
17:52
It's a set of rules that together constitute a piecewise model. We call the left side of the rule the rules “condition” and the right side of the rule its “action” (or the outcome prediction). As we've seen before, a rule is essentially an IF:THEN expression, or an “implication” from the field of logic. So more formally, we have “IF” the condition (or conditions) are satisfied, “THEN” this rule indicates the action to take or the class to predict. In this visualization,
18:22
any features that are specified as part of the condition are given as half circles filled in with the color blue or orange where (like for our instance cartoons) blue specifies the feature value of 1 and orange specifies the feature value of 0. So we can read this rule as follows: “IF” the fourth feature has a value of blue and the sixth and seventh features have a value of orange, “THEN” the predicted class is white. Next, let's talk about the features in the data set that were
18:53
not specified in this rule. These are represented by empty half circles with a hashtag in the gray boxes below them. Traditionally LCS algorithms have used the hashtag symbols to represent “wildcards” in a rule where the wildcard will satisfy any possible value for that given feature. These wild cards are an important part of how LCS algorithms train interpretable and generalizable models, as well as how they conduct internal features selection. If a feature in the data
19:23
is not useful for predicting outcome, then an LCS algorithm should learn to add a wildcard at that feature position for all or most rules. Now let's move on to step three, which is using matching to find rules in the population that have their conditions met by the current training instance. So, for this, we align the current training instance with each rule in the population. And we'll start with the rule that's already on the screen as an example. The first thing to note is
19:51
that during matching we don't care about either the true class of the instance or the predicted class of the rule. Instead, we just focus on the rules condition. Right off the bat, we know that all wild cards in the rule match automatically, so we can ignore them. And then we check each of the remaining specified feature values to make sure that they match (and in this case they do). So, this rule will be moved to the match set. Now let's look at an example where the rule doesn't
20:19
match the instance. So, this time will grab another rule from the population. And again, we have the same current training instance. We align them, ignore the outcome and rule prediction, and ignore all wild card features in the rule knowing that they automatically match. So now there are only two features left to check. The first one matches but the second one doesn't. So, this rule is not satisfied by the current training instance and so it's not passed to the match set.
20:48
Another thing to clarify is the difference between what we call a “rule” and what is considered to be a “classifier”, in an LCS algorithm. This here is a rule, as we've previously seen, made up of a condition and an action. However, a classifier is the rule linked to a number of rule parameters that are tracked and updated separately for each individual rule in the rule population. Typical
21:14
rule parameters include rule “numerosity”. This is the number of virtual rule copies that currently exist in the rule population. Since LCS’s don't allow multiple copies of the same rule to exist in the population whenever a mechanism tries to add a rule that already exists, the numerosity of the existing rule is increased. And if that rule is ever chosen to be deleted this numerosity is
21:39
decreased, but only when the numerosity of that rule reaches zero, is the rule entirely removed from the population. Next, there's “match count”. This simply tracks the number of times that a rule has been included in a match set over the course of learning. Then there's “correct count”. This tracks the number of times that the rule ended up in a correct set. And then we have the “accuracy” of the rule. This is the number of times it was in a correct set divided by the number
22:05
of times that it was in a match set. Of note, this is different than the standard accuracy of a model as we learned about in part 4 of this video series. Just because a rule has a high rule accuracy doesn't actually mean that it's a good rule. To illustrate this, imagine that the algorithm discovered a rule that only ever matches one instance in the entire data set. Assuming it predicted the correct class of that instance such a rule would have 100% rule accuracy,
22:34
but this rule would likely be overfitting that part of the problem space, since there is only one instance to support its value. The last key parameter we'll discuss here is fitness. In supervised learning classifier systems, the rule fitness is most commonly just some function of rule accuracy. For example rule accuracy to the power of five. Or in noisier problems it's usually best to leave this simply to be equivalent to the rule accuracy. Now let's review our LCS training
23:03
cycle so far. We begin with the training data, grab whatever instance is next and pass it to the current rule population. Then we apply matching to identify rules with a condition that is satisfied by the current training instance. These matching rules then form the match set of the current iteration. And the match set is further split into a respective correct and incorrect sets, based on whether the outcome (predicted by those rules) are the same as the current training
23:31
instance label. At this point, if the correct set is empty, the covering mechanism is activated. Let's look more closely at how the covering mechanism discovers a new rule to add to the current population and correct set. Here we have the current training instance and the backbone of a new rule that we will fill in, in a moment. Put simply, covering will initialize a rule by randomly generalizing an instance. So starting from the instance, we randomly pick some number of
23:59
features to specify in the rule. Note that these specified features have the same value as found in the training instance. If these features were quantitative instead of binary, LCS’s can instead specify a random value range in the rule (for each feature) that includes the observed value from the training instance. All remaining features are generalized with wild cards. And the predicted outcome of the rule becomes the outcome label of the current instance. As mentioned, a key
24:31
aspect of covering is that it only adds rules to the population that match at least one instance in the data. And this keeps the algorithm from searching irrelevant parts of the problem space. Back to our training cycle, we now have a correct set with at least one rule in it and an incorrect set that may or may not be empty. Now we conduct our parameter updates. Here all rules in the match
24:53
set have their parameters updated where rules in the correct set receive an accuracy and fitness increase and rules in the incorrect set receive decreases. Now let's take a quick moment to explain the “implicit generalization pressure” that LCS algorithms have but that most other algorithms do not. At the bottom of the screen, we have a few example rules that each specify a different number of feature values. Rules that specify fewer features are probabilistically
25:23
more likely to appear in match sets with a greater frequency. Of these three rules, this rule specifies the fewest features (in other words it's the simplest rule). Rules that more frequently end up in match sets inherently have a higher chance of being picked as parents by the genetic algorithm downstream. This observation yields an implicit evolutionary pressure that encourages the discovery of simpler or more general rules. Back to our algorithm schematic,
25:53
the next step is to apply “subsumption”, an explicit generalization pressure. Here we seek to illustrate the process of subsumption. In this visualization, we have three different rules that were each in the current correct set. The simpler and more generalized rule is the larger the problem space it's able to cover and typically the more instances it will match. We can see here that the rule covering the largest part of the problem space has only one feature specified. And rules
26:21
B and C each cover smaller parts of the problem space since each of them specify three features each. Note that both rules B and C specify the same feature specified in A. That means that rule A covers all the problem space of both B and C and beyond. However two of the features specified by B and C are different from one another. So the problem spaces they each cover may only be partially overlapping. With subsumption, we have an opportunity for one rule to consume another.
26:54
Where the consumer will increase in numerosity and the consumed rule will be removed entirely from the population. In order for subsumption to take place (for example between rule A and rule B), both rules have to have the same outcome (which is true here). Furthermore, for A to subsume B, A must completely cover the problem space that B covers, which again is true here. And lastly, for A to subsume B, A must be just as accurate as B. What this means is that
27:25
rule B specifies more features than is necessary to achieve the same accuracy. In other words, it's an overfit rule. So we explicitly remove B from the population and give rule “A” a larger chance of survival and a larger voice in making model predictions by increasing its numerosity. Consider here that while rule A would be eligible to subsume rule B, rule B would not be eligible to subsume rule C since it doesn't fully cover the same problem space. Back to our algorithm
27:56
schematic the next step in the training cycle is a more intelligent form of rule discovery. This time using a genetic algorithm. Let's look more closely at how the genetic algorithm discovers new rules based on existing ones. First, two parent rules need to be selected from the current correct set. Parent selection can be achieved in a number of ways including “roulette wheel” or “tournament selection”. Copies of the two selected parents are then used as templates for
28:24
the new offspring rules that will emerge. Next, “crossover” probabilistically decides whether to exchange feature specification versus wildcard generalization between the two selected rules. For example, here we have moved the specified blue value from the top rule down to the bottom and the specified orange value from the bottom rule to the top. This is then followed by a “mutation” which probabilistically decides whether to mutate feature specification or generalization at any
28:56
point in either rule. So in this example the top rule generalizes the second feature and specifies the third where this newly specified third feature value will correspond to the feature value in the current training instance. And again, this ensures that this new rule will still match the current training instance. And in the bottom rule, mutation has generalized the seventh feature. These new offspring rules have their parameter values initialized and then they're added to
29:22
the rule population. Back to our schematic, the final step in our training cycle is rule deletion. Basically here, whenever the size of our rule population becomes larger than the maximum allowed, then a rule is selected to be deleted until the rule population size is back to the maximum. Normally this maximum rule count is based on the sum of all rule numerosities in the current rule population. This means that if the rule population were set to 500,
29:50
that at the end of training, there will be many fewer actually unique rules in the population as many of them will have numerosities greater than one. The selection of a rule to delete is also probabilistic typically relying on something like roulette wheel selection. And this probability is inversely proportional to the fitness of rules. At this point we've walked through all typical
30:13
steps involved in the training of an LCS rule set. Don't forget that after training it's a good idea to compact the rule set or at least get rid of rules that have not seen all the training data or rules that are no more accurate than would be expected by random chance. And also, when it comes to applying your LCS set as a predictive model, the algorithm will use a prediction array, as
30:35
well as just these parts of the algorithm to make new predictions. Once you have a match set for a new testing instance, the prediction array makes a class decision based on how much support is given for one class or the other. The amount of support is based on the number numerosity and fitness of the rules predicting one class or the other. If you're interested in learning more about learning
30:57
classifier systems I'd first recommend you check out this 12 minute animated video on YouTube that will reiterate much of our discussion here but with more immersive animated visualization. And beyond that, myself and Professor Will Brown, who is currently chair of manufacturing robotics at the Queensland University of Technology, have previously collaborated to write this introductory textbook on LCS algorithms that includes a much deeper dive into this intriguing family
31:22
of machine learning algorithms. And furthermore, if you're interested in trying out LCS algorithms for yourself you can find scikit-learn compatible implementations of three different LCS algorithms on my lab's GitHub page here at this link. Thank you for joining me for part 7 of “Machine Learning Essentials for Biomedical Data Science”. In the next video, we'll move on for machine learning modeling to the next phase of our data science pipeline. Specifically, the elements of post
31:48
analysis. If you enjoyed this video please like and subscribe to follow my future content. [Music]
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat