1. If no discounting is used, the expected total utility is 1 + 2 + 3 = 6.

2. If γ = 0.5, the expected total utility is 1 + 2*0.5 + 3*0.5^2 = 2.75.

• If I'm at state a, I will exit and get reward of 10.
• If I'm at state b, I will move left because the sum of rewards is 10 (0+10).
• If I'm at state c, I will move left because the sum of rewards is 10 (0+0+10).
• If I'm at state d, I will move left because the sum of rewards is 10 (0+0+0+10).
• If I'm at state e, and have the option to move left or exit, I will move left because the sum of rewards is 10. quiz-policy1.png

Q2: For Y = 0.1:

• If I'm at state a, I will exit and get reward of 10.

• If I'm at state b, I will move left because the sum of discounted rewards is 1 (0+0.1 * 10). If I move right, the sum of discounted rewards is 0.001 (0.1^0*1).

• If I'm at state c, I will move left because the sum of rewards is 0.1 (0+0.1*0+0.1^2 * 10). If I move right, the sum of rewards is 0.001 (0+0.1 * 0+0.1^2 * 0+0.1^3 * 10).

• If I'm at state d, I will move right because the sum of rewards is 0.1 (0+0.1). If I move left, the sum of rewards is 0.001 (0+0.1 * 0+0.1^2 * 0+0.1^3 * 10).

Q3: Solving the linear equation 0Y+ 0Y^2 + 10Y^3 = 1*Y, we get Y = 0.316.

• In a certain point in time during the game, what states we have in terms of the score of the players. What about winning?. Look at this screenshot from a blackjack game:

• What are are the available actions for the user to take?

Q1 :

• Sates:

  • Each state has the player's current total hand value, the dealer's visible card value, and whether the player has a usable Ace or not.
  • The state space includes all valid combinations like: (7,14,False), (5,7,True). Each tuple represents the player's current sum, the dealer's facing card value, and whether or not the player has a usable Ace.
  • The possible values for the player's current sum range from 4 to 21. The minimum sum of 4 assumes scenarios where the lowest cards are drawn, like two 2s, and does not account for the flexibility of the Ace being used as 1 or 11. The dealer's facing card value can be any value from 1 to 10. The player's usable Ace can be either True or False.
  • The "bust" state is an extra state that happens when the player's total exceeds 21 (for example, the user has the cards 5 and 10, then draws another card whose value is 10. This will make a total of 25 (bust)).

• Actions: The actions available to a player in our model of Blackjack are typically "Hit" and "Stick"

Q2 :

• The reward structure in Blackjack is:

  • Winning a hand in Blackjack results in a reward equal to the bet placed. For simplicity, we can make a reward of 1 for the winning state.
  • Losing a hand results in losing the bet. For simplicity, we can make a reward of -1 for the losing state.
  • A draw results in a reward of 0 (no change in the player's money (the bet is returned)).

• The transition function in Blackjack defines the probability of moving to state s' after taking an action a. For example, the probability of reaching the state (17, 8, False) from the state (10, 8, False), when a hit action is taken, is modeled like this: P(s' = (17, 8, False) | s = (10, 8, False), a = 'hit') = 0.077. This probability assumes a reshuffled or effectively infinite deck where the likelihood of drawing a 7, with 8 such cards in a 104-card deck, remains constant.

Solving MDPs

Now that we have defined the MDP formalism, we can use it to solve reinforcement learning problems. The goal of the reinforcement learning agent is to maximize the expected total reward it receives by learning a policy π(s) that maps states to actions. So, given an MDP, how do we find the optimal policy? This is what we will learn in this lesson.

Policy

Recall that a policy is a function (π) that maps from the states to the actions. We say that we are executing some policy π if, whenever we are in state s, we take action a = π(s).

In our previous grid world example, an example of a policy is shown below:

π((1, 1)) = up
π((1, 2)) = up
π((1, 3)) = right
π((2, 1)) = left
π((2, 3)) = right
π((3, 1)) = left
π((3, 2)) = left
...

Thus, at any given state, the policy directs us on which action to take.

In a simple 4x4 grid world, there are 16 states and 4 actions per state. This results in 4₁₆ , which is over 4 billion possible policies.

Value Iteration Algorithm

There are different algorithms that can be used to find the optimal policy (solving MDPs). The algorithm we will use in this lesson is called value iteration.

Value iteration is a dynamic programming algorithm that computes the optimal state value function by iteratively improving the estimate of a value function V(s).

But, what is the value function V(s)? Let's find out.

Value Function V(s):

The value function V(s) tells us the expected total payoff (rewards) upon starting in a state s. These values are not known in advance. We have to learn them, as we will see later.

The optimal value function V*(s) is the maximum value function over all possible policies. If we can solve for the optimal value function V*(s), we can find the optimal policy π* which is the policy that maximizes the value function V*(s).

Here is an image that shows a sample value function output of each state:

Calculating the Values of the States

The value of each state is the expected total payoff (rewards) upon starting in that state. That is the immediate reward being at this state plus the discounted future rewards of the next states.

Which is equivalent to the general form using s and s' as follows: V(s) = E [ R(s) + γ * V(s')]

