Artificial Intelligence

Turing Test

Proposed by Alan Turing (1950), the Turing Test checks whether a machine can show intelligent behaviour indistinguishable from a human. A human interrogator asks written questions to two hidden parties, one human and one machine. If the interrogator cannot reliably tell which is the machine, the machine passes the test.

Capabilities a machine must have to pass

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

The Total Turing Test adds two more:

5. Computer vision: to perceive objects.
6. Robotics: to manipulate objects and move about.

Simple reflex agent

A simple reflex agent selects actions only on the basis of the current percept, ignoring the percept history. It works through condition-action rules ("if condition then action").

Working: sensors give the current percept, then INTERPRET-INPUT builds the state description, then RULE-MATCH finds a rule whose condition matches, then the rule's action is executed through the actuators.

function SIMPLE-REFLEX-AGENT(percept)
    state  <- INTERPRET-INPUT(percept)
    rule   <- RULE-MATCH(state, rules)
    return rule.ACTION

Example: a vacuum cleaner that sucks dirt if the current square is dirty, otherwise moves. It works well only when the environment is fully observable.

PEAS for an English-to-Nepali translating agent

Alpha-beta pruning

Alpha-beta pruning is an optimisation of the minimax algorithm that skips (prunes) branches of the game tree that cannot affect the final decision, so it returns the same result as minimax but explores fewer nodes.

• Alpha ($\alpha$): the best (highest) value found so far for MAX along the path.
• Beta ($\beta$): the best (lowest) value found so far for MIN along the path.
• Cut-off rule: prune the remaining children when $\alpha \ge \beta$.
  • Alpha cut-off happens at a MIN node when its value is $\le \alpha$ of an ancestor MAX node.
  • Beta cut-off happens at a MAX node when its value is $\ge \beta$ of an ancestor MIN node.

Example

Root A is MAX with MIN children B, C, D. The leaves are B: (3, 12, 8), C: (2, 4, 6), D: (14, 5, 2).

1. Evaluate B: leaves 3, 12, 8 give $B = \min = 3$. At the root, $\alpha = 3$.
2. Evaluate C: the first leaf is 2, so $C \le 2 \le \alpha = 3$. MAX will never choose C, so the leaves 4 and 6 are pruned (alpha cut-off).
3. Evaluate D: leaf 14 gives $\beta = 14$, leaf 5 gives $\beta = 5$, leaf 2 gives $D = 2$. $D = 2 < 3$, so it is not chosen.
4. Root value is $\max(3, 2, 2) = 3$, so the best move is B.

Leaves 4 and 6 were never examined. With the best ordering, the nodes searched drop from $O(b^d)$ to about $O(b^{d/2})$.

Knowledge representation system

A knowledge representation (KR) system is a scheme for encoding facts and rules about the world in a form that a computer can store, reason with and use to solve problems. A good KR system has representational adequacy (it can represent all needed knowledge), inferential adequacy (it can derive new knowledge), inferential efficiency and acquisitional efficiency. Examples are logic, semantic networks, frames, production rules and scripts.

Semantic network

A semantic network is a graph where nodes represent objects, concepts or classes, and labelled arcs (links) represent relations between them, such as is-a, has-part, instance-of, color. The is-a links give inheritance: a node inherits the properties of its superclass.

Example

Animal --has--> Skin
   ^
   | is-a
 Bird --can--> Fly
   ^                \
   | is-a            has --> Wings
Parrot --colour--> Green
   ^
   | instance-of
 Polly

From the network we can answer:

• Polly is a Parrot, a Parrot is a Bird, so Polly can fly (inherited).
• Polly is an Animal, so Polly has skin.
• Polly's colour is green.

Advantages: it is simple, visual and supports inheritance. Limitations: no standard semantics and it handles negation and quantifiers poorly.

Learning by analogy

Learning by analogy is learning to solve a new problem by recalling a similar problem solved earlier and transferring its solution (or the way it was found) to the new one. It involves retrieving a similar case, mapping the similarities and adapting the solution. An example is using what is known about water flow to understand electric current.

Transformational vs derivational analogy

Natural language processing (NLP)

NLP is the branch of AI that lets computers understand, interpret and generate human (natural) language, in text or speech. Applications include machine translation, speech recognition, chatbots, spell checking, sentiment analysis and information retrieval.

