🧠

Artificial Intelligence

TagsComputer science
Created
Updated
Image generated by Dalle2 https://twitter.com/Dalle2Pics/status/1545871607767384066

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://ai-timeline.sanchezcarlosjr.com/

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

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

👉🏼
Agent = Architecture + Program. Artificial intelligence’s concern is the program.

Worked examples

Further readings

Economic agents.

Solving problems by Searching.

💡
Searching problems are optimization problems.
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.

SA...GoalS\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)f(n) is the real or estimated cost of the nn solution.

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

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

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

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

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

Properties

Main idea: estimated heuristic \le actual costs.

Admissibility.

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

Consistency.

h(x)h(y)costs(x,y)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.

Beyond Classical Search.

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

You may also consider picking up some of the following books

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

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