AI

Artificial Intelligence (AI)

Understanding AI concepts, graphs in AI, and machine learning methods

Learning Objectives

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

  • Show understanding of how graphs can be used to aid Artificial Intelligence (AI)
  • Understand the purpose and structure of a graph
  • Use A* and Dijkstra's algorithms to perform searches on a graph
  • Show understanding of how artificial neural networks have helped with machine learning
  • Show understanding of Deep Learning, Machine Learning and Reinforcement Learning
  • Understand machine learning categories: supervised and unsupervised learning
  • Show understanding of back propagation of errors and regression methods in machine learning
  • Explain the applications of AI in real-world scenarios

Key Terms

Graph

A collection of nodes/vertices connected by edges with numerical labels

Dijkstra's Algorithm

Finds shortest path between nodes by checking all vertices systematically

A* Algorithm

Finds optimal route using heuristics (intelligent guesses) for efficiency

Artificial Intelligence

Machines with cognitive abilities like problem-solving and learning

Machine Learning

Systems that learn without being explicitly programmed

Deep Learning

Subset of ML using artificial neural networks with multiple layers

Supervised Learning

Uses labelled data with known inputs and outputs for training

Unsupervised Learning

Identifies hidden patterns in input data without right answers

Reinforcement Learning

Learns through trial and error using reward/punishment system

Back Propagation

Training method for neural networks by propagating errors backward

Regression

Statistical method to predict numerical values from given data

Neural Network

Interconnected nodes inspired by human brain structure

Graphs in Artificial Intelligence

Artificial intelligence problems can be defined and solved using graphs. A graph is a collection of nodes or vertices connected by edges. Each edge can have an associated numerical value label. Graphs provide structures for relationships between nodes and can be analyzed by algorithms like Dijkstra's and A*.

Real-Life Example: GPS Navigation

Think of Google Maps or GPS. The map is a graph where:

  • Nodes = Intersections or locations
  • Edges = Roads connecting locations
  • Edge labels = Distance or travel time between locations
  • Shortest path = Fastest route from your location to destination

When you ask for directions, the app uses graph algorithms to find the shortest path!

Graph Components

N
Node/Vertex

A point in the graph (e.g., a city in a map)

E
Edge

Connection between nodes (e.g., a road between cities)

W
Weight/Label

Numerical value on edge (e.g., distance or time)

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path between two points on a graph. It's the basis for technologies like GPS tracking and is an important part of AI.

Dijkstra's Algorithm Simulation

How it works: Dijkstra's algorithm checks every possible path systematically. It gives each vertex a "working value" (current shortest distance from start) and updates these values until it finds the shortest path to the destination.

Dijkstra's Algorithm Steps

  1. Give the start vertex a final value of 0 (distance from source to itself is zero)
  2. Give each vertex connected to the start vertex a "working value" (current shortest distance)
  3. Select the vertex with the smallest working value and make it "final"
  4. Update working values of vertices connected to this final vertex
  5. Repeat steps 3-4 until the end vertex is reached
  6. Trace the route back from end to start to find the shortest path

A* Algorithm

The A* algorithm finds the shortest (optimal) route between nodes but uses an additional heuristic (intelligent guess) approach to achieve better performance than Dijkstra's algorithm. It's based on Dijkstra but adds a heuristic value (h) - an estimate of how far we have to go to reach the destination efficiently.

A* Algorithm Grid Visualization

This 8×6 grid represents a simplified pathfinding problem. White squares are permitted moves, grey squares are blocked.

How A* works: Each node has three values:

g(n)

Movement cost from start to current node

h(n)

Heuristic estimate to destination (straight-line distance)

f(n) = g(n) + h(n)

Total estimated cost of path through node

Dijkstra vs A* Comparison

Dijkstra's Algorithm A* Algorithm
Checks every vertex systematically Uses heuristics to guide search
Guaranteed to find shortest path Usually finds shortest path (depends on heuristic)
Can be time-consuming for large graphs More efficient for larger, complex problems
Used in network routing protocols Used in games, robotics, and GPS

Real Applications

  • GPS Navigation - Finding fastest routes
  • Video Games - AI character pathfinding
  • Robotics - Planning movement through environments
  • Network Routing - Finding best paths for data packets
  • Disease Spread Modeling - Predicting infection pathways

