1 of 42

ME 4990: Intro to CS�Object-Oriented Programming & Machine Learning 101

�

Introduction to AI, Search for AI

2 of 42

Outline

  • Introduction to Artificial Intelligence
    • Some history
    • Search-based Problem
    • Inference
    • Model-based Problem
    • Learning
  • Types of Machine Learning
    • Supervised
    • Unsupervised
    • Reinforcement

​

​

​

​

3 of 42

Abridged history of AI

  • 1943 McCulloch & Pitts: Boolean circuit model of brain
  • 1950 Turing's "Computing Machinery and Intelligence"
  • 1956 Dartmouth meeting: "Artificial Intelligence" adopted
  • 1952—69 Look, Ma, no hands!
  • 1950s Early AI programs, including Samuel's checkers� program, Newell & Simon's Logic Theorist, � Gelernter's Geometry Engine
  • 1965 Robinson's complete algorithm for logical reasoning
  • 1966—74 AI discovers computational complexity� Neural network research almost disappears
  • 1969—79 Early development of knowledge-based systems
  • 1980—88 Expert systems industry boom
  • 1988—93 Expert systems industry busts: "AI Winter"
  • 1985—95 Neural networks return to popularity
  • 1988— Resurgence of probability; AI becomes science
  • 1995— The emergence of intelligent agents
  • 2003— Human-level AI back on the agenda
  • 2010-- BIG data? Deep learning?

4 of 42

Artificial Intelligence

  • ChatGPT gives an answer

​

​

​

​

​

​

5 of 42

Start Point

  • Artificial Intelligence is coined in 1955 in Dartmouth College
  • They propose:
    • Automatic Computers
    • Computer Language
    • Neuron Nets??????
    • Theory of the Size of a Calculation (Complexity, NP-hard?)
    • Self Improvement (Reinforcement Learning?)

6 of 42

Logic Reasoning Stage

  • Now a part of discrete mathematics
  • Example:
    • Propositions p, q, r and s are defined as follows:
      • p is "I shall finish my Coursework Assignment"
      • q is "I shall work for forty hours this week"
      • r is "I shall pass Maths"
      • s is "I like Maths“
    • Do these propositions hold true?
      • (a) If p is true, then p or q is true
      • (b) If p and q is true, then p is true
      • (c) If q is true, then not p or not q is true

​

7 of 42

Knowledge-based system

  • What is knowledge?
    • Logic Based Reasoning
      • One must buy a ticket to board the train
      • One must pay tuition to attend the college
      • One must put an article (the, a, an) before a countable noun in singular form.
      • One must ...
    • Reasoning from knowledge:
      • Train knowledge:
        • If some one board the train, he/she must have bought the ticket;
        • If some one didn’t buy ticket, he cannot board the train
        • Can we say: if some one didn’t board the train, he/she must haven’t bought a ticket
      • …

​

  • A knowledge base is a collection of all these knowledge
  • We (human) are a knowledge base, we learn knowledge, then we make reasonings
  • Can we make a general knowledge-base for reasoning

8 of 42

Knowledge-based system

  • What is knowledge?
    • Probabilistic-based reasoning knowledge
      • If one do HW by him/herself, the probability of passing the final next hour is 80%
      • If we observe cloud, the probability of rain in the next hour is 50%
      • If a robot odometer shows it has travelled 5m, the probability that it actually travelled between [4.5m, 5.5m] is 95%
    • We can reason
      • If one do HW and observe cloud, the probability of he/she passes the final in a training day is 40%.
      • That is, we are more confident that he/she will not pass the final exam in a rainy hour

​

      • If we see the robot is actually at 7m position, we have a large confidence that the odometer is broken and we shall call customer service
  • Bayes and Markov were our best friends

​

9 of 42

Probabilistic-based reasoning knowledge

  • Construct a Bayesian net from these variables: parents?
  • Markov assumption: depends on bounded set of
  • First order Markov process:
  • Second order Markov process:

​

​

​

​

  • Sensor Markov assumption:
  • Stationary process: transition model and sensor model are fixed for all t

10 of 42

Probabilistic-based reasoning knowledge

  • First-order Markov assumption not exactly true in real world!
  • Possible fixes:
    • 1. Increase order of Markov process
    • 2. Augment state, e.g., add Tempt, Pressuret
  • Example: robot motion.
    • Augment position and velocity with Batteryt

11 of 42

Search based problem

  • We can solve a complex problem by enumerate all possible cases
    • A man has to take a wolf, a goat, and some cabbage across a river.
    • His rowboat has enough room for the man plus either the wolf or the goat or the cabbage.
    • If he takes the cabbage with him, the wolf will eat the goat.
    • If he takes the wolf, the goat will eat the cabbage.
    • Only when the man is present are the goat and the cabbage safe from their enemies.
    • All the same, the man carries wolf, goat, and cabbage across the river. How?
  • We enumerate all cases till one viable solution:

​

​

12 of 42

Search based problem

  • On many problems, AI can beat people by search-based approaches
  • For example, Deep Blue (chess computer)
    • Feb 10-17, 1996, deep blue becomes the first AI to win a chess game against a reigning world champion under regular time controls.
  • Most of turn-based game AI are written use search-based approach
    • Sid Meier’s Civilization!

​

13 of 42