That means the value function of state s is the immediate reward R(s) plus the value function value of the next state `s' taking into account the probability of reaching that state. So we can use the following formula to express that:

Where: T(s, a, s') is the probability of reaching state s' from state s taking action a.

In fact, we can reach different states from the same state s by taking different actions. So, we sum over all possible states s' that we can reach from state s. Then, to get the optimal value function, we take the maximum value of all possible actions.

Now, you might want to read the previous section again! It's a bit confusing at first, but it will make sense as we go.

If you feel you need more explanation, you can watch this video that explains the value function and the value iteration algorithm in detail:

Stop at time 49:00

Example:

Assume that a robot in a 4x4 grid world and the transition probabilities are as follows:

• Each action has a 0.8 probability of moving in the intended direction and a 0.2 probability of moving in each of the other directions.
• The discount factor γ is 0.9
• The immediate reward R(s) is 0 for all states except the cup state which has a reward of 1 and the fire state which has a reward of -1.

Given the above information, we can calculate the value function of each state using the Bellman equation as follows:

V(s) = R(s) + γ * Σ_s' P_ss' * V(s')

Initially, the value function of each state is zero. Then, we take steps to update the values using the Bellman equation. So, V₀(s) = 0 for all s.

Then, starting from V₁(s), we can calculate the value function of each state using the Bellman equation. For example, let's calculate the value function of state (1,1):

State (1,1):

We have 2 possible actions: up and right. If we take the up action, we have a 0.8 probability of moving to state (1,2) and 0.1 probability of moving to each of the other states.

V(s=(1,1), a="up") = 0 + 0.9 * (0.8 * V(s=(1,2)) + 0.1 * V(s=(1,1)) + 0.1 * V(s=(2,1))) = 0 because the current values of V(s=(1,2)) and V(s=(2,1)) are zero.

Same for the right action:

V(s=(1,1), a="right") = 0 + 0.9 * (0.8 * V(s=(2,1)) + 0.1 * V(s=(1,1)) + 0.1 * V(s=(1,2))) = 0 because the current values of V(s=(1,2)) and V(s=(2,1)) are zero.

In this iteration, V1, most of the other states will have a value of zero as well. Let's calculate the value function of state (3,3):

V(s=(3,3), a="terminate") = 1 + 0.9 * (0.8 * 0 + 0.1 * 0 + 0.1 * 0) = 1

After 1 iteration, the value function of each state is updated as follows:

Note the arrows in the image above. For each state, we calculate the value function of each action and take the maximum value. For example, the value function of state (1,1) is the maximum value of the value function of the up action and the value function of the right action.

Doing the same calculations for the next iteration, we will end up with the following value function for V3(s):

When do we stop?

We stop when the value function converges to a stable value. That is, when the value function of each state does not change much between iterations or we exceed a maximum number of iterations we set.

Value Iteration Algorithm

Now The value iteration algorithm should be clear. We start with an initial estimate of the value function V(s) and iteratively update the estimate of the value function V(s) until it converges to the optimal value function V*(s). We stop when the change in the value function is less than a threshold or we exceed a maximum number of iterations we set.

Optimal Policy

Now that we have the optimal value function V*(s), we can find the optimal policy π*. Recall that the optimal policy returns the action that maximizes the expected total reward and we know from the previous equation which action maximizes the expected total reward. So basically, we can find the action that maximizes the expected total reward and use it as the optimal policy.

Value Iteration Mini-Blackjack

Here is a good example of running the value iteration algorithm on a simplified version of blackjack:

Note: The video has been trimmed to focus specifically on the relevant sections. It starts at 0:00 and ends at 17:35.

Value Iteration Frozen Lake Example

Gymnasium is an open source Python library for developing and comparing reinforcement learning algorithms. It provides a family of environments for testing reinforcement learning algorithms. Commonly used environments include the Frozen Lake environment, the CartPole environment, Blackjack environment, and the Mountain Car environment.

Each environment has an observation space and an action space. The observation space is the set of all possible states in the environment. The action space is the set of all possible actions that an agent can take in the environment.

Introduction to Gymnasium and Frozen Lake environment

Gymnasium is an open source Python library for developing and comparing reinforcement learning algorithms by providing a standard API to communicate between learning algorithms and environments. It is a fork of OpenAI's Gym library by its maintainers.

This practice lesson consists of two parts. The first part is a brief introduction to the Gymnasium library and the Frozen Lake environment. The second part is a demonstration of the value iteration algorithm on the Frozen Lake environment.

Part 1: Introduction to Gymnasium and Frozen Lake environment

Follow this colab notebook to learn about the Gymnasium library and the Frozen Lake environment. The notebook includes a brief introduction to the Gymnasium library and the Frozen Lake environment.

Quiz

After you have completed the Colab notebook, answer the following questions:

1. How do you show the states and actions for the Frozen Lake environment?
2. What does the variable env.unwrapped.P represent in an environment?
3. [True/False] In the Frozen Lake environment, where the action 0 means moving to the left, if the agent is in state 2,2 and takes action 0, the agent will certainly move to state 1,2.

print(env.observation_space)
print(env.action_space)

Part 2: Value Iteration on Frozen Lake environment

Follow this colab notebook to learn about the value iteration algorithm and how to apply it to the Frozen Lake environment.

Policy Iteration

Another common method for solving MDPs is policy iteration. Policy iteration operates as follows:

1. Initialize a policy arbitrarily. That means, for each state, we have to choose an action randomly.

   An example of a random policy in a grid world could be:

   policy = {
       (1, 1): 'up',
       (1, 2): 'up',
       (1, 3): 'Right',
       (2, 1): 'up',
       (2, 2): 'Right',
       (2, 3): 'up',
       (3, 1): 'up'
       (3, 2): 'Right'
       (3, 3): 'up'
   }
   

   This is totally arbitrary. We can choose any policy we want.

2. Policy Evaluation: Given a policy π, calculate the value function Vπ for the policy π. To do this, we will do the following:

• For each state, we calculate the value function using the following formula:

  

  k is the number of steps we take. This means that, after taking k+1 steps, the value of the state s is the sum of the immediate reward and the discounted value of the next state. That's close to the value iteration algorithm we have seen before except that, we are not taking the action that maximizes the expected value of the next state, but we are following the policy π. So, the immediate reward is R(s, π(s), s') which is the reward I get taking the action defined by π(s) in state s and reaching state s'. The discounted value of the next state is also calculated using the value function of the next state folowing the policy π.

  The input to the value function is the policy π. The output is the value function Vπ for the policy π. This is a system of linear equations that can be solved using linear algebra.

3. Policy Improvement: from the current state values we have from step1, consider all actions and choose the action that maximizes the expected values of the next states. This is the same as doing one iteration of the value iteration algorithm.

4. Policy Iteration: Repeat steps 2 and 3 until the policy converges.

Value Iteration vs Policy Iteration

For small MDPs (i.e. few hundred states), policy iteration is often very fast and converges with very few iterations. However, for MDPs with large state spaces (i.e. 10 thousands or more), solving for Vπ explicitly would involve solving a large system of linear equations, and could be difficult. In these problems, value iteration may be preferred. For this reason, in practice value iteration seems to be used more often than policy iteration.

If you feel you need more explanation, you can watch this video that explains the value function and the value iteration algorithm in detail:

You may stop at time 58:15

Solving Mini-Blackjack using Policy Iteration

Value Iteration Frozen Lake Example

To understand the application of the policy iteration algorithm in the Frozen Lake environment, please follow this Colab notebook. It provides step-by-step instructions and interactive exercises that demonstrate the algorithm's implementation.

Week 4 Quiz: Reinforcement Learning

Before attempting the quiz, read the following carefully.

• This is a timed quiz. You will have one attempt.
• You will have 40 minutes to complete multiple-choice questions.
• You should first study the lesson materials thoroughly.

➡️ Access the quiz here.

Assignment: Value Iteration on Blackjack environment

Follow this colab notebook to complete the assignment:

Submission

Submit your assignment via gradescope here

Supervised Machine Learning!

This week, we embark on an exciting journey into the world of machine learning, exploring its fundamentals and applications in various projects. Our lesson will cover a broad range of topics, including:

• The essence of machine learning
• Key types of machine learning: Supervised, Unsupervised, and Reinforcement Learning
• Regression and Classification techniques
• And more

In the previous weeks, we discussed various approaches to achieving intelligence: tweaking algorithms for improved search, modeling constraints and rules for constraint satisfaction problems (CSPs), and learning from experience and rewards in Reinforcement Learning (RL). This week, we shift our focus to deriving intelligence from data.

Intelligence by Learning from Data

Can intelligence emerge from data analysis? Absolutely. A significant portion of Machine Learning is dedicated to this very concept.

Learning from data involves developing algorithms and models capable of analyzing, interpreting, and making predictions or decisions based on data. This process requires training models on large datasets to identify patterns and relationships not immediately apparent. As models are exposed to more data, their predictive and decision-making capabilities improve.

What is Machine Learning?

The conceptual framework of Machine Learning is straightforward: we leverage data, examples, experiences, and observations to teach computers how to learn.

Arthur Samuel defined machine learning as a subfield of computer science that enables computers to learn without being explicitly programmed.

Explicitly Programmed vs. Learning from Data

• Explicitly programmed: Writing a program for a specific task.

• Learning from data: Providing numerous examples of inputs and outputs for the machine to learn from, enabling it to predict outputs for new inputs.

Consider the challenge of identifying a person from a photograph. Writing a program for direct comparison, such as pixel-by-pixel analysis, is impractical, due to the variability in photos. Machine learning overcomes this by using labeled photographs to teach computers to identify people in images, exemplifying AI learning.

Types of Learning:

Machine Learning encompasses three primary learning types:

• Supervised Learning: (Classification, Regression): Learning a function that maps inputs to outputs from example input-output pairs. This includes tasks like email spam classification, tumor malignancy classification, and stock price forecasting.

• Unsupervised Learning: (Clustering, Dimensionality Reduction): Finding patterns in unlabeled data, such as grouping customers by purchasing behavior or reducing the number of data features for efficiency.

• Reinforcement Learning: Learning from the outcomes of actions in an environment to maximize some notion of cumulative reward.

Supervised Learning

Supervised learning is a type of machine learning predominantly used in many real-world applications, witnessing rapid advancements and innovations. It involves learning a function that maps an input to an output based on example input-output pairs, a process also known as function approximation.

This approach entails providing the machine with numerous examples of inputs and outputs (labels), enabling it to learn from these examples and predict the output for any new input. The algorithm attempts to identify patterns within the data, creating a model capable of replicating the same underlying rules with new data. Remarkable, isn't it?

Model: An algorithmic formula designed to produce an outcome with new data, based on the principles derived from the training data. Once the model is developed, it can be applied to new data and evaluated for accuracy.

Examples of supervised learning algorithms include regression analysis, decision trees, k-nearest neighbors, neural networks, and support vector machines.

Examples of supervised learning applications include:

• Regression: Estimating a continuous value:

  • Forecasting a house's price in dollars based on its features.
  • Predicting a person's age based on their medical records.
  • Forecasting stock prices.

• Classification: Predicting a label (category) from a set of labels.

  • Classifying an email as spam or not spam.
  • Identifying a tumor as malignant or benign.
  • Recognizing images of handwritten digits.
  • Facilitating face recognition.
  • Categorizing news articles into different categories.

Unsupervised Learning

Unsupervised learning algorithms seek patterns in unlabeled data. For instance, consider data about a company's customers where the goal is to identify patterns. The aim is to find groups of customers with similar purchasing behaviors, despite the absence of predefined labels for these groups. An unsupervised learning algorithm might determine that the data can be segmented into two distinct groups or clusters.

Examples of unsupervised learning include:

• Clustering: Aggregating similar data points.

  • Sorting customers by their purchasing habits.
  • Organizing news articles by their topics.
  • Grouping patients based on their medical histories.

• Dimensionality Reduction: Decreasing the number of data features.

  • Data compression: Minimizing the data size.

• Anomaly Detection: Identifying outliers within the data.

  • Detecting fraud.
  • Identifying manufacturing defects.
  • Diagnosing medical issues.

We will commence with supervised learning, starting with regression.

Let's dive in! 🚀

Linear Regression

What is Regression?

In its simplest form, regression is a statistical method used to model the connection between a dependent variable and one or more independent variables. The dependent variable is the variable we aim to predict, while the independent variables are the variables used to predict the outcome.

An example of a simple regression problem is predicting the price of a house based on its size, number of rooms, and location. In this case, the price of the house is the dependent variable, while the size, number of rooms, and location are the independent variables.

The technique of regression analysis involves developing a mathematical model that describes the relationship between the dependent and independent variables.

In machine learning,the key idea behind regression is that, given that we have enough data, we can learn the relationship between the independent and dependent variables from the data. We can then use this learned relationship to predict the outcome of future events.Regression is a form of supervised learning.

Types of Regression

There are several types of regression, but the most common ones in machine learning are:

• Linear Regression: Models the linear relationship between the dependent and independent variables. It assumes a straight-line relationship.

• Polynomial Regression: Models the relationship between the dependent and independent variables as an nth-degree polynomial. It assumes a non-linear relationship.

• Logistic Regression: Models the relationship between the dependent and independent variables by estimating the probability that a given input belongs to a specific category. It is used for classification problems.

We will start with One-variable Linear Regression and then move on to other types of regression in the upcoming lessons.

One-variable Linear Regression

When we have one input variable (feature), we call it one-variable linear regression. Later on, we will learn about multiple variable linear regression, in which we have more than one input variable (multiple features).

Goal

Our goal in Linear Regression is to find the best fit line (equation) that describes the relationship between the variables that can later be used to predict the outcome of future events.

Here is a sample dataset that contains the amount of money spent on advertising and the resulting sales. The goal is to predict the amount of sales based on the amount of money spent on advertising.

Can you predict the sales when the money spent on advertising is 1170?

Data usually is not that simple. But let's illustrate the idea of regression using this simple example first and then we will move on to more complex examples.

Here is a scatter plot of the data:

This dataset forms a perfect straight line. The equation of a straight line is Y = wX + b. The value of w is the slope of the line. The value of b is the y-intercept of the line.

Using any two points on the line, or from the data table, we can calculate the slope of the line and the y-intercept of the line. Let's use the first and the last points to calculate the slope and the y-intercept of the line.

w (slope) = (y2 - y1) / (x2 - x1) = (5000 - 1000) / (500 - 100) = 4000 / 400 = 10

We can calculate the y-intercept of the line using the slope of the line and any point on the line like this:

b = y - wx = 1000 - 10 * 100 = 1000 - 1000 = 0

So, the equation of the line is y = 10x + 0 = 10x.

Having the equation of the regression line, we can predict the outcome of any future events. For example, if you want to predict the sales when you spend 3750 on advertising, you can predict that the resulting sales will be 10 * x = 37500.

This was a very simple example but we've learned a lot.

• We learned that the equation of a straight line is y = wx + b.
• We learned the parameters of the line w and b.
• We learned how to calculate the parameters of the line.
• We learned how to use the equation of the line to predict the outcome of future events.

Example: Car Price Prediction

Here is a video that explains the basics of linear regression with a simple example. Please watch it and then we will continue our discussion.

Now, let's move on to a more complex example. Here is a part of a dataset that contains the age of a person and the insurance cost of that person.

Can you predict the insurance cost of a person knowing their age? Can you draw a line on that plot that describes the relationship between the age of a person and their insurance cost 🤔?

It is not that easy, isn't it? Let's try to draw a line that describes the relationship between the age of a person and their insurance cost. Here are a few lines that I drew:

Just by looking at the graph, we can determine which lines are better than the others but, among the lines that are close to the data points, it is still not easy to determine which one is better.

Let's discuss a systematic way to determine which line is better than the others. But before we do that, let's learn how can we find these lines different lines.

Parameters

We can draw multiple candidate lines by adjusting the parameters. The line's parameters are w and b. We can experiment with different values of w and b to create different lines. Here are a few lines that I created by varying the line's parameters:

What values of w and b do we use? Initially, we'll rely on our intuition to make educated guesses about parameter values. Later on, we will utilize a technique called gradient descent to find the best parameter values for us.

Best Fit Line

How can we determine which line is the best fit? One approach to accomplish this is by calculating the distance between the data points and the line.

The smaller the distance between all points and the line, the better the line. This distance between a point and a line is referred to as the error.

Cost Function

Ideally, we would like the distance between the points and the line to be zero, but that is rare in real-life scenarios. Therefore, our objective is to identify the line with the smallest distances (smallest error) between the points and the line.

In a dataset showing the relationship between the age of a person and their insurance cost, here is a sample of the errors for one line:

Error

As you can see, the raw data does not tell us much. We need to find a way to summarize the errors in a way that is more meaningful. The average of the errors, for example, might be a good way to summarize the errors but having negative and positive errors might cancel each other out. In practice, there is a better method called the mean of squared errors to summarize the errors. Here is the equation of the mean of squared errors:

What the equation says is that we calculate the difference between the actual value and the predicted value for each point, square the difference, and then calculate the average of all the squared differences.

This is also called the cost function. The cost function is a function that maps some values of one or more variables onto a real number intuitively representing some "cost" associated with the event. This is precisely what we need to effectively utilize these error values.

If you feel you need more explanation, please watch this video.

In machine learning, we use a slightly modified version of the mean of squared errors. Here is the formula we use in machine learning:

Here is the explanation of the formula:

• J(w,b) is the cost function. It is a function of the parameters of the line w and b.
• m is the number of data points. The division by 2m is to make the calculation easier.
• y^(i) is the predicted value of the ith data point
• y(i) is the actual value of the ith data point
• ∑ is the summation symbol. It means we need to add all the values of the expression that follows it.

Theta Notation

In some references, the regression equation is modeled using θ0 and θ1 values instead of w and b. The equation of the line is then expressed as hθ(x) = θ0 + θ1x, where θ0 and θ1 are the y-intercept and the slope of the line, respectively. This approach stems from the assumption that our goal begins with a hypothesis, h, and we aim to find the best hypothesis that accurately describes the relationship between the variables.

The cost function, represented as J(θ0, θ1), takes the following form:

Cost Function Videos

If you feel you need more explanation of the cost function and how it is calculated, please watch the following videos:

• Cost Function
• Cost Function Intuition

Example:

Let's apply what we've learned so far using an example. Here is a sample dataset that contains the amount of money spent on advertising and the resulting sales. The goal is to predict the amount of sales based on the amount of money spent on advertising.

Finding the Best Fit Line

Remember that the goal of regression is to find the best fit line (equation) that describes the relationship between the variables that can later be used to predict the outcome of future events.

To do so, we need to find the parameters of the line: w and b that will find the best fit line. In other words, we need to find the values of w and b that will minimize the cost function.

Here is a manual way of finding the best fit line. We will try different values of w and b and calculate the cost function for each set of values. Then we will select the set of values that gives the smallest cost function.

Trying w =1 and b = 5

Y^ = wx + b = 1x + 5 = x + 5

The calculated cost function with w=1 and b=5 for our dataset is: 7,772,102.5. Seems like a very large number. Let's try another set of values for w and b.

Trying w =2 and b = 50:

The calculated cost function with w=2 and b=50 for our dataset is: 1,231,000.0. Better.

Trying w =5 and b = 500:

The calculated cost function with w=5 and b=500 for our dataset is: 39,000. Much better.

Trying w =2 and b = 1000:

The calculated cost function with w=2 and b=1000 for our dataset is: 319,000.0. Up again.

Trying w =2 and b = 500:

The calculated cost function with w=2 and b=500 for our dataset is: 777,100.0. Up again.

If we decide to stop here, we can use the equation of the line y = 5x + 500 to predict the outcome of future events. For example, if you want to predict the sales when you spend 3750 on advertising, you can predict that the resulting sales will be 5 * x + 500 = 5 * 3750 + 500 = 19,750.

Results

These were 5 iterations. We tried 5 different values of w and b. The smallest cost we could get is 39,000. So, the best fit line we could find so far is the one with w=5 and b=500.

Can we do better? We can if we try more values of w and b but we will hire the computer to do that for us in the next lesson.

Welcome to Learning!

What we saw above is a core part of how machines learning algorithms works. It tries to "learn" the best fit line by trying different values of the parameters and calculating the cost function for each set of values. Then it selects the set of values that gives the smallest cost.

Solve the exercise in the next section to practice what you've learned so far.

Summary

• Regression is a form of supervised learning employed to model the relation between one or more variables, allowing us to forecast outcomes based on this relationship.

• The primary objective of regression is to determine the most suitable line or curve that characterizes the relationship between the variables. This regression line or curve serves as a tool to anticipate outcomes in future scenarios.

• The equation of a straight line is y = wx + b. The value of w is the slope of the line. The value of b is the y-intercept of the line. The slope of the line is the change in y divided by the change in x. The y-intercept of the line is the value of y when x is 0.

• The "cost" or "loss" function is a function that maps some values of one or more variables onto a real number intuitively representing some "cost" associated with the event. This is precisely what we need to effectively utilize these error values.

• The common cost function used in machine learning is the mean of squared errors. Here is the formula we use:

Exercise: One-variable Linear Regression

Here is a sample dataset that contains the mid-term and final exam scores of 10 students. The goal is to predict the final exam score based on the mid-term exam score.

Questions:

1. What is the number of features in this dataset?

2. What is the number of data points (m) in this dataset?

3. Which of these w and b values will give the smallest cost function?

   • w = 1 and b = 10
   • w = 0.5 and b = 20
   • w = 3 and b = 7

4. Write a simple Python code to calculate the cost function for each set of w and b values and try different values to find the smallest cost function.

import numpy as np

# Given dataset
mid_term_scores = np.array([70, 80, 90, 60, 50, 40, 30, 20, 10, 0])
final_scores = np.array([80, 90, 100, 70, 65, 50, 40, 30, 20, 10])

# # Calculate the mean squared error (MSE) for given values of w and b

def calculate_mse(w, b):
    predicted_final = w * mid_term_scores + b
    m = len(mid_term_scores)
    mse = (1/(2*m)) * np.sum((predicted_final - final_scores)**2)
    return predicted_final, mse

# Test cases
w_values = [1, 0.5, 3]
b_values = [10, 20, 7]

for w, b in zip(w_values, b_values):
    predicted_final, mse = calculate_mse(w, b)
    print(f"For w = {w} and b = {b}:")
    print("Predicted Final Scores:", predicted_final)
    print("Mean Squared Error (MSE):", mse)
    print()

Gradient Descent

We have learned about linear regression and how to use it to predict the value of an output variable based on the value of one input variable(feature). We have also learned about the cost function and how to use it to measure the error of the model. In this lesson, we will learn about gradient descent, a popular optimization algorithm used to minimize the cost function.

Watch the following videos in the given order:

Introduction to Gradient Descent:

Gradient Descent Implementation:

Key points from the videos:

Gradient Descent

Gradient descent is an optimization algorithm used to minimize the cost function. The cost function is a function that measures the error of the model. The cost function for linear regression is the mean of squared error.

The equation of the gradient descent algorithm is as follows:

• The idea of gradient descent is to start with a random value for the coefficients and then iteratively update the coefficients in the direction of the gradient of the cost function until we reach a local minimum.

• The derivative term in the gradient descent equation tells us in which direction we should update the coefficients. In combination with the learning rate, the derivative term tells us how much we should update the coefficients.

• If we are already at a local minimum, the derivative term will be zero and the coefficients will not be changed.

The Learning Rate and Number of Iterations:

• The learning rate is a hyperparameter that controls how much we update the coefficients in each iteration.
• The learning rate is usually set to a small positive number between 0 and 1.
• If the learning rate is too small, the algorithm will take a long time to converge. If the learning rate is too large, the algorithm may overshoot the minimum and potentially never converge.
• The number of iterations is another hyperparameter that controls the number of iterations the algorithm will run. If the number of iterations is too small, the algorithm may not converge. If the number of iterations is too large, the algorithm will take a long time to converge.

Gradient Descent for Linear Regression:

Practice Quiz:

Q. Which of the following are true statements? Select all that apply.

1. To make gradient descent converge, we must slowly decrease alpha (α) over time.

2. Gradient descent is guaranteed to find the global minimum for any function J(θ0, θ1).

3. Gradient descent can converge even if α is kept fixed. (But α cannot be too large, or else it may fail to converge.)

4. For the specific choice of cost function J(θ0, θ1) used in linear regression, there are no local optima other than the global optimum.

Linear Regression with Multiple Variables

In our previous lessons, we learned about linear regression. More specifically, One-variable linear regression in which we had one input variable (feature) and one output variable. In this lesson, we will learn about multiple linear regression in which we have more than one input variable (multiple features). It is also known as multivariate linear regression.

Watch this video to learn about multiple linear regression:

Multiple Linear Regression

In multiple linear regression:

• We have more than one input variable that contribute in predicting the output variable.

• The equation of the line is a linear combination of the input variables.

  

Multiple Linear Regression Example

In this insurance dataset, we have the following features: age, sex, bmi, children, smoker, and region. We want to predict the charges (output variable) based on these features. Here is a sample of the data:

With x1, x2, ..., x6 being the age, sex, bmi, children, smoker, and region features, respectively, the equation is as follows.

fw,b(x) = w1x1 + w2x2 + .. + w6x6 + b

The model should learn the values of the coefficients w1, w2, ..., w6 that minimize the error between the predicted charges and the actual charges.

As we saw in the video, a common way to represent the features mathematically is by using vectors.

where X = [x1, x2, .. x6] and W = [w1, w2, .. w6]

Gradient Descent on Multiple Linear Regression

The gradient descent algorithm for multiple linear regression is the same as the one for one-variable linear regression. The only difference is that we have more than one coefficient to update. The gradient descent equation for multiple linear regression is as follows.

where w is a vector of the coefficients [w1, w2, ... wn] and x is a vector of the features [x1, x2, ... xn].

Watch this video to learn about gradient descent for multiple regression:

Polynomial Regression

Now that we have learned about multiple linear regression, let's see how we can use it to fit a polynomial function (a function that has a non-linear relationship between the input and output variables).

Watch this video to learn about polynomial regression:

Key points from the video:

• Polynomial regression is a form of regression in which the relationship between the variables are modeled as an n^th degree polynomial.
• Feature Engineering practices are very important in regression.

Practice Regression

Follow this Colab notebook to practice regression:

Logistic Regression and Classification

In this lesson, we will learn about classification and logistic regression.

Classification

While regression is used to predict continuous values, classification is used to predict classes, such as "spam," or "not spam," or "cancer" and "no cancer," or "cat," "dog," "bird," "fish," etc.

A binary classification, a sub-type of classification, predicts a binary output {0,1}, positive and negative, or yes and no. For example, a binary classifier may predict whether an email is spam or not spam.

A multi-class classification predicts a multi-class output {0,1,2,3} or {cat, dog, bird, fish}.

Approaching Classification Problems

At its core, we are still using the regression mindset. We are still trying to find the best parameters to fit the data. The only difference is that we are trying to fit the data to a binary or multi-class output, not a continuous one.

From Regression to Classification:

Logistic Regression

Logistic regression is a classification algorithm used to assign observations to a discrete set of classes. Unlike linear regression which outputs continuous number values, logistic regression transforms its output using the logistic function to return a probability value which can then be mapped to two or more discrete classes.

The sigmoid function

As mentioned in the video, the sigmoid function is an S-shaped curve that can take any real-valued number and map it into a value between the range of 0 and 1. This is exactly what we need because we want to map the output of the regression model function to probability values between 0 and 1.

Cost Function for Logistic Regression:

Notes on the Video:

• Recall that we use gradient descent to minimize the cost function and find the best parameters for the model.
• The shape of the cost function we used for linear regression (Mean Squared Error) is convex, which means that it has only one minimum. This makes it easy to find the global minimum.
• We can't use the same cost function (MSE) for logistic regression because the resulting cost function would be non-convex. This would make it difficult to find the global minimum.
• The cost (loss) function of logistic regression is defined as:

Let's now use gradient descent to minimize the cost function of logistic regression.

Gradient Descent for Logistic Regression:

Notes on the Video:

• Using the loss function of logistic regression, instead of the MSE of linear regression, we can use gradient descent to minimize the cost function and find the best parameters for the model.

Practice Classification

Follow this Colab notebook to practice classification using logistic regression:

Model Improvement

Overfitting

In machine learning, overfitting and underfitting are two key challenges that need to be addressed to build a good model.

Watch this video to understand the concept of overfitting and underfitting.

Addressing Overfitting

Naive Bayes Classifier

In our previous lessons, we learned about the classification problem and how to solve it using the logistic regression algorithm. In this lesson, we will highlight another classification algorithm that is widely used in machine learning: the Naive Bayes classifier.

The Naive Bayes classifier is a simple probabilistic classifier based on applying Bayes' theorem with strong (naive) independence assumptions. It is a fast, accurate, and reliable algorithm that is widely used for text classification, spam filtering, and recommendation systems.

How Naive Bayes Works

Watch the following video to learn how the Naive Bayes classifier works:

Notes on the Video

• Bayes' Theorem: It is a fundamental theorem in probability theory that describes the probability of an event, based on prior knowledge of conditions that might be related to the event. It is named after Thomas Bayes.

• Naive Bayes Classifier: It is a simple probabilistic classifier based on applying Bayes' theorem with strong (naive) independence assumptions. It is widely used for text classification, spam filtering, and recommendation systems.

Classification Algorithms

In the last lesson, we learned about the classification problem and how to solve it using the logistic regression algorithm. In this lesson, we will highlight other classification algorithms that are widely used in machine learning.

Watch this (trimmed) video to learn more about 6 common classification algorithms:

Week 5 Quiz : Machine Learning

Before attempting the quiz, read the following carefully.

• This is a timed quiz. You will have one attempt.
• You will have 20 minutes to complete multiple-choice questions.

➡️ Access the quiz here

Assignment: Naive Bayes Classifier

Your task for this assignment is to implement a Naive Bayes classifier to identify potential customers who have a higher probability of purchasing a loan.

Instructions

** A complete guide has been provided in the Colab notebook below to help you complete the assignment.**

• Use this bank_loan dataset to train and test your model.
• Create a Colab notebook and write your code in it.
• Without using any high-level libraries like sklearn or tensorflow, implement the Naive Bayes classifier to predict the potential customers who have a higher probability of accepting the personal loan offer.
• The dataset contains 12 featurs and 1 target variable ("Personal Loan").
  • age : Customer's age in completed years
  • experience : years of professional experience
  • income : Annual income of the customer
  • zip_code : Home Address ZIP code.
  • family : Family size of the customer
  • ccavg : Avg. spending on credit cards per month
  • education : Education Level (Undergrad, Graduate, Advanced/Professional)
  • mortgage : Value of house mortgage if any.
  • personal_loan : Did this customer accept the personal loan offered in the last campaign?
  • securities_account : Does the customer have a securities account with the bank?
  • cd_account : Does the customer have a certificate of deposit (CD) account with the bank?
  • online : Does the customer use internet banking facilities?
• Implement basic data exploration techniques to understand the dataset.

Guide

A complete guide, including a video, has been provided in the Colab notebook below to help you complete the assignment.

Submission

• Submit your notebook link via Gradescope here

Neural Networks and Computer Vision

CIFAR-10 Dataset

Welcome to the fascinating world of Neural Networks! This week, we embark on an exciting journey to explore the fundamentals of neural networks and their applications across a variety of projects.

By the end of this week, you will have the opportunity to construct an image classifier using a Convolutional Neural Network (CNN). Additionally, you'll learn how to effectively train and evaluate your model using TensorFlow and Keras, two powerful tools in the field of deep learning.

Your assignment for this week will be to build a CNN model that recognizes faces

Let's dive in! 🚀

Neural Networks

Neural networks, or more specifically, artificial neural networks (ANNs), represent a computational approach inspired by the human brain's structure and function. They are designed to learn from data, making them powerful tools for tasks such as classification, prediction, and more.

Neurons: The Building Blocks

At the heart of a neural network is the neuron. A neuron receives input, processes it through computation, and then outputs a result. It is the fundamental unit that makes up a neural network.

Consider a neuron that takes an individual's income as input and predicts whether they are likely to take out a loan.

You already know how to do similar tasks using linear regression. A neuron is like a linear regression model with a few additional components. As in linear regression, a neuron takes an input (income), multiplies it by a weight, adds a bias, and generates an output. However, the neuron also includes an activation function, which introduces non-linearity to the output.

Activation Functions: Introducing Non-linearity

AActivation functions play a critical role in introducing non-linearity to the neuron's output. This is crucial because it allows the model to handle complex, non-linear data. A commonly used activation function is the Rectified Linear Unit (ReLU), which outputs the input value if it is positive and zero otherwise.

Constructing a Simple Neural Network

A neural network is essentially a series of neurons connected together. The output of one neuron feeds into the input of another. For example, in a simple network:

Deep Neural Networks: Beyond the Basics

When a neural network includes multiple layers of neurons, it becomes a deep neural network. These layers allow for the modeling of complex relationships and patterns in the data.

Watch the following video for a reiteration of the concepts we discussed above using a different example.

Coding a Neural Network Layer

To grasp the inner workings of neural networks, you can implement a layer in Python with just a few lines of code:

import numpy as np

class Layer:
    def __init__(self, input_size, output_size):
        self.weights = np.random.rand(input_size, output_size)
        self.bias = np.random.rand(output_size)

    def output(self, input):
        return np.dot(input, self.weights) + self.bias  # Linear operation plus bias

This simple example initializes a layer with random weights and biases, demonstrating how input is transformed through the layer.

[Optional] Here's an interesting video that demonstrates how to code a neural network layer from scratch using Python.

Note that the previous two examples don't involve learning. Learning, as we know, involves adjusting the weights and biases in a neural network to improve its performance. We will learn more about this in the next sections.

Neural Network Types

Neural networks come in various shapes and sizes, each designed to solve a specific problem. Watch the video below for a brief overview of the different types of neural networks:

Test Your Understanding

• Q1. What is the difference between text, audio, and image data?

• Q2. What are the use cases of a CNN (Convolutional Neural Network)?

• Q3. What are the use cases of an RNN (Recurrent Neural Network)?

• Q4. Which type of neural network is shown in the image below?

  

• Q5. Which type of neural network is shown in the image below?

Practice Neural Networks

Follow the instructions in the neural networks practice notebook to build a neural network classifier for the MNIST dataset.

Computer Vision

Computer Vision is a transformative field within artificial intelligence that empowers computers and systems to extract meaningful information from digital images, videos, and other visual inputs. This field merges techniques from machine learning and traditional image processing to enable the interpretation and analysis of visual data.

Key Tasks in Computer Vision

Computer vision encompasses a range of tasks, each aimed at understanding visual data in some form. These include:

• Image Classification: Assigning a label to an image from a set of predefined categories.
• Object Detection: Identifying objects within an image and determining their boundaries.
• Image Segmentation: Dividing an image into segments to simplify its representation.

While machine learning algorithms, particularly those involving neural networks, play a crucial role in modern computer vision, the field also benefits from traditional image processing techniques. These foundational techniques, like filtering, edge detection, and image enhancement, are essential for preprocessing and improving image data for further analysis.

Basic Computer Vision Tasks: Berkeley CS198

Neural Networks in Computer Vision

Our exploration into neural networks revealed their potential in addressing computer vision challenges, such as image classification. However, standard neural networks face limitations in dealing with the complexity and scale of image data. This is due to their inability to efficiently handle large input sizes and to preserve the spatial structure of images (more on this later).

The Advent of Deep Learning in Computer Vision

Deep learning, a subset of machine learning, utilizes deep neural networks to uncover complex patterns in data. Its emergence has significantly advanced the field of computer vision, primarily through the use of Convolutional Neural Networks (CNNs). CNNs are adept at learning spatial hierarchies of features from images, making them particularly suited for computer vision tasks.

The breakthroughs in AI, particularly in computer vision, are largely attributed to the availability of large datasets and the computational capacity to train extensive models. The role of GPUs in this context cannot be overstated, as they have significantly accelerated the training processes.

Below is a comparison of some popular CNN architectures used in computer vision, including AlexNet, VGG, GoogLeNet, and ResNet. These models have been instrumental in advancing the field of computer vision, particularly in the ImageNet Large Scale Visual Recognition Challenge (ILSVRC).

ImageNet Models Comparison: MIT6.S191

As we delve deeper into CNNs and their applications in computer vision, we'll explore how these models are constructed, trained, and utilized in various tasks, providing a deeper understanding of both deep learning and computer vision.

Convolutional Neural Networks (CNNs)

Convolutional Neural Networks (CNNs) stand as the cornerstone of deep learning applications in computer vision. Invented by Yann LeCun in the 1990s and continuously refined, CNNs excel in automatically learning spatial hierarchies of features from images. This capability has made them indispensable for a wide range of computer vision tasks, including image classification, object detection, and image segmentation.

Understanding CNNs is crucial for grasping the essence of deep learning and its application in analyzing visual data.

The Convolution Operation

At the heart of CNNs is the convolution operation, a specialized mathematical process that extracts features from input data using a kernel (or filter). This small matrix moves across the input data, applying a dot product at each step to produce a feature map, highlighting important features while reducing the size of the data.

The convolution operation transforms the input image in a manner that may seem almost magical, emphasizing features like edges and textures, which are vital for the subsequent layers of the CNN to build upon.

Convolution Operation

Watch this video to understand the convolution operation in more detail:

Understanding Feature Extraction in CNNs

Feature extraction in CNNs unfolds through the network's convolutional layers, which learn to identify features directly from the data. Initial layers might capture basic elements such as edges and corners, while deeper layers can discern more intricate details like textures and object parts. This hierarchical learning process enables CNNs to tackle complex visual recognition tasks effectively.

Watch this (trimmed) video to understand how CNNs learn features from data:

In our upcoming lessons, we'll dive into practical demonstrations of CNNs in action, showcasing their power in solving real-world computer vision challenges.

Building CNNs

Building CNNs involves stacking convolutional layers, pooling layers, and fully connected layers to create a deep learning model that can learn from visual data. Watch this video to understand how to build a Convolutional Neural Network (CNN):

Building CNNs in TensorFlow

TensorFlow is a popular deep learning framework that provides a high-level API for building and training CNNs. Watch this video to learn how to build a CNN in TensorFlow:

Extra Helpfull Resources

• Visualizing Convolutional Output

• Batch Size in NN

• Understanding Learning Curves

That concludes this lesson! You've explored the essential components of Convolutional Neural Networks and learned how to construct them with TensorFlow. In the upcoming lesson, we'll focus on the practical aspect of building image classifiers, specifically using the CIFAR-10 dataset.

CNN Layers

Convolutional Neural Networks (CNNs) are composed of various layers, each serving a distinct function and purpose. The most common layers found in CNNs include:

• Convolutional Layer
• Pooling Layer
• Fully Connected Layer
• Flatten Layer
• Dropout Layer
• Softmax Layer

Let's explore some of these layers in detail.

Pooling Layer

This layer reduces the spatial dimensions of the input feature map, thereby decreasing the computational load of the network and the risk of overfitting. Pooling operations, such as max pooling or average pooling, summarize the presence of features in patches of the feature map.

Watch the following video to understand the concept of pooling in CNNs:

Dropout Layer

The dropout layer is a regularization technique that randomly sets the outputs of several neurons in the layer to zero during training. This prevents the network from becoming too dependent on any single neuron and helps in reducing overfitting.

Watch the following video to understand the concept of dropout in CNNs:

Softmax Layer

The softmax layer is typically used in the final layer of a neural network-based classifier. It converts the outputs into probability distributions, making it easier to determine the target class.

Classic CNN Architectures

Over the years, a variety of CNN (Convolutional Neural Network) architectures have been developed, each contributing to advancements in the field of deep learning and its applications. Among these, some of the most renowned architectures include:

• LeNet-5: One of the earliest convolutional neural networks, pivotal for handwriting recognition.
• AlexNet: A breakthrough architecture that significantly outperformed competitors in the ImageNet challenge.
• VGGNet: Known for its simplicity and depth, with a focus on increasing the depth of the network using small filters.
• GoogLeNet : GoogLeNet: Introduced the inception module, enabling the network to choose from filters of various sizes.
• ResNet: Introduced residual connections to facilitate training of very deep networks, solving the vanishing gradient problem.

To better understand the unique architectures and contributions of these CNNs, watch the following video:

Practice CNN

Follow this Colab notebook to practice using CNNs. You will build a CNN model to classify images from the CIFAR-10 dataset.

Embark on a Historical Journey through Computer Vision and Neural Networks

Are you ready for a thrilling historical journey in the world of computer vision and neural networks?

In 2012, the field of computer vision was forever transformed by the introduction of AlexNet, a deep convolutional neural network that took the challenge of image recognition to unprecedented heights. Developed by Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton, this groundbreaking model didn't just perform well—it shattered records, outperforming traditional methods by a staggering margin at the prestigious ImageNet Large Scale Visual Recognition Challenge (ILSVRC).

As you read through the paper, you'll gain insights into the architecture of convolutional neural networks (CNNs), understand the challenges the pioneers faced, and appreciate the elegant solutions they crafted. This isn't just a study session—it's an inspiration sprint. You'll see how embracing complexity and pushing boundaries in machine learning can lead to real-world impacts that were once thought to be in the realm of science fiction.

To start your journey, read the full paper here: AlexNet: ImageNet Classification with Deep Convolutional Neural Networks.

Week 6 Quiz : CNN

Before attempting the quiz, read the following carefully.

• This is a timed quiz. You will have one attempt.
• You will have 20 minutes to complete multiple-choice questions.

➡️ Access the quiz here.

Assignment: Face Recognition

In this assignment, you will build a face recognition model using a Convolutional Neural Network (CNN). You will use the ORL Faces dataset to train and test your model.

Please follow the instructions in the Colab notebook to complete the assignment. Some parts of the code are already implemented for you. You should write the code only where you are instructed to do so.

Submission

• Submit your notebook link via Gradescop here

Introduction to Logic and Knowledge Representation

Humans are logical beings. We use logic to reason about the world, and draw conclusions from facts. For example, if it’s sunny outside, we might decide to go for a walk. If it’s raining, we might decide to stay indoors. Can a computer do the same? Can a computer draw conclusions from facts and reason about the world?

We’ve seen how to achieve intelligence when we planned with search, modeled and used algebra with constraint satisfaction, learned from data with machine learning and deep learning, and learned by experience with reinforcement learning.

This week, we’ll explore how to achieve intelligence through logic and knowledge representation. We’ll start by understanding the basics of logic and knowledge representation, and then explore how to use logic to build intelligent systems. Let's start by asking the question: What is knowledge?

By the end of this lesson, you will be able to:

• Use propositional logic to represent facts and rules
• Use propositional logic to draw conclusions from facts and rules
• Use propositional logic to build an intelligent system like a medical diagnosis assistant
• Use first-order logic to represent more complex facts and rules utilizing quantifiers and predicates

Your assignment for this lesson is to build a home security system using propositional logic.

Logic and Knowledge Representation

What is logic?

In the context of AI, logic refers to a formal system used to represent and reason about knowledge and information. It is the same logic that we use in mathematics and philosophy, but applied to the domain of AI. Logic is used to represent facts and rules, and to draw conclusions from them. For example, we can use logic to represent the fact that "it's raining outside", and the rule that "if it's raining outside, then I should take an umbrella", and then use it to draw the conclusion that "I should take an umbrella".

What is Knowledge?

Knowledge refers to the information, understanding, and awareness that an individual or a system possesses about the world. It encompasses facts, concepts, beliefs, insights, experiences, and skills acquired through learning, observation, reasoning, and experimentation.

Knowledge of facts, also called propositional knowledge, is often characterized as true belief that is distinct from opinion or guesswork by virtue of justification. - Wikipedia

Since our study is about intelligent systems and decision making, we are interested in the propositional knowledge. This is the type of knowledge that can be represented as a set of propositions, or statements that can be either true or false.

Knowledge Representation (KB)

Knowledge representation is a field of artificial intelligence that focuses on how to formally represent knowledge in a way that can be used to solve problems.

Based on the goals and the type of questions you will ask or use the KB for, you would select the appropriate knowledge representation model. For example, if you are interested in representing the knowledge in a way that allows you to query facts, you would use a different model than if you are interested in representing the knowledge in a way that allows you to generate new content.

Knowledge Representation Models

Semantic Networks, Frames, Conceptual Graphs, Neural Networks and Logic are all examples of knowledge representation models. Each model is suitable for different types of problems.

Semantic networks, for example, are suitable for representing knowledge about the relationships between objects, which is useful in building cognitive systems like chatbots. On the other hand, logic-based knowledge representation is suitable for representing facts and rules, which is useful in building expert systems.

In this lesson, we focus on the logic-based knowledge representation model. This model allows us to represent facts and rules, and to draw conclusions from them.

An example of what we can do with logic-based knowledge representation is a medical diagnosis assistant.

• If a person exhibits sneezing and a runny nose but no fever, it is certain that they have allergies.

• If a person exhibits fever, cough, and body aches, it is certain that they have flu.

• If a person exhibits cough and runny nose, but no fever, it is certain that they have a common cold.

We can represent these facts and rules in a knowledge base, using propositional logic or first-order logic, and then use it to diagnose a patient based on their symptoms.

Different Types of Logic

There are different types of logic, each suitable for different types of problems. The two main types of logic that we will focus on in this class are:

• Propositional Logic
• First-Order Logic

Other types of logic include:

• Temporal Logic
• Fuzzy Logic
• Probabilistic Logic
• and more.

Propositional Logic

Propositional logic is a type of logic that deals with propositions. A proposition is a statement that is either true or false. For example, "Kibo is an institution that allows students to earn a degree in Computer Science." is a proposition, and it is true. "The sky is green" is also a proposition, but it is false.

Propositional Symbols

In propositional logic, we use variables (or symbols) to represent propositions. For example, we can use the variable p to represent the proposition "Kibo is an institution that allows students to earn a degree in Computer Science." and the variable q to represent the proposition "The sky is green". We can then use logical operators to combine these propositions.

Premises

In logic, the term "premises" refers to the statements or propositions that are assumed to be true in an argument or inference.

Sentences

A sentence is a combination of propositions and logical operators. For example, the sentence "The sky is blue and it is daytime" is a combination of the propositions "The sky is blue" and "It is daytime" using the logical operator "and".

Logical Connectives

Logical connectives are operators that can be used to combine propositions. The main logical connectives are:

• Negation or Not (¬): This operator takes a proposition and returns its negation. For example, if p is the proposition "The sky is blue", then ¬p is the proposition "The sky is not blue".

• Conjunction or And (∧): This operator takes two propositions and returns their conjunction. For example, if p is the proposition "The sky is blue" and q is the proposition "It is daytime", then p ∧ q is the proposition "The sky is blue and it is daytime".

• Disjunction or Or (∨): This operator takes two propositions and returns their disjunction. For example, if p is the proposition "The sky is blue" and q is the proposition "The sky is green", then p ∨ q is the proposition "The sky is blue or the sky is green".

• Implication (→): This operator takes two propositions and returns their implication (if...then). For example, if p is the proposition "The sky is blue" and q is the proposition "It is daytime", then p → q is the proposition "If the sky is blue, then it is daytime".

• Biconditional (↔): This operator takes two propositions and returns their biconditional. For example, if p is the proposition "The sky is blue" and q is the proposition "The sky is green", then p ↔ q is the proposition "The sky is blue if and only if the sky is green".

Truth Tables

Truth tables are tables that show the truth value of a compound proposition for all possible combinations of truth values of its components. For example, the truth table for the conjunction p ∧ q is:

The truth table for the implication p → q is:

The truth table for the biconditional p ↔ q is:

Knowledge Base (KB)

In the context of propositional logic, A knowledge base is a set of propositions that represent the facts and rules about the world. For example, the knowledge base for the medical diagnosis assistant we mentioned earlier might contain the following proposition:

"If a person exhibits sneezing and a runny nose but no fever, it is certain that they have allergies."

Which can be represented as: ( S ^ R ^ ¬F ) → A

Where:

• S: A person has sneezing.
• R: A person has a runny nose.
• F: A person has fever.
• A: A person has allergies.

It represents the rule that if a person has sneezing and a runny nose, but no fever, then they have allergies.

You can write a simple python code to represent the above knowledge base and query it just by using if else statements. However, in real-world problems, the knowledge base can be very large and complex, and so it is not practical to use if else statements to represent it. This is where logic-based knowledge representation comes in handy.

Representing the facts and the rules, as we did above, is a cruical step in building an intelligent system that can reason about the world. The next step will be using algorithms to draw conclusions from the knowledge base.

Watch this video for another example:

Code Example

Let's write a simple python code to represent the medical diagnosis knowledge base we mentioned earlier and query it.

# colab notebook for this code is available here: 
# https://colab.research.google.com/drive/1DQMAZz8j_-OeZ932crsQE3hIukBFBSr2

# Define symbols
S = Symbol("Sneezing")
R = Symbol("RunnyNose")
F = Symbol("Fever")
A = Symbol("Allergies")


# Construct the knowledge base
knowledge = Implication(And(S, R, Not(F)), A)

# a set of propositions that represent a possible state about the world that we can query next
model = And(And(S, R), Not(F))

# query to ask
query = Implication(model, A)

# Check if the knowledge base entails the person has allergies
# can we imply A (Allergies) from the model ( S ^ R ^ ¬F )?
result = model_check(knowledge, query)

print("Does the person have allergies?", result)

In the above code, we define the symbols S, R, F, and A to represent the propositions "A person has sneezing", "A person has a runny nose", "A person has fever", and "A person might have allergies", respectively.

We then construct the query to represent the question "Does the person have allergies if they have sneezing and a runny nose, but no fever?".

The code used the model_check function to check if the knowledge base entails the query. We will discuss the model_check function in the next section.

Entailment

The result of the above program is True, which means that the knowledge base entails the query, and so the person has allergies.

Entailment is the relationship between a knowledge base and a query. A knowledge base entails a query if the query is true in the knowledge base.

The notation for entailment is |=. For example, if KB is the knowledge base and q is the query, then KB |= q means that the knowledge base entails the query.

Test Your Understanding

Q1. In the context of a knowledge base (KB) in propositional logic, what does the expression (S ∧ R ∧ ¬F) → A signify given the propositions S: Sneezing, R: Runny Nose, F: Fever, A: Allergies?

• A) If a person has sneezing, a runny nose, and no fever, then they have allergies.
• B) A person with a fever, sneezing, and a runny nose has allergies.
• C) Sneezing and a runny nose are sufficient to conclude allergies, regardless of fever.
• D) If a person has allergies, they will have sneezing, a runny nose, and no fever.

Q2. Consider the propositions p: "The sky is blue", q: "It is raining". Which of the following represents the statement "If the sky is blue, then it is raining"?

• A) p → q
• B) p ∧ q
• C) p ∨ q
• D) p ↔ q

Consider the propositions p: "The sky is blue", q: "It is raining". Which of the following represents the biconditional 'p if and only if q'?

• A) p → q
• B) p ∧ q
• C) p ∨ q
• D) p ↔ q

Summary

• Propositional logic is a type of logic that deals with propositions.
• A proposition is a statement that is either true or false.
• Propositional logic uses variables (or symbols) to represent propositions.
• Logical connectives are operators that can be used to combine propositions.
• A knowledge base is a set of propositions that represent the facts and rules about the world.
• Entailment is the relationship between a knowledge base and a query. A knowledge base entails a query if the query is true in the knowledge base.

Practice: KB Representation

Open the Colab notebook below and complete the following exercise:

Extend the knowledge base in the notebook to include the following two rules:

1. If a person exhibits fever, cough, and body aches, it is certain that they have the flu.

2. If a person exhibits cough and a runny nose, but no fever, it is certain that they have a common cold.

# Define symbols
S = Symbol("Sneezing")
R = Symbol("RunnyNose")
F = Symbol("Fever")
A = Symbol("Allergies")
C = Symbol("Cough")
B = Symbol("BodyAches")

# Construct the knowledge base
knowledge = And(
    Implication(And(S, R, Not(F)), A),  # Rule for allergies
    Implication(And(F, C, B), Symbol("Flu")),  # Rule for flu
    Implication(And(C, R, Not(F)), Symbol("CommonCold"))  # Rule for common cold
)

# Questions
questions = [
    (And(F, C), "Does the person have a common cold?"),  # Question 1
    (And(F, B, C), "Does the person have a common cold?"),  # Question 2
    # Add more questions here
]

# Check each question against the knowledge base
for query, question_text in questions:
    result = model_check(knowledge, query)
    print(question_text, result)

Inferring with Logic

Inference is the process of determining whether a given sentence can be derived from the knowledge base.

Assume a knowledge base with the following formulae:

KB = ( A ∨ C ) ∧ (B ∨ ¬ C )

It could be representing something like:

• A: It is raining.
• B: It is cloudy.
• C: You have an umbrella.

And the knowledge base states that "It is raining or you have an umbrella" and "It is cloudy or you don't have an umbrella".

KB = ( A ∨ C ) ∧ (B ∨ ¬ C )

Our aim is to determine if the sentence α = ( A ∨ B ) can be inferred from the knowledge base or not.

To solve similar problems, we need an inference algorithm. An inference algorithm is a procedure to determine whether a given sentence can be derived from the knowledge base.

There are several algorithms to perform inference in propositional logic. Some of the most common algorithms are:

• Truth Table
• Forward Chaining
• Backward Chaining
• Resolution

Model Checking with Truth Table

The model checking approach uses truth tables for inference. It is a brute force algorithm that checks all possible interpretations of the knowledge base. The algorithm works as follows:

1. Create a truth table with all possible combinations of truth values for the propositional symbols in the knowledge base.

2. For each interpretation, check if the knowledge base entails the sentence α (i.e. sentence α evaluates to true whenever KB evaluates to true)

We have 3 symbols (A, B, C), so we have 2^3 = 8 possible interpretations. For all possible interpretations, The sentence α evaluates to true whenever the knowledge base evaluates to true. Therefore, we can conclude that the sentence α can be inferred from the knowledge base.

In logic.py module that we used earlier, this is what the function model_check does. It enumerates all possible interpretations and checks if the knowledge base entails a given sentence or not.

Inferring with Model Checking

Watch the video (~20 minutes) below to see an example of the model checking algorithm.

The video shows how to use the model checking algorithm to determine if a given sentence can be inferred from the knowledge base.

The code used in the video is available here

Soundness and Completeness

Soundness

A logical inference algorithm is said to be sound if it never derives a false conclusion from premises. In other words, it will not give wrong answers (false positives).

The truth model checking approach is a sound algorithm. It does not give us wrong answers.

Completeness

An inference algorithm is complete if it is capable of deriving any valid conclusion that can be drawn from a given set of premises. In other words, it checks all possible interpretations and does not miss any valid inference.

The model checking approach is a complete algorithm. It checks all possible interpretations and does not miss any valid inference.

Question:

What is the time complexity of the model checking / truth table algorithm?

Think about the number of rows in the truth table and the number of propositional symbols in the knowledge base. Think about it before you click to see the answer below.

Inference Rules

As we need only to check the KB for True values, we can improve the truth table algorithm by using the inference rules approach. We can use the inference rules to simplify the knowledge base and then check if a sentence α can be inferred from the simplified knowledge base. Inference rules can be used to generate new (sound) sentences from existing ones.

Inference Rules

Inference rules are used to generate new sentences from existing ones. Some of the most common inference rules are:

• Modus Ponens: If we know that A implies B and we know that A is true, then we can infer that B is true.

• And Elimination: If we know that A ∧ B is true, then we can infer that A is true and we can infer that B is true.

• Double Negation: If we know that A is true, then we can infer that ¬¬A is true.

• Implication Elimination: If we know that A implies B, then we can infer that ¬A ∨ B is true.

• Bidirectional Elimination: If we know that A is true if and only if B is true, then we can infer that (A → B) ∧ (B → A) is true.

• De Morgan's Law: If we know that ¬(A ∧ B) is true, then we can infer that ¬A ∨ ¬B is true.

• Distribution: If we know that A ∨ (B ∧ C) is true, then we can infer that (A ∨ B) ∧ (A ∨ C) is true.

• And many more...

[Optional] Inference By Resolution

Inferring by resolution is based on the resolution rule, which is a sound and complete inference rule. The resolution rule is used to generate new clauses from existing ones.

Watch the video below to see how to use the resolution rule to perform inference.

Summary

• Inference is the process of determining whether a given sentence can be derived from the knowledge base.
• The model checking approach uses truth tables for inference. It is a sound and complete algorithm, but it has an exponential time complexity.
• Inference rules can be used to simplify the knowledge base and then check if a sentence α can be inferred from the simplified knowledge base.
• The resolution rule is a sound and complete inference rule. It is used to generate new clauses from existing ones.

First Order Logic

First Order Logic is a type of logic that extends propositional logic by allowing us to represent more complex statements and reason about them. In first order logic, we can use quantifiers to express statements about objects and predicates to express relationships between objects.

Constant Symbols

In first order logic, a constant is a symbol that represents a specific object in a domain. For example, we can use the constant Solomon to represent the object 'Solomon' and the constant Math to represent the subject 'Math'.

Predicate Symbols

In first order logic, a predicate symbolically represents a property or relationship that can be true or false for objects. It takes objects as arguments. For example, we can use the predicate Student(x) to represent the statement "x is a student". Another example is the predicate TakesCourse(x, y) which represents the statement "x takes the course y".

Examples of predicate symbols:

• Student(Solomon): This predicate indicates that 'Solomon' is a student.
• TakesCourse(Solomon, Math): This predicate indicates that 'Solomon' takes the course 'Math'.
• ¬TakesCourse(Solomon, JavaEE): This predicate indicates that 'Solomon' does not take the course 'JavaEE'.

Quantifiers

Quantifiers are used to express more complex statements about objects. The two main quantifiers in first order logic are:

• Universal Quantifier (∀): This quantifier is used to express that a statement is true for all objects in a domain. For example, the statement 'All students take Prog1 class' can be expressed as:

  ∀x Student(x) → TakesCourse(x, Prog1).

• Existential Quantifier (∃): This quantifier is used to express that a statement is true for at least one object in a domain. For example, the statement 'Some students take JavaEE class' can be expressed as:

  ∃x Student(x) ∧ TakesCourse(x, JavaEE).

Logic Programming : A New Programming Paradigm

First order logic is the foundation of logic programming, a programming paradigm that uses logical inference to solve problems. In logic programming, we can use first order logic to represent the rules and facts about a problem, and then use a logical inference engine to derive new facts and solve problems.

The most popular logic programming language is Prolog, which is based on first order logic and is used in artificial intelligence and natural language processing.

Logic programming is a general-purpose programming paradigm that can be used to solve a wide range of problems, including constraint satisfaction problems, planning problems, and natural language processing problems.

Here is an example of a Prolog program that uses first order logic to represent the rules and facts about courses, students, and professors:

studies(charlie, csc135).
studies(olivia, csc135).
studies(jack, csc131).
studies(arthur, csc134).

teaches(kirke, csc135).
teaches(collins, csc131).
teaches(collins, csc171).
teaches(juniper, csc134).


professor(X, Y) :- 
    teaches(X, C), studies(Y, C).

## Queries 
?- studies(charlie, What). // charlie studies what? OR What does charlie study?
?- professor(kirke, Students). // Who are the students of professor kirke.  

Here is a sample run output from Online SWI-Prolog Interpreter

An extensive discussion on Logic Programming is beyond the scope of this class but it is important to know about it and be able to identify potential uses of logic programming in your engineering career.

Summary

• First order logic extends propositional logic by allowing us to represent more complex statements and reason about them.
• In first order logic, we can use constant symbols to represent specific objects in a domain, predicate symbols to represent relationships between objects, and quantifiers to express more complex statements about objects.
• The two main quantifiers in first order logic are the universal quantifier (∀) and the existential quantifier (∃).
• The universal quantifier is used to express that a statement is true for all objects in a domain, while the existential quantifier is used to express that a statement is true for at least one object in a domain.

Practice: First Order Logic

Q1. Translate the statement "David is a professor." into First-Order Logic.

Q2. Translate the statement "Mohammed Teaches AI." into First-Order Logic.

Q3. Translate the statement "Deans are professors." into First-Order Logic.

Convert the sentence "There exists a product with a price higher than $100" into First-Order Logic.

Translate the statement "For every product that has been ordered, there exists a customer who placed the order" into First-Order Logic.

Represent the statement "All employees who work on a project are assigned specific tasks" in First-Order Logic.

Week 7 Quiz

Before attempting the quiz, read the following carefully.

• This is a timed quiz. You will have only one attempt.
• You will have 20 minutes to complete multiple-choice questions.

➡️ Access the quiz here.

Assignment: Home Security System

The objective of this assignment is to use propositional logic to model and query a basic security system for a home. The home is equipped with various sensors and alarms, and the system should be capable of answering queries about the home's state.

➡️ Access the assignment and all details here.

Introduction to NLP

This image was generated with the help of Natural Language Processing (NLP).

Ever wondered how chatbots, such as ChatGPT, can feel so remarkably human-like in their responses? Or marveled at how your favorite virtual assistant always seems to know just what you need? Get ready to uncover the exciting secrets behind language translation, text summarization, question answering, text classification, and much more! Welcome to the world of Natural Language Processing (NLP)! It's the groundbreaking technology that makes all of this possible.

Natural Language Processing (NLP) is a field of computer science, artificial intelligence, and computational linguistics. It focuses on the interactions between computers and human (natural) languages.

When we discussed computer vision, we learned that its aim is to empower computers to comprehend, analyze, and effectively utilize visual information. Similarly, NLP serves the same purpose but for textual data. It involves the capability of a computer program to understand human language as it is spoken or written.

After completing this lesson, you will be able to:

• Explain what Natural Language Processing (NLP) is.
• Clean text data.
• Perform basic NLP tasks such as tokenization, stemming, and lemmatization.
• Explain Language Models and their applications.
• Build NLP applications such as sentiment analysis, text summarization, and text generation.

Language and Natural Language Processing

Let's start by defining what a language is and what is natural language processing.

A language is a system of communication that is used to express thoughts, feelings, and ideas. It is a system that is made up of words, grammar, and syntax.

A Natural Language, such as English, is a language that has evolved naturally in human societies. It is a language that is spoken and written by humans.

An artificial language, like Python, is a language that has been designed by humans for a specific purpose. For example, Python is a language that has been designed for computer programming.

Processing, In computing, 'processing' refers to the methods and techniques used by computers to handle tasks such as understanding, generating, and translating human language.

Natural Language Processing (NLP) is the study of how computers can deal with human language. For example, understanding the purpose of a text, generate a summary of a text, or translate a text from one language to another.

Natural Language Complexity

Natural languages, unlike artificial ones, are inherently complex, presenting numerous challenges for computer comprehension. This complexity arises from various factors, including the ambiguity of human language, the contextual nuances within which text is employed, and the requisite background knowledge necessary for understanding.

Here is an article that delves deeper into the reasons why natural languages are difficult: Why Human Language is Hard

NLP has existed for more than 50 years, but it has gained significant traction in the last decade due to the rise of deep learning and the availability of large-scale datasets. It has roots and close ties to the field of linguistics.

In the 1950s, with the aspiration for machine translation, encountering early setbacks that led to the first AI Winter. By the 1960s, the field experienced a revival with innovations such as ELIZA, an early chatbot. The late 1990s witnessed a paradigm shift towards statistical models, leveraging data over predefined rules.

Applications of NLP

1. Text Classification

Text classification involves categorizing text documents into predefined categories or classes. NLP techniques are used to analyze the content of text documents and assign appropriate labels based on their topics, sentiments, or other attributes. Applications include spam detection, sentiment analysis, topic modeling, and content categorization.

2. Machine Translation

Machine translation aims to automatically translate text from one language to another. NLP models are trained on large bilingual corpora to learn the mappings between languages and generate accurate translations. Popular examples include Google Translate, Microsoft Translator, and DeepL.

3. Named Entity Recognition (NER)

Named Entity Recognition (NER) is the task of identifying and classifying named entities (such as persons, organizations, locations, and dates) in text data. NLP techniques are used to extract and classify entities, which is essential for various applications such as information extraction, question answering systems, and entity linking.

4. Text Summarization

Text summarization involves condensing large volumes of text into shorter, coherent summaries while retaining the most important information. NLP techniques, including extractive and abstractive summarization methods, are employed to generate concise and informative summaries from documents, articles, or other textual content.

5. Sentiment Analysis

Sentiment analysis, also known as opinion mining, aims to determine the sentiment or emotional tone expressed in a piece of text. NLP models analyze the text to classify it as positive, negative, or neutral, providing valuable insights into public opinion, customer feedback, and social media sentiment.

6. Question Answering Systems

Question Answering (QA) systems automatically generate accurate answers to user queries posed in natural language. NLP techniques, combined with information retrieval and knowledge representation methods, enable QA systems to understand questions, search for relevant information, and generate appropriate responses from structured or unstructured data sources.

And many more! NLP has a wide range of applications across various domains, including healthcare, finance, e-commerce, education, and entertainment.

Cleaning

Before we can start building NLP models or executing NLP tasks, we need to clean the text. This is important because it ensures that the text is consistent and that the model can learn from it effectively.

The list of cleaning approaches is long and depends on the specific task and the data. Some typical cleaning approaches include removing punctuation, converting text to lowercase, removing stop words, removing special characters, and many more. Most of these cleaning approaches can be implemented using regular expressions and basic Python's string methods. However, some cleaning tasks may require more complex methods.

Let's explore some common cleaning approaches further.

Removing Stop Words

To remove stop words, we need to first download the list of stop words from the NLTK library. Then, we can remove the stop words from the text using a list comprehension.

import nltk
from nltk.corpus import stopwords

# Removing stop words
stop_words = set(stopwords.words('english'))
text = "the quick brown fox jumps over the lazy dog"

text = ' '.join([word for word in text.split() if word not in stop_words])

print(text) # quick brown fox jumps lazy dog

Lemmatization

A lemma is the base form of a word. For instance, the lemma of "rocks" is "rock". Lemmatization is the process of reducing words to their base or root form. This is important because it ensures that the model treats words with different forms consistently. Lemmatization involves determining the base or dictionary form of a word based on its context. It uses language dictionaries and morphological analysis to accurately reduce words to their base form.

To lemmatize the text, we can use the WordNetLemmatizer from the NLTK library.

import nltk
from nltk.stem import PorterStemmer, WordNetLemmatizer
nltk.download('wordnet')

text = "rocks and cats"

lemmatizer = WordNetLemmatizer() 
text = ' '.join([lemmatizer.lemmatize(word) for word in text.split()])
print(text) # rock and cat

Stemming

Stemming performs a similar function to lemmatization. It follows a rule-based approach reduces words to 1their base or root form by removing suffixes, such as "ing" or "ed".

import nltk
from nltk.stem import PorterStemmer, WordNetLemmatizer
nltk.download('wordnet')

text = "running in a stunning day"

stemmer = PorterStemmer()
text = ' '.join([stemmer.stem(word) for word in text.split()])

print(text) # run in stun day

Note that the NLTK's WordNetLemmatizer is designed to lemmatize words based on their part-of-speech (POS) tag. By default, if no POS tag is specified, it assumes the word is a noun. However, to lemmatize verbs accurately, you need to explicitly provide the POS tag.

lemmatizer.lemmatize("runnin") # running 

lemmatizer.lemmatize("running", pos = 'v') # run

Exercise

Use any paragraph of text and clean it using the following steps:

• Remove punctuation marks.
• Convert all text to lowercase.
• Remove numbers.
• Remove stopwords (common words that often do not carry significant meaning like "the", "is", "and", etc.).

Tokenization

Probably the first thing most NLP algorithms have to do is to split the text into tokens, this is called tokenization. Tokenization is the process of breaking a text into words, phrases, symbols, or other meaningful elements.

Tokenizing a sentence from Pride and Prejudice. Infographic by Jen Looper

You've probably built some tokenizers yourself, even if you didn't realize it. For example, if you've ever used the split method in Python, you've tokenized a string. However, tokenization is not always as simple as splitting a string by spaces. For example, in the sentence "Good muffins cost $3.88 in New York. Please buy me... two of them.\n\nThanks.", the ellipsis ("..."), the dollar sign ("$"), and the newline characters ("\n") are all tokens that should be separated from the words.

Luckily, there are many libraries that provide tokenization methods that can handle these edge cases. Natural Language Toolkit (nltk) library provides a word_tokenize method that can handle these edge cases. Here's an example of how to use it:

# pip install nltk to install nltk 

from nltk.tokenize import word_tokenize
text = "Good muffins cost $3.88\nin New York.  Please buy me... two of them.\n\nThanks."
tokens = word_tokenize(text)
print(tokens)

This code will output:

['Good', 'muffins', 'cost', '$', '3.88', 'in', 'New', 'York', '.', 'Please', 'buy', 'me', '...', 'two', 'of', 'them', '.', 'Thanks', '.']

The library spaCy also provides a tokenizer that can handle these edge cases. Here's an example of how to use it:

# pip install spacy # to install the spacy 
# spacy download en_core_web_sm # to download the english model

import spacy
nlp = spacy.load("en_core_web_sm")
doc = nlp("Good muffins cost $3.88\nin New York.  Please buy me... two of them.\n\nThanks.")
tokens = [token.text for token in doc]
print(tokens)

This code will output:

['Good', 'muffins', 'cost', '$', '3.88', '\n', 'in', 'New', 'York', '.', ' ', 'Please', 'buy', 'me', '...', 'two', 'of', 'them', '.', '\n\n', 'Thanks', '.']

The sent_tokenize method in nltk and spaCy can be used to tokenize sentences. Here's an example of how to use it in nltk:

from nltk.tokenize import sent_tokenize
text = "Good muffins cost $3.88\nin New York.  Please buy me... two of them.\n\nThanks."
sentences = sent_tokenize(text)
print(sentences)

This code will output:

['Good muffins cost $3.88\nin New York.', 'Please buy me... two of them.', 'Thanks.']

And here's an example of how to use it in spaCy:

import spacy
nlp = spacy.load("en_core_web_sm")
doc = nlp("Good muffins cost $3.88\nin New York.  Please buy me... two of them.\n\nThanks.")
sentences = [sent.text for sent in doc.sents]
print(sentences)

This code will output:

['Good muffins cost $3.88\nin New York.', 'Please buy me... two of them.', 'Thanks.']

Keras also provides a tokenizer that can be used to tokenize text. Here's an example of how to use it:

from keras.preprocessing.text import Tokenizer

# Example text data
texts = [
    "This is an example sentence.",
    "Another example sentence to tokenize."
]

# Initialize tokenizer
tokenizer = Tokenizer()

# Fit tokenizer on texts
tokenizer.fit_on_texts(texts)

# Convert texts to sequences of tokens
sequences = tokenizer.texts_to_sequences(texts)

# Print tokenized sequences
print("Tokenized sequences:")
for seq in sequences:
    print(seq)

The output of this code will be:

Tokenized sequences:
[3, 4, 5, 1, 2]
[6, 1, 2, 7, 8]

This code initializes a Keras Tokenizer, fits it on the example texts, and then converts the texts into sequences of tokens. Additionally, it builds a word index that can be used to convert tokens back into words. Finally, it prints the tokenized sequences.

Here's an example of how to use the word index to convert tokens back into words:

# Convert tokens back into words
print("Words:")
word_index = tokenizer.word_index
for seq in sequences:
    words = [list(word_index.keys())[list(word_index.values()).index(word_id)] for word_id in seq]
    print(" ".join(words))

Different Tokenization Approaches

Besides the word and sentence tokenization, there are other tokenization approaches that are used in NLP, such as:

• Subword Tokenization: This approach splits words into smaller units, such as characters or subwords. This is useful for languages like Turkish, where words can be very long and complex. It is also useful for languages like English, where words can be combined to form new words, such as "unbelievable" and "incredible".

• Byte Pair Encoding (BPE): This is a subword tokenization approach that is used in many NLP models such as GPT-2 and GPT-3. It is based on the frequency of pairs of characters in a corpus of text.

• WordPiece Tokenization: This is a subword tokenization approach that is used in many NLP models, such as BERT. It is based on the frequency of words in a corpus of text. It is useful for languages like English, where words can be combined to form new words, such as "unbelievable" and "incredible".

• Character Tokenization: This approach splits words into characters. This is useful for languages like Chinese, where there are no spaces between words.

• And more...

N-grams

N-grams are sequences of n words. For example, "I am" is a 2-gram (or bigram), "I am learning" is a 3-gram (or trigram), and "I am learning NLP" is a 4-gram (or 4-gram). N-grams are used in many NLP tasks, such as language modeling, machine translation, and text generation.

N-grams. Infographic by Jen Looper

We can consider that N-grams are sequences of the tokens we generated in the tokenization process. For example, if we have the sentence "I am learning NLP", the 2-grams (or bigrams) would be "I am", "am learning", and "learning NLP". The 3-grams (or trigrams) would be "I am learning" and "am learning NLP". And the 4-grams would be "I am learning NLP".

You can use the ngrams method in the nltk library to generate n-grams. Here's an example of how to use it:

import nltk
from nltk.util import ngrams

# Example sentence
sentence = "The quick brown fox jumps over the lazy dog."

nltk.download("punkt")

# Tokenize the sentence
tokens = nltk.word_tokenize(sentence)

# Generate n-grams
n = 2  # Example for bigrams
bigrams = list(ngrams(tokens, n))

# Print the bigrams
print("Bigrams:", bigrams)

This code will output:

[nltk_data] Downloading package punkt to /root/nltk_data...
[nltk_data]   Unzipping tokenizers/punkt.zip.

Bigrams: [('The', 'quick'), ('quick', 'brown'), ('brown', 'fox'), ('fox', 'jumps'), ('jumps', 'over'), ('over', 'the'), ('the', 'lazy'), ('lazy', 'dog'), ('dog', '.')]

N-grams play pivotal roles across various NLP tasks, including language modeling, machine translation, and text generation. Moreover, they are integral components within numerous NLP models, exemplified by GPT-2 and BERT.

Part-of-Speech Tagging

Every word that has been tokenized can be tagged as a part of speech - a noun, verb, or adjective. The sentence "the quick red fox jumped over the lazy brown dog" might be POS tagged as fox = noun, jumped = verb.

POS tagging a sentence from Pride and Prejudice. Infographic by Jen Looper

In information retrieval and search engines, part-of-speech tagging (POS tagging) helps in improving search engine results by understanding the context of search queries. For example, distinguishing between nouns and verbs can help prioritize search results based on the user's intent. It could also be used in other NLP tasks, such as named entity recognition, text classification, and sentiment analysis.

You can use the pos_tag method in the nltk library to POS tag a sentence. Here's an example of how to use it:

import nltk
from nltk.tokenize import word_tokenize

# Sample sentence
sentence = "The quick brown fox jumps over the lazy dog."

# Tokenize the sentence
tokens = word_tokenize(sentence)

# Perform POS tagging
pos_tags = nltk.pos_tag(tokens)

# Print the POS tags
print("POS tags:")
print(pos_tags)

Named Entity Recognition

Named Entity Recognition (NER) is the process of identifying and classifying named entities in a text. Named entities are real-world objects such as persons, locations, organizations, dates, and more. NER is a fundamental task in information extraction and text analysis, and it is used in a wide range of applications such as question answering, information retrieval, and machine translation.

NER can be used to extract structured information from unstructured text data. For example, in the sentence "Apple is headquartered in Cupertino, California", NER can be used to identify "Apple" as an organization and "Cupertino, California" as a location.

Example:

import nltk

# Sample text
text = """
Barack Obama was born in Hawaii. He served as the 44th President of the United States from 2009 to 2017.
"""

# Tokenize the text into sentences
sentences = nltk.sent_tokenize(text)

# Tokenize each sentence into words and perform part-of-speech tagging
tagged_sentences = [nltk.pos_tag(nltk.word_tokenize(sentence)) for sentence in sentences]

# Perform named entity recognition (NER)
named_entities = nltk.ne_chunk_sents(tagged_sentences, binary=False)

# Function to extract named entities from the named entity chunk tree
def extract_entities(tree):
    entities = []
    if hasattr(tree, 'label') and tree.label():
        if tree.label() == 'NE':
            entities.append(' '.join([child[0] for child in tree]))
        else:
            for child in tree:
                entities.extend(extract_entities(child))
    return entities

# Extract named entities from each chunk tree
named_entities_list = []
for tree in named_entities:
    for entity in extract_entities(tree):
        named_entities_list.append(entity)

# Print named entities
print("Named Entities:")
for entity in named_entities_list:
    print(entity)

Text Segmentation

Before we tokenize a text, specifically a long text, we might need to segment it into paragraphs, sections, or other meaningful units. This is called text segmentation.

Text segmentation is the process of dividing a text into meaningful units, such as paragraphs, sections, or chapters.

This process could be as simple as splitting a text by newline characters or as complex as using machine learning algorithms to identify the boundaries of paragraphs or sections. It's important to note that nltk and spaCy` do not provide built-in methods for segmenting text into paragraphs or sections.