Phases of NLP

1. Lexical analysis: splits text into words, tokens and sentences and finds word structure (morphology).
2. Syntactic analysis (parsing): checks grammar and builds a parse tree of the sentence.
3. Semantic analysis: finds the literal meaning of words and sentences.
4. Discourse integration: the meaning of a sentence depends on the preceding ones (e.g. resolving pronouns such as "he", "it").
5. Pragmatic analysis: interprets the sentence in its real-world context to find the intended meaning.

Importance of pragmatic analysis

Pragmatics deals with the speaker's intention, the context, the situation and the world knowledge needed to understand what is really meant rather than what is literally said. For example, "Can you pass the salt?" is literally a question about ability but pragmatically a request. "It's cold here" may mean "close the window". Without pragmatic analysis, a system would give literal and often wrong responses to such sentences, and it could not resolve ambiguity, sarcasm or indirect speech. It is therefore essential for dialogue systems and chatbots to behave naturally.

Importance of an expert system in AI

An expert system is an AI program that captures the knowledge of a human expert in a narrow domain and uses it to give advice or decisions. It is important because it:

• makes scarce expert knowledge available to many people at any time,
• is consistent, does not get tired and has no emotional bias,
• preserves expertise when experts retire,
• is faster and cheaper than consulting a human expert,
• can explain its reasoning, and can solve problems in dangerous or complex fields (medical diagnosis such as MYCIN, fault finding, geology such as PROSPECTOR).

Architecture of an expert system

1. Knowledge base: facts and heuristic rules (usually IF-THEN) about the domain, supplied by the expert.
2. Inference engine: the reasoning part that applies the rules to the facts to reach conclusions, using forward chaining (data-driven) or backward chaining (goal-driven).
3. Working memory (blackboard): holds the facts of the current problem and intermediate results.
4. User interface: lets the user enter queries and facts and receive the answers.
5. Explanation facility: tells the user how (and why) a conclusion was reached.
6. Knowledge acquisition module: lets the knowledge engineer and expert add and update knowledge.

User <-> User Interface <-> Inference Engine <-> Knowledge Base
                               |   \
                       Working Memory  Explanation Facility
                                         ^ Knowledge Acquisition (Expert / Knowledge Engineer)

Feed-forward neural network

In a feed-forward network the connections go in one direction only, from the input layer through the hidden layers to the output layer. There are no loops or feedback, so the output depends only on the current input. Examples are the single-layer perceptron and the multilayer perceptron (trained by backpropagation). They are used for classification and pattern recognition.

Feedback (recurrent) neural network

In a feedback network the outputs of neurons are fed back as inputs to the same or earlier layers, creating loops. The network has memory and its state evolves over time until it settles. Examples are the Hopfield network, Elman network and Boltzmann machine. They are used for associative memory, optimisation and sequence processing.

AND and OR gates with a perceptron

Each neuron computes a weighted sum $net = w_1 x_1 + w_2 x_2 + b$ and uses the step activation

$y = \begin{cases} 1 & net \ge 0 \\ 0 & net < 0 \end{cases}$

AND gate: choose $w_1 = w_2 = 1$, $b = -1.5$ (threshold 1.5).

OR gate: choose $w_1 = w_2 = 1$, $b = -0.5$ (threshold 0.5).

Both outputs match the truth tables of AND and OR, so a single neuron with suitable weights, bias and step activation realises each gate. (XOR is not linearly separable and needs a hidden layer.)

Quantifiers in FOPL

• Universal quantifier ($\forall$): states that a predicate holds for all objects in the domain. $\forall x\, Cat(x) \rightarrow Mammal(x)$ means every cat is a mammal. It is normally used with implication.
• Existential quantifier ($\exists$): states that a predicate holds for at least one object. $\exists x\, Student(x) \land Smart(x)$ means some student is smart. It is normally used with conjunction.

Converting FOPL to CNF