Activity 1: Dijkstra's Algorithm Practice

Use Dijkstra's algorithm to find the shortest path from vertex A to all other vertices in this graph:

A --6-- B --5-- C
|           |          |
1         2        2
|           |          |
D --1-- E --5-- F

Task: Calculate the shortest distance from A to each vertex (B, C, D, E, F) and write the path for each.

Solution:
  • A to B: 6 (Path: A→B)
  • A to C: 11 (Path: A→B→C)
  • A to D: 1 (Path: A→D)
  • A to E: 3 (Path: A→D→E)
  • A to F: 8 (Path: A→D→E→F)

Explanation: Dijkstra's algorithm systematically evaluates all paths from A, updating the shortest known distance to each vertex until all are finalized.

Activity 2: A* Heuristic Calculation

In a 10×10 grid, the start position is at (1,1) and the goal is at (10,10). Calculate the heuristic (straight-line) distance for these positions:

  1. Position (3,4) to goal (10,10)
  2. Position (7,2) to goal (10,10)
  3. Position (5,8) to goal (10,10)

Hint: Use the Manhattan distance formula: |x₁ - x₂| + |y₁ - y₂|

Solution:
  1. (3,4) to (10,10): |3-10| + |4-10| = 7 + 6 = 13
  2. (7,2) to (10,10): |7-10| + |2-10| = 3 + 8 = 11
  3. (5,8) to (10,10): |5-10| + |8-10| = 5 + 2 = 7

Note: The heuristic helps A* algorithm prioritize nodes that seem closer to the goal, making the search more efficient than Dijkstra's algorithm.

Check Your Understanding: Graphs in AI

Answer
  • [1 mark] A graph is a collection of nodes/vertices connected by edges
  • [1 mark] Edges can have numerical value labels representing distance, cost, or weight
  • [Additional] Graphs provide structures for relationships between nodes and can represent AI problems like pathfinding
Answer
  • [1 mark] Dijkstra checks all vertices systematically without considering direction to goal
  • [1 mark] A* uses heuristics (intelligent guesses) to guide search toward destination
  • [1 mark] A* is generally faster/more efficient for larger problems
  • [Additional] A* uses f(n) = g(n) + h(n) where h(n) is heuristic estimate to goal
Answer
  • [1 mark] It checks every vertex in the graph systematically
  • [1 mark] It doesn't use heuristics to prioritize search toward destination
  • [Additional] It explores paths that lead away from the goal before finding optimal path
Answer
  • [1 mark] GPS navigation systems (Google Maps, Waze)
  • [1 mark] Network routing (Internet data packet routing)
  • [Additional] Video game AI (character pathfinding), robotics (movement planning), disease spread modeling
Answer
  • [1 mark] g(n) = actual movement cost from start node to current node n
  • [1 mark] h(n) = heuristic estimated cost from current node n to goal node
  • [Additional] f(n) represents total estimated cost of path through node n
Answer
  • [1 mark] A heuristic is an "intelligent guess" or estimate of distance/cost to goal
  • [1 mark] It helps guide the search toward the destination more efficiently
  • [Additional] Common heuristics include Manhattan distance or Euclidean distance

Artificial Intelligence & Machine Learning

Artificial Intelligence (AI) refers to machines with cognitive abilities such as problem-solving and learning from examples. Machine Learning is a subset of AI where algorithms are 'trained' to learn from past experiences and examples. Deep Learning is a subset of machine learning that uses artificial neural networks.

Artificial Intelligence

Machines with cognitive abilities (problem-solving, learning)

Machine Learning

Subset of AI: systems that learn without explicit programming

Deep Learning

Subset of ML: uses neural networks with multiple layers

AI Categories

1. Narrow AI

Machine has superior performance to a human in one specific task

Example:

Chess-playing AI, spam filters, voice assistants

2. General AI

Machine performance similar to human in any intellectual task

Example:

Theoretical - no true examples yet

3. Strong AI

Machine has superior performance to human in many tasks

Example:

Advanced hypothetical systems

Real-Life AI Examples You Use Daily

Smart Assistants
  • Amazon Alexa, Google Assistant, Apple Siri
  • Use natural language processing to understand commands
  • Learn your preferences over time
Recommendation Systems
  • Netflix movie suggestions
  • YouTube video recommendations
  • Amazon product recommendations

