Requisites

compressive sensing (sparse coding),

information theory,

control theory,

economics,

logic,

operations research,

game theory,

and optimization.

Resources

Introduction

What is AI?

We struggle with what is intelligent, but not artificial.

We use rational agents as our approach. An agent is an entity that can perceive an environment X and can act on it where X can be virtual or physical. How an agent decides to act given all previous considerations is a black box.

So, intelligence or rationality is when an agent makes the best decision in a given environment and goal with constraints and acts in accordance with it. Therefore, we evaluate an agent by its results, not by its mental state.

If an agent makes the best decision in all environments and goals, it is called artificial general intelligence.

If an agent makes the best decision in a specific environment, it is called weak AI.

From a scientific point’s view is understanding complete AI, but from an engineering point’s view is making incomplete, imperfect, and weak artificial intelligence.

Some constraints are lack of knowledge, time to learn, time to execute, money, actuators, and sensors.

But, now black boxes become white boxes. If you are here, then you are interested in white boxes which are computational procedures. You’re going to learn them!

Ecosystem

https://inside.com/ai

https://www.csail.mit.edu/

https://bair.berkeley.edu/

http://ai.ucsd.edu/

https://www.microsoft.com/en-us/research/collaboration/bair/

https://people.eecs.berkeley.edu/~yima/ by https://twitter.com/YiMaTweets

Story

Computing Machinery and Intelligence.

The Imitation Game (Turing test).

Player A is a computer who claims to be a man.

Player B is a man.

Interrogator.

Total Turing Test.

Loebner Prize.

The Argument from Extrasensory Perception. During Cold War, people were interested in viz, telepathy, and precognition, so Turing prepared an argument for the situation.

https://courses.cs.washington.edu/courses/csep590a/06au/projects/history-ai.pdf

https://plato.stanford.edu/entries/artificial-intelligence/

https://journals.sagepub.com/doi/pdf/10.1177/0008125619864925

https://dl.acm.org/doi/fullHtml/10.1145/2063176.2063177

https://sitn.hms.harvard.edu/flash/2017/history-artificial-intelligence/

Association for Computing Machinery (ACM). (2022, December 22). January 2023 CACM: The End of Programming. Youtube. Retrieved from https://www.youtube.com/watch?v=OnYJXm9NvyA&ab_channel=AssociationforComputingMachinery(ACM)

Related work

Cognitive science

Philosophy of mind

Worked examples

• “Surely computers cannot be intelligent—they can do only what their programmers tell them.” Is the latter statement true, and does it imply the former?

  Argument 0.

  If we assume "The Universal Machine can do all possible processes", we cannot say "Some possible processes can't be done by the Universal Machine" since it follows a contradiction, that is, "The Universal Machine is not universal". The big questions are “are computers universal machines?”, “are humans universal machines?”, “Can we generate life, intelligence, or conscientiousness from inorganic materials?”

  Argument 1.

  Formerly,

  $p:\text{computers can be intelligent}$

  $q:\text{computers can do what their programmers tell them}$

  Implication:

  $q\implies \lnot p$

  Conversely,

  $p\implies \lnot q$

  If $\lnot q\implies FALSE$, $p\implies FALSE$, so $q$ doesn’t imply $\lnot p$.

  But, is $q$ true?

  All computer actions are programmed.

  There are computer actions as randomness by entropy devices are not programmed.

  Some computer actions are not programmed.

  $q$ is false.

  https://ieeexplore.ieee.org/document/7313842

  BUG? Turing Machine Deterministic and Nondeterministic equivalence.

FAQ

I learned in the Theory of computation some problems are undecidable, but I see those problems solved with Artificial Intelligence, how is that?

AI Framework.

Intelligent Agents. Rational agents.

Agent class

