Unit V-

Other Types of Learning

Unit V: Reinforcement learning - Elements of Reinforce learning – Model based Learning – Temporal difference learning - representation Learning-Active learning –Instance based Learning – Association rule learning algorithm - Ensemble Learning Algorithm - Regularization Algorithm.

Reinforcement Learning(RL)

• Reinforcement Learning is a feedback-based Machine learning technique in which an agent(computer program) learns to behave in an environment by performing the actions and seeing the results of actions. For each good action, the agent gets positive feedback or rewards and for each bad action, the agent gets negative feedback or penalty.
• In Reinforcement Learning, the agent learns automatically using feedbacks without any labeled data, unlike supervised learning. Since there is no labeled data, so the agent is to learn by its experience only.
• RL solves a specific type of problem where decision making is sequential and the goal is long-term, such as games, robotics etc.
• The agent interacts with the environment and explores it by itself. The

primary goal of an agent in reinforcement learning is to improve the

performance by getting the maximum positive rewards.

• Example: In maze environment, the agent goal is to find the diamond. The agent interacts with the environment by performing some actions, and based on those actions, the state of the agent gets changed, and it also receives a reward or penalty as feedback.

• The agent continues doing these three things (take action, change state/remain in the same state, and get feedback), and by doing these actions, its learns and explores the environment.
• The agent learns that what actions lead to positive feedback or rewards and what actions lead to negative feedback or penalty. As a positive reward, the agent gets a positive point, and as a penalty, it gets a negative point.

Key Features of Reinforcement Learning

• In RL, the agent is not instructed about the environment and what actions need to be taken.
• It is based on the hit and trial process.
• The agent takes the next action and changes states according to the

feedback of the previous action.

• The agent may get a delayed reward.
• The environment is stochastic, and the agent needs to explore it to reach to get the maximum positive rewards.

​

Elements of Reinforcement Learning

There are four main elements of Reinforcement Learning, which are

given below:

• Policy
• Reward Signal
• Value Function
• Model of the environment

1. Policy π : The policy π, defines the agent’s behavior and is a mapping from the states of the environment to actions: π : S → A. The policy defines the action to be taken in any state s_t : a_t = π(s_t). The value of a policy π, V^π(s_t), is the expected cumulative reward that will be received while the agent follows the policy, starting from state s_t .

​

• Reward Signal: The goal of reinforcement learning is defined by the reward signal. At each state, the environment sends an immediate signal to the learning agent, and this signal is known as a reward signal. These rewards are given according to the good and bad actions taken by the agent.

The agent's main objective is to maximize the total number of rewards for good actions. The reward signal can change the policy, such as if an action selected by the agent leads to low reward, then the policy may change to select other actions in the future.

3. Value Function: The value function gives information about how good the situation and action are and how much reward an agent can expect. A reward indicates the immediate signal for each good and bad action, whereas a value function specifies the good state and action for the future. The value function depends on the reward, as without reward there could be no value. The goal of estimating values is to achieve more rewards.
4. Model: The model, which mimics the behavior of the environment. With the help of the model, one can make inferences about how the environment will behave. Such as, if a state and an action are given, then a model can predict the next state and reward.

The model is used for planning, which means it provides a way to take a course of action by considering all future situations before actually experiencing those situations. The approaches for solving the RL problems with the help of the model are termed as the model-based approach. Comparatively, an approach without using a model is called a model-free approach.

How does Reinforcement Learning Work?

To understand the working process of the RL, consider two main things: 1.Environment: It can be anything such as a room, maze, football ground, etc. 2.Agent

Let's take an example of a maze environment that the agent needs to

explore.

The agent is at the very first block of the maze. The maze is consisting of an S₆ block, which is a wall, S₈ a fire pit, and S₄ a diamond block. The agent cannot cross the S₆ block, as it is a solid wall. If the agent reaches the S₄ block, then get the +1 reward; if it reaches the fire pit, then gets -1 reward point. It can take four actions:

move up, move down, move left, and move right.

States

The agent can take any path to reach to the final point, but he needs to make it in possible fewer steps. Suppose the agent considers the path S9- S5-S1-S2-S3, so he will get the +1-reward point.

The agent will try to remember the preceding steps that it has taken to reach the final step. To memorize the steps, it assigns 1 value to each previous step.

Now, the

agent has successfully stored the

previous steps assigning the 1 value to each previous block.

If assigned all blocks as 1, then it is difficult to reach the goal.

[Ex]: If the agent starts moving from the block, which has 1 value block on both sides?

