What is Artificial Intelligence?

• A broad category of research initiatives aimed to make non-human agents display intelligent-like behaviour
  • The problem of whether or not a machine or computer program can become intelligent is the subject of much debate in philosophy, computer science, and cognitive psychology
• In humans, at least, intelligence comes from perception and cognition
  • These are primarily provided by our nervous system

The Turing Test

• Alan Turing developed a test for artificial intelligence in 1950:
  • A machine and a human are both separated from the judge
  • The judge interacts with both the machine and the human
  • "If the judge cannot reliably tell the machine from the human, the machine is said to have passed the test"
• The Turing test has been ostensibly been passed multiple times recently, mostly by chat bots
  • These are computer programs that chat with you, as if they are real people
  • e.g. Cleverbot

Case Study: Driverless/Autonomous Cars

• Driverless cars combine the following AI topics:
  • Computer vision
  • Prediction, collision avoidance
  • Communication with other agents
  • Navigation
  • Constraint satisfaction
  • Motor control
  • ... and more ...

Case Study: Driverless/Autonomous Cars

• Also check out: Chris Urmson's TED Talk

Sensation

• Sensation is the raw collection of information from the environment
  • Not generally associated with intelligence, but necessary for it
• Machines already have sophisticated devices for this purpose, similar to (or sometimes better than) their human equivalents

Sensation - Human

• Human sensation (the five major senses):

  Vision

  eyes detect visible light

  Hearing

  ears detect sound waves

  Touch

  skin detects pressure (also heat, …)

  Taste

  taste buds detect chemicals

  Smell

  olfactory sensors detect chemicals

Sensation - Machine

• Machine sensation (simulating the five major senses):

  Vision

  CCD/CMOS detect visible/IR/UV light, Lidar/Radar detects objects

  Hearing

  microphones detect sound waves

  Touch

  haptic sensors detect pressure, temperature sensors detect heat, …

  Taste/Smell

  chemoreceptor sensors detect chemicals

Sensation - Technology

• Self-driving cars use a number of sensors:

  Lidar

  Uses reflected light from a laser
  Used to identify other objects on/near the road

  CCD

  Detects visible light
  Used to read street signs, traffic signals, etc.

  GPS

  Uses satellites to determine position
  Used to determine current position

  Speedometer, traction sensor

  Used to differentiate safe vs. unsafe driving

What is Perception?

• Perception is the process by which raw information, collected by the sense, is processed into a useful form
  • e.g. For raw visual input: recognizing shapes, letters, faces, and emotions, as well as tracking objects as they move
  • e.g. For raw audio input: recognizing words, threatening sounds, infants crying, and finding the direction of sounds

Perception - Computer Vision

• Computer vision topics:
  • Tracking objects (e.g. suspects fleeing scene in surveillance video)
  • Gesture recognition (e.g. using hand gestures to control your TV)
  • Recognizing faces (e.g. biometric login for your smart TV or phone)
  • Recognizing presence (e.g. counting the occupants in carpool lane, counting people at a concert)
  • Recognizing objects (e.g. weapons), distance, motion (e.g. speed)
  • Character recognition (e.g. license plate readers, scanning printed documents)
  • 3D scene reconstruction (e.g. being able to rotate the scene based on an image, revealing obscured parts of a room)
  • Augmented reality (e.g. games, driver alerts)

Perception - Speech Recognition

• Converting audio into a stream of recognized natural language text
  • Software that looks for audio patterns to replace with text equivalents
    • This is an example of a Greedy Algorithm strategy, similar to divide and conquer discussed in the last lecture section
  • Speech recognition demo

Perception - Self-driving Car

• In a self-driving car, perception is the key to:
  • Correctly recognizing
    • Street signs
    • Traffic signal status
  • Identifying hazards
    • Potholes
    • Snow drifts
    • Construction sites

What is Cognition?

• Cognition involves the high-level brain activities:
  • Memory and knowledge representation
  • Language
  • Reasoning
  • Decision-making and problem solving
  • Learning

Cognition - Knowledge Representation

• Computers already have memory
  • In fact, a computer's memory is more reliable than a human's (in general)
• The challenge comes from figuring out how to represent knowledge

Cognition - Knowledge Representation

• Knowledge representation (KR) is how to store knowledge, beyond basic facts
• Methods being used to represent knowledge:
  • Rule systems
  • Semantic networks

Cognition - Knowledge Representation

• Knowledge representation (KR) is how to store knowledge, beyond basic facts
• Methods being used to represent knowledge:
  • Rule systems
    • Describe some conditions, and the course of action (often with a probability)
    • e.g. A patient experiences chronic headaches, may have:
      • High blood pressure (58%)
      • Meningitis (12%)
      • Brain tumour (9%)
  • Semantic networks

Cognition - Knowledge Representation

• Knowledge representation (KR) is how to store knowledge, beyond basic facts
• Methods being used to represent knowledge:
  • Rule systems
  • Semantic networks
    • An informally-structured graph showing named relationships between concepts, perhaps learned through data mining or natural language processing of large corpora
    • e.g. Napoleon ––birth year—> 1769

Cognition - Knowledge Representation with Semantic Networks

• A simple semantic network:

Cognition - Knowledge Representation with Semantic Networks

• A more realistic semantic network:

Cognition - Language

Lexical analysis

finding words

Syntax analysis

understanding sentence structure and word groups

Semantic analysis

understanding sentence meaning, usually from the component word groups

Pragmatics

Dealing with references to other sentences or the domain world (e.g. she, the manager, their car), idioms, etc.

Cognition - Language

• Formal semantics: Use a math representation for each word, which can be combined in a well-defined way
  • Works close to 100%, but only a small subset of natural languages (e.g. English) have been implemented