• Code

  @startuml
  Agent <|-- "Rational Agent"
  class Agent {
     actuators
     sensors
     type
     process: 'competitive' | 'cooperative'
     performance measure
     percepts(environment)
     choose the best decision by performance measure(): Decision
  }
  note left of Agent::percepts
     What is the environment like now?
  end note
  note left of Agent::"choose the best decision by performance measure"
     What action I should take now?
     It's called the agent program too.
     Building a small program is a key challenge. 
     No brute force such as a vast table!
     But remember, sometimes, memory = intelligence.
     In fact, if you know all the possible results, 
     it's called Omniscience.
     Memory is called safe steps.
     Decreasing memory increases heuristic steps.
  end note
  class "Rational Agent" {}
  note right: Learning and Autonomy
  "Rational Agent" <|-- "Reflex agent"
  "Rational Agent" <|-- "Model-based reflex agent"
  "Rational Agent" <|-- "Goal-based agent"
  "Rational Agent" <|-- "Utility-based agent"
  Agent --> Environment: action
  Environment --> Agent: percepts
  class Environment {
     observable: 'Fully' | 'Partially'
     agent: agents: Agent[] // Single, Multi
     deterministic: 'deterministic'| 'nondeterministic'| 'stochastic'
     sequential: 'episodic' | 'sequential'
     static: 'static' | 'dynamic' | 'semi-dynamic'
     discrete: 'discrete' | 'continuous'
     known: 'Known' | 'Unknown'
  }
  class Actuators
  Agent o-- Actuators
  class "Reflex agent" {
    choose the best decision by performance measure(): Decision
    - rule match(state, rules)
    - interpret input(environment): state
  }
  class "Model-based reflex agent" {
    current state
    choose the best decision by performance measure(): Decision
    - transit()
  }
  @enduml
  note right of "Reflex agent"::"choose the best decision by performance measure"
     condition-action rules
     f(x)
  end note
  note right of "Model-based reflex agent"::"choose the best decision by performance measure"
     state machine (DFA/Meadly/Moore/...)
  end note

Worked examples

Further readings

Economic agents.

Solving problems by Searching.

graph TD
  S["S, environment"] -->|"cost(S,action1, A)"| A["A, new environment"]
  S -->|"cost(S,action2, B)"| B["B, new environment"]
  S -->|"cost(S,action3, C)"| C["C, new environment"]
  subgraph possible_solutions3
    C-->E["..."]
  end
 subgraph possible_solutions2
    B-->F["..."]
  end
  subgraph possible_solutions1
    A-->D["..."]
  end
  D-->Goal,["Goal, new environment == goal"]

Searching problem model

classDiagram
    class SearchProblem {
      heuristic()
      start_state()
      is_goal(state)
      expand(state)
      valid_actions_from(state)
      action_cost(state, action, next_state)
      next_state(state, action)
    }
    class State {
       distance_from_start_state
       previous_state
       environment
       build()
       relax()
       reconstruct_path()
    }
    class SearchingStrategy {
       findPlanFor(problem)
    }
    class Agent {
      searchingStrategy: SearchingStrategy
      problem: SearchProblem
      act(state)
    }
    Agent *-- SearchingStrategy
    Agent *-- SearchProblem
    SearchingStrategy <|-- BFS
    SearchingStrategy <|-- DFS
    SearchingStrategy <|-- AStar
    SearchingStrategy <|-- Dijistra
    SearchingStrategy <|-- LinearProgramming

Searching strategies

Searching strategies

Searching for solutions

Considerations.

We build a tree or graph on demand by searching strategies.

We have got to avoid cycles in order to keep away infinite loops.

Each new state saves the reference's previous state and we only choose valid action, so when our searching algorithm reaches the goal; it reconstructs the path from the start state.

$S\to A\to ...\to Goal$

Codification matters.

Uninformed search strategies

BFS

DFS

Informed Search Strategies

A*, Greedy Search, Hill Climbing, Simulated Annealing, Best-First Search

Heuristic Functions

A heuristic is a function that estimates the distance from the current state to the goal.

$f(n)$ is the real or estimated cost of the $n$ solution.

$g(n)$ is the cost to reach $n$ from the start state. $\sum_{i=0}^n cost(i,action,i+1)$

$h(n)$ is the estimated cost to reach the goal state from the $n$ state, so it uses the available information from the problem or environment state in order to estimate the cost.

$h^*(n)$ is the real cost to reach the goal state from the $n$ state.

$\sum_{i=n}^g cost(i,action,i+1)$

Note $h(n) \to0$ and $h^*(n)\to 0$.

Properties

Main idea: estimated heuristic $\le$ actual costs.

Admissibility.

$0 \le h(x) \le \text{costs to goal}$

Consistency.

$h(x)-h(y) \le costs(x,y)$

Dominance.

Optimal.

How do you find a heuristic function?

Relax your problems, use available information about the current state or the goal, use min, and max functions, or use some distance functions such as Manhattan distance, Euclidean distance, Hamming distance, … and norms.

Heuristic. Safe steps.

Offline, Online.

Solving problems by searching are graph algorithms that generate new nodes by heuristic and safe steps and test them, wrong answers are rejected them.

Hands-on Projects

8-Queen solver

Hanoi tower

Maze solver

Graph Theory Visualizer: Maze. (2022, July 03). Retrieved from https://graph-theory.sanchezcarlosjr.com

Project 0 - Unix, Python and Autograder Tutorial - CS 188: Introduction to Artificial Intelligence, Spring 2021. (2022, September 29). Retrieved from https://inst.eecs.berkeley.edu/~cs188/sp21/project0/#question-1-addition

The farmer, fox, goose, and grain

Integral solver

Pacman