Exercises

Open a python file in your local dev environment, install the required libraries, and complete the following exercises.

• Exercise 1: Tokenize the following sentence using the word_tokenize method in nltk: "Welcome to your professional community"

• Exercise 2: Tokenize the following sentence using the spaCy tokenizer: "Welcome to your professional community"

• Exercise 3: Generate bigrams for the following sentence: "While spaCy can be used to power conversational applications, it’s not designed specifically for chat bots, and only provides the underlying text processing capabilities.".

Word Representation

To make our job easier while working with text on a computer, we need to represent words in a way that will help us solve a certain task, such as text classification or named entity recognition. In this lesson, we will discuss different ways to represent words and documents like one-hot encoding, word embeddings, and bag-of-words.

One-hot encoding

One simple way to represent words is to use one-hot encoding, where each word is represented by a vector of zeros, except for one element that is one. This technique is commonly used in machine learning models to represent categories numerically instead of using words. In NLP, here is how it looks:

This is a very simple approach; however, simplicity comes at a cost. To represent each word in a text, we need a vector of size equal to the size of the vocabulary, which can be very large. Also, this approach does not capture the meaning of words and it does not take into account the context in which the words are used. Two words that have similar meanings will have totally different one-hot encodings.

Distributed Representation and Word Embeddings