1. Eliminate implications and biconditionals: $P \rightarrow Q \equiv \lnot P \lor Q$.
2. Move negation inward (De Morgan's laws, $\lnot\forall x \equiv \exists x\lnot$, $\lnot\exists x \equiv \forall x\lnot$).
3. Standardise variables apart (rename so each quantifier has a unique variable).
4. Skolemise: remove $\exists$ by replacing the variable with a Skolem constant or function of the enclosing universal variables.
5. Drop the universal quantifiers.
6. Distribute $\lor$ over $\land$ to get a conjunction of clauses.

FOPL for the statements

1. All students are talented persons: $\forall x\,(Student(x) \rightarrow Talent(x))$
2. Every talented person is smart: $\forall x\,(Talent(x) \rightarrow Smart(x))$
3. Someone who is not smart is dumb: $\forall x\,(\lnot Smart(x) \rightarrow Dumb(x))$
4. Ram is dumb but talented: $Dumb(Ram) \land Talent(Ram)$

Conversion to CNF

1. $\forall x\,(\lnot Student(x) \lor Talent(x))$ gives the clause $\lnot Student(x) \lor Talent(x)$
2. $\forall x\,(\lnot Talent(x) \lor Smart(x))$ gives the clause $\lnot Talent(x) \lor Smart(x)$
3. $\forall x\,(\lnot\lnot Smart(x) \lor Dumb(x))$ which is $Smart(x) \lor Dumb(x)$
4. $Dumb(Ram)$ and $Talent(Ram)$ as two separate unit clauses.

Final CNF clauses:

$(\lnot Student(x) \lor Talent(x)) \land (\lnot Talent(x) \lor Smart(x)) \land (Smart(x) \lor Dumb(x)) \land Dumb(Ram) \land Talent(Ram)$

No existential quantifiers occur, so no Skolemisation is needed.

Uninformed vs informed search

State space used for the illustration

            S
          /   \
         A     B
        / \     \
       C   D     E
           |
           G (goal)

Breadth-first search (BFS)

BFS expands the shallowest unexpanded node first, using a FIFO queue, level by level.

• Queue: S. Expand S, giving A, B.
• Expand A, giving B, C, D. Expand B, giving C, D, E.
• Expand C (no children). Expand D, giving G is generated. Expand E.
• Goal G found.

Order of visit: S, A, B, C, D, E, G. Path found: S - A - D - G.

BFS is complete, and optimal when step costs are equal. Time and space are $O(b^d)$, which is high.

Iterative deepening search (IDS)

IDS repeats depth-limited DFS with the limit 0, 1, 2, ... until the goal is found. It combines the low memory of DFS with the completeness and optimality of BFS.

• Limit 0: S (not goal).
• Limit 1: S, A, B (not goal).
• Limit 2: S, A, C, D, B, E (not goal).
• Limit 3: S, A, C, D, G. Goal found.

Path: S - A - D - G. The shallow nodes are regenerated several times, but this costs little because most nodes lie at the deepest level. Time is $O(b^d)$ and space is only $O(bd)$.

A goal-based agent chooses actions by searching or planning for a sequence that reaches a stated goal. A utility-based agent also measures how good each outcome is using a utility function, so it can choose the best way of reaching the goal.

Example (goal-based): a navigation program whose only goal is to reach Pokhara from Kathmandu. Any route that arrives is acceptable.

Example (utility-based): a taxi agent that picks among routes to Pokhara by weighing time, fuel cost, safety and comfort. It chooses the route with the highest expected utility, not just any route that arrives.

Constraint satisfaction formulation

• Variables: C, R, O, S, A, D, N, G, E (each a distinct digit 0-9) plus carries $c_1,c_2,c_3,c_4,c_5$.
• Constraints: all letters differ; C, R, D are non-zero (leading digits); column sums hold.

$\begin{array}{r} C\,R\,O\,S\,S \\ +\;R\,O\,A\,D\,S \\ \hline D\,A\,N\,G\,E\,R \end{array}$

Column equations (right to left):

• $S+S = R + 10c_1$
• $S+D+c_1 = E + 10c_2$
• $O+A+c_2 = G + 10c_3$
• $R+O+c_3 = N + 10c_4$
• $C+R+c_4 = A + 10c_5$
• $c_5 = D$, so $D=1$.

Solving

1. $D=1$ and $C+R+c_4 = A+10$.
2. Try $C=9$, $R=6$, $c_4=0$: this gives $A=5$.
3. From $R+O+c_3=N+10c_4$ with $c_4=0$ and $R=6$: $6+O+c_3=N$. Take $O=2$, $c_3=0$, so $N=8$.
4. Column 3: $O+A+c_2=G$ gives $2+5+c_2=G$. With $c_2=0$, $G=7$ and $c_3=0$, which is consistent.
5. Column 2: $S+D+c_1=E$ gives $S+1+c_1=E$. Column 1: $2S=6+10c_1$, so $S=3$ and $c_1=0$. Then $E=4$.
6. Digits used: C=9, R=6, O=2, S=3, A=5, D=1, N=8, G=7, E=4. All are distinct.

Solution

$96233 + 62513 = 158746$

Check: $96233+62513=158746$, which is DANGER.

Issues in knowledge representation

1. Important attributes: some attributes occur in many objects (for example instance and isa). The representation must support them.
2. Relationships among attributes: inverses, existence of values, techniques for reasoning about values, and single-valued attributes.
3. Choosing the granularity: deciding the level of detail at which knowledge is represented.
4. Representing sets of objects: some properties hold for a set as a whole, not for each member.
5. Finding the right structure: choosing the right structure from a large store of knowledge when it is needed.

Solutions to two of them

• Choosing granularity: use a hierarchy of levels. High-level facts (for example "John is a student") sit at the top. Low-level primitives such as Roll(John, x) are added only when needed. Frames and semantic nets let the system work at the level the query requires.
• Finding the right structure: use indexing and selection. Index structures by key features, such as a frame's name or slots, and pick the best match through pattern matching. If the chosen frame fails, backtrack to a more suitable one. Default values in the frame fill in missing information.

Supervised learning

The model learns from a labelled dataset, where each input $x$ has a known output $y$. It learns a mapping $f: x \to y$ by minimising the error between its predictions and the labels.

• Types: classification (discrete output) and regression (continuous output).
• Algorithms: decision trees, SVM, k-NN, linear regression, neural networks.
• Example: predicting whether an email is spam or not spam from emails already labelled spam/not spam. Another example is predicting house prices from past sales.

Unsupervised learning

The model learns from unlabelled data. It finds hidden structure, patterns or groups without a teacher.

• Types: clustering, association, dimensionality reduction.
• Algorithms: k-means, hierarchical clustering, PCA, Apriori.
• Example: grouping customers of a shop into segments by buying behaviour with no predefined segments. Another is market-basket analysis finding that bread and butter are bought together.

An expert system is an AI program that imitates the decision-making of a human expert in a narrow domain by using stored knowledge and inference.

Architecture

1. Knowledge base: domain facts and rules (usually IF-THEN) obtained from experts.
2. Inference engine: applies the rules to the facts to reach conclusions, using forward chaining (data-driven) or backward chaining (goal-driven).
3. User interface: lets the user enter queries and facts and see the results.
4. Explanation facility: tells the user how and why a conclusion was reached.
5. Knowledge acquisition module: helps the knowledge engineer add or update knowledge.
6. Working memory: holds the facts of the current case.

Flow: User -> User interface -> Inference engine <-> Knowledge base, with the explanation facility and knowledge acquisition attached to the engine and knowledge base.

Application areas

• Medical diagnosis: for example MYCIN, which diagnoses bacterial infections.
• Mineral exploration / configuration: for example PROSPECTOR for geology, and XCON for configuring computer systems.

Need for an activation function

An activation function decides the output of a neuron from its weighted sum.

• It introduces non-linearity. Without it, any stack of layers collapses to a single linear transformation and cannot learn complex patterns.
• It limits the output to a useful range (for example sigmoid to 0-1).
• It decides whether a neuron "fires" (for example a step or ReLU function).
• It makes gradient-based learning such as back-propagation possible when it is differentiable.

Perceptron for AND gate

Net input: $net = w_1x_1 + w_2x_2 + b$. Output: $y = 1$ if $net \ge 0$, else $0$. Update rule: $w_i \leftarrow w_i + \eta (t - y) x_i$ and $b \leftarrow b + \eta (t - y)$.

Training with $\eta = 1$, starting from $w_1=w_2=b=0$. After a few epochs the weights settle at $w_1=1,\ w_2=1,\ b=-2$.

All four patterns are classified correctly.

X = [(0,0),(0,1),(1,0),(1,1)]
T = [0,0,0,1]
w = [0, 0]; b = 0; lr = 1

def step(n):
    return 1 if n >= 0 else 0

for epoch in range(20):
    errors = 0
    for (x1, x2), t in zip(X, T):
        y = step(w[0]*x1 + w[1]*x2 + b)
        e = t - y
        if e != 0:
            w[0] += lr*e*x1
            w[1] += lr*e*x2
            b += lr*e
            errors += 1
    if errors == 0:
        break

print(w, b)
for (x1, x2) in X:
    print(x1, x2, step(w[0]*x1 + w[1]*x2 + b))

a) Hopfield Network

