Introduction to Machine Learning (Topics 7 - 12)
7. Different Approaches to Machine Learning
Machine learning encompasses various approaches, each with distinct methods, data requirements, and limitations.
It is considered that three main fields of machine learning are:
- Supervised Learning: Learning from labeled data, where the algorithm makes predictions or classifications based on input-output pairs.
- Unsupervised Learning: Learning from unlabeled data, focusing on discovering patterns or insights, such as clustering or dimensionality reduction.
- Reinforcement Learning: Learning through interactions with an environment, where an agent takes actions to maximize cumulative rewards through trial and error.
Supervised Learning
Overview: In supervised learning, models are trained on labeled datasets, where each input is paired with the correct output. This approach is prevalent in classification and regression tasks, such as image recognition and predictive analytics.
Data Requirements:
- Requires large, labeled datasets to achieve high accuracy.
- Data must be representative of all classes to avoid biases.
Limitations:
- Data labeling is time-consuming and resource-intensive.
- Models may overfit if trained on datasets that do not generalize well to new instances.
- Performance heavily depends on the quality and quantity of labeled data available.
Unsupervised Learning
Overview: Unsupervised learning deals with unlabeled data, aiming to discover underlying patterns or structures within the dataset. It is useful for clustering, dimensionality reduction, and anomaly detection.
Data Requirements:
- Can operate on raw, unlabeled datasets, reducing costs associated with data preparation.
- Requires data preprocessing to enhance feature relevance.
Limitations:
- Results may be less interpretable and require domain expertise to make meaningful conclusions.
- Lacks specificity in guiding precise tasks, like classification, compared to supervised methods.
- Validation and evaluation of results can be challenging due to the absence of ground truth.
Reinforcement Learning
Overview: Reinforcement learning trains agents to make a sequence of decisions by interacting with an environment, maximizing cumulative rewards. This approach is prominent in robotics, game AI, and autonomous systems.
Data Requirements:
- Requires a well-defined environment with a reward system to simulate interactions.
- Often benefits from simulated data to expedite training.
Limitations:
- High computational demands and complexity in learning optimal strategies.
- Sample inefficiency, requiring extensive interactions to learn effectively.
- Designing appropriate reward functions can be challenging and crucial for success.
Key Points
- Data Reliance: Supervised learning depends heavily on labeled data, while unsupervised can discover patterns without it. Reinforcement learning needs an interactive environment and a reward structure.
- Use Cases: Supervised learning is ideal for tasks with clear input-output pairs, unsupervised for exploratory analysis, and reinforcement for decision-making processes.
- Challenges: Each approach has unique limitations, from data-related issues in supervised learning to environmental complexity in reinforcement learning.
8. The basic concept of supervised learning
Supervised learning focuses on using labeled datasets to train models that predict outcomes or classify data points into categories. It involves input-output pairs, where the model learns a mapping function to associate input features with correct outputs, enabling accurate predictions on unseen data.
The strength of supervised learning lies in its ability to leverage labeled information for precise predictions. It applies to various domains, including image recognition, language processing, and predictive analytics. A major constraint is the reliance on large, accurately labeled datasets, which can be costly to obtain.
More formal
Given a training set of
Underfitting and Overfitting
- Underfitting: Occurs when the model is too simple to capture the underlying patterns in the data, leading to high bias and low variance.
- Overfitting: Happens when the model is too complex, capturing noise in the training data and failing to generalize well to new instances, resulting in low bias and high variance.
Example Figure of Supervised Learning
Below is a simple depiction of the supervised learning process:
- Input Data: Features
paired with Labels . - Model Training: Learn the mapping from inputs to outputs using a supervised learning algorithm.
- Model Evaluation: Assess the model's performance on a separate validation dataset.
- Prediction: Use the trained model to make predictions on new, unseen data.
Here’s how you might visualize it:
Key Points
- Labeled Data: Supervised learning requires labeled data for training, where each input is associated with the correct output.
- Model Training: The goal is to learn a function that approximates the underlying data distribution, enabling accurate predictions on unseen instances.
- Bias-Variance Tradeoff: Balancing model complexity is crucial to avoid underfitting and overfitting.
- Evaluation: Models are evaluated based on their performance on validation or test datasets, ensuring generalization to new data.
9. Supervised learning by decision trees
Decision trees are a supervised learning approach that models decisions and their possible consequences as a tree structure. Each node represents a decision based on a feature value, while branches represent the outcomes leading to leaf nodes, which are predictions. Decision trees are intuitive, easily interpretable, and effective for both classification and regression tasks.
Constructing a decision tree involves selecting features that best split data at each node, often using criteria like information gain. A limitation is their tendency to overfit training data, making techniques like pruning, which simplifies the tree, essential for enhancing generalization to unseen datasets.
Generalized Workflow
Maps a vector of attribute values to a single output "decision".
Sequence of tests
- Start at the root node.
- Explore branches based on attribute values.
- Reach a leaf node with the final decision.
Nodes represent features, edges decisions, and leaves outcomes.
Input and output values can be discrete or continuous.
Simplest example is a boolean decision tree. Which is equivalent to a logical statement of form:
Example (Restuarant Waiting)
Description of steps in a decision tree for a restaurant waiting scenario:
- Alternate: whether there is a suitable alternative restaurant nearby.
- Bar: whether the restaurant has a comfortable bar area to wait in.
- Fri/Sat: true on Fridays and Saturdays.
- Hungry: whether we are hungry right now.
- Patrons: how many people are in the restaurant (values are None, Some, and Full).
- Price: the restaurant’s price range ($, $$, $$$).
- Raining: whether it is raining outside.
- Reservation: whether we made a reservation.
- Type: the kind of restaurant (French, Italian, Thai, or burger).
- WaitEstimate: host’s wait estimate: 0–10, 10–30, 30–60, or >60 minutes
Dataset
| Example | Alt | Bar | Fri | Hun | Pat | Price | Rain | Res | Type | Est | Output |
|---|---|---|---|---|---|---|---|---|---|---|---|
| x₁ | Yes | No | No | Yes | Some | $$$ | No | Yes | French | 0-10 | y₁ = Yes |
| x₂ | Yes | No | No | Yes | Full | $ | No | No | Thai | 30-60 | y₂ = No |
| x₃ | No | Yes | No | No | Some | $ | No | No | Burger | 0-10 | y₃ = Yes |
| x₄ | Yes | No | Yes | Yes | Full | $ | Yes | No | Thai | 10-30 | y₄ = Yes |
| x₅ | Yes | No | No | No | Full | $$$ | No | Yes | French | >60 | y₅ = No |
| x₆ | No | Yes | Yes | Yes | Some | $$ | Yes | Yes | Italian | 0-10 | y₆ = Yes |
| x₇ | No | Yes | No | No | None | $ | Yes | No | Burger | 0-10 | y₇ = No |
| x₈ | No | No | No | Yes | Some | $$ | Yes | No | Thai | 0-10 | y₈ = Yes |
| x₉ | No | Yes | Yes | No | Full | $ | Yes | No | Burger | >60 | y₉ = No |
| x₁₀ | Yes | Yes | Yes | No | Full | $$$ | No | Yes | Italian | 10-30 | y₁₀ = No |
| x₁₁ | No | No | No | No | None | $ | No | No | Thai | 0-10 | y₁₁ = No |
| x₁₂ | Yes | Yes | Yes | No | Full | $ | No | No | Burger | 30-60 | y₁₂ = Yes |
Processing
Find most significant features and split the data accordingly.
E.g. Patrons, Price, and Type are significant features.
Resulting decision tree is going to have shorter paths, simpler than the initial one and fitted to the training data.
Goal is to select the most significant features (attributes) based on information gain defined by expected entropy reduction of the output.
Generalization is crucial to avoid overfitting:
- if we increase the number of attributes, the tree becomes more complex and may overfit the data.
- if we increase the number of training samples, overfitting is less likely.
Pruning is a technique to reduce the complexity of the tree by removing nodes that do not contribute significantly to the model's performance.
- Look at test nodes that have only leaves as children.
- If the test (feature) appears to be irrelevant, remove the node and replace it with a leaf node.
- Use significance tests to measure low information gain.
Pros and Cons
Pros:
- Ease of understanding
- Scalability to large data sets
- Versatility in handling discrete and continuous inputs
- Performing classification and regression
Cons:
- Suboptimal accuracy (largely due to the greedy search)
- If trees are very deep, then getting a prediction for a new example can be expensive
- Decision trees are unstable – adding just one new example can change the entire tree
Key Points
- Decision Trees: Supervised learning method that partitions data based on feature values to predict target variables.
- Workflow: Sequence of tests leading to a final decision, with nodes representing features and leaves outcomes.
- Generalization: Balancing model complexity through feature selection and pruning to avoid overfitting.
- Pros and Cons: Decision trees are easy to interpret but may lack accuracy and stability compared to other methods.
10. The basic concept of unsupervised learning
Unsupervised learning seeks patterns within unlabeled data, uncovering hidden structures without predefined outputs. It applies to clustering, dimensionality reduction, and anomaly detection tasks, offering insights into data that inform subsequent analysis or modeling steps.
The fundamental advantage is its ability to process vast datasets automatically, identifying meaningful groupings or structures. However, it requires careful interpretation, as results may not inherently align with intuitive or domain-specific expectations, posing challenges in translating raw insights into action.
Key Characteristics
- No Labels: Unlike supervised learning, it does not require labeled output data. Therefore, it can work with raw, unstructured datasets.
- Pattern Discovery: Identifies hidden structures and relationships in the data.
Common Techniques
Clustering:
- Groups data points into clusters based on similarity.
- Algorithms include k-means and hierarchical clustering.
Dimensionality Reduction:
- Reduces the number of features to simplify data visualization and analysis.
- Methods such as Principal Component Analysis (PCA) are widely used.
Anomaly Detection:
- Identifies outliers or unusual data points within a dataset.
Cluster
A cluster is a group of data points that are similar to each other within the same group and dissimilar to data points in other groups. Clustering algorithms aim to partition data into clusters based on similarity metrics, such as distance measures.
Clustering vs. Classification
Clustering:
- Unsupervised Learning: Does not require labeled data.
- Goal: Discover natural groupings within the data.
- Output: Often produces clusters representing different segments or patterns.
Classification:
- Supervised Learning: Requires labeled data for training.
- Goal: Assign new data points to predefined categories or labels.
- Output: Predicts discrete labels based on input features.
Differences
Data Requirement:
- Clustering: Works with unlabeled data.
- Classification: Needs labeled data for training.
Purpose:
- Clustering: Mainly used for exploratory data analysis and pattern discovery.
- Classification: Used for predicting outcomes based on input features.
Approach:
- Clustering: Groups similar items without prior knowledge.
- Classification: Learns from labeled examples to make predictions.
Limitations
- Interpretability: Results can be difficult to interpret without domain expertise.
- Evaluation: Lack of ground truth makes it challenging to assess model performance.
- Scalability: Handling very large datasets can be computationally intensive.
Diagram of Clustering Mechanism
Below is a representation of a clustering process using k-means:
Key Points
- Unsupervised Learning: Identifies patterns in unlabeled data, offering insights into underlying structures.
- Clustering: Groups data points based on similarity, revealing natural groupings within the dataset.
- Limitations: Challenges in interpretation, evaluation, and scalability pose constraints on unsupervised learning methods.
11. The working mechanism of k-means algorithm
The k-means algorithm partitions data points into
The simplicity and interpretability of k-means make it a popular choice for clustering tasks. However, the algorithm struggles with clusters of varying sizes and densities, and results can be sensitive to centroid initialization, requiring multiple runs or sophisticated methods for selecting initial centroid placements.
Scary Math
Iterative process for clustering - minimizing the within-cluster variance:
where:
is the objective function for k-means clustering. is the assignment matrix, where if is assigned to cluster . is the centroid matrix, where is the centroid of cluster . is the set of data points assigned to cluster . is the number of clusters. is the number of data points. is the -th data point. is the centroid of cluster . is the squared Euclidean distance between and .
Calculating the centroids:
General overview
- Input: a data set
, is a norm defined on , is the number of clusters, is the maximum number of iterations, is a distance measure, is the tolerance for convergence. - Initialization:
is the initial set of centroids. - For
do: - Determine the partition matrix
. - Determine the cluster centroids
from previous equation. - If
, then stop.
- Determine the partition matrix
- Result: the partition matrix
and the cluster centroids .
Key Steps in k-Means
- Initialization: Pick
random points from the data as the starting centers (centroids) of the clusters. - Group: For each data point, find the closest center and assign the point to that center's cluster.
- Update Centers: For each cluster, find the average position of all its points and move the center (centroid) to this new position.
- Repeat:
- Go back to step 2 and reassign the points to the nearest centers.
- Keep doing this until the centers don't move much or you've repeated a set number of times.
Convergence
The k-means algorithm iteratively refines the positions of centroids, minimizing the variance within each cluster. The process converges when data point assignments no longer change between iterations.
Example (Wrestlers' heights and weights)
Given a following dataset of wrestlers:
| ID | Height (cm) | Weight (kg) |
|---|---|---|
| 1 | 185 | 76 |
| 2 | 170 | 60 |
| 3 | 168 | 68 |
| 4 | 179 | 74 |
| 5 | 182 | 73 |
| 6 | 188 | 75 |
We want to group them into two clusters (
Initialization: Randomly select two points as the initial centroids.
- Centroid 1:
- Centroid 2:
First iteration
Grouping:
- Assign each wrestler to the nearest centroid based on Euclidean distance.
- Calculate the distance between each wrestler and the centroids.
- Assign wrestlers to the cluster with the closest centroid.
Therefore we get the following clusters:
- Cluster 1: Wrestlers 1, 4, 5, 6
- Cluster 2: Wrestlers 2, 3
Update Centers:
- Calculate the average height and weight for each cluster.
- Move the centroids to the new positions.
We get the new centroids:
- Centroid 1:
- Centroid 2:
Second iteration
Repeat the grouping and updating steps.
- Cluster 1: Wrestlers 1, 4, 5, 6
- Cluster 2: Wrestlers 2, 3
New centroids:
- Centroid 1:
- Centroid 2:
Since the assignments did not change, the algorithm has converged.
Considerations
- Choosing k: Selecting the appropriate number of clusters
is crucial and can be guided by methods like the Elbow Method. - Scalability: Efficient for large datasets yet sensitive to initial centroid choices and outliers.
- Assumptions: Assumes spherical cluster shapes and similar cluster sizes, which may not always fit real-world data.
Key Points
- k-Means Algorithm: Clustering method that partitions data into
clusters by minimizing within-cluster variance. - Steps: Initialization, grouping data points, updating centroids, and iterating until convergence.
- Convergence: Reached when data point assignments stabilize between iterations.
- Considerations: Selecting
, handling outliers, and interpreting results are key aspects of k-means clustering.
12. The mechanism of reinforcement learning
Reinforcement learning is about teaching agents to make smart decisions by taking actions that lead to the most rewards from their surroundings. The agent learns through interactions, trying different actions and seeing how they impact the outcome. Over time, it figures out the best ways to reach its goals based on these experiences.
A key part is balancing trying new things and using what it already knows. Exploring helps the agent find better strategies, while exploiting means sticking to actions that work well. Methods like Q-learning and policy gradients assist in this learning. Q-learning uses a value system to help choose actions, while policy gradients adjust the agent’s approach to improve performance. Because real-world environments can be complex, agents often practice in simulated settings to become better and more adaptable decision-makers.

Key Concepts
- Agent: The learner or decision maker.
- Environment: Everything the agent interacts with.
- Actions: Choices made by the agent.
- States: Different situations in which the agent can find itself.
- Rewards: Feedback from the environment to evaluate the actions.
Core Mechanism
- Initialization: The agent starts with no knowledge of how to act.
- Observation: The agent observes the current state of the environment.
- Action: Based on a policy, the agent chooses an action to take.
- Feedback: The environment responds to the action with a new state and a reward signal.
- Update: The agent updates its knowledge to enhance future decision-making, usually through a value function.
- Repeat: This cycle repeats with the agent continuously learning from interactions.

Exploration vs. Exploitation
Exploration: Trying new actions to learn more about the environment. To discover better strategies, the agent must explore paths which were not tried before.
Exploitation: Using the knowledge gained so far to make decisions. The agent exploits the best-known strategies to maximize rewards.
Markov Decision Process (MDP)
In mathematics, a Markov decision process (MDP) is a discrete-time stochastic control process.
It provides a mathematical framework for modelling decision making in situations where outcomes are partly random and partly under the control of a decision maker.
The Markov property expresses that the likelihood of changing to a specific state is reliant exclusively on the present state and elapsed time and not on the series of states that have preceded it.
Application of MDPs in reinforcement learning:
- States: MDPs define the environment using a set of states, representing all possible situations the agent can encounter. This helps the agent understand its current position in the environment.
- Actions: MDPs specify a set of actions the agent can take, allowing it to interact with the environment and transition between states.
- Rewards: MDPs incorporate a reward function that assigns a numerical value to each state-action pair, guiding the agent towards desirable outcomes.
- Transition Probabilities: MDPs define the probability of transitioning from one state to another based on the agent's actions, enabling the agent to learn the dynamics of the environment.
- Policy: The agent learns a policy, which is a strategy for deciding which actions to take in each state to maximize expected cumulative rewards.
- Value Function: MDPs use value functions to estimate the expected cumulative rewards an agent can achieve from a given state or state-action pair, aiding in decision-making.

Key Points
- Reinforcement Learning: Teaches agents to make decisions by maximizing rewards from interactions with the environment.
- Core Mechanism: Involves observing states, taking actions, receiving feedback, updating knowledge, and repeating the process.
- Exploration vs. Exploitation: Balancing trying new strategies with using known ones to optimize decision-making.
- Markov Decision Process: Mathematical framework for modelling decision-making in stochastic environments, defining states, actions, rewards, and policies.