It will be a difficult condition for the agent whether it should go up or down as each block has the same value. So, the above approach is not suitable for the agent to reach the destination.

The Bellman Equation:

Hence to solve the problem, use the Bellman equation, which is the main concept behind reinforcement learning.

The Bellman equation was introduced by the

Mathematician Richard Ernest Bellman in the year 1953, and hence it is called as a Bellman equation. It is associated with dynamic programming and used to calculate the values of a decision problem at a certain point by including the values of previous states.

Bellman Equation is used to calculate the value functions in dynamic programming or environment that leads to modern reinforcement learning.

How to represent the agent state?

Represent the agent state using the Markov State that contains all the required information from the history. The State S_t is Markov state if it follows the given condition:

P[S_t+1 | S_t ] = P[S_{t +1} | S₁,......, S_t]

The Markov state follows the Markov property, which says that the future is independent of the past and can only be defined with the present. The RL works on fully observable environments, where the agent can observe the environment and act for the new state.

​

Markov Decision Process or MDP

It is used to formalize the reinforcement learning problems. If the environment is completely observable, then it can be modeled as a Markov Process. In MDP, the agent constantly interacts with the environment and performs actions; at each action, the environment responds and generates a new state.

MDP is used to describe the environment for the RL, and almost all the RL problem can be formalized using MDP.

MDP contains a tuple of four

elements (S, A, P_a, R_a):

1. A set of finite States S

2. A set of finite Actions A
3. Rewards received after transitioning from state S to state S', due to action a.
4. Probability P_a.

​

MDP uses Markov property

Markov Property: It says that "If the agent is present in the current state S1, performs an action a1 and move to the state s2, then the state transition from s1 to s2 only depends on the current state and future action and states do not depend on past actions, rewards, or states.

Definition of initial state, goal state, Episode, Policy and Optimal Policy Depending on the application, a certain state may be designated as the initial state(search starts) and in some applications, there is a goal state where the search ends; all actions in this terminal state transition to itself with probability 1 and without any reward.

The sequence of actions from the start to the terminal state is an episode or a trial.

​

The policy, π, defines the agent’s behavior and is a mapping from the states of the environment to actions: π : S →A. The policy defines the action to be taken in any state s_t : a_t = π(s_t). The value of a policy π, V^π(s_t), is the expected cumulative reward that will be received while the agent follows the policy, starting from state s_t.

For each policy π, optimal policy there is a V^π(s_t), and to find the optimal policy π^∗ such that

V^∗(s_t) = max [V^π(s_t)] , ∀s_t

Problem : Apply Bellman equation for the given Maze game. Agent

is at s9th block , goal is at s4, wall is at s6, fire is at s8.

The key-elements used in Bellman equations are: Action performed by the agent is referred to as "a" State occurred by performing the action is "s."

The reward/feedback obtained for each good and bad action is "R."

The Discount factor is “γ "

Where,