A Hopfield network is a fully connected, recurrent neural network with a single layer of neurons that serves as an associative (content-addressable) memory.

• Every neuron connects to every other neuron; there is no self-connection ($w_{ii}=0$) and weights are symmetric ($w_{ij}=w_{ji}$).
• Neurons are binary (+1/-1 or 1/0) and update as $x_i = \text{sign}\left(\sum_j w_{ij}x_j\right)$.
• Patterns are stored with Hebbian learning: $w_{ij} = \sum_p x_i^p x_j^p$.
• It has an energy function that decreases with each update, so the network settles into a stable state (a stored pattern).
• Uses: pattern recall from noisy or partial input, optimisation problems. Its capacity is limited to about $0.15N$ patterns for $N$ neurons.

b) Best First Search

Best-first search is an informed search that always expands the node that looks most promising according to an evaluation function $f(n)$.

• It uses a priority queue (OPEN list) ordered by $f(n)$ and a CLOSED list of expanded nodes.
• In greedy best-first search, $f(n)=h(n)$, the estimated cost to the goal.
• Steps: put the start node on OPEN; pick the node with the lowest $f$; if it is the goal, stop; otherwise expand it, add its children to OPEN, and repeat.
• It is fast but neither optimal nor always complete. Time and space are $O(b^m)$ in the worst case.