• Probabilistic methods: Use a probability, which is influenced by context, to guess the meaning of a word or phrase
  • Works close to 80%, yet there are systems which seem to understand all of English in some way or another

Cognition - Reasoning

• Rule-based systems
  • Since rules are implications (similar to if-then), we can simply follow the chain of implications to a conclusion
  • When rules are probabilistic, we can follow the tree of implications to a set of conclusions, each with a probability

Cognition - Reasoning

• A simple rule-based system:

Cognition - Reasoning

• Symbolic programming
  • The values are represented in symbolic form

  \begin{equation}\label{01} \begin{split} F &=sin(x^2) + cos(x)\\ \end{split} \end{equation}

  • The rules are axioms from mathematics:
    • Rules for solving, simplifying
    • Rules for differentiation (e.g. power rule)
    • Rules for integration (e.g. product rule)
    • Rules for logic (e.g. inference, conjunction)
    • Rules for linear algebra (e.g. inverting a matrix)

Cognition - Decision-making

• State graphs
  • A graph showing all possible states, and the transitions between them

Cognition - Decision-making

• Decision tree
  • A tree where each node's children represent the decisions that can be made at that state

Cognition - Game Playing

Backgammon

IBM's TD-Gammon was the first program capable of beating the world's best 1992

Checkers

U of Alberta's Chinook beat the world's best in 1995

Chess

IBM's Deep Blue vs. world champ Garry Kasparov

• 1996: Kasparov won 4-2
• 1997: Deep Blue won 3.5-2.5

Go

Taiwan's MoGo and Rémi Coulom's Crazy Stone have beat the world's best Go players in 2015

Cognition - General Game Playing

• Competitors write programs to solve previously unknown games
  • Competitors are given a file which describes the rules of the game
    • How to go from one game state to another, how a game is won, lost
  • The competitors' program reads the file and comes up with one move at a time to play

Cognition - Pathfinding

• Pathfinding is a well-known problem, used by:
  • Games
  • GPS navigation devices
• The basic algorithms for pathfinding are:
  • A* (A-star) algorithm
  • Dijkstra's algorithm

Cognition - Pathfinding

• Pathfinding for single units is fairly straightforward:

Cognition - Pathfinding

• Multi-unit (swarm) pathfinding is more complicated:

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Break down the world into a rectangular grid

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Choose your start and goal locations

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Examine all spaces adjacent to the start position

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • From each examined space, examine its adjacent spaces

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process, remembering the fastest way to get to each space

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding Example

• Pathfinding with Dijkstra's Algorithm:
  • Repeat the process

Cognition - Pathfinding

• A website for experimenting with different pathfinding techniques:
  • Pathfinding.js

Cognition - Machine Learning

• Machine learning generally involves training:
  • The program makes decisions, and they are evaluated
  • Good decisions are reinforced, bad decisions are ignored

Cognition - Machine Learning

• Unsupervised training:
  • A set of problems are given
  • The program tries to find relationships between them
    • e.g. Finding related articles on BBC.com, Vice.com, etc.
• Supervised training:
  • A set of problems and solutions are given
  • The program is modified, running it against the problems multiple times, choosing the best modifications
    • e.g. E-Mails, marked as either spam or not spam

Cognition - Machine Learning

• Common machine learning techniques:
  • Artificial neural networks (ANNs)
    • The connection between neurons is reinforced by correct solutions
  • Genetic algorithms
    • Future solutions are based on the level of fitness of existing solutions
  • Bayesian networks
    • Probabilities are updated according to the actual frequency of events

Cognition - Machine Learning

• Artificial neural networks use a simulation of neurons (brain cells) to solve problems
  • ANNs have been used to solve many problems:
    • Computer vision (e.g. stop sign recognition)
    • Decision-making (e.g. medical diagnosis)
    • Classifying data (e.g. is this message spam?)
    • Game-playing (e.g. blackjack)

Cognition - Machine Learning

• Biological neurons have a relatively complicated structure:

Cognition - Machine Learning

• We can simulate the same process in software:

Cognition - Machine Learning

• A simple neural network
  • Nodes at the bottom are input nodes (connected to sensors)
  • Nodes at the top are control nodes (connected to motors)
  • Nodes in between represent more and more abstract concepts
  • An ANN with multiple middle layers is popularly called a deep learning network

Cognition - Machine Learning

• Determine how to represent the problem as a string or number
• Randomly generate a bunch of solutions:
  • Consider each solution a chromosome
  • Each component of the chromosome is a gene
• Using rules of genetics, continually generate more solutions:
  • Each chromosome (solution) is evaluated on its fitness (quality of the solution)
  • Choose parents probabilistically, based on fitness (selection)
  • To reproduce, combine genes from the different chromosomes (crossover)
  • Optionally, also include mutations on individual chromosomes (mutation)
• Example: BoxCar2D

Cognition - Machine Learning

• Bayesian networks are built on top of Bayesian inference
  • The use of Bayes theorem to infer, using Bayesian probability:
    • P(A) – The independent probability of A
    • P(B) – The independent probability of B
    • P(A|B) – The probability of B, given that A has occurred
    • P(B|A) – The probability of A, given that B has occurred

\begin{equation}\label{02} \begin{split} P(A|B) &= \frac{P(B|A)P(A)}{P(B)}\\ \end{split} \end{equation}

Cognition - Self-driving/Autonomous Car

• In a self-driving car, many techniques may be combined for the car to function:
  • ANNs for adapting speed, based on speed limit signs
  • Pathfinding for navigation
  • Constraint satisfaction, decision tree search for avoiding collisions (brake, turn left, turn right?)
  • Bayesian networks for predicting other drivers', cyclists', and pedestrians' actions

Another Case Study: RoboCup