CSBP 301: Artificial Intelligence Artificial Neural Networks

Artificial Neural Networks

• Learning methods using artificial neural networks have been very successful and are often confused with artificial intelligence.
• Computational models are inspired by the human brain.
• Algorithms mimic the brain.
• Massively parallel, distributed system, made up of simple processing units (neurons).
• Synaptic connection strengths among neurons are used to store the acquired knowledge.
• Knowledge is acquired by the network from its environment through a learning process.
• These methods are well suited for signal and image processing, where extensive data are available.

History of Neural Networks

• 1943: Mac Culloch and Pitts defined a formal neuron.
• 1958: Rosenblatt, Widrow, and Hoff developed a model with a learning process called the perceptron.
• 1969: Minsky and Papert identified the limits of perceptrons.
• 1972: Kohonen worked on associative memories.
• 1980s: Rumelhart and McClelland, along with Werbos and Le Cun, introduced the multi-layer perceptron with efficient learning mechanisms like back-propagation of the gradient.
• 1986: David Rumelhart added recurrent neural networks, incorporating the notion of time and memory.
• 1997: Hochreiter and Schmidhuber introduced LSTM (Long Short Term Memory) recurrent neural networks with short and long memory to process sequential data.
• 1998: Convolutional Neural Networks were developed.
• Yoshua Bengio: Born in 1964, a Canadian computer scientist known for his work on artificial neural networks and deep learning.

Biological Model

• Neurons receive signals (electrical impulses) through dendrites and send information through axons.
• Contacts between two neurons (between axon and dendrite) are via synapses.
• The signals do not operate in a linear way; they exhibit a threshold effect.

Artificial Neurons

• A neural net consists of simple processing elements called neurons, units, cells, or nodes.
• Each neuron is connected to other neurons by directed communication links, each with associated weight.
• The weights represent information used by the net to solve a problem.
• Output Y is 1 if at least two of the three inputs are equal to 1.

Network with Hidden Layers

• Artificial Neural Networks can be represented as a weighted directed graph, where artificial neurons form the nodes.
• The association between neuron outputs and neuron inputs can be viewed as directed edges with weights.
• The Artificial Neural Network receives the input signal from the external source as a pattern or image in the form of a vector.
• These inputs are mathematically assigned by the notations $x(n)$ for every $n$ number of inputs.
• Formula for hidden layer calculation: $HL<em>i = \sum</em>{k=1}^{N} w<em>{ki} * x</em>{ki}$

Training Neural Networks

• At the beginning of training, all the weights are selected randomly.
• The method of computing the values of each node is the same for each hidden layer.
• This operation is called forward propagation.
• In order to choose the best weights, an operation of backward propagation should be performed.
• Formula for forward propagation: $HL<em>i = \sum</em>{k=1}^{N} w<em>{ki} * x</em>{ki}$

Backward Propagation

• This operation is performed by computing the difference between the real output and the predicted output, termed the Loss function.
• The Loss function measures the errors across all training layers. Example of squared loss:
• The weights are updated using the Loss function, the previous weight, gradient, and a learning rate.
• The learning rate controls how quickly the model is adapted to the problem.
• Smaller learning rates require more training epochs, whereas larger learning rates result in rapid changes and require fewer training epochs.
• Epoch: is when an entire dataset is passed forward and backward through the neural network.

Activation Function

• The activation function decides whether a neuron should be activated or not by calculating the weighted sum and adding bias to it.
• The purpose of the activation function is to introduce non-linearity into the output of a neuron.
• Components: Input, Weights, Sum, Activation function, Output.
• Output = Activation function (Linear combination of the inputs)

Intelligent Agents

• An agent perceives its environment through sensors and acts upon that environment through actuators.
• Examples: Human, Robot, Thermostat
• Human agent: eyes, ears as sensors; hands, legs as actuators.
• Robotic agent: cameras as sensors; various motors as actuators.
• The definition of “agents” also technically includes calculators or cars, artifacts with very limited to no intelligence. Self-driving cars come closer to what we view as intelligent agents.

Key Terminology