To address the meaning problem, we can store words using real numbers, where each word is represented by a vector of real numbers and each element of the vector represents a feature of the word. Words with similar meanings will have vector values close to each other. This approach is called distributed representation. To generate these vectors, we can utilize machine learning models trained on large amounts of text data. Based on the context, the computer can learn words with similar or related meanings.

Word2vec

Word2Vec is a popular model for word distributional representation, developed by researchers at Google. It operates on the principle that words which appear in similar contexts often share similar meanings. Word2vec employs a shallow neural network to learn word representations from extensive text corpora.

Watch this video to delve deeper into word representation and Word2vec:

I'm blown away by the king-queen example in the above video. It's amazing how word2vec can capture the meaning of words.

The code utilized in the video is available here

Word Embeddings

Word embedding, a form of distributed representation, captures semantic relationships between words by mapping them to dense, low-dimensional vectors within a continuous vector space. Word2Vec serves as a specific algorithm for word embedding.

✅ Try this interesting tool to experiment with word embeddings. Clicking on one word reveals clusters of similar words: 'toy' clusters with 'Disney', 'LEGO', 'PlayStation', and 'console'.

Here's a Python example for word embedding:

from gensim.models import Word2Vec
from nltk.tokenize import word_tokenize
import nltk
nltk.download('punkt')

