## General-to-Specific Ordering of Hypotheses

In the last post, we said that all concept learning problems share 1 thing in common regarding their structure, and it is the fact that we can order the hypotheses from the most specific one to the most general one. This will enable the machine learning algorithm to explore the hypothesis space exhaustively, without having to enumerate through each and every hypothesis in this space, which is absolutely impossible when you have an infinitely large hypothesis space. Now, we will talk about the general-to-specific ordering and show you how we can use this to define a sense of order among our hypotheses in a hypothesis space in *any *concept learning problem.

As a reminder, take a look at our old example regarding Joe wanting to play golf on a specific day or not. Remember that we would like to learn the concept of Play about Joe.

Now, consider the following 2 hypotheses:

**h _{1} = <Rainy, Warm, Strong>**

**h _{2} = <Rainy, ?, Strong>**

The question is which instances and how many of them are classified positive by each one of these hypotheses (i.e., satisfy these hypotheses). For *h _{1}*, only example number 4 is satisfactory, while for

*h*, both example 3 and 4 are satisfactory and classified as positive. Why is that? What is the difference between these 2 hypotheses?

_{2}**. As you can see,**

*The answer lies into the strictness of the constraints that are imposed by each one of these hypotheses**h*imposes more constraints compared to

_{1}*h*! Naturally,

_{2}*h*is able to classify more examples as positive than

_{2}*h*! Actually, in this example, we can claim the following:

_{1}**“If an example could satisfy h _{1}, it will FOR SURE satisfy h_{2}, but NOT the other way around”**

This is because *h _{2} *is

**more general than**

*h*. This has been demonstrated below:

_{1}*h*encompasses more possibilities than

_{2}*h*. If we have an instance with the values:

_{1}**<Rainy, Freezing, Strong>**,

*h*will classify it as positive but

_{2}*h*will not be satisfied by it. But when

_{1}*h*classifies an instance as positive , say,

_{1}**<Rainy, Warm, Strong>**, then it is certain that

*h*will also classify it as positive.

_{2}## More-General-than-or-Equal-to Relationship

Let’s remind ourselves of 2 crucial definitions:

- For a given example
*x*in the instance space**X**, and a hypothesis*h*in the hypothesis space**H**, we say that*x*satisfies*h if and only if***h(x) = 1.** - We define the “
**more general than or equal to**” relationship between 2 hypotheses, and we base it on the sets of examples that satisfy each one of the 2 hypotheses.

Now, here is the long-awaited definition:

**Hypothesis h _{j} is more general than or equal to the hypothesis h_{k}, if and only if any instance x in the instance space X that can satisfy h_{k} (i.e., h_{k}(x) = 1) also satisfies h_{j} (i.e., h_{j}(x) = 1)**

We can show this relationship with the following notation:

**h _{j} ≥_{g} h_{k}**

Where **g** is short for **general**. There are cases where a hypothesis is more general than the other one, but * NOT *equal to it. Below you can see the definitions for both cases:

_{ }

Finally, there are cases where it just makes sense to look at the same definition but from a different angle. So, after understanding what * more general* means, we can also consider the other side of the spectrum. Meaning that, if hypothesis

*h*is more general than

_{k}*h*then we can say, equivalently, that

_{j}*h*is more specific than

_{j}*h*. This is just another way for saying the same thing.

_{k}## Let's Get More Visual, Shall We...

Let’s consider the following hypotheses from our table:

**h1 = <sunny, ?, strong>**

**h2 = <sunny, ?, ?>**

**h3 = <sunny, warm, ?> **

Now, based on what we learned regarding **≥ _{g}** relation, can you compare these hypotheses and determine which one is more general than or equal to the others?

If we look closely, we can see that all the instances that satisfy both h1 and h3, also satisfy h2, so we can say that:

h2 **≥ _{g}** h1 and h3

But what about the relationship between h1 and h3? Can we conclude anything regarding these 2? Yes we can, and here it is: Neither h1 nor h3 are more general than each other! Look closer and determine why this is the case!

**hint: ***You should find instances that can satisfy h3 but not h1 to prove that h1 is NOT more general than h3. Same story but the other way around to prove that h3 is not more general than h1.*

## Super Important Note!!!

Remember that both **≥ _{g}**

**and**

**>**relationships are defined

_{g}**absolutely INDEPENDENT of the target concept!**In both cases, we are interested in the instances that satisfy the hypotheses, regardless of their classification label (i.e., target concept value, ground-truth).

In the next post, we will focus on the algorithms that take advantage of both **≥ _{g}**

**and**

**>**relationships in order to make the search in the hypothesis space more efficient and basically practically feasible and smart.

_{g}**Best of Luck! ML-Dawn**

SSSN USHA DEVI NExcellent Explanation

mehran@mldawn.comPerfect