• Percept: Agent’s perceptual inputs at any given instant.
• Percept sequence: Complete history of everything the agent has ever perceived.

Agent Function & Program

• Agent’s behavior is mathematically described by an Agent function: a function mapping any given percept sequence to an action.
• Practically, it is described by an agent program: The real-time implementation.

Vacuum-cleaner world

• Vacuum cleaner agent has a location sensor and a dirt sensor, knowing its location (room A or room B) and whether the room is dirty.
• It can go left, go right, suck, or do nothing.
• A possible performance measure is to maximize the number of clean rooms over a certain period.
• Perception: Clean or Dirty? Where is it?
• Actions: Move left, Move right, suck, do nothing.

Concept of Rationality

• An agent should be able to "do the right thing", based on what it can perceive and the actions it can perform.
• The right action is the one that will cause the agent to be most successful
• Rational agent: One that does the right thing.
• Every entry in the table for the agent function is correct (rational).
• What is correct? The actions that cause the agent to be most successful.
• So we need ways to measure success.

Performance Measure

• An objective function that determines how the agent does successfully.
• E.g., 90% or 30%?
• A general rule: Design performance measures according to what one actually wants in the environment rather than how one thinks the agent should behave.
• E.g., in vacuum-cleaner world, we want the floor clean, no matter how the agent behaves.

Rationality Factors

• What is rational at any given time depends on four things:
  • The performance measure defining the criterion of success.
  • The agent’s prior knowledge of the environment.
  • The actions that the agent can perform.
  • The agent’s percept sequence up to now.

Rational Agent

• For each possible percept sequence, a rational agent should select an action expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.
• E.g., an exam: Maximize marks, based on the questions on the paper & your knowledge.

Rational Agent Example

• Performance measure: Awards one point for each clean square.
• Prior knowledge about the environment:
  • The geography of the environment.
  • Only two squares.
  • The effect of the actions.
• Actions that can perform: Left, Right, Suck and NoOp.
• Percept sequences: Where is the agent? Whether the location contains dirt?
• Under this circumstance, the agent is rational.

Learning

• Learning is the operation of considering the performed actions.
• Does a rational agent depend on only current percept? No, the past percept sequence should also be used. This is called learning.
• After experiencing an episode, the agent should adjust its behaviors to perform better for the same job next time.

Software Agents

• Sometimes, the environment may not be the real world.
• E.g., flight simulator, video games, Internet. They are all artificial but very complex environments.
• Those agents working in these environments are called software agents (softbots) because all parts of the agent are software.

PEAS Representation

• PEAS is a type of model on which an AI agent works upon.
• When we define an AI agent or rational agent, then we can group its properties under PEAS representation model.
• It is made up of four words:
  • P: Performance measure
  • E: Environment
  • A: Actuators
  • S: Sensors
• In designing an agent, the first step must always be to specify the task environment as fully as possible. Here performance measure is the objective for the success of an agent's behavior.

PEAS Example: Self-Driving Cars

• Performance: Safety, Time, Legal Drive, Comfort
• Environment: Roads, other vehicles, road signs, pedestrians
• Actuators: Steering, accelerator, brake, signal, horn
• Sensors: Camera, GPS, speedometer, odometer, accelerometer, sonar.

PEAS Examples

• Medical Diagnose
  • Performance measure: Healthy patient, Minimized cost
  • Environment: Patient, Hospital, Staff
  • Actuators: Tests, Treatments
  • Sensors: Keyboard (Entry of symptoms)
• Vacuum Cleaner
  • Performance measure: Cleanness, Efficiency, Battery life, Security
  • Environment: Room, Table, Wood floor, Carpet, Various obstacles
  • Actuators: Wheels, Brushes, Vacuum Extractor
  • Sensors: Camera, Dirt detection sensor, Cliff sensor, Bump Sensor, Infrared Wall Sensor
• Part-picking Robot
  • Performance measure: Percentage of parts in correct bins.
  • Environment: Conveyor belt with parts, Bins
  • Actuators: Jointed Arms, Hand
  • Sensors: Camera, Joint angle sensors.

Properties of Task Environments