# Example sentences
sentences = [
    "The quick brown fox jumps over the lazy dog.",
    "The cat is cute.",
    "The dog is friendly."
]


# Tokenize the sentences
tokenized_sentences = [word_tokenize(sentence.lower()) for sentence in sentences]

# Train the Word2Vec model
model = Word2Vec(sentences=tokenized_sentences, vector_size=100, window=5, min_count=1, workers=4)

# Get the word vectors
word_vectors = model.wv

# Print the word vector for a specific word
print("Vector representation of 'dog':", word_vectors['dog'])

# Find similar words
similar_words = word_vectors.most_similar('dog')
print("Words similar to 'dog':", similar_words)

Bag-of-Words

Bag-of-Words (BoW) is a simple and popular method for representing text data. It is based on the idea that the order of words in a document does not matter, and that the presence of words in a document is more important than the order of the words. In our previous section when we talked about cleaning text by removing stop words and punctuation, we were preparing the text for BoW.

BoW represents a document as a vector of word counts. Each element in the vector represents the count of a word in the document. The size of the vector is equal to the size of the vocabulary. Here's an example of how to use BoW in nltk:

from sklearn.feature_extraction.text import CountVectorizer
corpus = [
    'This is the first document.',
    'This document is the second document.',
    'And this is the third one.',
    'Is this the first document?',
]
vectorizer = CountVectorizer()
X = vectorizer.fit_transform(corpus)
print(vectorizer.get_feature_names_out())
print(X.toarray())