Step 1: Convert to First-Order Logic (FOL)

1. $\forall x\ (Likes(Tashi,x) \rightarrow Easy(x))$ (Tashi likes only easy courses)
2. $\forall x\ (Science(x) \rightarrow Hard(x))$
3. $\forall x\ (CompApp(x) \rightarrow Easy(x))$
4. $CompApp(AI)$
5. Common knowledge: nothing is both easy and hard: $\forall x\ \neg(Easy(x) \wedge Hard(x))$. Not needed for this proof.

Goal: find $x$ such that $Likes(Tashi,x)$. The system derives that Tashi would like AI.

Step 2: Convert to clause form

Facts 3 and 4 give $Easy(AI)$. To find what Tashi likes we need a rule of the form "if easy then Tashi likes". The statement "Tashi only likes easy courses" is read as "Tashi likes a course if it is easy". So clause 1 becomes $\forall x\ (Easy(x) \rightarrow Likes(Tashi,x))$.

• C1: $\neg Easy(x) \vee Likes(Tashi,x)$
• C2: $\neg Science(x) \vee Hard(x)$
• C3: $\neg CompApp(x) \vee Easy(x)$
• C4: $CompApp(AI)$
• Negated goal (with an answer literal): C5: $\neg Likes(Tashi,y) \vee Ans(y)$

Step 3: Resolution

1. C3 and C4, with $x/AI$: $Easy(AI)$ (C6)
2. C1 and C6, with $x/AI$: $Likes(Tashi,AI)$ (C7)
3. C5 and C7, with $y/AI$: $Ans(AI)$

Conclusion: the answer literal is $Ans(AI)$, so Tashi would like Artificial Intelligence. She would not like Science courses, which are hard.

A* algorithm

A* is an informed best-first search that finds the least-cost path from a start node to a goal using

$f(n) = g(n) + h(n)$

where $g(n)$ is the actual cost from the start to $n$ and $h(n)$ is the heuristic estimate from $n$ to the goal. If $h$ is admissible ($h(n) \le$ true cost) A* is optimal. If $h$ is also consistent, A* is complete.

Algorithm

