Artificial Intelligence

Why AI needs search: Most AI problems (puzzles, planning, game playing, route finding, theorem proving) have no direct formula for the answer. The agent has a set of states, a set of actions and a goal, and must find a sequence of actions leading from the initial state to a goal state. Since the right sequence is not known in advance, the agent has to explore the state space, trying alternatives and comparing them. Hence problem solving in AI is formulated as search (uninformed or heuristic), and without searching an intelligent agent could not choose among many possible actions.

8-puzzle with hill climbing. The figure is not given, so the standard instance is used (blank shown as _).

Start:

2 8 3
1 6 4
7 _ 5

Goal:

1 2 3
8 _ 4
7 6 5

Heuristic $h(n)$ = number of tiles (not counting the blank) out of place compared with the goal. Hill climbing moves to the neighbour with the lowest $h$ and stops if no neighbour is better.

Step 1. Start has $h=4$ (tiles 2, 8, 1, 6 misplaced). Blank moves:

• Up: 2 8 3 / 1 _ 4 / 7 6 5, $h=3$
• Left: $h=5$
• Right: $h=5$

Best is Up, $h=3$.

Step 2. From 2 8 3 / 1 _ 4 / 7 6 5:

• Up: 2 _ 3 / 1 8 4 / 7 6 5, $h=3$
• Left: 2 8 3 / _ 1 4 / 7 6 5, $h=3$
• Right: 2 8 3 / 1 4 _ / 7 6 5, $h=4$

No neighbour has $h<3$. Simple (strict) hill climbing stops here on a plateau or local optimum, without reaching the goal. This is its main weakness.

With sideways moves allowed (accept equal $h$):

• Take Up: 2 _ 3 / 1 8 4 / 7 6 5, $h=3$
• Blank left: _ 2 3 / 1 8 4 / 7 6 5, $h=2$
• Blank down: 1 2 3 / _ 8 4 / 7 6 5, $h=1$
• Blank right: 1 2 3 / 8 _ 4 / 7 6 5, $h=0$, the goal.

So hill climbing solves it only if sideways moves (or random restarts) are used; otherwise it can get stuck.

Knowledge, representation and reasoning

• Knowledge is the facts, rules, concepts and relationships about a domain that an intelligent system needs to behave intelligently.
• Knowledge representation is the way this knowledge is encoded in a form a computer can store and use, for example propositional and predicate logic, semantic networks, frames, production rules and scripts. A good representation is expressive, efficient and easy to update.
• Reasoning is the process of drawing new conclusions from the represented knowledge, for example by deduction (modus ponens, resolution), induction or abduction.

