DS161 Introduction to Data Science & Artificial Intelligence
Lecture 1
Introduction to Artificial Intelligence: From Rules to Generative AI
Krishnendu Ghosh
Intelligence
Modern AI
RIGHT BRAIN
Classical AI
LEFT BRAIN
Foundations of AI
Philosophy
Can formal rules be used to draw valid conclusions?
How does the mind arise from a physical brain?
Where does knowledge come from?
How does knowledge lead to action?
Rationalism, Dualism, Materialism, Empiricism, Induction, Logical Positivism, Confirmation Theory
Foundations of AI
Mathematics
What are the formal rules to draw valid conclusions?
What can be computed?
How do we reason with uncertain information?
Algorithm, Incompleteness Theorem, Computability, Traceability, NP-completeness, Probability
Foundations of AI
Economics
How should we make decisions so as to maximize payoff?
How should we do this when others may not go along?
How should we do this when the payoff may be far in the future?
Utility, Decision Theory, Game Theory, Operations Research, Markov Decision Processes, Satisficing
Foundations of AI
Neuroscience
How do brains process information?
Neurons, Singularity
Foundations of AI
Psychology
How do humans and animals think and act?
Behaviorism, Cognitive Psychology, Cognitive Science
Foundations of AI
Computer engineering
How can we build an efficient computer?
For artificial intelligence to succeed, we need two things: intelligence and an artifact. The computer has been the artifact of choice.
These supports came from both hardware and software sides.
Foundations of AI
Control theory and cybernetics
How can artifacts operate under their own control?
The central figure in the creation of what is now called control theory was Norbert Wiener (1894–1964). They viewed purposive behavior as arising from a regulatory mechanism trying to minimize “error”—the difference between current state and goal state.
Ashby’s Design for a Brain (1948, 1952) elaborated on his idea that intelligence could be created by the use of homeostatic devices containing appropriate feedback loops to achieve stable adaptive behavior.
Modern control theory, especially the branch known as stochastic optimal control, has as its goal the design of systems that maximize an objective function over time.
Foundations of AI
Linguistics
How does language relate to thought?
Modern linguistics and AI, then, were “born” at about the same time, and grew up together, intersecting in a hybrid field called computational linguistics or natural language processing.
Much of the early work in knowledge representation was tied to language and informed by research in linguistics, which was connected in turn to decades of work on the philosophical analysis of language.
History of AI
The gestation of artificial intelligence (1943–1955)
Hebbian Learning:
They drew on three sources: knowledge of the basic physiology and function of neurons in the brain; a formal analysis of propositional logic due to Russell and Whitehead; and Turing’s theory of computation.
They proposed a model of artificial neurons in which each neuron is characterized as being “on” or “off,” with a switch to “on” occurring in response to stimulation by a sufficient number of neighboring neurons.
The state of a neuron was conceived of as “factually equivalent to a proposition which proposed its adequate stimulus.”
History of AI
Physical Symbol System:
The success of GPS and subsequent programs as models of cognition led Newell and Simon (1976) to formulate the famous physical symbol system hypothesis, which states that “a physical symbol system has the necessary and sufficient means for general intelligent action.”
What they meant is that any system (human or machine) exhibiting intelligence must operate by manipulating data structures composed of symbols.
History of AI
Knowledge-based systems: The key to power? (1969–1979)
Weak Methods, Expert Systems, Certainty Factors, Frames
The picture of problem solving that had arisen during the first decade of AI research was of a general-purpose search mechanism trying to string together elementary reasoning steps to find complete solutions. Such approaches have been called weak methods because, although general, they do not scale up to large or difficult problem instances. The alternative to weak methods is to use more powerful, domain-specific knowledge that allows larger reasoning steps and can more easily handle typically occurring cases in narrow areas of expertise. One might say that to solve a hard problem, you have to almost know the answer already.
History of AI
AI becomes an industry (1980–present)
In the mid-1980s at least four different groups reinvented the back-propagation learning algorithm first found in 1969 by Bryson and Ho. The algorithm was applied to many learning problems in computer science and psychology, and the widespread dissemination of the results in the collection Parallel Distributed Processing (Rumelhart and McClelland, 1986) caused great excitement.
History of AI
The return of neural networks (1986–present)
Back-propagation, Connectionist
History of AI
AI adopts the scientific method (1987–present)
Hidden Markov Models, Bayesian Network, Data Mining
The field of speech recognition illustrates the pattern. In the 1970s, a wide variety of different architectures and approaches were tried. Many of these were rather ad hoc and fragile, and were demonstrated on only a few specially selected examples. In recent years, approaches based on hidden Markov models (HMMs) have come to dominate the area. Two aspects of HMMs are relevant. First, they are based on a rigorous mathematical theory. This has allowed speech researchers to build on several decades of mathematical results developed in other fields. Second, they are generated by a process of training on a large corpus of real speech data. This ensures that the performance is robust, and in rigorous blind tests the HMMs have been improving their scores steadily.
History of AI
AI adopts the scientific method (1987–present)
Hidden Markov Models, Bayesian Network, Data Mining
Judea Pearl’s (1988) Probabilistic Reasoning in Intelligent Systems led to a new acceptance of probability and decision theory in AI, following a resurgence of interest epitomized by Peter Cheeseman’s (1985) article “In Defense of Probability.” The Bayesian network formalism was invented to allow efficient representation of, and rigorous reasoning with, uncertain knowledge. This approach largely overcomes many problems of the probabilistic reasoning systems of the 1960s and 1970s; it now dominates AI research on uncertain reasoning and expert systems.
History of AI
The emergence of intelligent agents (1995–present)
Human-level AI, Artificial Generative Intelligence, Friendly AI
The availability of very large data sets (2001–present)
Bootstrap
AI Applications
Problem Solving: Constraint satisfaction, Optimization, Search
Planning: Abstraction
Deduce: Logic, Reasoning algorithms
Learn: Models, Data, Learning algorithms
Handle uncertainty
Interface with the real world
AI Core Capabilities
Constraints and Optimization
AI Planning
Machine Learning
Agents
An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.
We use the term percept to refer to the agent’s perceptual inputs at any given instant. An agent’s percept sequence is the complete history of everything the agent has ever perceived.
We say that an agent’s behavior is described by the agent function that maps any given percept sequence to an action. Internally, the agent function for an artificial agent will be implemented by an agent program.
Agents
An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.
Agents
This particular world has just two locations: squares A and B.
The vacuum agent perceives which square it is in and whether there is dirt in the square.
It can choose to move left, move right, suck up the dirt, or do nothing.
Agent Function
One very simple agent function is the following: if the current square is dirty, then suck; otherwise, move to the other square.
Specifying the Task Environment
The vacuum world was a simple example; let us consider a more complex problem: an automated taxi driver. We should point out, before the reader becomes alarmed, that a fully automated taxi is currently somewhat beyond the capabilities of existing technology.
Specifying the Task Environment
Properties of Task Environments
Fully observable vs. partially observable: If an agent’s sensors give it access to the complete state of the environment at each point in time, then we say that the task environment is fully observable. A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action; relevance, in turn, depends on the performance measure. Fully observable environments are convenient because the agent need not maintain any internal state to keep track of the world. An environment might be partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data—for example, a vacuum agent with only a local dirt sensor cannot tell whether there is dirt in other squares, and an automated taxi cannot see what other drivers are thinking.
Properties of Task Environments
Single agent vs. multiagent: The distinction between single-agent and multiagent environments may seem simple enough. For example, an agent solving a crossword puzzle by itself is clearly in a single-agent environment, whereas an agent playing chess is in a two-agent environment.
For example, in chess, the opponent entity B is trying to maximize its performance measure, which, by the rules of chess, minimizes agent A’s performance measure. Thus, chess is a competitive multiagent environment. In the taxi-driving environment, on the other hand, avoiding collisions maximizes the performance measure of all agents, so it is a partially cooperative multiagent environment.
Properties of Task Environments
It is also partially competitive because, for example, only one car can occupy a parking space. The agent-design problems in multiagent environments are often quite different from those in single-agent environments; for example, communication often emerges as a rational behavior in multiagent environments; in some competitive environments, randomized behavior is rational because it avoids the pitfalls of predictability.
Properties of Task Environments
Deterministic vs Stochastic: If the next state of the environment is completely determined by the current state and the action executed by the agent, then we say the environment is deterministic; otherwise, stochastic.
A Nondeterministic != Stochastic
Properties of Task Environments
Episodic vs. Sequential: In an episodic task environment, the agent’s experience is divided into atomic episodes. In each episode the agent receives a percept and then performs a single action. Crucially, the next episode does not depend on the actions taken in previous episodes. For example, an agent that has to spot defective parts on an assembly line.
In sequential environments, on the other hand, the current decision could affect all future decisions. Chess and taxi driving are sequential: in both cases, short-term actions can have long-term consequences.
Properties of Task Environments
Static vs. Dynamic: If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent; otherwise, it is static. Static environments are easy to deal with because the agent need not keep looking at the world while it is deciding on an action, nor need it worry about the passage of time.
If the environment itself does not change with the passage of time but the agent’s performance score does, then the environment is semidynamic. Taxi driving is clearly dynamic: the other cars and the taxi itself keep moving while the driving algorithm dithers about what to do next. Chess, when played with a clock, is semidynamic. Crossword puzzles are static.
Properties of Task Environments
Discrete vs. Continuous: The discrete/continuous distinction applies to the state of the environment, to the way time is handled, and to the percepts and actions of the agent.
For example, the chess environment has a finite number of distinct states (excluding the clock). Chess also has a discrete set of percepts and actions. Taxi driving is a continuous-state and continuous-time problem: the speed and location of the taxi and of the other vehicles sweep through a range of continuous values and do so smoothly over time. Taxi-driving actions are also continuous. Input from digital cameras is discrete, strictly speaking, but is typically treated as representing continuously varying intensities and locations.
Properties of Task Environments
Known vs. Unknown: This distinction refers to the agent’s state of knowledge about the “laws of physics” of the environment. In a known environment, the outcomes for all actions are given. If the environment is unknown, the agent will have to learn how it works in order to make good decisions. Note that known/ unknown environments are not same as fully/partially observable environments. It is quite possible for a known environment to be partially observable—for example, in solitaire card games, I know the rules but am still unable to see the cards. Conversely, an unknown environment can be fully observable—in a new video game, the screen may show the entire game state but I still don’t know what the buttons do until I try them.
Properties of Task Environments
Simple Reflex Agents
The simplest kind of agent is the simple reflex agent. These agents select actions on the basis of the current percept, ignoring the rest of the percept history.
The agent program for a simple reflex agent in the two-state vacuum environment.
Simple Reflex Agents
Simple reflex behaviors occur even in more complex environments. Imagine yourself as the driver of the automated taxi. If the car in front brakes and its brake lights come on, then you should notice this and initiate braking. In other words, some processing is done on the visual input to establish the condition we call “The car in front is braking.” Then, this triggers some established connection in the agent program to the action “initiate braking.” We call such a connection a condition–action rule, written as:
if car-in-front-is-braking then initiate-braking
Simple Reflex Agents
Simple Reflex Agents
Simple reflex agents have the admirable property of being simple, but they turn out to be of limited intelligence.
The agent will work only if the correct decision can be made on the basis of only the current percept—that is, only if the environment is fully observable. Even a little bit of unobservability can cause serious trouble.
For example, the braking rule given earlier assumes that the condition car-in-front-is-braking can be determined from the current percept—a single frame of video.
Simple Reflex Agents
Suppose that a simple reflex vacuum agent is deprived of its location sensor and has only a dirt sensor. Such an agent has just two possible percepts: [Dirty] and [Clean]. It can Suck in response to [Dirty]; what should it do in response to [Clean]? Moving Left fails (forever) if it happens to start in square A, and moving Right fails (forever) if it happens to start in square B. Infinite loops are often unavoidable for simple reflex agents operating in partially observable environments.
Escape from infinite loops is possible if the agent can randomize its actions. For example, if the vacuum agent perceives [Clean], it might flip a coin to choose between Left and Right. It is easy to show that the agent will reach the other square in an average of two steps. Then, if that square is dirty, the agent will clean it and the task will be complete. Hence, a randomized simple reflex agent might outperform a deterministic simple reflex agent.
Model-based Reflex Agents
The most effective way to handle partial observability is for the agent to keep track of the part of the world it can’t see now. That is, the agent should maintain some sort of internal state that depends on the percept history and thereby reflects at least some of the unobserved aspects of the current state.
This knowledge about “how the world works”—whether implemented in simple Boolean circuits or in complete scientific theories—is called a model of the world. An agent that uses such a model is called a model-based agent.
Model-based Reflex Agents
Model-based Reflex Agents
Goal-based Agents
Knowing something about the current state of the environment is not always enough to decide what to do.
For example, at a road junction, the taxi can turn left, turn right, or go straight on. The correct decision depends on where the taxi is trying to get to. In other words, as well as a current state description, the agent needs some sort of goal information that describes situations that are desirable—for example, being at the passenger’s destination.
Goal-based Agents
Utility-based Agents
Goals just provide a crude binary distinction between “happy” and “unhappy” states. A more general performance measure should allow a comparison of different world states according to exactly how happy they would make the agent. Because “happy” does not sound very scientific, economists and computer scientists use the term utility instead.
An agent’s utility function is essentially an internalization of the performance measure. If the internal utility function and the external performance measure are in agreement, then an agent that chooses actions to maximize its utility will be rational according to the external performance measure.
a rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes—that is, the utility the agent expects to derive, on average, given the probabilities and utilities of each outcome.
Utility-based Agents
Learning Agents
A learning agent can be divided into four conceptual components. The most important distinction is between the learning element, which is responsible for making improvements, and the performance element, which is responsible for selecting external actions. The learning element uses feedback from the critic on how the agent is doing and determines how the performance element should be modified to do better in the future. The last component of the learning agent is the problem generator. It is responsible for suggesting actions that will lead to new and informative experiences.
Learning Agents