Lesson 5.3. Concept Learning as Search

-

In the context of concept learning, the process involves searching through a hypothesis space to find the hypothesis that best fits the training examples. Let's use the house-buying scenario to illustrate this concept:

 Concept Learning in the House-Buying Scenario

In the house-buying scenario, Jordan decides whether to buy a house based on certain features:

1. Location: Urban (A), Suburban (B), Rural (C)

2. Budget: Within budget (Yes), Not within budget (No)

3. Size: Small, Medium, Large

4. Garden: Has garden (Yes), No garden (No)

5. Schools Nearby: Good schools nearby (Yes), No good schools nearby (No)

6. Public Transport: Convenient public transport (Yes), Inconvenient public transport (No)

 Instance Space (X)

- The instance space X consists of all possible combinations of these features. With the values given for each feature, the total number of distinct instances can be calculated as follows:

3*2*3*2*2*2 = 144

  (3 options for Location, 2 for Budget, 3 for Size, and 2 each for Garden, Schools Nearby, and Public Transport)

 Hypothesis Space (H)

- The hypothesis space H  includes all possible rules that can be formed using these features to decide whether to buy a house.

- Each feature can have specific values, be marked as "don't care" (indicated by "?"), or be marked as unacceptable (indicated by "0").

- For simplicity, let's assume that the unacceptable value ("0") is not used in this example. Then, the total number of syntactically distinct hypotheses can be calculated considering each attribute can take all of its possible values plus a "don't care" option:

(3+1)*(2+1)*(3+1)*(2+1)*(2+1)*(2+1) = 1296

  This results in a significantly large hypothesis space, though not all hypotheses may be semantically distinct.

 Searching the Hypothesis Space

- Learning in this context involves searching through  H to find a hypothesis that best explains the instances in X based on Jordan's preferences.

- For example, if Jordan has seen several houses and decided on each whether it's a buy or not, a learning algorithm would try to find a hypothesis that matches these decisions.

- This process could involve starting with a general hypothesis and specializing it based on the instances, or it could involve other search strategies like gradient descent in more complex spaces.

 Practical Application

- In real-world machine learning tasks, the hypothesis space can be very large or even infinite. Efficient search algorithms and heuristics are necessary to navigate this space.

- The chosen hypothesis representation (like decision trees, neural networks, etc.) limits the kinds of hypotheses that can be expressed and learned. The design of this representation is crucial in defining the learning algorithm's capabilities.

 Conclusion

In summary, concept learning in the house-buying scenario involves defining a space of possible instances (combinations of house features) and a space of hypotheses (rules to decide on buying). The learning task is to search through the hypothesis space to find the rule that best matches Jordan's preferences based on the examples he has encountered.

Comments

Post a Comment

Popular posts from this blog

ANN Series - 10 - Backpropagation of Errors

-
Image
Watch the video to understand the forward pass in an ANN. Backpropagation, short for "backward propagation of errors," is a fundamental algorithm used for training artificial neural networks. It efficiently computes the gradient of the loss function with respect to the weights of the network, which is essential for adjusting the weights and minimizing the loss through gradient descent or other optimization techniques. The process involves two main phases: a forward pass and a backward pass.     Forward Pass   1. Input Layer:  The input features are fed into the network. 2. Hidden Layers:  Each neuron in these layers computes a weighted sum of its inputs (from the previous layer or the input layer) plus a bias term. This sum is then passed through an activation function to produce the neuron's output. This process repeats layer by layer until the output layer is reached. 3. Output Layer:  The final output of the network is computed, which is then used to calculate the loss
Read more

Regression 10 - Pseudo-Inverse Matrix Approach - Relationship between MLE and LSA - Derivation

-
Pseudo-Inverse Matrix Approach: The pseudo-inverse matrix approach is essentially the OLS approach. It provides a solution to the linear regression problem by minimizing the sum of squared residuals between the observed and predicted values. This approach is a direct algebraic method that does not make any probabilistic assumptions about the residuals; it simply finds the best fit in the least squares sense.   For simple linear regression, the MLE estimates of the coefficients will actually be the same as the Ordinary Least Squares (OLS) estimates, which are also the same as what you get from the pseudo-inverse matrix method, under the assumption of i.i.d. normal errors. In this blog we show how to prove that  Maximization of likelihood function under conditional Gaussian noise for a linear model is similar to the minimization of the sum of the squares error function.  The complete derivation along with formulae used are provided. Ensure that you go through the previous blogs to get a
Read more

Regression 9 - Maximum Likelihood Estimation(MLE) Approach for Regression - Derivation

-
  MLE Approach: When performing linear regression using MLE under the assumption that the residuals (errors) are independently and identically distributed (i.i.d.) with a normal distribution, we estimate the regression coefficients that maximize the likelihood of observing the given data. In this blog we see how to perform regression on a dataset that applies MLE for model fitting. The mathematical assumptions and derivations are given in detail.   The MLE approach gives you point estimates for the coefficients (mean of the likelihood distribution), and you can also compute the variance-covariance matrix of these estimates, which gives you the variances (and covariances) of the estimates. These variances are a measure of the uncertainty or the spread of the likelihood distribution of the parameter estimates. For simple linear regression, the MLE estimates of the coefficients will actually be the same as the Ordinary Least Squares (OLS) estimates, which are also the same as what you get
Read more