• Environments is everything in the world which surrounds the agent. It could be a physical world / a real world or a virtual one.
• So the environment is where the agent operates.
• The task environment described by PEAS representation
• 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 the environment is effectively and fully observable.
  • If the sensors detect all aspects that are relevant to the choice of action Partially observable.
  • 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.
  • Example: A local dirt sensor of the cleaner cannot tell whether other squares are clean or not.
• Deterministic vs. stochastic
  • If the next state of the environment is completely determined by the current state and the actions executed by the agent, then the environment is deterministic, otherwise, it is Stochastic.
  • Strategic environment: deterministic except for actions of other agents
  • Cleaner and taxi driver are: Stochastic because of some unobservable aspects like noise or unknown.
• Episodic vs. sequential
  • An episode = agent’s single pair of perception & action
  • The quality of the agent’s action does not depend on other episodes. Every episode is independent of each other. Episodic environment is simpler.
  • The agent does not need to think ahead
  • Sequential: Current action may affect all future decisions. Ex. Taxi driving and chess.
• Static vs. dynamic
  • A dynamic environment is always changing over time, E.g., the number of people in the street.
  • While static environment E.g., the destination Semi-dynamic environment is not changed over time but the agent’s performance score does.
• Discrete vs. continuous
  • If there are a limited number of distinct states, clearly defined percepts and actions, the environment is discrete. E.g., Chess game.
  • Continuous: Taxi driving
• Single agent VS. multiagent
  • Playing a crossword puzzle – single agent
  • Chess playing – two agents. Competitive multiagent environment = Chess playing.
  • Cooperative multiagent environment = Automated taxi driver (avoiding collision).
• Known vs. unknown
  • This distinction refers not to the environment itself but to the agent’s (or designer’s) state of knowledge about the environment.
  • In a known environment, the outcomes for all actions are given (example: solitaire card games).
  • If the environment is unknown, the agent will have to learn how it works in order to make good decisions (example: new video game).

Structure of Agents

• The task of AI is to design an agent program which implements the agent function.
• The structure of an intelligent agent is a combination of architecture and agent program.
• It can be viewed as: Agent = Architecture + Agent program
• The main three terms involved in the structure of an AI agent:
  • Architecture: Architecture is machinery that an AI agent executes on.
  • Agent Function: Agent function is used to map a percept to an action.
  • Agent program: Agent program is an implementation of agent function. An agent program executes on the physical architecture to produce function f.
• Agent = architecture + program
  • Architecture = some sort of computing device (sensors + actuators)
  • (Agent) Program = some function that implements the agent mapping = “?”
• Agent programs
  • Input for Agent Program = Only the current percept
  • Input for Agent Function = The entire percept sequence
  • The agent must remember all of them
  • Implement the agent program as a look up table (agent function)
• Skeleton design of an agent program
  • Table-driven agents: the function consists in a lookup table of actions to be taken for every possible state of the environment.
  • If the environment has n variables, each with t possible states, then the table size is $t^n$.
  • Only works for a small number of possible states for the environment.
  • Agent Programs $P$ = the set of possible percepts, $T$ = lifetime of the agent. The total number of percepts it receives.
  • Size of the look up table. Consider playing chess, $P = 10, T = 150 . Will require a table of at least 10^{150} entries: \sum_{t=1}^{T} P^t$
• The key challenge of AI is to find out how to write programs that, to the extent possible, produce rational behavior.
• From a small amount of code rather than a large amount of table entries. E.g., a five-line program of Newton’s Method V.s. huge tables of square roots, sine, cosine, …

Types of Agent Programs

• Simple reflex agents
• Model-based reflex agents
• Goal-based agents
• Utility-based agents

Simple Reflex Agents

• Deciding on the action to take based only on the current perception and not on the history of perceptions.
• It uses just condition-action rules. The rules are like the form “if … then …”
• Efficient but have narrow range of applicability because knowledge sometimes cannot be stated explicitly.
• Work only if the environment is fully observable.
• A Simple Reflex Agent in Nature:
  • RULES: (1) If small moving object, then activate SNAP (2) If large moving object, then activate AVOID and inhibit SNAP ELSE (not moving) then NOOP
  • Action: SNAP or AVOID or NOOP needed for completeness percepts (size, motion)