The Bellman equation is: V(s) = max [R(s,a) + γ V(s`)]

V(s)= value calculated at a particular point.

R(s,a) = Reward at a particular state s by performing an action. V(s`) = The value at the previous state.

For s3 block:

V(s3) = max [R(s,a) + γV(s`)]

Here V(s')= 0 because there is no previous state .

The Reward of R(s,a) =1[ If it move to right side the reward is 1]

V(s3)= max[R(s,a) + γV(s`)] γ= 0.9(Assume)

max[1+0.9 × 0]

V(s3)= max[1] 🡪 V(s3)= 1.

For s2 block:

V(s2) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 1, and R(s, a)= 0, because there is no reward at this

state.

V(s2)= max[0+ 0.9(1)]

V(s2)= max[0.9] 🡪 V(s2) =0.9

For s1 block:

V(s1) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 0.9, and R(s, a)= 0, because there is no reward at this state also.

V(s1)= max[0 + 0.9(0.9)]

V(s1)= max[0.81] 🡪 V(s1) =0.81

For s5 block:

V(s5) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 0.81, and R(s, a)= 0, because there is no reward at this state also.

V(s5)= max[0+0.9(0.81)]

V(s5)= max[0.73]🡪 V(s5) =0.73

For s9th block:

V(s9) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 0.73, and R(s, a)= 0, because there is no reward at

this state also.

V(s9)= max[0+ 0.9(0.73)]

V(s9)= max[0.66]🡪 V(s9) =0.66

For s10th block:

V(s10) = max [R(s,a) + γV(s`)] Here γ= 0.9, V(s')= 0.66, and R(s,a)= 0, because there is no reward at this state also.

V(s10)= max[0+ 0.9(0.66)]

V(s10)= max[0.59]🡪 V(s10)

=0.59

Similarly find for s11,s12, s7

V(s11) =0.53

V(s12) =0.48

V=0.59 V=0.53

V=0.48

For s7th block: The agent is in 7^th block, there are 4 actions.

Left side is wall, Right side is Fire, Up is s3, Bottom is s11. Compare s3 and s11 values, the value of s3 is high.

The agent may change the route because it always tries to find the optimal path. So now, let's consider from s7th block and the previous state is s3,

V(s7) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 1, and R(s, a)= 0, because there is no reward at this state also.

V(s7)= max[0+ 0.9 ×1]

V(s7)= max[0.99]🡪 V(s7) =0.9

V=0.59

V=0.53

V=0.48

V=0.9

For s11, consider the previous state as s7 or s10, find the value for s11 which is higher than the previous value by s7.

For s11th block:

V(s11) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 0.9, and R(s, a)= 0, because there is no reward at this

state also.

V(s11)= max[0+ 0.9(0.9)]

V(s11)= max[0.81]🡪 V(s11) =0.81 which is greater than the previous value 0.53

​

For s10th block:

V(s10) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 0.81, and R(s, a)= 0, because there is no reward at this state also.

V(s10)= max[0+ 0.9(0.81)]

V(s10)= max[0.73]🡪 V(s10) =0.73 which is greater than the previous

value 0.59

For s12th block:

V(s12) = max [R(s,a) + γV(s`)]

Here γ= 0.9, V(s')= 0.81, and R(s, a)= 0, because there is no reward at

this state also.

V(s12)= max[0+ 0.9(0.81)]

V(s12)= max[0.73]🡪 V(s12) =0.73 which is greater than the previous value 0.59

Types of Reinforcement learning

There are mainly two types of reinforcement learning, which are:

1. Model Based Learning 2. Temporal based Learning

​

Model Based Learning : The agent learn the optimal behavior by learning a model of the environment by taking actions and observing the outcomes that include the next state and the immediate reward. The agent know the environment model parameters and do not need any exploration and can directly solve for the optimal value function and policy using dynamic programming.

​

Temporal based Learning : The agent learning from an environment through episodes with no prior knowledge of the environment. The difference between the current state Q value and the next state of one time step later is called as Temporal Difference(TD). Such algorithms are called temporal difference (TD) algorithms

Model based Reinforcement Learning

In this learning, the optimal value function is known, the optimal policy is to choose the action that maximizes the value in the next state.

Where π is the policy

E[r_t+1] is the expected reward at S_t+1 stage V[S_t+1] is the value function

γ is the Discount factor

Model-based algorithms are Dynamic Programming (Policy Iteration and Value Iteration) - these all use the model's predictions of next state and reward in order to calculate optimal actions. Specifically in Dynamic Programming, the model must provide state transition probabilities, and expected reward from any state, action pair. This is rarely a learned model.

Value Iteration: To find the optimal policy, use the optimal value function, and there is an iterative algorithm called value iteration that has been shown to converge to the correct V^∗ values. Its pseudocode is

Where Q is the value of the action „a‟ in the state „s‟.

Policy Iteration: In policy iteration, store and update the policy. The idea is to start with a policy and improve it repeatedly until there is no change. The value function can be calculated. Then check whether improve the policy or not by considering values of the value function. This step is guaranteed to improve the policy, and when no improvement is possible, the policy is guaranteed to be optimal. The pseudocode is

Problem: Find the optimal policy for the ship to reach its homeland

safely with maximum rewards.

Consider a pirate ship, which is currently anchored at an island and, has

to reach its homeland safely. There are two routes it could choose from. If it takes the route to the north, then it can reach an island which is full of gold, which it can collect, and then move south to reach the homeland. However, there is an area with a very high gravity (like the Bermuda triangle) to the north of the gold island. If the ship reaches there by mistake, then it will be sucked into it and the ship is lost forever.

If it takes the route to the south, then it can reach an island, which is full of silver, which it can collect, and then move north to reach the homeland. There is a prison island to the south of the silver island. If the ship lands there by mistake, then the ship will be captured and the crew will be imprisoned. The ship‟s captain possesses a broken compass. . So, every time, the captain makes a move towards north, he moves north with a probability of 0.8, however, he might miss the mark and reach south with a probability of 0.2. Similarly, if he moves south, there is a

0.8 probability of going south and 0.2 probability of going north.

Rewards (Positive and Negative):

The rewards to each of the ship‟s landing are,

• Reaching homeland will allow the pirate ship to collect +1 point.
• Landing on the gold island will allow the pirate ship to collect +2 points.
• Landing on the silver island will allow the pirate ship to collect +1 point.
• If the ship gets sucked into Bermuda triangle, then the ship gets -2 points.
• If the ship is captured in the prison island, then the ship get -0.5 points.

​

Solution: Understand the problem and draw the state transition diagram

with states and actions.

Each island is a state and there are two actions, „north‟ and „south‟.

Rewards for each state should included in the diagram.

There are six states including start and destination states. Let us label the

states from S1 to S6 as follows:

S1: Start state

S2: State of landing in gold Island S3: State of landing in silver Island

S4: State of landing in Bermuda Triangle Island S5: State of landing in destination Island

S6: State of landing in prison Island

Transition probability matrix: Compute transition probabilities for

each state/action pair. Based on the probabilities provided above, the

state transition diagram and two actions[North,

South] to build a

transition probability matrix for both actions. Applying Bellman‟s

equation, T(S, a, S‟) refers to the transition probability of moving from

state S to state S‟ after taking an action „a‟.

Transition Probability Matrix for Action North

Transition Probability Matrix for Action South

Policy Iteration algorithm:

Step 1: Randomly initialize the policy. Initialize actions randomly at every state of the system.

Step 2(Policy Evalation) : Calculate the value function of each state

using Bellman equation[sum of the (reward + total value of each action)]

Here is p is the transition probability, also denoted by T.

Step 3 (policy improvement) : For every state, get the best action from

value function using

If the best action is better than the present policy action, then replace the

current action by the best action.

Policy Iterations:

Iterate steps 2 and 3, until convergence. If the policy did not change throughout an iteration, then consider that the algorithm has converged.

​

Step 1: Randomly initialize the policy.

Let randomly initialize the policy (state to action mapping) as moving north for all states. P = {N, N, N, N, N, N}

If observe the state transition diagram, the states S4, S5, S6 do not have any actions supported in these states, as these are end states. So let curtail the policy, to apply to only the first three states where action can taken. P = {N, N, N}

The Bellman equation is: V(s) = max [R(s,a) + γ V(s`)]

First iteration:

Let us assume the initial value V(s) for all states as 0 and the discount factor λ = 0.Thus, the Bellman equation would reduce to V(s) = R(s), where R(s) is the reward for entering a state.

Policy Evaluation for first iteration:

V[S1] = 0; V[S2] = 2; V[S3] = 1; V[S4] = -2 ; V[S5] = 1 ; V[S6] = -0.5

Policy Improvement for first iteration: Let us apply the equation

provided for Policy Improvement.

I Iteration : Policy Improvement

The policy obtained based on the above table is as follows: P = {N,S,N}

Second iteration: Policy Evaluation for the second iteration:

Before second iteration the values are V[S1] = 0; V[S2] = 1; V[S3] = 1.5;

V[S4] = -2 ; V[S5] = 1 ; V[S6] = -0.5.

After, second iteration ,values for each state could be changed as

V[S1] = 3; V[S2] = 1; V[S3] = 1.5; V[S4] = -2 ; V[S5] = 1 ; V[S6] = -0.5.

S1: Start state S2: State of landing in gold Island

S3=1.5

S3: State of landing in silver Island S4: State of landing in Bermuda Triangle Island S5: State of landing in destination Island

S6: State of landing in prison Island

After second iteration

​

S2=1

Policy Improvement for second iteration:

The policy obtained based on above table is as follows: P = {S, S, N} ; The policy is different from previous iteration of P = {N, S, N} ; Repeat the iteration when policy never change.

Third iteration:

Policy Evaluation for third iteration:

Values for each state could be summarized as below: V[S1] = 2.5; V[S4] = -2

V[S2] = 1; V[S5] = 1

V[S3] = 1.5; V[S6] = -0.5

Policy Improvement for third iteration:

The policy obtained based on above table is as follows:

P = {S, S, N}

If compare this policy, to the policy obtained in second iteration. Observe that policies did not change, which implies algorithm has converged and this is the optimal policy.

The policy obtained is P = {S, S, N} The policy indicates S1 =S, S2=S, S3=N The policy maps the states with actions. At S1 state, it take south action

At S2 state, it take south action

At S3 state, it take north action

Temporal based Reinforcement Learning Algorithms

The main used algorithms are:

Q-Learning: Q-learning is an Off policy temporal based RL algorithm. These methods are the way of comparing temporally successive predictions. It learns the value function Q (S, a), which means to take action "a" at a particular state “s”.

​

State Action Reward State action (SARSA): SARSA stands for State Action Reward State action, which is an on-policy temporal based learning method. The on-policy control method selects the action for each state while learning using a specific policy. The goal of SARSA is to calculate the Q^π(s, a) for the selected current policy π and all pairs of (s,a).

​

In off-policy method, the value of the best next action is used without using the policy. In on-policy method, the policy is used to determine the next action. The on-policy version of Q learning is the Sarsa algorithm.

Q Learning and SARSA Learning

Other Types of Learning

• Representation learning – Feature Learning
• Active learning
• Instance-based Learning
• Association Rule Learning Algorithm
• Ensemble learning
• Regularization algorithm

Representation learning

Another name for representation learning is feature learning. The main objective of representation learning is to find an appropriate representation of data based on features to perform a machine learning task. Representation learning has become a field in itself because of its popularity.

Example for Representation Learning: Classify/identify the types of triangles . Find unique characteristics of the type of triangle given as input.

The Representation Learning Model work as,

Input – Triangular image

Representation – Three angles, length of sides.

Model – It gets an input representation (angles, length of sides) and applies rules as per Table , to detect the type of triangle.

• What happens when the input shapes like square, rectangle, circle, or all sort of shapes instead of a triangle? What if the image contains both a triangle and a circle? Designing to adapt to this kind of features requires deep domain expertise for real-world applications.
• Deep Learning goes one step further and learns/tries to learn features on its own. To feed in an image as input and the system learn features like human beings do.
• Representation learning are most widely used in words, speech recognition, signal processing, music, and image identification.

V represents the input data, and H represents the causes. When the causes (H) explains the data (V) , it is called as Recognition. When unknown causes (H) are combined, it can also generate the data (V), it is called as generative (or) Generation.

​

Representation learning can be either supervised or unsupervised. The different types of Representation learning are,

1. Supervised neural networks and multilayer perceptron
2. Independent Component Analysis (unsupervised)
3. Autoencoders (unsupervised) and
4. Various forms of clustering

Independent Component Analysis(ICA)

ICA is used primarily for separating unknown source signals from their observed linear mixtures after the linear mixture with an unfamiliar matrix (A) . Nil information is known about the sources or the mixing process except that there are N different recorded mixtures. The job is to recuperate a version(U) of the sources (S) which are identical except for scaling, by finding a square matrix (W) specifying filters that linearly invert the mixing process, i.e. U = WX.

Cocktail Party Problem or Blind Source Separation problem

Sources S

​

unfamiliar matrix (A)

​

Recorded signals (X)

Recorded signals (X)

Matrix (W)

recuperate version(U)

X= SA 🡪 S= A^-1 X

W= A^-1

U = WX = A^-1 S A = S

Autoencoders

Autoencoders belong to the neural network family. The neural network‟s (autoencoder) target output is its input (x) in a different form (x‟). In Autoencoders, the dimensionality of the input is equal to the dimensionality of the output, and essentially

x‟ = x. x‟ = Decode (Encode(x))

To get the value from the hidden layer, multiply the (input to hidden) weights by the input. To get the value from the output, multiply (hidden to output) weights by the hidden layer values.

Z = f (WX) Y = g (VZ)

So Y = g(V f (WX)) = VWX

​

Heuristics for Autoencoders

Autoencoder training algorithm can be summarized as below: For each input x

1. Do a feed-forward pass to compute activations at all hidden layers, then at the output layer to obtain an output X
2. Measure the deviation from output X to the input X
3. Back propagate the error through the net and perform weight updates.

ACTIVE LEARNING

Active learning is a type of semi-supervised learning in which a learning algorithm can interactively query the user (or some other information source) to obtain the desired outputs at new data points. The information source is also called teacher or oracle.

This approach is used to construct a high-performance classifier while keeping the size of the training dataset to a minimum by actively selecting the valuable data points.

Where should apply active learning?

• Small amount or a huge amount of dataset.
• Annotation of the unlabeled dataset cost human effort, time, and money.
• Limited processing power.

Let P be the population set of all data under consideration. During each

iteration, I, P (total population) is broken up into three subsets.

1. P(K, i): Data points where the label is known (K).
2. P(U, i): Data points where the label is unknown (U)
3. P(C, i): A subset of P(U, i)that is chosen (C) to be labelled.

Active learning concentrates on identifying the best method P(C, i) to chose (C) the data points.

Heuristics for active learning

1. Start with a pool of unlabelled data P(U, i)
2. Pick a few points at random and get their labels P(C, i)
3. Repeat

Example: On a certain planet, there are various fruits of different size(1- 5), some of them are poisonous and others don‟t. The only criteria to decide a fruit is poisonous or not is ,its size. Train the classifier that predicts the given fruit is poisonous or not. A fruit with size 1 is not poisonous, the fruit of size 5 is poisonous and after a particular size, all fruits are poisonous.

There are two ways to train the model.

1. check each and every size of the fruit, which consumes time and resources.
2. Apply the binary search and find the transition point (decision boundary). This approach uses fewer data and gives the same results as of linear search.

Algorithm :

1. Train classifier with the initial training dataset
2. Calculate the accuracy
3. While(accuracy < desired accuracy)
4. Select the most valuable data points (in general,

decision boundary)

points close to

5. Query that data point/s (ask for a label) from human oracle
6. Add that data point/s to initial training dataset
7. Re-train the model
8. Re-calculate the accuracy

Active learning query strategies

Few logics for determining which data points should be labelled are

1. Uncertainty sampling
2. Query by committee
3. Expected model change
4. Expected error reduction
5. Variance reduction

Uncertainty sampling: In this method, the active learning algorithm first tries to label the points for which the current model is least specific on the correct output.

​

Query by committee: A range of models are trained on the current labelled data, and vote on the output for unlabelled data; label those points for which the „committee‟ disagrees the most.

​

Expected model change: In this method, the active learning algorithm first tries to label the points that would most change the existing model itself.

​

Expected error reduction: In this method, the active learning algorithm first tries to label the points that would mostly reduce the model‟s generalization error.

​

Variance reduction: In this method, the active learning algorithm first tries to label the points that would reduce output variance

INSTANCE-BASED LEARNING

It is a family of learning algorithms that, instead of performing explicit generalization, compare new problem instances with instances seen in training, which have been stored in memory. The computation is postponed until a new instance is observed, these algorithms are sometimes referred to as "lazy”. It is called instance-based because it constructs hypotheses directly from the training instances themselves. It is also called as memory-based learning.

​

Examples of instance-based learning include K-nearest neighbour algorithm (K-NN), kernel machines (support vector machine, PCA), and radial basis function (RBF) networks.

​

All these algorithms store already known instances and compute distances or similarities between this instance and the training instances to make the final decision.

Radial basis function

Radial basis function (RBF) networks typically have three layers: one

input layer, one hidden layer with a non-linear RBF activation function,

and one linear output layer.

An input vector(X) is used as input to all radial basis functions, each with different parameters. The input layer

(X) is merely a fan-out layer, and no

processing happens here. The second layer (hidden) performs radial basis functions, which are the non-linear mapping from the input space (Vector X) into a higher order dimensional space. The output of the network (Y) is a linear combination of the outputs from radial basis functions. If pattern classification is required (in Y), then a hard-limiter or sigmoid function could be placed on the output neurons to give 0/1 output values

The distinctive part of the radial basis function network (RFFN) is the procedure implemented in the hidden layer. The Gaussian function is the most commonly used radial basis function. In an RBF network, r is the distance from the cluster centre.

Space (distance) computed from the cluster centre is usually the Euclidean distance. For each neuron that is part of the hidden layer, the weights represent the coordinates of the centre of the cluster. Therefore, when that neuron receives an input pattern, X, the distance is found using the following equation:

The variable sigma, σ, denotes the width or radius of the bell-shape

and is to be determined by calculation.

The output y(t) is a weighted sum of the outputs of the hidden layer,

given by

Where u(t) is the input

ϕ(.) is an arbitrary non-linear radial basis function

ǁ.ǁ denotes the norm that is usually assumed to be Euclidean

c are the known centres of the radial basis functions w are the weights of the function

​

The most commonly used radial function is the Gaussian radial

filter, which in case of a scalar input is

Where c is the centre and equal to 0

β is the radius (width) and equal to 1

in Gaussian RBF

2

Pros and cons of instance-based learning method

Advantage: Instance-based learning (IBL) methods are particularly well suited to problems where the target function is highly complex Disadvantages : 1. The cost of classification of new instances can be high (a majority of the calculation takes place at this stage).

2. Many IBL approaches usually study all characteristics of the instances leading to dimensionality-related problems.

ASSOCIATION RULE LEARNING

Association rule learning is a method that extracts rules that best explain

variables in data. These rules

observed relationships between

discover important and

can

commercially useful associations in large

multidimensional data sets that can be exploited by an organization. The most popular association rule learning algorithms are Apriori algorithm and Eclat process.

Apriori algorithm

Apriori is designed to function on a large database containing various types of transactions (for example, collections of products bought by customers, or details of websites visited by customers frequently). Apriori algorithm refers to the algorithm which is used to calculate the association rules between objects. It means how two or more objects are related to one another. In other words, the apriori algorithm is an association rule leaning that analyzes that people who bought product A also bought product B.

Definition of common terms : 1. Itemset 2. Support count

3. Association rule 4. Support 5. Confidence

Itemset: One or more items are grouped together and are surrounded by brackets to indicate that they form a set. Ex: {Bread,Milk, Egg} can be grouped together to form an itemset as those are frequently bought together.

To generalize, if I = {i₁ , i₂ ,…, i_n } are the items in a market basket data and T = {t₁, t₂ ,…, t_n } are the set of all the transactions, then each transaction t_i contains a subset of items from I. A collection of zero or more items is called an itemset. A null itemset is the one which does not contain any item. In the association analysis, an itemset is called k- itemset if it contains k number of items. Thus, the itemset {Bread, Milk, Egg} is a three-itemset.

​

Support count: It denotes the number of transactions in which a particular itemset is present. This is a very important property of an itemset as it denotes the frequency of occurrence for the itemset.

Association rules: It specify patterns of relationships among items. A

typical rule might be expressed as{Bread, Milk}→{Egg}, which denotes that if Bread and Milk are purchased, then Egg is also likely to be purchased. Thus, association rules are learned from subsets of itemsets. For example, the preceding rule is identified from the set of

{Bread, Milk, Egg}. An association rule is an expression of X → Y

where X and Y are disjoint itemsets, i.e. X ∩ Y = 0.

​

Support : It indicates how often a rule is applicable to a given data set. support is the ratio of the number of transactions comprising that product by the total number of transactions.

Support s ( X🡪Y) = X ᴜ Y / N

​

Confidence : It indicates how often the items in Y appear in

transactions that contain X in a total transaction of N. Confidence c ( X🡪Y) = X ᴜ Y / X

Need for Support and Confidence : If there are k items which may or may not be part of an itemset, then there is 2^k ways of creating itemsets with those items.

• For example, if a seller is dealing with 100 different items, then the learner need to evaluate 2¹⁰⁰ itemsets for arriving at the rule, which is computationally impossible. So, it is important to filter out the most important (and thus manageable in size) itemsets and use the resources on those to arrive at the reasonably efficient association rules.
• So, decide the minimum support and minimum confidence of the association rules. From a set of transaction T, find out all the rules that have support ≥ minS and confidence ≥ minC, where minS and minC are the support and confidence thresholds, respectively.

Important strategies for arriving at the association rules:

1. Generate Frequent Itemset: Once the minS is set for a particular assignment, identify all the itemsets that satisfy minS. These itemsets are called frequent itemsets.
2. Generate Rules: From the frequent itemsets found in the previous step, discover all the high confidence rules. These are called strong rules.

Advantages of Apriori Algorithm: 1. use in both large and small

itemsets. 2. Simple to understand and apply.

Disadvantages of Apriori Algorithms: 1. expensive method to find

support since the calculation has to pass through the whole database.

2. Sometimes, it produce huge number of rules, so it becomes

computationally more expensive.

Eclat algorithm[Equivalence Class Clustering and bottom-up Lattice Traversal] : It is is another set of frequent itemset generation similar to Apriori algorithm. Three traversal approaches such as „Topdown‟,

„Bottom-up‟, and Hybrid approaches are supported. Transaction IDs (TID list) are stored here.

​

How the algorithm work? :

​

Step1 : Use Transaction Id Sets(tidsets) and compute the support value of a candidate and avoiding the generation of subsets.

Step2: In the first iteration, all single items are used along with their tidsets.

Step3: Then the iteration is repeated, for each item-tidset pair is verified and combined with other item-tidset pairs. This process is continued until no candidate item-tidset pairs can be combined.

Problem: Apply Eclat algorithm and derive the association rules. The given data is a boolean matrix where for each cell (i, j), the value denotes whether the j‟th item is included in the i‟th transaction or not. 1 means true while 0 means false. The minimum support is 2

Iteration 2 : Arrange each item with it‟s tidset in a table k = 2, minimum support = 2

Iteration 1 : Arrange each item with it‟s tidset in a table k = 1, minimum support = 2

Iteration 4 : Arrange each item with it‟s tidset in a table k = 4, minimum support = 2

Iteration 3 : Arrange each item with it‟s tidset in a table k = 3, minimum support = 2

Conclude the rules for the given dataset:-

ENSEMBLE LEARNING ALGORITHM

Ensemble means collaboration/joint/group. Ensemble methods are models that contain many weaker models that are autonomously trained and whose forecasts are combined approximately to create the overall prediction model.

Weaker models : A model that achieves slightly better than 50 percent accuracy.

The most popular ensemble learning algorithms are

• Bootstrap Aggregation (bagging)
• Boosting
• AdaBoost
• Stacked Generalization (blending)
• Gradient Boosting Machines (GBM)
• Gradient Boosted Regression Trees (GBRT)
• Random Forest

Bootstrap Aggregation (bagging): Bootstrap Aggregation (bagging) works using the principle of the Bootstrap sampling method. Given a training data set D containing m examples, bootstrap drawing method

draws a sample of training examples D , by selecting m examples in

uniform random with replacement.

It comprises two phases namely Training phase and Classification Phase.

Training Phase:

1. Initialize the parameters
2. D = {Ф }
3. H = the number of classification
4. For k = 1 to h
5. Take a bootstrap sample S_k from training set S
6. Build the classifier D_k using S_k as a training set
7. D = D⋃D_i
8. Return D

​

Classification Phase:

• Run D₁ , D₂ ,………..D_k on the input k
• The class with a maximum number of the vote is chosen as the label

for X.

The original sample has eight data points. All the Bootstrap samples also have eight data points. Within the same bootstrap sample, data points are repeated due to selection with the replacement.

Boosting

Like bagging, boosting is another key ensemble based technique. Boosting is an iterative technique. It decreases the biasing error. If an observation was classified incorrectly, then it boosts the weight of that observation. In this type of ensemble, weaker learning models are trained on resampled data, and the outcomes are combined using a weighted voting approach based on the performance of different models. Adaptive boosting or AdaBoost is a special variant of a boosting algorithm. It is based on the idea of generating weak learners and learning slowly.

​

Gradient boosting machines (GBM)

Gradient Boosting Machines or GBM is another ensemble machine learning algorithm that works for both regression and classification problems. GBM uses the boosting technique, combining a number of weak learners to form a strong learner. Decision trees used as a base learner, each subsequent tree in series is built on the errors calculated by the previous tree.

Example: Predict the age of a group of people using the below data:

1. The mean age is assumed to be the predicted value for all observations

in the dataset.

2. The residual errors are calculated using this mean prediction and

actual values of age

3. A tree model is created using the errors calculated for the target

variable. The objective is to find the best split to minimize the error.

4. The predictions by this model are combined with the predictions 1

5. This value calculated above is the new prediction.
6. New errors are calculated using this predicted value and actual value.
7. Steps 2 to 6 are repeated till the maximum number of iterations is reached (or error function does not change).

REGULARIZATION ALGORITHM

This is an extension made to another method (typically regression method) that penalizes models based on their complexity, favouring simpler models that are also better at generalizing. Regularization algorithms have been listed separately here because they are famous, influential, and generally simple modifications made to other methods.

The most popular regularization algorithms are

1. Ridge Regression,
2. Least Absolute Shrinkage and Selection Operator (LASSO),
3. Elastic Net
4. Least-Angle Regression (LARS)

Elastic Net

When working with high-dimensional data sets with a large number of independent variables, correlations (relationships) among the variables can be often result in multicollinearity. These correlated variables which sometimes form groups or clusters called as an elastic net of correlated variables. To include the complete the model selection even if just one variable has been selected.

Ridge regression: It performs L2 regularization, i.e. it adds penalty

equivalent to square of the magnitude of coefficients.

Minimization objective of ridge = LS Obj + λ × (sum of square of

coefficients) where

LS Obj = Least square objective loss function= λ = any scalar value starts from 1, 2,3 …. (sum of square of coefficients) =

​

​

Lasso regression: It performs L1 regularization, i.e. it adds penalty

equivalent to the absolute value of the magnitude of coefficients. Minimization objective of ridge = LS Obj + λ × (absolute value of the magnitude of coefficients)

where

LS Obj = Least square objective loss function= λ = any scalar value starts from 1, 2,3 …. (sum of square of coefficients) =