Search-based approach for path planning

14 of 42

Agent based approach (mostly for robotics)

  • An agent is like a human that interact with the environment

​

​

​

​

​

  • There are many types of agent-based approach
    • Reflex
    • Model based
    • Goal based
    • Utility based
    • …

15 of 42

Simple reflex agents

  • The action to be selected only depends on the most recent percept, not a sequence
  • These agents are stateless devices which do not have memory of past world states

16 of 42

Introduction to control (ME4391)

  • You can write in your resume:
    • AI (simple reflex agents) after completion of ME4391
    • The agent is the controller

​

17 of 42

Model-based reflex agents

  • Have internal state which is used to keep track of past states of the world
  • Can assist an agent deal with some of the unobserved aspects of the current state

18 of 42

Goal-based agents

�

  • Agent can act differently depending on what the final state should look like
  • E.g., automated taxi driver will act differently depending on where the passenger wants to go

19 of 42

Utility-based agents

  • An agent's utility function is an internalization of the external performance measure
  • They may differ if the environment is not completely observable or deterministic

20 of 42

Learning agents

  • Learning agent cuts across all of the other types of agents: any kind of agent can learn

21 of 42

Machine Learning

  • Machine learning used to be diversified that needs the knowledge beyond the computer community
  • For example, in image matching
    • Human think: window to window
    • Door to door
  • How can we describe window mathematically?
    • Some one like color: white is window
    • Some one like shape: square is window
    • Some one goes more abstract:�(a vector like this is window)

22 of 42

Machine Learning

  • The old algorithm (some are still used actively)
    • Linear regression
    • Logistic regression
    • Decision tree
    • SVM algorithm
    • Naive Bayes algorithm
    • KNN algorithm
    • K-means
    • Random forest algorithm
    • Dimensionality reduction algorithms
    • Gradient boosting algorithm and AdaBoosting algorithm

�

23 of 42

Machine learning

  • Some achievements that are popular:
    • Kinect v1 (using random forest algorithm)

​

24 of 42

Deep Learning

  • Deep learning is a subset of machine learning
  • It uses “deep neuron network” to model problems
  • “Deep neuron network” is basically, a bunch of standardized functions with huge number of parameters
  • Usually by-pass the feature extraction stage
  • In many cases, we cannot interpret the network using our current knowledge
  • Some very old history can be found at:

https://cs.stanford.edu/people/eroberts/courses/soco/projects/neural-networks/History/history1.html#:~:text=In%201943%2C%20neurophysiologist%20Warren%20McCulloch,neural%20network%20using%20electrical%20circuits.

​

​

​

25 of 42

Deep Learning

  • Post office had problems in recognizing the hand-writing zip code
  • LeCun proposes to use a “network” to solve the problem in 1989
  • Achieved 3.4% of error rate

​

​

​

​

​

​

​

​

​

​

26 of 42

Deep Learning

  • ImageNet challenge
    • A dataset with over 1 million pictures with 732 classes

​

27 of 42

Deep Learning

  • A “convolutional neural network” called “alexNet is used in 2012
  • Significantly reduced error (top 5 class) from ~25% to 15%

​

​

​

​

​

​

​

28 of 42

Deep Learning

  • Applied in language processing

​

29 of 42

Deep Learning

​

​

​

​

​

​

​

30 of 42

Deep learning

  • Do illegal business
  • Just google deepfake

31 of 42

Outline

  • Introduction to Artificial Intelligence
    • Some history
    • Search-based Problem
    • Inference
    • Model-based Problem
    • Learning
  • Types of Machine Learning
    • Supervised
    • Unsupervised
    • Reinforcement
  • Course Goal

​

​

​

32 of 42

Machine Learning

  • Generally, there are three categories
    • Supervised learning
    • Unsupervised learning
    • Reinforcement learning

33 of 42

Supervised Learning

  • Most machine learning algorithm are developed by supervised learning
  • In Cal Poly Pomona, our slogan is “learn by imitation”. Basically, we learn by imitate examples (we believe the teacher is always right)

34 of 42

Supervised learning

  • Generally, any supervised learning procedure is as follows:
    • Collect data and label data
    • Train a model
    • Test a model

35 of 42

Supervised Learning

  • Dog v Cat
  • We have data, and each data must have a label
  • We some times call the data with label “ground truth”

Dog

Cat

36 of 42

Supervised Learning

  • Training phase
  • We want to fit (find) a model (function) that matches the label

Find a Function

Dog

Cat

37 of 42

Supervised Learning

  • Testing/application phase

​

Function

???

38 of 42

Unsupervised learning

  • Generally, any unsupervised learning procedure is as follows:
    • Collect data and label data
    • Train a model
    • Test a model

39 of 42

Unsupervised learning

  • No label is provided, no ground truth
  • Just group data by proximity

​

​

40 of 42

Unsupervised learning

  • Category the insects in 5 classes

41 of 42

Reinforcement Learning

  • Training is online, no existing data set
  • Give reward based on action
  • AlphaGo used reinforcement learning

42 of 42

Outline

  • Introduction to Artificial Intelligence
    • Some history
    • Search-based Problem
    • Inference
    • Model-based Problem
    • Learning
  • Types of Machine Learning
    • Supervised
    • Unsupervised
    • Reinforcement

​

​

​

​