1. Put the start node on OPEN with $f = h(start)$.
2. Pick the node $n$ on OPEN with the least $f$. If OPEN is empty, fail.
3. If $n$ is the goal, return the path.
4. Move $n$ to CLOSED. For each successor $m$, compute $g(m)=g(n)+c(n,m)$ and $f(m)=g(m)+h(m)$.
5. If $m$ is new, add it to OPEN. If it exists with a higher $g$, update it with the better path. Repeat from step 2.

Example. Graph edges: S-A (1), S-B (4), A-B (2), A-C (5), B-C (1), C-G (3), A-G (12). Heuristics: $h(S)=7,\ h(A)=6,\ h(B)=2,\ h(C)=1,\ h(G)=0$.

• Expand S: A has $f=1+6=7$, B has $f=4+2=6$. Pick B.
• Expand B ($g=4$): C has $f=5+1=6$. A stays at 7. Pick C.
• Expand C ($g=5$): G has $f=8+0=8$. OPEN has A(7), G(8). Pick A.
• Expand A ($g=1$): B via A gives $g=3$, so $f=3+2=5$ is better than 6; update B. G via A gives $g=13$, so $f=13$, worse. Pick B ($f=5$).
• Expand B ($g=3$): C via B gives $g=4$, $f=5$, better. Pick C, then G with $g=4+3=7$, $f=7$.

Optimal path: S -> A -> B -> C -> G with cost $1+2+1+3 = 7$.

Informed vs uninformed search

Quantifiers

• Universal quantifier $\forall$: the statement holds for every object in the domain. $\forall x\ (Student(x) \rightarrow Studies(x))$ means "all students study".
• Existential quantifier $\exists$: the statement holds for at least one object. $\exists x\ (Student(x) \wedge Topper(x))$ means "some student is a topper".
• Relations: $\neg\forall x\,P \equiv \exists x\,\neg P$ and $\neg\exists x\,P \equiv \forall x\,\neg P$.

Bayesian Belief Network (BBN)

A BBN is a directed acyclic graph in which nodes are random variables and edges show direct causal influence. Each node has a conditional probability table $P(X \mid Parents(X))$.

• The joint probability is $P(x_1,\dots,x_n) = \prod_i P(x_i \mid parents(x_i))$.
• It allows compact representation and reasoning under uncertainty using Bayes' rule, $P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}$.
• Example: Burglary and Earthquake -> Alarm -> JohnCalls and MaryCalls. We can compute $P(Burglary \mid JohnCalls)$.

Back-propagation to train an ANN

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

1. Initialise weights with small random values.
2. Forward pass: compute each layer's output, $net_j=\sum w_{ij}x_i + b_j$ and $o_j = f(net_j)$ (for example sigmoid).
3. Error: $E = \frac12\sum (t_k - o_k)^2$.
4. Backward pass: for an output neuron, $\delta_k = (t_k-o_k)\,o_k(1-o_k)$. For a hidden neuron, $\delta_j = o_j(1-o_j)\sum_k \delta_k w_{jk}$.
5. Weight update: $\Delta w_{ij} = \eta\,\delta_j\,o_i$ and $w_{ij} \leftarrow w_{ij} + \Delta w_{ij}$ (with an optional momentum term).
6. Repeat for all training patterns (epochs) until the error falls below a threshold or a maximum number of epochs is reached.

The learning rate $\eta$ controls step size. Back-propagation can get stuck in local minima, which momentum and good initialisation reduce.

Artificial Intelligence (AI) is the branch of computer science concerned with building machines and software that perform tasks normally requiring human intelligence, such as reasoning, learning, perception, problem solving and language understanding. It can be viewed as systems that think or act rationally, or like humans.

Components of AI

1. Knowledge representation: storing facts and rules in forms the machine can use (logic, semantic nets, frames, rules).
2. Reasoning and problem solving: searching and inferring to reach conclusions or plans.
3. Machine learning: improving performance from data and experience.
4. Natural language processing: understanding and generating human language.
5. Perception (computer vision and speech recognition): interpreting sensory input such as images and sound.
6. Robotics and planning: acting in the physical world and planning sequences of actions.
7. Expert systems: reproducing the decisions of human experts in a domain.

$\begin{array}{r} T\,W\,O \\ +\;T\,W\,O \\ \hline F\,O\,U\,R \end{array}$