Project 1 - Search - CS 188: Introduction to Artificial Intelligence, Spring 2021. (2022, September 29). Retrieved from https://inst.eecs.berkeley.edu/~cs188/fa22/projects/proj1/

Worked examples

References

https://aimacode.github.io/aima-javascript/3-Solving-Problems-By-Searching/

How to solve it: Modern Heuristics by Zbigniew Michalewicz, David B. Fogel.

Adversarial Search

MinMax

https://www.youtube.com/watch?v=l-hh51ncgDI&ab_channel=SebastianLague

MonteCarlo

matchmaking algorithms

Hands-on Projects

Tic Tac Toe

Chess

Pacman v2

Notion – The all-in-one workspace for your notes, tasks, wikis, and databases. (2023, April 20). Retrieved from https://www.chessengines.org

Project 2. (2022, October 13). Retrieved from https://inst.eecs.berkeley.edu/~cs188/fa22/projects/proj2

Constrain satisfaction Problems

Knowledge, reasoning, and planning

Logical Agents

Knowledge, Syntax, Semantics

Prolog,

Relational databases, SQL, Datalog?

Knowledge base (domain-specif facts) + inference engine.

Syntax, set of possible worlds, truth condition.

Sound Algorithm.

Complete Algorithm.

Theorem-proving.

Model-checking.

https://www.youtube.com/watch?v=CAsq7hm3sbI&ab_channel=IITDelhiJuly2018

https://www.youtube.com/watch?v=xFpndTg7ZqA&t=1s&ab_channel=IITDelhiJuly2018

https://www.youtube.com/watch?v=h6zCkrZ8ehE&t=1s&ab_channel=RichNeapolitan

tammet. (2022, December 13). gkc. Retrieved from https://github.com/tammet/gkc

Program

class KnowledgeAgent:
  KB knowledge base
  t int
  act(environment):
    tell(KB, MakePerceptSentence(environment, t))
    action = ask(KB, MakeActionQuery(t))
    tell(KB, MakeActionSentence(action, t))
    t = t+1
    return action 

Inference machine

First-Order Logic

Inference in First-Order Logic

Worked examples

Projects

Card fraud detector

Make an online quiz system about Artificial Intelligence

8-eight queen

Pacman Finder

https://inst.eecs.berkeley.edu/~cs188/sp21/project3/

Wordle Solver

https://swi-prolog.discourse.group/t/wordle-solver/5124

https://cheatle.occasionallycogent.com/

Resources

• http://www.learnprolognow.org/ is a great place to start

• http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/ covers some advanced topics

• http://www.coli.uni-saarland.de/projects/milca/courses/comsem/html/ more advanced

• http://www.mtome.com/Publications/PNLA/prolog-digital.pdf This is my personal favorite

You may also consider picking up some of the following books

• Clocksin - Mellish: Programming in Prolog

• Covington - Nute - Vellino: Prolog Programming in Depth

• Sterling - Shapiro : The Art of Prolog

• Bratko : Prolog Programming for Artificial Intelligence

FAQ

What are real-world projects where people use PROLOG?

https://www.quora.com/What-is-Prolog-used-for-today

https://www.cs.nmsu.edu/ALP/2011/03/natural-language-processing-with-prolog-in-the-ibm-watson-system/

https://www.drdobbs.com/parallel/the-practical-application-of-prolog/184405220

Classical Planning

Planning and Acting in the Real World

Knowledge representation

Uncertain knowledge and reasoning

Quantifying Uncertainty

Probabilistic Reasoning

Probabilistic Reasoning over Time

Making Simple Decisions

Making Complex Decisions

* Learning

https://github.com/afshinea/stanford-cs-229-machine-learning/tree/master/en

https://course.fast.ai/

https://www.fast.ai/

https://huggingface.co/

Learning from Examples

Knowledge in Learning

Learning Probabilistic Models

Reinforcement Learning

* Communicating, perceiving, and acting

Natural language processing

References

https://ipfs.io/ipfs/QmdVkKvX5JBSNTWjNBW5LdbPFTT8wLQb1vCJtUzXRppXbg?filename=nlp.pdf

Natural Language for Communication

Perception

Robotics

*Philosophical Foundations

Weak AI: Can Machines Act Intelligently?

Strong AI: Can Machines Really Think?

The Ethics and Risks of Developing Artificial Intelligence

AI: Present and Future

Machine learning

Datasets

• Google Dataset

• Kaggle

Notebooks

https://www.youtube.com/watch?v=T-fAkfU9j_o&ab_channel=Elpensamientoenllamas

TODO

Natural Computing

NACO

https://fcampelo.github.io/EC-Bestiary/

black hole algorithm

Mandelbrot set from scratch, Markov text-generation,

and John Conway’s Game of Life ar