Model-Based Reflex Agents

• If the world is not fully observable, the agent must remember observations about the parts of the environment it cannot currently observe.
• For the world that is partially observable, the agent has to keep track of an internal state that depends on the percept history, reflecting some of the unobserved aspects.
• E.g., driving a car and changing lane Requiring two types of knowledge:
  • How the world evolves independently of the agent.
  • How the agent’s actions affect the world.

Software Agents

• Example Table Agent With Internal State:
  • If Saw an object ahead, and turned right, and it’s now clear ahead - > Go straight
  • Saw an object Ahead, turned right, and object ahead again -> Hallt

Goal-Based Agents

• The agent has a purpose and the action to be taken depends on the current state and on what it tries to accomplish (the goal).
• In some cases, the goal is easy to achieve.
• In others, it involves planning, sifting through a search space for possible solutions, and developing a strategy.
• The current state of the environment is always not enough. The goal is another issue to achieve.
• Judgment of rationality / correctness Actions chosen -> goals, based on
• The current state
• The current percept
• Conclusion Goal-based agents are less efficient but more flexible.
• Agent -> Different goals -> different tasks
• Search and planning: Two other sub-fields in AI to find out the action sequences to achieve its goal.

Agent Types

• Goal-based Agents Agent keeps track of the world state as well as set of goals it’s trying to achieve: chooses actions that will (eventually) lead to the goal(s).
• More flexible than reflex agents -> may involve search and planning

Utility-Based Agents

• The agent is aware of a utility function that estimates how close the current state is to the agent's goal.
• Goals alone are not enough to generate high-quality behavior.
• E.g. meals in Canteen, good or not ? Many action sequences -> the goals some are better and some worse If the goal means success, then utility means the degree of success (how successful it is)
• It is said state A has higher utility If state A is more preferred than others Utility is therefore a function that maps a state onto a real number = the degree of success.
• Utility has several advantages:
  • When there are conflicting goals, only some of the goals but not all can be achieved. Utility describes the appropriate trade-off.
  • When there are several goals None of them are achieved certainly. Utility provides a way for the decision-making.

Learning Agents

• After an agent is programmed, can it work immediately? No, it still needs teaching.
• In AI, Once an agent is done, we teach it by giving it a set of examples and test it by using another set of examples. We then say the agent learns: A learning agent.
• Four conceptual components:
  • Learning element: Making improvement
  • Performance element: Selecting external actions
  • Critic: Tells the Learning element how well the agent is doing with respect to fixed performance standard. (Feedback from user or examples, good or not?)
  • Problem generator: Suggest actions that will lead to new and informative experiences.

Summary of Agent Types

• (1) Table-driven agents use a percept sequence/action table in memory to find the next action. They are implemented by a (large) lookup table.
• (2) Simple reflex agents are based on condition-action rules, implemented with an appropriate production system. They are stateless devices which do not have memory of past world states.
• (3) Agents with memory - Model-based reflex agents have internal state, which is used to keep track of past states of the world.
• (4) Agents with goals – Goal-based agents are agents that, in addition to state information, have goal information that describes desirable situations. Agents of this kind take future events into consideration.
• (5) Utility-based agents base their decisions on classic axiomatic utility theory in order to act rationally.
• (6) Learning agents they have the ability to improve performance through learning.

Agent Summary

• An agent perceives and acts in an environment, has an architecture, and is implemented by an agent program.
• A rational agent always chooses the action which maximizes its expected performance, given its percept sequence so far.
• An autonomous agent uses its own experience rather than built-in knowledge of the environment by the designer.
• An agent program maps from percept to action and updates its internal state.
• Reflex agents (simple / model-based) respond immediately to percepts.
• Goal-based agents act in order to achieve their goal(s), possible sequence of steps.
• Utility-based agents maximize their own utility function.
• Learning agents improve their performance through learning.
• Representing knowledge is important for successful agent design.
• The most challenging environments are partially observable, stochastic, sequential, dynamic, and continuous, and contain multiple intelligent agents.