Constraints: each letter is a distinct digit; T and F are non-zero. Since two 3-digit numbers sum to under 2000, $F=1$.

Let $c_1,c_2,c_3$ be carries from the units, tens and hundreds columns:

• $O+O = R + 10c_1$
• $W+W+c_1 = U + 10c_2$
• $T+T+c_2 = O + 10c_3$
• $c_3 = F = 1$

Solving

1. $F=1$, so $c_3=1$ and $2T + c_2 = O + 10$. Hence $T \ge 5$.
2. R is even (it equals $2O$ mod 10), so $O$ and $R$ follow from $O$.
3. Try $T=7$, $c_2=0$: $14 = O + 10$, so $O=4$. Then $R = 8$, $c_1=0$.
4. $2W + 0 = U + 10c_2$ with $c_2=0$ gives $U = 2W$. Choose $W=3$, so $U=6$.
5. Digits: T=7, W=3, O=4, F=1, U=6, R=8, all distinct.

Solution

$734 + 734 = 1468$

(Other valid assignments exist, for example $765+765=1530$ and $836+836=1672$.)

An agent is anything that perceives its environment through sensors and acts upon it through actuators. For example, a robot vacuum senses dirt with sensors and acts with its motors and brushes. A rational agent chooses the action that maximises its expected performance measure.

Types of agents

1. Simple reflex agent: acts only on the current percept using condition-action rules. Example: a thermostat.
2. Model-based reflex agent: keeps an internal state about the world to handle partially observable environments.
3. Goal-based agent: chooses actions that achieve a stated goal, using search and planning.
4. Utility-based agent: chooses among ways of reaching the goal by maximising a utility (degree of happiness) function.
5. Learning agent: improves with experience. It has a learning element, critic, performance element and problem generator.

An expert system is a computer program that holds the knowledge of human experts in a specific domain and uses inference to give advice or solve problems at expert level. It consists of a knowledge base, an inference engine and a user interface. Examples are MYCIN (medical diagnosis) and DENDRAL (chemistry).

Stages of expert system development

1. Identification: define the problem, its scope, the goals, the available experts and the resources.
2. Conceptualisation: identify the key concepts, relations and the problem-solving strategy used by the experts.
3. Formalisation: choose the knowledge representation (rules, frames) and the tool or shell, and map the concepts into it.
4. Implementation: the knowledge engineer builds the knowledge base and inference engine as a working prototype.
5. Testing: run the prototype on real cases with the expert, find errors and gaps, and refine the rules.
6. Deployment and maintenance: install the system for users, train them and keep updating the knowledge base.

Development is iterative: the knowledge engineer repeatedly goes back to the expert to acquire and correct knowledge.

Consider this tree: A is the root with children B and C; B has children D and E; C has child F.

Breadth-first search (BFS)

BFS expands the shallowest unexpanded node first. It uses a FIFO queue.

• Order of visit: A, B, C, D, E, F.
• Complete, and optimal when all step costs are equal.
• Time and space are $O(b^d)$, where $b$ is the branching factor and $d$ the depth of the shallowest goal. Memory is its main weakness.

Depth-first search (DFS)

DFS expands the deepest unexpanded node first. It uses a LIFO stack (or recursion).

• Order of visit: A, B, D, E, C, F.
• Not complete in infinite or cyclic spaces and not optimal.
• Time is $O(b^m)$ and space is only $O(bm)$, where $m$ is the maximum depth.

Inference vs reasoning

Why probabilistic reasoning is important in AI

• The real world is uncertain, because sensors are noisy and information is incomplete or ambiguous. Pure logic (true/false) cannot express this.
• It represents degrees of belief, for example $P(Disease \mid Symptom)$.
• It updates beliefs as evidence arrives using Bayes' rule, $P(H\mid E) = \frac{P(E\mid H)P(H)}{P(E)}$.
• It supports decision-making under uncertainty, such as in medical diagnosis, spam filtering, robotics and speech recognition.
• Models such as Bayesian networks and HMMs handle uncertainty efficiently.

Learning in neural networks

Learning is the process by which a neural network adjusts its weights and biases in response to training data so that its outputs approach the desired outputs. A learning rule, such as the delta rule or back-propagation, repeatedly reduces an error measure until the network performs well on the task.