The output of this code will be:

['and' 'document' 'first' 'is' 'one' 'second' 'the' 'third' 'this']
[[0 1 1 1 0 0 1 0 1]
 [0 2 0 1 0 1 1 0 1]
 [1 0 0 1 1 0 1 1 1]
 [0 1 1 1 0 0 1 0 1]
]

In the above sample, we can see that the word "document" appears once in the first document (first text in the corpus list), twice in the second document, 0 times in the third, and once in the fourth.

Document-Term Matrix (DTM):

DTM represents documents as rows and words (terms) as columns in a matrix. Each cell in the matrix represents the frequency of a particular word in a particular document.

This format is called the document-term matrix. Each row in the matrix represents a document, and each column represents a word in the vocabulary. The value in each cell represents the count of the word in the document. The document-term matrix can be used as input to machine learning models for tasks such as text classification, topic modeling, and sentiment analysis.

For example, if we have three documents ["The cat is cute.", "The dog is cute too.", "The cat and the dog are friends."], and a vocabulary of ["the", "cat", "is", "cute", "dog", "too", "and", "are", "friends"], the DTM might look like:

Comparison

Each of the above techniques has its own advantages and disadvantages, and the choice of representation depends on the specific task at hand. Let's summarize the differences between word embedding, DTM, and BoW:

Word Embedding:

Represents words as dense vectors in a continuous vector space, capturing semantic similarities. Advantages:

• Captures semantic relationships between words effectively.
• Handles out-of-vocabulary words by learning continuous representations.
• Useful for various NLP tasks like classification, sentiment analysis, and translation.

Disadvantages:

• Requires substantial training data and computational resources.
• May struggle with rare or domain-specific words.

Suitable for tasks like sentiment analysis, language translation, and document clustering.

Document-Term Matrix (DTM):

Represents term frequencies in documents as a matrix, with rows for documents and columns for terms. Advantages:

• Provides a simple and interpretable representation of text data.
• Easy to implement and understand.
• Compatible with various machine learning algorithms. Disadvantages:
• Doesn't capture semantic relationships between words.
• Memory-intensive for large datasets due to high dimensionality.

Suitable for sentiment analysis, topic modeling, and spam detection.

Bag of Words (BoW):

The Bag of Words (BoW) model represents documents as unordered collections of word frequencies.

Advantages:

• Simple and intuitive representation of text data.
• Easy to implement and understand.
• Compatible with various machine learning algorithms. Disadvantages:
• Loses information about word order and context.
• Doesn't capture semantic relationships between words.
• Memory-intensive for large datasets due to high dimensionality.

Use Cases

1. One-hot Encoding:

   • Typically used in tasks where categorical data, such as words or features, need to be represented as numerical vectors.
   • Commonly employed in simple classification tasks or as input to machine learning models that require numerical inputs.

2. Distributed Representation and Word Embeddings (Word2Vec):

   • Widely utilized in natural language processing (NLP) tasks to capture semantic relationships between words.
   • Suitable for tasks like sentiment analysis, language translation, and document clustering.
   • Especially effective in scenarios where contextual understanding and semantic relationships are crucial.

3. Bag-of-Words (BoW):

   • Frequently used in text classification tasks where word order is not important.
   • Suitable for sentiment analysis, topic modeling, and spam detection.
   • Often applied in scenarios where the presence of specific words matters more than their sequence.