Machine Learning Types

Artificial Neural Network Visualization

This simple neural network shows how data flows from input to output through hidden layers.

Supervised Learning

Uses labelled data where inputs and correct outputs are known. The model is trained using examples, then tested.

  • Training: Input + correct output provided
  • Testing: Model predicts outputs for new inputs
  • Examples: Email spam detection, image classification
Real Example:

Teaching a system to recognize cats in photos by showing it thousands of labelled "cat" and "not cat" images.

Unsupervised Learning

Identifies hidden patterns in input data without "right answers." The system organizes data to reveal structures.

  • No labelled data - system finds patterns itself
  • Clustering: Groups similar data points
  • Examples: Customer segmentation, anomaly detection
Real Example:

Amazon grouping customers with similar purchase histories for targeted marketing.

Reinforcement Learning

Learns through trial and error using a reward/punishment system. The agent takes actions to maximize cumulative reward.

  • No training data - learns from environment
  • Reward/punishment for actions
  • Examples: Game AI (chess, Go), robotics
Real Example:

AlphaGo learning to play Go by playing millions of games against itself, receiving rewards for winning.

Semi-Supervised Learning

Uses both labelled and unlabelled data. A small amount of labelled data is combined with large amounts of unlabelled data.

  • Cost-effective: Labelling data is expensive
  • Web crawlers analyze unlabelled web pages
  • Examples: Web page classification, speech recognition
Real Example:

Classifying millions of web pages into categories (sports, news, etc.) using a small labelled dataset.

Deep Learning Applications

Face Recognition

Deep learning systems analyze facial features to identify individuals:

  • Distance between eyes
  • Width of nose
  • Shape of cheekbones
  • Length of jawline
  • Shape of eyebrows

Used in: Phone unlocking (Face ID), security systems, photo tagging

Chatbots

AI systems that simulate human conversation using predefined scripts and machine learning:

  • Process typed messages or voice recordings
  • Use natural language processing (NLP)
  • Learn from interactions to improve responses
  • Examples: Customer service bots, virtual assistants

Used in: Websites, messaging apps, customer support

Machine Learning vs Deep Learning

Machine Learning Deep Learning
Enables machines to make decisions based on past data Enables machines to make decisions using artificial neural networks
Needs only a small amount of data for training Needs large amounts of data during training
Modular approach: each problem solved separately then combined Solves problem from beginning to end as single entity
Testing takes a long time to carry out Testing takes much less time
Examples: Spam detection, recommendation systems Examples: Face recognition, self-driving cars

Back Propagation

Training method for neural networks where errors are propagated backward to adjust weights:

  1. Random weights assigned to neural connections initially
  2. System learns from inputs and corresponding outputs
  3. Outputs compared to expected results, errors calculated
  4. Errors propagated back through network to update weights
  5. Process repeated until errors are within acceptable limits
Types:

Static: Maps static inputs to static outputs instantly.
Recurrent: Activation fed forward until fixed value achieved (more complex).

Regression Analysis

Statistical method used in machine learning to predict numerical values:

  • Analyzes relationship between input and output variables
  • Creates mathematical formula based on correlation
  • Used to make predictions from new data
  • Example: Weather forecasting, stock price prediction
How it works:

1. System provided with actual input/output values
2. Correlation between values investigated
3. Mathematical formula established if correlation found
4. Formula used to predict outputs for new inputs

Activity 3: Spam Detection Classification

A spam detection system is trained with these labelled emails:

  • "Win free money now!" → SPAM
  • "Meeting tomorrow at 3pm" → NOT SPAM
  • "Your account statement" → NOT SPAM
  • "Click here for amazing offers" → SPAM
  • "Homework assignment due Friday" → NOT SPAM

Task: 1. What type of machine learning is this?
2. How would the system classify this new email: "Limited time offer - buy now!"
3. What features might the system use to distinguish spam from non-spam?

Solution:
  1. Type: Supervised Learning (uses labelled training data with known classifications)
  2. Classification: The email "Limited time offer - buy now!" would likely be classified as SPAM because it contains keywords like "offer" and "buy now" similar to other spam emails.
  3. Features:
    • Keywords: "win", "free", "money", "offer", "click", "buy"
    • Presence of exclamation marks
    • Urgent language ("now", "limited time")
    • Sender's email address
    • Links to unknown websites