Turing test: A machine passes the Turing test when a human interrogator, communicating through text with both a machine and a human without seeing them, cannot reliably tell which is the machine (the machine is taken as intelligent if the interrogator's judgement is no better than chance, commonly judged after about five minutes of conversation).

Two examples of constraint satisfaction problems

1. Map colouring: colour the regions of a map so that adjacent regions have different colours. Variables are regions, domain is the set of colours, constraints are that neighbours differ.
2. 8-queens / Sudoku / cryptarithmetic (SEND + MORE = MONEY): place queens so that no two attack each other, with constraints on rows, columns and diagonals.

Why CNF is necessary: Resolution is a single inference rule that works only on clauses, i.e. disjunctions of literals. Converting every sentence into Conjunctive Normal Form (a conjunction of clauses) gives one uniform format, so resolution can be applied mechanically and proof by refutation can be automated. It also removes implications, quantifiers and complex nesting.

FOPL representation

• (a) $\forall x\,(cow(x)\lor pig(x)\lor horse(x)\rightarrow mammal(x))$
• (b) $\forall x\,\forall y\,(horse(x)\land child(y,x)\rightarrow horse(y))$ ($child(y,x)$: y is a child of x)
• (c) $horse(Bluebeard)$
• (d) $father(Bluebeard, Charlie)$
• (e) $\forall x\,\forall y\,(father(x,y)\leftrightarrow child(y,x))$
• (f) $\forall x\,(mammal(x)\rightarrow \exists y\,father(y,x))$

Goal: $mammal(Charlie)$.

Clauses (CNF)

1. $\lnot cow(x)\lor mammal(x)$
2. $\lnot pig(x)\lor mammal(x)$
3. $\lnot horse(x)\lor mammal(x)$
4. $\lnot horse(x)\lor\lnot child(y,x)\lor horse(y)$
5. $horse(Bluebeard)$
6. $father(Bluebeard, Charlie)$
7. $\lnot father(x,y)\lor child(y,x)$
8. $\lnot child(y,x)\lor father(x,y)$
9. $\lnot mammal(x)\lor father(f(x),x)$ (Skolem function $f$)
10. Negated goal: $\lnot mammal(Charlie)$

Resolution proof

• 10 and 3 with $x=Charlie$: $\lnot horse(Charlie)$ (11)
• 6 and 7 with $x=Bluebeard,\ y=Charlie$: $child(Charlie, Bluebeard)$ (12)
• 4 and 12 with $x=Bluebeard,\ y=Charlie$: $\lnot horse(Bluebeard)\lor horse(Charlie)$ (13)
• 13 and 5: $horse(Charlie)$ (14)
• 14 and 11: empty clause (contradiction)

The negated goal leads to a contradiction, so $mammal(Charlie)$ is true: Charlie is a mammal.

A utility-based agent is more general, since a goal can be seen as a utility function with only two values.

Task of an activation function: In a neural network, a neuron computes the weighted sum of its inputs plus bias, $net=\sum w_ix_i+b$. The activation function transforms this value into the neuron's output, $y=f(net)$. Its tasks are to introduce non-linearity (without it, a multi-layer network would reduce to a single linear model) and to limit or decide the output range so that the neuron fires or not.

Types

1. Step (threshold) function: $f(x)=1$ if $x\ge\theta$, else $0$. Used in the perceptron.
2. Sigmoid (logistic): $f(x)=\dfrac{1}{1+e^{-x}}$, output between 0 and 1, used for probabilities.
3. Tanh: $f(x)=\dfrac{e^x-e^{-x}}{e^x+e^{-x}}$, output between $-1$ and $1$, zero-centred.
4. ReLU: $f(x)=\max(0,x)$, fast and widely used in deep networks.
5. Leaky ReLU: $f(x)=x$ for $x>0$, $0.01x$ otherwise.
6. Softmax: converts a vector into probabilities that sum to 1, used in the output layer for multi-class classification.
7. Linear (identity): $f(x)=x$, used for regression outputs.

Dempster-Shafer (D-S) theory is a way of reasoning with uncertainty and incomplete evidence. Instead of assigning probability to single outcomes, it assigns belief mass to subsets of the frame of discernment $\Theta$ (the set of all mutually exclusive hypotheses). Ignorance can be represented, as mass left on $\Theta$ itself rather than being split equally.

• Basic probability assignment (mass) $m$: $m(\emptyset)=0$ and $\sum_{A\subseteq\Theta} m(A)=1$.
• Belief: $Bel(A)=\sum_{B\subseteq A} m(B)$ (lower bound).
• Plausibility: $Pl(A)=1-Bel(\lnot A)$ (upper bound).
• The certainty about $A$ is the interval $[Bel(A),\,Pl(A)]$.
• Dempster's rule of combination merges two independent evidence sources:

$m_{12}(A)=\frac{\sum_{B\cap C=A} m_1(B)\,m_2(C)}{1-K},\qquad K=\sum_{B\cap C=\emptyset} m_1(B)\,m_2(C)$

Example. Let $\Theta=\{flu, cold\}$.

• Evidence 1: $m_1(\{flu\})=0.6$, $m_1(\Theta)=0.4$.
• Evidence 2: $m_2(\{flu\})=0.5$, $m_2(\{cold\})=0.2$, $m_2(\Theta)=0.3$.

Conflict: $K=m_1(flu)\,m_2(cold)=0.6\times0.2=0.12$.

$m_{12}(flu)=\dfrac{0.6\times0.5+0.6\times0.3+0.4\times0.5}{0.88}=\dfrac{0.30+0.18+0.20}{0.88}=\dfrac{0.68}{0.88}\approx0.773$

$m_{12}(cold)=\dfrac{0.4\times0.2}{0.88}=\dfrac{0.08}{0.88}\approx0.091$

$m_{12}(\Theta)=\dfrac{0.4\times0.3}{0.88}=\dfrac{0.12}{0.88}\approx0.136$

So $Bel(flu)=0.773$ and $Pl(flu)=1-Bel(cold)=1-0.091=0.909$. The belief in flu is in the interval $[0.773, 0.909]$, which shows reasoning with certainty and the remaining ignorance.

Expert system: An expert system is an AI program that captures the knowledge of human experts in a specific narrow domain (for example MYCIN for medical diagnosis, DENDRAL for chemistry) and uses it to give advice, make decisions or solve problems at an expert's level, usually with an explanation of its reasoning.

Architecture

1. Knowledge base: stores domain facts and rules (usually IF-THEN production rules), obtained from experts.
2. Inference engine: the reasoning part. It applies rules to the facts using forward chaining (from facts to conclusions) or backward chaining (from a goal back to facts) to derive new knowledge. It also handles conflict resolution.
3. Working memory (database): holds the facts of the current problem and intermediate results.
4. User interface: lets the user enter queries and facts and view results, often in natural language or menus.
5. Explanation facility: explains how a conclusion was reached (HOW) and why a question is being asked (WHY).
6. Knowledge acquisition module: helps the knowledge engineer to add, update and test knowledge from experts.

The user interacts through the interface, the inference engine reads the knowledge base and working memory, and the answer plus explanation are returned.

Purpose: Alpha-beta pruning is an optimisation of the minimax algorithm used in two-player games (chess, tic-tac-toe). Minimax must examine every node of the game tree, which grows exponentially. Alpha-beta pruning gives the same result as minimax but skips (prunes) branches that cannot influence the final decision, so the search is much faster and deeper searches become possible.

How it works: Two values are carried along the search.

• $\alpha$: the best (highest) value found so far for the MAX player along the path, initially $-\infty$.
• $\beta$: the best (lowest) value found so far for the MIN player, initially $+\infty$.

A branch is pruned whenever $\alpha\ge\beta$, because the opponent would never let the game reach that position.

Example: MAX node with two MIN children. The first MIN child has leaves 3 and 5, so its value is 3, giving $\alpha=3$ at MAX. In the second MIN child the first leaf is 2. MIN can get at most 2, which is less than $\alpha=3$, so MAX will never choose this branch; the remaining leaves of that child are pruned.

With best move ordering the number of nodes examined drops from $O(b^d)$ to about $O(b^{d/2})$, where $b$ is the branching factor and $d$ is the depth.

The question leaves the representation scheme open. A frame/script style (like Prolog facts and rules) is used here for a shopping mall, "My Mall".

Scenario: A customer enters the mall, picks products from shops, pays at the counter and receives a bill. Members get a discount.

Concepts as facts (Prolog)

% shops and the products they sell
shop(clothes_hub).  shop(fresh_mart).  shop(tech_zone).
sells(clothes_hub, shirt, 1500).
sells(fresh_mart, rice, 120).
sells(tech_zone, earphones, 2000).

% customers
customer(ram).  customer(sita).
member(ram).

% wants to buy
buys(ram, shirt).
buys(sita, rice).

Rules

% price with discount: members get 10 percent off
price_for(C, Item, P) :-
    sells(_, Item, Base),
    ( member(C) -> P is Base * 0.9 ; P = Base ).

% total bill for a customer's purchases
bill(C, Item, Amount) :-
    buys(C, Item),
    price_for(C, Item, Amount).

Queries

?- bill(ram, shirt, A).    % A = 1350.0   (Rs 1500 less 10 percent)
?- bill(sita, rice, A).    % A = 120      (not a member)

Script (sequence of events): enter mall, browse shops, select item, go to the billing counter, pay (cash or card), receive the bill, exit. This is also represented as a frame with slots: customer, item, shop, price, payment_mode.

Deterministic environment: the next state of the environment is completely determined by the current state and the action the agent executes. There is no uncertainty, e.g. chess, 8-puzzle.

Non-deterministic (stochastic) environment: the same action in the same state can lead to different outcomes, so the agent must handle uncertainty, e.g. taxi driving, poker, robot moving on a slippery floor.

BFS vs DFS

Here $b$ is the branching factor, $d$ the depth of the shallowest goal and $m$ the maximum depth.

Ambiguity means a piece of language can be interpreted in more than one way. NLP must resolve it at each level.

1. Lexical ambiguity: a single word has several meanings or parts of speech. "Bank" can be a river bank or a financial bank; "book" can be a noun or a verb.
2. Syntactic (structural) ambiguity: a sentence has more than one valid parse tree. "I saw the man with a telescope" can mean I used the telescope, or the man had it.
3. Semantic ambiguity: the sentence is syntactically fine but its meaning is unclear, often from word-sense or quantifier scope. "Every student read a book" may mean one common book or a different book each.
4. Referential (anaphoric) ambiguity: a pronoun or phrase can refer to several earlier entities. "Ram told Hari that he won" - who is "he"?
5. Pragmatic ambiguity: the intended meaning depends on context or speaker intention. "Can you pass the salt?" is a request, not a question about ability.
6. Discourse ambiguity: the interpretation of a sentence depends on the preceding sentences.

Resolution uses part-of-speech tagging, word-sense disambiguation, probabilistic parsing, context and world knowledge.

Learning by analogy is a form of learning in which a new problem is solved by recognising its similarity to a problem already solved, and transferring the known solution (or knowledge) to the new situation, with suitable adaptation.

Steps

1. Retrieve a similar past case (source) from memory.
2. Find the mapping between the source and the target problem.
3. Transfer the source's solution or knowledge to the target.
4. Adapt it to the differences, and test it.
5. Store the new solved case for future use.

Example: a student who knows that water flowing through a pipe depends on pressure difference and pipe resistance learns electric current. By analogy, water pressure maps to voltage, flow rate to current, and pipe resistance to electrical resistance, so $I = V/R$ is understood as the analogue of flow $=$ pressure$/$resistance. Another example is a doctor diagnosing a new patient from a similar earlier case.

It is the basis of case-based reasoning, and its quality depends on how good the similarity measure and mapping are.

Turing Test: proposed by Alan Turing (1950). A human interrogator asks written questions to a hidden human and a hidden machine. If the interrogator cannot reliably tell which is the machine, the machine passes.

Capabilities a machine needs

1. Natural language processing to communicate in a human language.
2. Knowledge representation to store what it knows or hears.
3. Automated reasoning to use the stored knowledge to answer questions and draw new conclusions.
4. Machine learning to adapt to new circumstances and detect patterns.

The Total Turing Test adds computer vision and robotics for perceiving and manipulating objects.

Ambiguities at each NLP step

Each is resolved using context, probabilities and world knowledge.

Agent: anything that perceives its environment through sensors and acts upon it through actuators. A human has eyes and ears as sensors and hands and legs as actuators; a robot has cameras and motors; a software agent has keystrokes or packets as input and screen output or messages as actions. An agent maps its percept history to an action: $f: P^* \rightarrow A$.

PEAS is the task-environment description of an agent:

• Performance measure: how success is judged.
• Environment: the world the agent operates in.
• Actuators: the means of acting.
• Sensors: the means of perceiving.

Example, automated taxi:

Types of environment

1. Fully vs partially observable: sensors give the complete state or not. Chess is fully observable; poker and taxi driving are partially observable.
2. Deterministic vs stochastic: the next state is fully determined by the current state and action or not. Chess is deterministic; taxi driving is stochastic.
3. Episodic vs sequential: in episodic environments each decision is independent (image classification); in sequential ones the current action affects future ones (chess, taxi).
4. Static vs dynamic: whether the environment changes while the agent deliberates. Crossword is static; taxi driving is dynamic.
5. Discrete vs continuous: finite number of states and actions (chess) or continuous values (taxi speed, position).
6. Single vs multi-agent: crossword is single-agent; chess is competitive multi-agent; taxi driving is cooperative/competitive multi-agent.
7. Known vs unknown: whether the rules of the environment are known to the agent.

The hardest case is partially observable, stochastic, sequential, dynamic, continuous and multi-agent, such as taxi driving.

Depth Limited Search (DLS)

DFS can go down an infinite or very deep branch and never return, so it is incomplete. DLS runs DFS but treats nodes at a predefined depth limit $l$ as if they had no successors. Hence it never goes deeper than $l$, so it always terminates, and memory stays $O(bl)$.

It returns three outcomes: a solution, failure (no solution at all), or cutoff (no solution within limit $l$).

Limitations

• Incomplete if the shallowest goal is deeper than $l$ ($l < d$).
• Not optimal if $l > d$, since it may return a deeper solution first.
• Choosing a good $l$ needs knowledge of the problem (e.g. the diameter of the state space). A bad choice gives failure or wasted time.
• Time is $O(b^l)$.

Iterative deepening search removes the need to choose $l$ by trying $l=0,1,2,\dots$.

AO* search on multiplying three matrices

AO* works on an AND-OR graph: an OR arc gives alternative ways to solve a node, and an AND arc means all its sub-problems must be solved. Matrix chain multiplication $A \times B \times C$ is the example. The problem is the root. It can be solved by two OR alternatives:

• $(AB)C$: AND of sub-problems $\{AB,\ (AB)C\}$
• $A(BC)$: AND of sub-problems $\{BC,\ A(BC)\}$

Let $A$ be $10\times 30$, $B$ be $30\times 5$, $C$ be $5\times 60$. The cost of multiplying a $p\times q$ matrix with a $q\times r$ matrix is $pqr$.

• $(AB)C$: $AB$ costs $10\cdot30\cdot5 = 1500$; then $(10\times5)(5\times60)$ costs $10\cdot5\cdot60 = 3000$. Total $=4500$.
• $A(BC)$: $BC$ costs $30\cdot5\cdot60 = 9000$; then $(10\times30)(30\times60)$ costs $10\cdot30\cdot60=18000$. Total $=27000$.

Steps of AO*:

1. Start with the root and expand it, giving the two AND arcs with heuristic estimates for each unsolved child.
2. Compute each arc's cost as the sum of its children's costs plus the arc cost, and mark the cheapest arc as the current best.
3. Expand an unsolved leaf on the best path, recompute costs, and propagate revised costs back up to the root.
4. Repeat until the root is labelled solved.

The best solution graph is the $(AB)C$ arc with cost $4500$, so the order of multiplication is $(A\times B)\times C$.

An expert system is a program that emulates the decision-making of a human expert in a narrow domain (e.g. MYCIN for diagnosis, DENDRAL for chemistry).

Architecture

1. Knowledge base: domain facts and heuristic rules (usually IF-THEN) obtained from experts.
2. Inference engine: the reasoning part. It applies the rules to the facts using forward chaining (data-driven) or backward chaining (goal-driven) to derive conclusions, and decides the order in which rules fire.
3. Working memory (fact base): the current facts of the case being solved plus conclusions drawn so far.
4. User interface: lets the user enter queries and facts and see results in a natural, convenient form.
5. Explanation facility: explains why a question is asked and how a conclusion was reached, which builds trust.
6. Knowledge acquisition module: helps the knowledge engineer to add, edit and validate knowledge from experts.

Flow: the user enters facts through the interface, the inference engine matches them against the knowledge base, updates working memory, and returns a conclusion with an explanation.

A genetic algorithm (GA) is a search and optimisation technique inspired by natural selection. It evolves a population of candidate solutions towards better ones.

Working

1. Initialisation: create a random population of individuals (chromosomes), each encoding a solution as a bit string or similar.
2. Fitness evaluation: compute a fitness value for every chromosome using an objective function.
3. Selection: choose fitter individuals as parents (roulette wheel, tournament, rank selection).
4. Crossover: combine two parents at a crossover point to make offspring. For example $1101|001$ and $0110|110$ give $1101110$ and $0110001$.
5. Mutation: randomly flip a few bits with small probability to maintain diversity and escape local optima.
6. Replacement: form the new generation from offspring (and possibly the best old individuals, called elitism).
7. Termination: repeat steps 2-6 until a satisfactory fitness is reached or the maximum number of generations is done. The best chromosome is the answer.

GAs need no gradient information and work on complex search spaces, but they are slow and give no guarantee of the global optimum.

Neural networks are classified by structure and learning style.

1. Single-layer feed-forward network (perceptron): inputs connect directly to output neurons. It can solve only linearly separable problems such as AND and OR.
2. Multilayer feed-forward network (MLP): has one or more hidden layers between input and output, and signals flow in one direction only. With back-propagation it can learn non-linear functions such as XOR.
3. Recurrent (feedback) network: contains feedback connections, so outputs are fed back as inputs and the network has memory. Examples are Hopfield networks, Elman networks and LSTM, used for sequences and associative memory.
4. Radial Basis Function network: hidden units use radial (Gaussian) functions; used for function approximation and classification.
5. Self-organising map (Kohonen): unsupervised, competitive learning that clusters input data onto a low-dimensional map.
6. Convolutional neural network: uses convolution and pooling layers for images.

By learning method: supervised, unsupervised and reinforcement networks.

Machine learning (ML) is the branch of AI in which a computer improves its performance on a task from experience (data) without being explicitly programmed. Mitchell's definition: a program learns from experience $E$ with respect to task $T$ and performance measure $P$ if its performance on $T$, measured by $P$, improves with $E$. Types are supervised, unsupervised and reinforcement learning, e.g. spam filtering, house price prediction.

NLU (Natural Language Understanding): the part of NLP that converts human language into a machine-usable meaning representation. It involves lexical, syntactic and semantic analysis, resolving ambiguity, and extracting intent and entities. Example: from "Book a flight to Pokhara tomorrow" it extracts intent = book flight, destination = Pokhara, date = tomorrow.

NLG (Natural Language Generation): the part of NLP that produces natural-language text from structured data or an internal representation. Stages: content determination, document structuring, sentence aggregation, lexicalisation, and surface realisation. Example: generating a weather report "Tomorrow will be sunny with a high of 25 degrees" from numerical forecast data.

NLU maps text to meaning; NLG maps meaning to text. A chatbot uses both.

Forward chaining is data-driven reasoning: start with the known facts, fire rules whose conditions are satisfied, add new facts, and continue until the goal is derived or no rule applies.

Backward chaining is goal-driven reasoning: start with the goal (hypothesis), find rules that conclude it, and treat their conditions as sub-goals to be proved, recursively, until they match known facts.

Example Rules: R1: $A \wedge B \rightarrow C$; R2: $C \rightarrow D$; R3: $D \rightarrow E$. Facts: $A, B$. Goal: $E$.

• Forward: $A,B$ fire R1, giving $C$; $C$ fires R2, giving $D$; $D$ fires R3, giving $E$. Goal reached.
• Backward: to prove $E$ use R3, so prove $D$; use R2, so prove $C$; use R1, so prove $A$ and $B$; both are known facts. Hence $E$ is true.

Game: a game is a multi-agent (usually competitive) environment with a fixed set of rules in which players take turns choosing actions, and each outcome gives a payoff. It is formally defined by the initial state, the players, the legal actions in each state, a transition model, a terminal test, and a utility function (e.g. $+1$ win, $0$ draw, $-1$ loss). Examples: chess, tic-tac-toe.

State space representation: Water jug problem (4-litre jug and 3-litre jug, no markings, a pump; get exactly 2 litres in the 4-litre jug).

• State: $(x, y)$ with $x$ litres in the 4-litre jug, $y$ in the 3-litre jug; $0\le x\le4$, $0\le y\le3$.
• Initial state: $(0,0)$. Goal state: $(2, n)$ for any $n$.
• Operators:
  • Fill the 4-litre jug: $(x,y)\to(4,y)$ if $x<4$
  • Fill the 3-litre jug: $(x,y)\to(x,3)$ if $y<3$
  • Empty either jug: $(x,y)\to(0,y)$ or $(x,0)$
  • Pour 3-litre into 4-litre until full or empty: $(x,y)\to(x+y,0)$ if $x+y\le4$, else $(4,\,y-(4-x))$
  • Pour 4-litre into 3-litre similarly.
• A solution path: $(0,0)\to(0,3)\to(3,0)\to(3,3)\to(4,2)\to(0,2)\to(2,0)$.

The goal $(2,0)$ is reached in 6 moves.

A semantic network is a graph-based knowledge representation: nodes are concepts or objects and labelled arcs are relations (commonly is-a and has/eats).

Statements:

1. Plants are living things (or: Animals and plants are living things).
2. A rose is a plant.
3. A carnivore is an animal that eats animals.
4. A tiger is a carnivore.
5. Animals eat plants or other animals (herbivores eat plants).

Network:

              Living Thing
              ^          ^
          is-a|          |is-a
          Animal        Plant
          ^   ^            ^
      is-a|   |eats        |is-a
  Carnivore ----> Animal  Rose
      ^
  is-a|
    Tiger

Arcs: Animal -is-a-> Living Thing; Plant -is-a-> Living Thing; Rose -is-a-> Plant; Carnivore -is-a-> Animal; Carnivore -eats-> Animal; Tiger -is-a-> Carnivore.

Inheritance: a Tiger inherits all properties of Carnivore, Animal and Living Thing, so we can infer "a tiger eats animals" and "a tiger is a living thing" without storing them explicitly.

A belief network (Bayesian network) is a directed acyclic graph (DAG) that represents probabilistic dependencies among random variables.

• Each node is a random variable.
• Each directed edge $X\rightarrow Y$ means $X$ directly influences $Y$ ($X$ is a parent of $Y$).
• Each node has a conditional probability table (CPT) $P(X_i \mid \text{Parents}(X_i))$.

The joint distribution factorises as

$P(X_1,\dots,X_n)=\prod_{i=1}^{n}P(X_i\mid \text{Parents}(X_i))$

Example (alarm network): Burglary (B) and Earthquake (E) cause Alarm (A); Alarm causes JohnCalls (J).

Let $P(B)=0.001$, $P(E)=0.002$, $P(A\mid B,E)=0.95$, $P(A\mid B,\neg E)=0.94$, $P(A\mid \neg B,E)=0.29$, $P(A\mid \neg B,\neg E)=0.001$, $P(J\mid A)=0.90$, $P(J\mid \neg A)=0.05$.

Probability that John calls, the alarm sounds, with a burglary but no earthquake:

$P(J,A,B,\neg E)=P(B)\,P(\neg E)\,P(A\mid B,\neg E)\,P(J\mid A)=0.001\times0.998\times0.94\times0.90\approx 0.000844$

Belief networks allow inference under uncertainty, e.g. computing $P(B\mid J)$ via Bayes' rule.

Hill climbing is a local search algorithm that repeatedly moves to the neighbouring state with the best (highest) heuristic value, and stops when no neighbour is better than the current state. It is like climbing a hill in fog, looking only at the immediate surroundings.

Algorithm (steepest-ascent)

1. Start with an initial state as current.
2. Generate all successors of the current state and pick the best one.
3. If it is better than the current state, make it current and repeat; otherwise stop and return the current state.

It uses very little memory (only the current state) and no backtracking.

Limitations

1. Local maxima: a peak higher than its neighbours but lower than the global maximum; the search gets stuck.
2. Plateau: a flat region where all neighbours have equal value, so there is no direction to move.
3. Ridges: a sequence of local maxima that are hard to climb since the needed move is not a single step.
4. It is neither complete nor optimal.

Remedies: random restart, simulated annealing, sideways moves, stochastic hill climbing.

Issues in knowledge representation

1. Choice of attributes: which attributes are important enough to represent (e.g. instance and isa), and whether they are general enough to support inheritance.
2. Relationships between attributes: inverses, existence in an isa hierarchy, techniques for reasoning about values, and single-valued attributes.
3. Granularity: the level of detail at which knowledge is stored - primitives or high-level facts.
4. Representing sets of objects: properties of a set as a whole versus properties of its members.
5. Finding the right structure: selecting the appropriate stored structure when it is needed.
6. Also: incompleteness, uncertainty, inconsistency, and the trade-off between expressiveness and efficiency.

Resolution proof

Knowledge base in predicate logic:

1. $Eats(Ava, Apple)$
2. $Eats(Ava, Watermelon)$
3. $Loves(Ava, Apple)$
4. $Loves(Ava, Watermelon)$
5. $\forall x\,\forall y\;[Eats(y,x)\wedge Loves(y,x)\rightarrow Fruit(x)]$ (anything eaten by anybody and loved so much is a fruit)
6. $\forall x\,\forall y\;[Loves(y,x)\rightarrow Likes(y,x)]$

Clauses (CNF):

• C1: $Eats(Ava,Apple)$
• C2: $Eats(Ava,Watermelon)$
• C3: $Loves(Ava,Apple)$
• C4: $Loves(Ava,Watermelon)$
• C5: $\neg Eats(y,x)\vee\neg Loves(y,x)\vee Fruit(x)$
• C6: $\neg Loves(y,x)\vee Likes(y,x)$

(a) Ava likes watermelon. Negated goal: $\neg Likes(Ava,Watermelon)$. Resolve with C6 using $\{y/Ava,\ x/Watermelon\}$ to get $\neg Loves(Ava,Watermelon)$. Resolve with C4 to get the empty clause. Hence proved.

(b) Apple and watermelon are fruits. Negated goal: $\neg Fruit(Apple)\vee\neg Fruit(Watermelon)$.

• Resolve with C5 using $\{x/Apple,\ y/Ava\}$: $\neg Eats(Ava,Apple)\vee\neg Loves(Ava,Apple)\vee\neg Fruit(Watermelon)$
• With C1 and then C3: $\neg Fruit(Watermelon)$
• With C5 using $\{x/Watermelon,\ y/Ava\}$: $\neg Eats(Ava,Watermelon)\vee\neg Loves(Ava,Watermelon)$
• With C2 and then C4: empty clause. Hence both are fruits.

(c) Ava eats watermelon and loves it so much. Negated goal: $\neg Eats(Ava,Watermelon)\vee\neg Loves(Ava,Watermelon)$. Resolving with C2 gives $\neg Loves(Ava,Watermelon)$, and with C4 gives the empty clause. Proved.

(d) Anything eaten by anybody and loved so much is a fruit. This is the general rule C5 itself. It is consistent with the facts: both items Ava eats and loves (apple, watermelon) are derived to be fruits in (b) by instantiating it with unification.

Evaluating a search algorithm uses four criteria:

1. Completeness: does it always find a solution if one exists?
2. Optimality: does it find the least-cost solution?
3. Time complexity: the number of nodes generated.
4. Space complexity: the maximum number of nodes held in memory.

Complexity is expressed with $b$ (branching factor), $d$ (depth of shallowest goal) and $m$ (maximum depth).

Constraint satisfaction problems (CSPs): problems defined by

• a set of variables $X=\{X_1,\dots,X_n\}$,
• a domain $D_i$ of allowed values for each variable,
• a set of constraints specifying allowed combinations of values.

A solution is a complete assignment that satisfies all constraints. Examples: map colouring, N-queens, Sudoku, scheduling. They are solved by backtracking search with forward checking, arc consistency and heuristics like minimum remaining values.

Greedy Best-First vs A*

Mathematical model of a neuron

A neuron receives inputs $x_1,\dots,x_n$ with weights $w_1,\dots,w_n$ and a bias $b$. It computes the net input and applies an activation function $f$:

$net=\sum_{i=1}^{n} w_i x_i + b,\qquad y=f(net)$

Common choices of $f$: step, sigmoid $f(z)=\dfrac{1}{1+e^{-z}}$, tanh, ReLU.

Learning rule vs learning rate

• A learning rule is the formula or procedure by which the weights are updated, e.g. the Hebbian rule $\Delta w_i=\eta x_i y$, the perceptron rule $\Delta w_i=\eta(t-y)x_i$, the delta rule, or back-propagation.
• The learning rate $\eta$ is a small positive constant inside that rule that scales the size of each weight update. Too large causes oscillation or divergence; too small makes learning slow.

Back-propagation

It trains a multilayer feed-forward network by gradient descent on the error $E=\tfrac12\sum_k (t_k-y_k)^2$.

1. Initialise weights with small random values.
2. Forward pass: present an input, compute hidden outputs and then output $y_k$.
3. Error: compute $t_k-y_k$ at the output.
4. Backward pass: for sigmoid units,
   • output layer: $\delta_k=(t_k-y_k)\,y_k(1-y_k)$
   • hidden layer: $\delta_j=h_j(1-h_j)\sum_k \delta_k w_{jk}$
5. Update weights: $\Delta w_{ij}=\eta\,\delta_j\,x_i$, $w_{ij}\leftarrow w_{ij}+\Delta w_{ij}$.
6. Repeat over all training patterns (epochs) until the error is below a threshold.

The error is propagated backward from the output layer, layer by layer, using the chain rule, so every weight gets its share of the gradient.

Reinforcement learning (RL) is learning by interaction: an agent takes actions in an environment, receives a numerical reward (positive feedback) or punishment (negative reward), and learns a policy that maximises the cumulative reward.

Role of reward and punishment

• Reward reinforces the action that led to it, making it more likely to be chosen again in that state.
• Punishment discourages the action that led to it.
• They are the only teaching signal: there is no labelled correct answer, so the agent learns through trial and error.
• They define the goal. The agent maximises the expected discounted return $G_t=\sum_{k=0}^{\infty}\gamma^k r_{t+k+1}$, $0\le\gamma\le1$.
• Delayed rewards force the agent to balance short-term and long-term gains, and exploration against exploitation.

Example: a robot in a maze. It gets $+10$ on reaching the exit, $-10$ for hitting a wall or trap, and $-1$ per step. Early on it moves randomly. Over many episodes, Q-learning updates

$Q(s,a)\leftarrow Q(s,a)+\alpha\big[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\big]$

so actions leading to the exit gain high values, wall-hitting actions get low values, and the robot learns the shortest safe path. Other examples: game playing (AlphaGo), training a dog with treats.

Conceptual dependency (CD) represents the meaning of a sentence using primitive acts (e.g. ATRANS = transfer of possession, PTRANS = transfer of physical location, PROPEL = application of force, MOVE = move a body part, INGEST, EXPEL, MTRANS = transfer of mental information), with conceptual cases: actor, object, recipient, direction, instrument.

(a) He opened the door. (Door opened by moving the hand to push it.)

$He \Leftrightarrow PROPEL \xleftarrow{o} door \xleftarrow{R}{\scriptstyle\text{from closed to open}}$

• Actor: He; act: PROPEL (applies force to the door; instrument: he MOVEs his hand to the door)
• Object: door
• Result: door's state changes, $door$ (position = closed) $\Rightarrow$ $door$ (position = open)
• Tense: past.

(b) Ram gave rose to Sita.

$Ram \Leftrightarrow ATRANS \xleftarrow{o} rose \xleftarrow{R}_{\;Ram}^{\;Sita}$

• Actor: Ram; act: ATRANS (transfer of possession)
• Object: rose
• Direction: from Ram (donor) to Sita (recipient)
• Tense: past.

(c) She is crying.

$She \Leftrightarrow EXPEL \xleftarrow{o} tears \xleftarrow{D}{}_{\;eyes}^{\;She}$

• Actor: She; act: EXPEL (tears expelled from her eyes), conceptually also showing the state $She$ (sad) as the cause
• Object: tears
• Tense: present (continuing).

Here $b$ is the branching factor, $d$ the depth of the shallowest goal and $m$ the maximum depth. For a tree with root A, children B, C, and B's children D, E: BFS visits A, B, C, D, E; DFS visits A, B, D, E, C.

Rational agent: an agent that, for each possible percept sequence, selects an action expected to maximise its performance measure, given the evidence from the percept sequence and its built-in knowledge. Rationality depends on the performance measure, prior knowledge, available actions and the percept sequence so far. Rational does not mean omniscient or perfect, only doing the best it can with what it knows.

Applications of AI

• Healthcare: diagnosis, medical imaging, drug discovery
• Robotics and automation: industrial robots, drones
• Natural language processing: machine translation, chatbots, voice assistants
• Computer vision: face recognition, object detection, self-driving cars
• Expert systems: finance, fault diagnosis
• Games: chess, Go
• Education: intelligent tutoring, personalised learning
• Banking and e-commerce: fraud detection, recommendation systems
• Agriculture: crop monitoring, yield prediction

Unification is the process of finding a substitution $\theta$ that makes two logical expressions identical. $Unify(p,q)=\theta$ such that $SUBST(\theta,p)=SUBST(\theta,q)$.

Example: $Knows(John, x)$ and $Knows(John, Jane)$ unify with $\theta=\{x/Jane\}$. $Knows(John,x)$ and $Knows(y, Mother(y))$ unify with $\theta=\{y/John,\ x/Mother(John)\}$. $Knows(John,x)$ and $Knows(x,Elizabeth)$ fail, because $x$ cannot be both John and Elizabeth (this can be fixed by standardising variables apart).

Rules: a variable can be bound to a term; constants must match exactly; function symbols must match with unifiable arguments; a variable cannot be bound to a term containing itself (occurs check). The unifier returned should be the most general unifier (MGU).

Lifting means extending inference rules from propositional logic to first-order logic so that reasoning works directly with variables instead of instantiating all possible ground terms. Generalised Modus Ponens is the lifted rule:

$\frac{p_1',\dots,p_n',\ (p_1\wedge\dots\wedge p_n\Rightarrow q)}{SUBST(\theta,q)}\quad\text{where } SUBST(\theta,p_i')=SUBST(\theta,p_i)$

Example: given $King(John)$, $Greedy(John)$ and $King(x)\wedge Greedy(x)\Rightarrow Evil(x)$, unification finds $\theta=\{x/John\}$ and concludes $Evil(John)$ in a single step, with no need to generate all instances. Lifting plus unification makes first-order inference (resolution, forward and backward chaining) efficient.

Structure: simple reflex: Sensors $\rightarrow$ condition-action rules $\rightarrow$ Actuators. Model-based: Sensors $\rightarrow$ update state (using world model) $\rightarrow$ rules $\rightarrow$ Actuators.

A script is a structured knowledge representation for a stereotyped sequence of events in a particular context, proposed by Schank and Abelson. It lets a system fill in unstated details and answer questions about typical situations such as eating at a restaurant, visiting a doctor, or attending a lecture.

Components

• Entry conditions: conditions that must hold for the script to be invoked (the customer is hungry and has money).
• Roles: the participants (customer, waiter, cook, cashier).
• Props: objects used (table, menu, food, bill).
• Track: a variant of the script (fast food, restaurant).
• Scenes: the ordered sequence of events (entering, ordering, eating, exiting).
• Results: conditions true after the script (customer is not hungry, has less money, owner has more money).

Example: restaurant script Scene 1 Entering: customer enters, looks for a table, sits. Scene 2 Ordering: gets menu, calls waiter, orders. Scene 3 Eating: cook prepares, waiter serves, customer eats. Scene 4 Exiting: waiter brings bill, customer pays, leaves.

Use in knowledge representation: Given "Ram went to a restaurant, ordered a pizza and left a tip", a system using the script infers that Ram sat down, was served, ate it and paid, though none of this is stated. It supports story understanding, question answering, and filling in missing information. Its limitation is that it is rigid and handles unusual situations poorly.

NLP converts human language into machine-usable form and back through these steps:

1. Lexical analysis (morphological): divide the text into paragraphs, sentences and words (tokenisation), identify word structure (root, prefix, suffix), and assign parts of speech.
2. Syntactic analysis (parsing): check grammar and build a parse tree showing how words form phrases and sentences, using a grammar. "Ram eats rice" is parsed as S $\rightarrow$ NP VP. Ungrammatical sentences like "Rice Ram the eats" are rejected.
3. Semantic analysis: assign meaning to the structure, mapping the parse into a context-free meaning representation (logical form). "Hot ice-cream" is semantically anomalous.
4. Discourse integration: the meaning of a sentence depends on previous sentences, and affects later ones. It resolves pronouns: "Ram went to the market. He bought apples."
5. Pragmatic analysis: interpret the sentence in terms of the real-world context and speaker intention. "Do you know the time?" is a request to tell the time.

Each step must resolve ambiguity. A typical flow is: input text $\rightarrow$ lexical $\rightarrow$ syntactic $\rightarrow$ semantic $\rightarrow$ discourse $\rightarrow$ pragmatic $\rightarrow$ meaning.

An expert system emulates a human expert in a narrow domain. Its components are:

1. Knowledge base: domain facts and rules (typically IF-THEN production rules, frames or semantic nets) gathered from human experts.
2. Inference engine: the reasoning mechanism. It matches facts against rules and derives conclusions by forward chaining (data-driven) or backward chaining (goal-driven), with a conflict-resolution strategy to choose which rule fires.
3. Working memory: stores the facts about the current problem and intermediate conclusions.
4. User interface: the means for the user to input data and receive advice, usually through questions, menus or natural language.
5. Explanation subsystem: justifies the reasoning, answering "why do you ask this?" and "how did you reach this conclusion?".
6. Knowledge acquisition subsystem: tool for the knowledge engineer to elicit, enter and update expert knowledge.

People involved: the domain expert, the knowledge engineer and the end user. Examples: MYCIN (medical), DENDRAL (chemistry), XCON (computer configuration).

Problem formulation in state space representation

A problem is formulated by defining:

1. State space: the set of all states reachable from the initial state by any sequence of actions.
2. Initial state: where the agent starts.
3. Actions/operators: the legal moves in each state.
4. Transition model: the resulting state of applying an action.
5. Goal test: whether a state is a goal.
6. Path cost: a numeric cost for each path (sum of step costs).

A solution is a path from the initial state to a goal state.

State space with heuristics

Start $S$, goal $G$. Edges carry actual costs; each node carries a heuristic $h$ (estimated cost to $G$).

Greedy Best-First Search uses $f(n)=h(n)$ and always expands the open node with the smallest $h$.

1. Open = {S}. Expand S: A ($h=7$), B ($h=4$).
2. Smallest is B (4). Expand B: D (3), E (2). Open = {A 7, D 3, E 2}.
3. Smallest is E (2). Expand E: G (0).
4. Pick G, the goal.

Path found: $S\rightarrow B\rightarrow E\rightarrow G$ with actual cost $3+6+3=12$.

The path $S\rightarrow B\rightarrow D\rightarrow G$ costs $3+3+5=11$, which is cheaper, so greedy best-first is fast but not optimal.

Unification finds a substitution $\theta$ that makes two predicate-logic expressions identical, e.g. $Knows(John,x)$ and $Knows(y,Mother(y))$ unify with $\theta=\{y/John,\ x/Mother(John)\}$. The most general unifier (MGU) is used, and a variable cannot be bound to a term containing itself (occurs check).

Lifting means using inference rules directly on first-order sentences with variables, instead of converting to propositional logic by instantiating with every ground term. Generalised Modus Ponens uses unification to apply a rule: from $King(John)$, $Greedy(John)$ and $King(x)\wedge Greedy(x)\Rightarrow Evil(x)$ with $\theta=\{x/John\}$ we infer $Evil(John)$ at once.

Knowledge base (FOL) for:

1. Every student is smart.
2. Smart people are intelligent.
3. Ram is a student.
4. Anyone who is intelligent passes the exam (or: Ram is not a fool).

Using predicates $Student(x)$, $Smart(x)$, $Intelligent(x)$, $Passes(x)$:

1. $\forall x\;[Student(x)\rightarrow Smart(x)]$
2. $\forall x\;[Smart(x)\rightarrow Intelligent(x)]$
3. $Student(Ram)$
4. $\forall x\;[Intelligent(x)\rightarrow Passes(x)]$

Conversion to CNF

Eliminate implication ($P\rightarrow Q\equiv\neg P\vee Q$). All variables are universally quantified, so drop the quantifiers after standardising; there are no existentials, so no Skolemisation is needed.

1. $\neg Student(x)\vee Smart(x)$
2. $\neg Smart(y)\vee Intelligent(y)$
3. $Student(Ram)$
4. $\neg Intelligent(z)\vee Passes(z)$

Check: resolving 3 with 1 ($x/Ram$) gives $Smart(Ram)$; with 2 gives $Intelligent(Ram)$; with 4 gives $Passes(Ram)$.

Learning rule: the mathematical formula or procedure that specifies how the weights of a neural network are changed in response to inputs and (target) outputs, i.e. $w_{new}=w_{old}+\Delta w$. Examples: Hebbian rule, perceptron rule, delta rule, back-propagation.

Training an ANN by back-propagation

Back-propagation trains a multilayer feed-forward network by gradient descent on the squared error

$E=\frac12\sum_k (t_k-y_k)^2$

where $t_k$ is the target and $y_k$ the actual output.

Algorithm

1. Initialise all weights and biases with small random values; choose learning rate $\eta$.
2. Forward pass: for an input pattern, compute hidden outputs $h_j=f\big(\sum_i w_{ij}x_i+b_j\big)$ and output values $y_k=f\big(\sum_j w_{jk}h_j+b_k\big)$, with sigmoid $f(z)=1/(1+e^{-z})$ so $f'=f(1-f)$.
3. Output error term:

$\delta_k=(t_k-y_k)\,y_k(1-y_k)$

4. Hidden error term (error propagated back through the weights):

$\delta_j=h_j(1-h_j)\sum_k \delta_k\,w_{jk}$

5. Weight update:

$\Delta w_{jk}=\eta\,\delta_k\,h_j,\qquad \Delta w_{ij}=\eta\,\delta_j\,x_i$

and the biases similarly with input 1.

6. Repeat steps 2-5 for all patterns (one epoch), and for many epochs until $E$ falls below a threshold or the epoch limit is reached.

The forward pass computes the output; the backward pass distributes the output error to every weight using the chain rule, so each weight moves in the direction that reduces $E$. Limitations: may stop at local minima, and is slow if $\eta$ is badly chosen.

Artificial intelligence (AI) is the branch of computer science concerned with building machines and software that perform tasks which normally require human intelligence, such as reasoning, learning, perception, problem solving and language understanding. Russell and Norvig classify definitions as systems that think like humans, act like humans, think rationally, or act rationally.

Turing Test

Proposed by Alan Turing in 1950 as an operational test for machine intelligence.

• Three participants: a human interrogator, a human, and a machine, the latter two hidden in separate rooms.
• The interrogator communicates only by text and asks any questions for a fixed period.
• If the interrogator cannot reliably tell which respondent is the machine, the machine passes the test and is considered intelligent.

To pass, the machine needs natural language processing, knowledge representation, automated reasoning and machine learning. The Total Turing Test also needs computer vision and robotics. Criticism: Searle's Chinese Room argument says that passing shows imitation, not understanding.

Intelligent agent: an entity that perceives its environment through sensors and acts on it through actuators so as to achieve its goals, choosing actions that maximise its expected performance measure; it is autonomous, reactive and goal-directed.

PEAS for a particle-picking robot

Iterative deepening search (IDS) repeatedly runs depth-limited search with limit $l=0,1,2,\dots$ until a goal is found. It combines the small memory use of DFS with the completeness and optimality (for unit step cost) of BFS.

Algorithm

1. For $l=0,1,2,\dots$:
2. Run depth-limited DFS to depth $l$.
3. If a goal is found, return the solution; otherwise (cutoff) increase $l$ and repeat.

Example: tree with S at root; children A, B; A's children C, D; B's children E, F; goal = F.

• $l=0$: visit S. Not goal.
• $l=1$: visit S, A, B. No goal.
• $l=2$: visit S, A, C, D, B, E, F. Goal F found.

The goal at depth 2 is found at iteration $l=2$, so the shallowest goal is returned.

Properties

• Complete (finite $b$) and optimal for uniform step costs.
• Time $O(b^d)$. The upper levels are regenerated, but it is a small overhead since most nodes are at the bottom level: nodes generated $=(d)b+(d-1)b^2+\dots+b^d$.
• Space $O(bd)$.

Dempster-Shafer Theory (DST) is a mathematical theory of evidence for reasoning under uncertainty that generalises Bayesian probability. Instead of assigning probability to single hypotheses, it assigns belief mass to sets of hypotheses, so ignorance can be represented explicitly.

• Frame of discernment $\Theta$: the set of all mutually exclusive hypotheses.
• Basic probability assignment (mass) $m:2^\Theta\rightarrow[0,1]$, with $m(\emptyset)=0$ and $\sum_{A\subseteq\Theta}m(A)=1$.
• Belief: $Bel(A)=\sum_{B\subseteq A}m(B)$ (lower bound).
• Plausibility: $Pl(A)=1-Bel(\neg A)$ (upper bound).
• The interval $[Bel(A),Pl(A)]$ shows the uncertainty about $A$.

Dempster's rule of combination for two independent evidence sources $m_1,m_2$:

$m_{12}(A)=\frac{\sum_{B\cap C=A}m_1(B)\,m_2(C)}{1-K},\qquad K=\sum_{B\cap C=\emptyset}m_1(B)\,m_2(C)$

Use in statistical reasoning: it lets a system combine evidence from several independent sources (sensors, experts, symptoms) to narrow down the set of possible hypotheses and compute belief intervals, without needing prior probabilities. Example: in medical diagnosis, two tests give mass to {flu, cold} and {flu}; combining them increases belief in {flu}. Applications include diagnosis, sensor fusion and expert systems.