4. Document-Term Matrix (DTM):

   • Commonly used in text mining and information retrieval tasks.
   • Ideal for tasks like document clustering, keyword extraction, and topic modeling.
   • Effective in scenarios where understanding the frequency distribution of words across documents is essential.

Summary

In this lesson, we explored key techniques for representing text in Natural Language Processing (NLP), covering one-hot encoding, Word2Vec, Bag-of-Words (BoW), and Document-Term Matrix (DTM). Each method offers unique strengths for tasks like text classification, sentiment analysis, and topic modeling. Understanding these techniques is essential for effective text analysis in NLP applications.

Practice: Data Cleaning

Follow the Colab notebook provided below to practice data cleaning:

Practice : Text Summarization

Follow the Colab notebook provided below to practice and build a text summarizer:

Language Models

Before we begin discussing language models, I'd like you to take a minute and think about the term "model." What does it mean to you? What comes to mind when you hear the word "model"? How useful do you find having a model of something?

What is a Language Model?

A language model is a representation of a language. We are interested in finding ways to represent languages so that machines can understand and process them.

One model I thought of while writing this section is one that represents sentences without any stop words or punctuation, with each word converted to its root form. How could this be useful? Well, this model could be used to compare sentences to see if they are similar or not, and perhaps even to compress text.

In the field of natural language processing (NLP), however, we are interested in more sophisticated models that can capture the entirety of a language and its dynamics. This helps us perform complex tasks such as machine translation, text summarization, and question answering.

Rule-based Language Models

The natural starting point for developing language models is to turn to the field of linguistics, which has been the study of languages for centuries. This involves understanding how linguists have defined and represented languages over time.

A common method in this area mirrors how we typically learn languages in school. We study grammar rules, vocabulary, and syntax. We learn to construct sentences, use punctuation, and spell words correctly. This approach to language learning is rule-based.

Grammar and Syntax

One method of teaching a computer to understand the structure of a natural language involves teaching it the rules of grammar and syntax. This constitutes the rule-based approach to language understanding.

A formal grammar is a collection of rules for generating sentences in a language.

A context-free grammar (CFG) is a type of formal grammar that describes the syntactic structure of a language through a set of production rules. These rules dictate how various constituents (such as words, phrases, and sentences) can be combined to form grammatically correct sentences. A context-free grammar includes the following elements:

Terminals: These are the basic building blocks of the language, including words or punctuation symbols. Terminals are the most fundamental units of the language and cannot be broken down further. For instance, in English, terms like "cat", "dog", "run", and "jump" serve as terminals.

Non-terminals: These symbols represent categories of linguistic elements, such as noun phrases (NP), verb phrases (VP), Nouns (N), and verbs (V), among others. Non-terminals act as placeholders that can be substituted with terminals or other non-terminals in accordance with the production rules.

Production Rules: These rules outline how non-terminals can be expanded or substituted by other symbols (terminals or non-terminals). Each rule includes a non-terminal symbol on the left-hand side and a sequence of symbols (terminals or non-terminals) on the right-hand side.

To delve deeper into context-free grammars and their application in sentence generation, watch this informative video:

The code sample below utilizes the Natural Language Toolkit (NLTK) library in Python to establish a context-free grammar (CFG) and parse sentences based on that grammar.

import nltk

# Define a context-free grammar (CFG) for parsing sentences
grammar = nltk.CFG.fromstring("""
    S -> NP VP

    AP -> A | A AP
    NP -> N | D NP | AP NP | N PP
    PP -> P NP
    VP -> V | V NP | V NP PP

    A -> "big" | "blue" | "small" | "dry" | "wide"
    D -> "the" | "a" | "an"
    N -> "she" | "city" | "car" | "street" | "dog" | "binoculars"
    P -> "on" | "over" | "before" | "below" | "with"
    V -> "saw" | "walked"
""")

# Create a parser using the defined grammar
parser = nltk.ChartParser(grammar)

# Take an input sentence from the user
sentence = input("Sentence: ").split()
try:
    # Parse the sentence and generate parse trees
    for tree in parser.parse(sentence):
        tree.pretty_print()
except ValueError:
    # If no parse tree is possible, inform the user
    print("No parse tree possible.")

In this approach, we manually feed the computer with the rules of grammar and syntax. This method, however, has its limitations, as it is challenging to formulate rules that cover all possible sentences in a language. Additionally, accounting for the inherent ambiguity of human language poses a significant challenge.

Statistical Language Models

You might already have an idea of what this entails. Isn't it similar to the approach we've been discussing throughout this course? We either hard-code the rules or—what's the other option? Yes, we use data to learn the rules or identify patterns.

Statistical language models are predicated on the notion that language behaves as a statistical phenomenon. These models employ statistical techniques to discern patterns and structures within a language from a vast corpus of textual data.

In statistical language models, rather than handling the entirety of the text data at once, we can adopt the n-gram methodology we explored earlier. This strategy involves segmenting the text into smaller fragments to learn patterns within each segment. This forms the basis of statistical language models. For instance:

Consider the sentence "I am going to the ". A statistical language model might predict that the next word is "store" with considerable probability because the phrase "going to the store" frequently occurs in English.

Or take the sentence "no the dark eat banana." A statistical language model could indicate that this sequence is likely not a valid English sentence. It might even suggest a more grammatically correct version of the sentence if possible.

Here's an interesting example involving the use of a Markov chain statistical model to generate text:

The code used in the video is available here

A Markov chain represents a mathematical model that transitions from one state to another among a finite or countable number of possible states.

Watch this video for a slightly different take on statistical language models:

Neural-Networks-based Language Models

Another approach to language modeling leverages neural networks to model the probability distribution over words in a sentence. Beyond this, we can employ various types of neural networks to learn different aspects, capture distinct patterns, and address a wide array of problems.

Watch this video to learn about neural network-based language models and how RNNs and Transformers are used in language modeling:

Recurrent Neural Networks (RNNs)

One of the most favored neural network architectures for language modeling is the Recurrent Neural Network (RNN). Designed to process sequential data, such as word sequences in a sentence, RNNs are adept at capturing the context of a word within its sentence, rendering them particularly suitable for language modeling tasks.

An advancement in language models involves the application of RNNs, especially Long Short-Term Memory (LSTM) networks, to model the probability distribution across words. We have a practice on this topic in the next section.

Transformers

The inherent sequential nature of RNNs introduces inefficiencies when processing lengthy data sequences, such as extended sentences or documents. This inefficiency stems from the vanishing gradient problem, hindering the network's ability to recognize long-range dependencies within the data. In response, researchers have devised more sophisticated neural network architectures like transformers, optimized for efficiently handling long data sequences.

Transformers employ the attention mechanism, enabling the model to concentrate on different segments of the input sequence during prediction. This model has attained unparalleled performance, forming the backbone of the most advanced language models, including BERT, GPT-2, and GPT-3.

Large Language Models

A "large" language model is typically characterized by its training on a vast dataset. The term "large" reflects not just the dataset's volume but also its complexity and diversity. These models are developed on extensive text corpora, potentially comprising billions or even trillions of words, gathered from a variety of sources like books, articles, websites, and other text repositories. Training on such broad datasets allows the model to acquire a comprehensive understanding of natural language, encompassing syntax, semantics, and contextual subtleties, often resulting in more accurate and robust models capable of efficiently performing a plethora of natural language processing tasks.

Training large language models requires considerable computational resources, such as powerful GPUs or TPUs, alongside expansive distributed training infrastructure. This process usually involves executing millions of iterations of the training algorithm, tuning the model parameters based on the gradients of the loss function relative to the parameters.

Language Models Examples

Modern language models such as Google's BERT, OpenAI's GPT series, Facebook AI's RoBERTa, and Palm's T5 signify progress in natural language processing.

BERT revolutionized understanding bidirectional context through its transformer architecture, enhancing performance in tasks like text classification and named entity recognition.

The GPT series, notably GPT-3, is celebrated for its autoregressive approach, sequentially generating coherent text based on preceding tokens. RoBERTa refined BERT's architecture, enhancing pre-training methods for better efficacy in tasks such as sentiment analysis and machine translation.

T5 marked a significant advancement by treating all NLP tasks as text-to-text tasks, thus enabling a unified approach to handling diverse tasks and facilitating adaptation to new domains. T5's adaptability, scalability, and its integration of transformer architecture with a multi-task learning approach, establish it as a cutting-edge solution for a broad range of language processing challenges.

Large Language Models Resources

For those keen on delving deeper into large language models, the following resources are invaluable:

• Large Language Models From Scratch
• How to Train a new Language Model
• How to Build a Large Language Model from Scratch Using Python
• Creating a Large Language Model from scratch: A beginner's guide
• GPT-3: Language Models are Few-Shot Learners
• BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
• T5: Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer

Practice: Create Poetry

Carefully watch the video below and follow the associated Colab notebook to learn how to generate text using an LSTM:

Colab Notebook

Deep Reinforcement Learning for Dialogue Generation

This lesson is about the paper "Deep Reinforcement Learning for Dialogue Generation" by Jiwei Li, Will Monroe, Alan Ritter, Dan Jurafsky, Michel Galley, and Jianfeng Gao.

The paper was presented at the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP). The paper introduces a novel approach to dialogue generation using deep reinforcement learning, aiming to improve the quality and coherence of conversational agents.

The authors propose a model that combines reinforcement learning with sequence-to-sequence models to generate more contextually relevant and engaging responses. Through this lesson, students will learn about the challenges of dialogue generation and how deep reinforcement learning can be used to enhance the performance of conversational agents.

Read the paper here.

Happy learning!

Week 8 Quiz

Before attempting the quiz, read the following carefully.

• This is a timed quiz. You will have only one attempt.
• You will have 20 minutes to complete multiple-choice questions.

➡️ Access the quiz on here

Assignment : Next Word Prediction

Follow the below Colab notebook to complete the assignment on next word prediction:

Submission

Submit your assignment via gradescope here

Final Project

The final project is an opportunity for you to apply the knowledge and skills that you have learned in the course to a real-world problem. You are required to select one of the provided project ideas, develop a working solution, and submit 3 key deliverables:

• Working Project: A functional AI-based system.
• Source Code: The source code of the project (Github link).
• Project Report: A document detailing your development process, including the sections below.

Team Size: 1 - 3

Submission Deadline: 14 June 2024 Submission Link: Submit Your Project

Progressive Project Report

You are required to fill the project report progressively while working during week 9 and week 10. Otherwise, your submission might not be accepted. Progressively means that you should fill the report as you work on the project, not all at once at the end of the project.

Project Report

Your project report (a sample can be found here.) must document the following steps:

• Problem Identification: Clearly define your project's computational problem (~50 words).
• Exploration of Alternatives: Investigate various algorithms and methodologies that could solve the problem. Discuss the pros and - cons of at least three approaches (~200 words).
• Selection and Justification: Choose the most appropriate solution and provide a rationale for your choice based on its - efficiency, accuracy, and suitability for the problem (~50 words).
• Implementation Details: Provide details on the dataset used, the model/algorithm chosen, the frameworks and tools, etc.
• Demo Link: Include a link to a working demo of the project. It could be a live link on the web or a recorded video.

Project Ideas

Project 1: AI-Powered Home Security System

Objective: Develop a system that utilizes cameras placed at home entrances to detect and alert homeowners about human presence in a designated security zone. Requirements: Implement an object detection system to identify human figures in a video feed.

Project 2: Stock Market Prediction

Objective: Construct a model to forecast future stock prices using historical data.

Requirements: Develop a time series forecasting model that predicts the stock price of a certain company. Visualize prediction accuracy and model performance.

Project 3: Business Question Answering System

Objective: Build an AI-driven system that acts as a customer service agent to answer frequently asked questions about a business.

Requirements: Develop a natural language processing model capable of understanding and responding to user queries.

Evaluation Rubric

Problem Identification (10 Points)

• [0 Points]: The problem is not clearly defined; lacks detail.
• [3 Points]: The problem is identified but not clearly articulated; some details are missing.
• [5 Points]: The problem is well-defined and detailed with clear relevance to AI.

Methodology (20 Points)

• [20 Points]: Excellent, thorough exploration of varied alternatives; detailed analysis including pros and cons of each. Well-justified selection; reasoning is comprehensive, detailed, and thoroughly logical.
• [15 Points]: Moderate exploration of alternatives; moderate detail and consideration of options.
• [10 Points]: Some exploration of alternatives; moderate detail and consideration of options.
• [4 Points]: Limited or no exploration of alternative solutions; lacks depth.

Implementation and Testing (70 Points)

• [60-70 Points]: Excellent implementation; system functions flawlessly with reasonable performance and robust testing. Process and implementation details well documented.
• [50-60 Points]: Good implementation; system functions as intended with good performance. Documentation is adequate.
• [40-50 Points]: Implementation is mostly complete; minor issues in functionality or performance.
• [0-40 Points]: Implementation is incomplete or flawed; major issues in functionality.

Total Points: 100