Problem Solving by Searching

• In computer science, problem-solving refers to artificial intelligence techniques such as efficient algorithms to find desirable solutions.
• The basic crux of artificial intelligence is to solve problems just like humans.
• In the digitized world, artificial intelligence techniques are widely used to automate systems that can efficiently use resources and time.
• Some of the well-known problems experienced in everyday life are games and puzzles. Using AI techniques, we can solve these problems efficiently.
• In this sense, some of the most common problems resolved by AI are:
  • Travelling Salesman Problem
  • Tower of Hanoi Problem
  • Water-Jug Problem
  • N-Queen Problem
  • Chess
  • Sudoku
  • Crypt-arithmetic Problems
  • Magic Squares
  • Logical Puzzles and so on.

Problem-Solving Techniques

• In artificial intelligence, problems can be solved using searching algorithms, evolutionary computations, knowledge representations, etc.
• Various searching techniques are used to solve a problem. In general, searching is referred to as finding information one needs The process of problem-solving using searching consists of the following steps:
  • Define the problem
  • Analyze the problem
  • Identification of possible solutions
  • Choosing the optimal solution
  • Implementation

Properties of Search Algorithms

• Completeness: A search algorithm is said to be complete when it gives a solution or returns any solution for a given random input.
• Optimality: If a solution found is best (lowest path cost) among all the solutions identified, then that solution is said to be an optimal one.
• Time complexity: The time taken by an algorithm to complete its task is called time complexity. If the algorithm completes a task in a lesser amount of time, then it is an efficient one.
• Space complexity: It is the maximum storage or memory taken by the algorithm at any time while searching.
• These properties are also used to compare the efficiency of the different types of searching algorithms.

Problem-Solving Agent

• A kind of goal-based agent.
• It solves problems by finding sequences of actions that lead to desirable states (goals).
• To solve a problem, the first step is the goal formulation, based on the current situation
• Goal formulation
  • The goal is formulated as a set of world states, in which the goal is satisfied.
  • Reaching from initial state -> goal state Actions are required
  • Actions are the operators causing transitions between world states
  • Actions should be abstract enough at a certain degree, instead of very detailed E.g., turn left VS turn left 30 degree, etc.
• Problem formulation
  • The process of deciding what actions and states to consider
  • E.g., driving A -> B. States: Some places in A & B.
  • Actions: Turn left, Turn right, go straight, accelerate & brake, etc.
• Search for Solution
  • Because there are many ways to achieve the same goal, those ways are together expressed as a tree.
  • Multiple options of unknown value at a point, the agent can examine different possible sequences of actions and choose the best.
  • This process of looking for the best sequence is called search.
  • The best sequence is then a list of actions, called the solution Search algorithm
  • Defined as taking a problem and returns a solution.
  • Once a solution is found, the agent follows the solution and carries out the list of actions – execution phase Design of an agent = “Formulate, search, execute” Functionalities of problem solving agent.

Functionalities of Problem Solving Agent

• Goal Formulation: limiting the objetives
• Problem Formulation: Actions and states
• Search is looking for a sequence of actions: Takes a problem as input and returns a solution
• Execution

Example: Buckets

• Measure 7 liters of water using a 3-liter, a 5-liter, and a 9-liter buckets.
  • Formulate goal: Have 7 liters of water in 9-liter bucket
  • Formulate problem: States: Amount of water in the buckets Operators: Fill bucket from source, empty bucket
  • Find solution: sequence of operators that bring you from current state to the goal state.
  • Solution Step Description

Problem characteristics:

• State-space is defined implicitly. It implicitly represents all the actions that are feasible in each state.
• Only the results of the actions (the successor states) and their costs are returned by the function
• The successor function is a “black box”: its content is unknown
• An arc cost is a positive number measuring the “cost” of performing the action corresponding to the arc, e.g.:
  • 1 in the 8-puzzle example
  • expected time to merge two sub-assemblies
• We will assume that for any given problem the cost c of an arc always verifies: c ">= ε> 0, where ε is a constant