Activity 4: Regression Analysis Scenario

A weather prediction system uses regression analysis. It has been given these historical data points:

Temperature (°C) Humidity (%) Rainfall (mm)
25 80 15
30 60 5
20 90 25

Task: 1. What would regression analysis do with this data?
2. If the system finds rainfall = 0.5 × humidity - 0.2 × temperature, predict rainfall for temperature=28°C, humidity=75%
3. Why might this prediction be inaccurate?

Solution:
  1. Regression analysis: Would analyze the relationship between temperature/humidity (independent variables) and rainfall (dependent variable) to find a mathematical formula that best fits the data.
  2. Prediction:
    Rainfall = 0.5 × 75 - 0.2 × 28
    = 37.5 - 5.6
    = 31.9 mm
  3. Inaccuracy reasons:
    • Small dataset (only 3 points)
    • Other factors not considered (wind, pressure, season)
    • Real-world relationships may be non-linear
    • Formula may be oversimplified

Check Your Understanding: AI & Machine Learning

Answer
  • [1 mark] Artificial Intelligence (AI) is the broadest concept - machines with cognitive abilities
  • [1 mark] Machine Learning is a subset of AI - systems that learn without explicit programming
  • [1 mark] Deep Learning is a subset of Machine Learning - uses neural networks with multiple layers
Answer
Supervised Learning:
  • Uses labelled data (known inputs and outputs)
  • Model trained with correct answers
  • Example: Email spam detection
  • Goal: Predict outputs for new inputs
Unsupervised Learning:
  • Uses unlabelled data (no right answers)
  • Finds hidden patterns in data
  • Example: Customer segmentation
  • Goal: Discover structure in data
Answer
  • [1 mark] Learns through trial and error without training data
  • [1 mark] Uses reward/punishment system for actions taken
  • [1 mark] Agent takes actions to maximize cumulative reward over time
  • [Additional] Examples: Game AI (chess), robotics, autonomous systems
Answer
  • [1 mark] Training method for adjusting weights in neural networks
  • [1 mark] Errors between actual and expected outputs are calculated
  • [1 mark] Errors are propagated backward through network to update weights
  • [Additional] Process repeated until errors are within acceptable limits
Answer
  • [1 mark] Deep learning systems analyze specific facial features
  • [1 mark] Features include: distance between eyes, width of nose, shape of cheekbones
  • [1 mark] Creates unique facial signature for each individual
  • [Additional] Used in phone unlocking (Face ID), security systems, photo tagging
Answer
  • [1 mark] Statistical method to predict numerical values from given data
  • [1 mark] Analyzes relationship between input and output variables
  • [1 mark] Creates mathematical formula based on correlation in data
  • [Additional] Used for predictions like weather forecasting, stock prices

Key Takeaways

  • Graphs are fundamental to AI - they represent relationships between nodes and enable pathfinding algorithms like Dijkstra's and A*
  • Dijkstra's algorithm finds shortest paths by systematically checking all vertices, but can be time-consuming for large graphs
  • A* algorithm is more efficient - it uses heuristics (intelligent guesses) to guide search toward destination
  • AI, ML, and Deep Learning are nested concepts: Deep Learning ⊂ Machine Learning ⊂ Artificial Intelligence
  • Supervised learning uses labelled data with known inputs/outputs (e.g., spam detection)
  • Unsupervised learning finds hidden patterns in unlabelled data (e.g., customer segmentation)
  • Reinforcement learning uses trial and error with reward/punishment system (e.g., game AI)
  • Neural networks are inspired by the human brain - they process information through interconnected nodes
  • Back propagation trains neural networks by propagating errors backward to adjust weights
  • Regression analysis predicts numerical values by finding mathematical relationships in data
  • Deep learning excels at complex pattern recognition like face recognition, natural language processing
  • Real-world AI applications are everywhere - from GPS navigation to recommendation systems to voice assistants

Question Bank

Marking Scheme & Answer
  • [1 mark] AI problems can be defined and solved as finding paths in graphs
  • [1 mark] Graphs provide structures for relationships between nodes/entities
  • [1 mark] Artificial neural networks can be represented using graphs
  • [1 mark] Graphs can be analyzed by algorithms like Dijkstra's and A* for pathfinding
  • [Additional] Examples: GPS navigation, network routing, disease spread modeling