Learning paradigms:

• Supervised: trained with input-target pairs.
• Unsupervised: finds patterns in unlabelled data (for example self-organising maps).
• Reinforcement: learns from rewards and penalties.

Types of neural networks

1. Single-layer feed-forward (perceptron): input directly connected to output; can solve only linearly separable problems.
2. Multilayer feed-forward (MLP): one or more hidden layers; trained with back-propagation; handles non-linear problems.
3. Recurrent neural network (RNN): has feedback loops and memory; used for sequences, speech and text. Hopfield networks are recurrent.
4. Convolutional neural network (CNN): uses convolution layers; used for images and video.
5. Self-organising map (Kohonen): unsupervised clustering and dimensionality reduction.
6. Radial basis function network: uses radial functions in the hidden layer; used for function approximation.

Comparison of A* and greedy best-first search

Both are informed searches that use a heuristic $h(n)$, the estimated cost from $n$ to the goal.

How heuristic cost gives the optimum

A* adds the real cost $g(n)$ already paid to the estimate $h(n)$ still to go. If $h(n)$ never overestimates (admissible), the first time the goal is selected from OPEN its $f$ equals the true cheapest cost, because every other path on OPEN has $f \ge$ that value. Greedy ignores $g$, so it can follow a path that looks close to the goal but is expensive.

Example. Edges: S-A (2), S-B (5), A-G (10), B-G (3). Heuristics: $h(S)=6,\ h(A)=1,\ h(B)=3,\ h(G)=0$. The true best cost is S-B-G = 8; the other path S-A-G costs 12.

• Greedy: from S, A has $h=1$ and B has $h=3$, so it picks A, then G. Path S-A-G, cost 12 (not optimal).
• A*: from S, A has $f=2+1=3$, B has $f=5+3=8$. It expands A and reaches G with $f=12+0=12$. B ($f=8$) is now the lowest, so it expands B and reaches G with $f=8+0=8$. G with $f=8$ is chosen before G with $f=12$. Path S-B-G, cost 8 (optimal).

So A* uses the heuristic and the path cost together to guarantee the optimum, while greedy only reaches a goal quickly.

Frame

A frame is a data structure for representing stereotyped knowledge about an object, event or situation. It is a collection of slots (attributes) with fillers (values), default values, and procedures (if-needed, if-added). Frames are organised in a hierarchy and inherit slots from parent frames through is-a links. Example:

• Frame: Person, with slots: isa = Mammal, has = Nose.
• Frame: Sandip, with slots: isa = Person, team = Nepali team, uniform colour = red/blue.

Semantic net

A semantic net is a graph for knowledge representation. Nodes represent objects or concepts and labelled arcs represent relations between them (for example is-a, has-part, instance). It supports inheritance: a node inherits the properties of its parents.

Conversion of the given statements

Nodes and arcs (node --relation--> node):

• (a) Person --is-a--> Mammal
• (b) Sandip --instance-of--> Person
• (c) Person --has--> Nose
• (d) Sandip --member-of--> Nepali team
• (e) Sandip --uniform colour--> {Red, Blue}

Resulting net:

Mammal <--is-a-- Person --has--> Nose Person <--instance-of-- Sandip --member-of--> Nepali team Sandip --uniform colour--> Red / Blue

By inheritance, Sandip is a mammal and has a nose, even though those facts are not stored on the Sandip node.

Forward propagation (feed-forward) networks

Signals travel in one direction only: input layer -> hidden layers -> output layer. There are no feedback loops, so the output depends only on the current input.

Backward propagation / feedback (recurrent) networks

Here the question is read as networks in which information also flows backward through feedback connections (recurrent networks), and the error is propagated back to train the weights. Outputs depend on the current input and on earlier states.

When feed-forward networks are better

• Static pattern recognition and classification, for example handwritten digits and image classification.
• Function approximation and regression where each input is independent.
• When fast, stable and simple training and prediction are needed.
• When there is limited computing power or data.

When feedback (backward) networks are better

• Sequential or time-dependent data such as speech, text, time series and language modelling.
• Tasks needing memory of earlier inputs, such as predicting the next word.
• Associative memory and pattern completion from noisy input (Hopfield network).
• Control and dynamic systems where the output depends on previous states.