Marking Scheme & Answer
  1. [1 mark] Give the start vertex a final value of 0 (distance from source to itself)
  2. [1 mark] Give each vertex connected to start vertex a "working value" (current shortest distance)
  3. [1 mark] Select vertex with smallest working value and make it "final"
  4. [1 mark] Update working values of vertices connected to this final vertex
  5. [1 mark] Repeat steps 3-4 until end vertex is reached and all vertices have final values
  6. [1 mark] Trace route back from end to start to find shortest path
Marking Scheme & Answer
  • [1 mark] A* uses heuristics (intelligent guesses) to guide search toward destination
  • [1 mark] It calculates f(n) = g(n) + h(n) where h(n) is heuristic estimate to goal
  • [1 mark] This makes it more efficient than Dijkstra's for larger, complex problems
  • [1 mark] A* explores fewer nodes by prioritizing those that seem closer to goal
  • [Additional] However, A* depends on quality of heuristic and may not always find shortest path
Marking Scheme & Answer
Supervised Learning:
  • Uses labelled data
  • Known inputs and outputs
  • Predicts outputs for new inputs
  • Example: Spam detection
Unsupervised Learning:
  • Uses unlabelled data
  • Finds hidden patterns
  • Discovers structure in data
  • Example: Customer segmentation
Reinforcement Learning:
  • No training data
  • Learns by trial and error
  • Reward/punishment system
  • Example: Game AI
Commonality: All are machine learning methods used to enable systems to learn and make decisions.
Marking Scheme & Answer
  1. [1 mark] Initial random weights are assigned to neural connections
  2. [1 mark] System processes inputs and produces outputs
  3. [1 mark] Outputs are compared to expected results, errors are calculated
  4. [1 mark] Errors are propagated backward through the network
  5. [1 mark] Weights are adjusted based on error contribution of each connection
  6. [Additional] Process is repeated iteratively until errors are within acceptable limits
Marking Scheme & Answer
  • [1 mark] Regression analysis is a statistical method to predict numerical values
  • [1 mark] It analyzes relationship between input and output variables
  • [1 mark] Creates mathematical formula based on correlation in data
  • [1 mark] Used in ML to make predictions from new input data
  • [Additional] Examples: Weather forecasting, stock price prediction, sales forecasting
Marking Scheme & Answer
  • [1 mark] Deep learning systems analyze multiple facial features
  • [1 mark] Features include: distance between eyes, width of nose, shape of cheekbones
  • [1 mark] System creates unique facial signature/embedding for each person
  • [1 mark] Compares new face against database of known faces
  • [1 mark] Uses neural networks with multiple layers to process complex patterns
  • [Additional] Applications: Phone unlocking (Face ID), security systems, photo organization
Marking Scheme & Answer
1. Narrow AI:
  • Superior to human in one specific task
  • Examples: Chess AI, spam filters
  • Most current AI falls in this category
2. General AI:
  • Similar to human in any intellectual task
  • Hypothetical - no true examples yet
  • Would require human-like reasoning
3. Strong AI:
  • Superior to human in many tasks
  • Advanced hypothetical systems
  • Beyond human capabilities
Key Difference: Narrow AI is specialized for specific tasks, while General and Strong AI would have broader, more human-like capabilities.
Marking Scheme & Answer
  • [1 mark] Semi-supervised learning uses both labelled and unlabelled data
  • [1 mark] Small amount of labelled data combined with large amounts of unlabelled data
  • [1 mark] Cost-effective since labelling data is expensive/time-consuming
  • [1 mark] Example: Classifying web pages into categories (sports, news, finance)
  • [Additional] Web crawler analyzes unlabelled pages, small set manually labelled for training
Marking Scheme & Answer
Machine Learning Advantages:
  • Needs less data for training
  • Faster training on smaller datasets
  • Easier to interpret results
  • Works well with structured data
Machine Learning Disadvantages:
  • Limited with complex patterns
  • Requires feature engineering
  • Struggles with unstructured data
  • Modular approach can be complex
Deep Learning Advantages:
  • Excels with complex patterns
  • Automatic feature extraction
  • Works well with unstructured data
  • End-to-end problem solving
Deep Learning Disadvantages:
  • Requires large amounts of data
  • Computationally intensive
  • Harder to interpret ("black box")
  • Long training times