Artificial Intelligence

Cognitive science is the interdisciplinary study of the mind and its processes, such as perception, memory, language, reasoning and learning. It combines psychology, neuroscience, linguistics, philosophy, anthropology and artificial intelligence to understand how intelligence works in humans and how it can be modelled in machines.

A rule-based agent chooses actions using a set of condition-action (IF-THEN) rules. It works in this cycle:

1. The sensors give the current percept.
2. The agent interprets the percept to describe the current state.
3. It matches the state against the condition parts of its rules and picks the rule that fires.
4. The action part of that rule is executed through the actuators.

Example: IF the room is dirty THEN clean; IF the car in front is braking THEN brake. A simple reflex agent has no memory, whereas a model-based rule agent also keeps an internal state.

Omniscience means having complete knowledge: an omniscient agent knows the actual outcome of every action it takes. This is impossible in the real world. A rational agent is therefore not omniscient; it maximises expected performance given the percepts and knowledge it actually has, not the actual result.

A Constraint Satisfaction Problem (CSP) is defined by three components: a set of variables $X=\{X_1,\dots,X_n\}$, a domain of possible values $D_i$ for each variable, and a set of constraints that specify the allowed combinations of values. A solution is a complete assignment of values to all variables that satisfies every constraint.

Example: map colouring. Variables are the regions (A, B, C), the domain is {Red, Green, Blue}, and the constraint is that adjacent regions must have different colours. Other examples are the N-Queens problem and Sudoku.

Conjunctive Normal Form (CNF) is a standard form of a logical sentence in which the sentence is a conjunction (AND) of clauses, and each clause is a disjunction (OR) of literals.

$(A \lor \lnot B) \land (C \lor D \lor \lnot E)$

Every propositional sentence can be converted to CNF, and CNF is the input form required for resolution theorem proving.

Fuzzy logic is a form of many-valued logic in which truth values lie anywhere between 0 and 1 instead of being only true (1) or false (0). It uses membership functions $\mu_A(x)\in[0,1]$ to express partial truth, so it can handle vague and imprecise concepts such as "warm", "tall" or "fast". It is used in washing machines, air conditioners and control systems.

A version space is the set of all hypotheses that are consistent with the training examples seen so far. It is bounded by the most general boundary (G) and the most specific boundary (S). The candidate elimination algorithm updates S and G after each example, removing hypotheses inconsistent with it, so that the version space shrinks as more data is seen.

A rational agent is an agent that, for each possible percept sequence, selects the action expected to maximise its performance measure, based on the evidence provided by the percept sequence and its built-in knowledge. Rationality depends on the performance measure, prior knowledge, available actions and percept history.

Machine learning is a branch of artificial intelligence in which computers learn from data and experience to improve their performance on a task without being explicitly programmed. A program is said to learn from experience $E$ with respect to task $T$ and performance measure $P$ if its performance at $T$, measured by $P$, improves with $E$. Main types are supervised, unsupervised and reinforcement learning.

Natural Language Processing (NLP) is important because language is the main way humans communicate and store knowledge. NLP lets machines understand, interpret and generate human language, so people can interact with computers in plain language. It enables machine translation, speech recognition, chatbots, sentiment analysis, information retrieval and text summarisation, and it is also a key test of intelligence (the Turing test).

Syntactic analysis (parsing) checks whether a sentence follows the grammar of the language and builds its structure, usually a parse tree. Steps:

• The sentence is split into tokens and each word is tagged with its part of speech using a lexicon.
• A grammar (for example a context-free grammar such as S -> NP VP, NP -> Det N) is used with a parser (top-down or bottom-up, or a transition network) to build the parse tree.
• Sentences that do not fit the grammar are rejected.

Semantic analysis assigns meaning to the parsed sentence. Steps:

• Each word is given a meaning from the lexicon, resolving ambiguity (word sense disambiguation).
• The meanings are combined according to the parse tree structure, producing a representation such as predicate logic, semantic networks or frames. For example, "Ram eats rice" becomes $eats(Ram, Rice)$.
• The result is checked for consistency with world knowledge.

Syntax answers "is it well formed?" while semantics answers "what does it mean?".

Rational agent: A rational agent is one that does the right thing: for every possible percept sequence it selects the action expected to maximise its performance measure, given its percepts and built-in knowledge. Rationality is not omniscience; it concerns expected, not actual, success.

Differences between utility-based and model-based agents

State space representation describes a problem as a graph in which nodes are states and edges are actions (operators) that move from one state to another. It is defined by:

• an initial state,
• a set of operators/actions that produce successor states,
• a goal test,
• a path cost function.

Solving the problem means finding a path from the initial state to a goal state.

Example: 8-puzzle. A state is an arrangement of the tiles 1-8 and the blank on a $3\times3$ board. The initial state is any scrambled arrangement. The actions are moving the blank up, down, left or right. The goal state is the tiles in order with the blank at the end, and each move costs 1. Searching this state space (by BFS, A* and so on) gives the sequence of moves to solve the puzzle.

The term is forward chaining. Forward chaining is a data-driven inference method. It starts from the known facts and applies rules whose premises are satisfied (modus ponens) to derive new facts, repeating until the goal is derived or no new facts can be added.

Example. Rules and facts:

• R1: $Parent(x,y)\land Male(x)\Rightarrow Father(x,y)$
• R2: $Father(x,y)\Rightarrow Ancestor(x,y)$
• Facts: $Parent(Ram, Sita)$, $Male(Ram)$

Step 1: R1 fires, giving $Father(Ram,Sita)$. Step 2: R2 fires, giving $Ancestor(Ram,Sita)$. The goal $Ancestor(Ram,Sita)$ is reached.

It contrasts with backward chaining, which starts from the goal and works back to the facts.

AI is defined in four ways: systems that think like humans, act like humans, think rationally, and act rationally. In practice, early AI tried to encode intelligence with hand-written rules, but results were limited. When large quantities of data and computing power became available, simple methods such as neural networks and statistical learning began to show behaviour that looks intelligent, for example recognising speech and images, translating text and playing chess or Go.

Thus a quantitative increase in data, memory, processors and training examples produced a qualitative change: machines that act rationally and perform tasks requiring human intelligence. This supports the statement that sometimes quantity becomes quality. For example, a language model trained on a small corpus only predicts words, but at a very large scale it can converse, translate and reason, which meets the "acting humanly/rationally" definitions of AI.

A Convolutional Neural Network (CNN) is a deep network designed for grid-like data such as images. It automatically learns features through the following layers:

1. Input layer: the image as a matrix of pixel values (height x width x channels).
2. Convolution layer: small filters (kernels) slide over the image and compute dot products to produce feature maps that detect edges, textures and shapes. Weights are shared, so there are fewer parameters.
3. Activation (ReLU): $f(x)=\max(0,x)$ adds non-linearity.
4. Pooling layer: max or average pooling reduces the size of the feature maps, keeping important features and giving translation invariance.
5. Fully connected layer: the flattened features are fed to dense layers that combine them.
6. Output layer: softmax gives class probabilities.

The network is trained by backpropagation with gradient descent, adjusting filter weights to minimise the loss. Early layers learn simple features and deeper layers learn complex ones. Uses include image classification, face recognition and object detection.

Artificial Intelligence (AI) is the broad goal of building machines that can perform tasks requiring human intelligence, such as reasoning, perception, planning and language understanding. Machine Learning (ML) is a subset of AI that achieves this goal by letting systems learn patterns from data and improve with experience instead of being explicitly programmed. Deep learning is in turn a subset of ML.

Relationship

• AI is the umbrella field; ML is one of the main approaches to achieve AI.
• Classical AI used hand-coded rules and knowledge bases (expert systems). ML replaces much of this by learning the rules from data.
• Learning is considered a key element of intelligence, so an intelligent agent needs a learning component to improve its performance and adapt to new environments.
• ML supplies techniques for many AI tasks: supervised learning for classification and prediction, unsupervised learning for clustering, and reinforcement learning for decision making and game playing.
• Application areas of AI that rely on ML include NLP, computer vision, speech recognition, recommender systems and robotics.

Comparison

Hence every ML system is part of AI, but not all AI uses ML.

(a) Brothers are siblings.

$\forall x\,\forall y\;\big(Brother(x,y)\Rightarrow Sibling(x,y)\big)$

(b) "Sibling" is reflexive (as given in the question, each person is a sibling of themselves).

$\forall x\;Sibling(x,x)$

(c) One's mother is one's female parent.

$\forall x\,\forall y\;\big(Mother(x,y)\Leftrightarrow Female(x)\land Parent(x,y)\big)$

(d) A cousin is a child of a parent's sibling.

$\forall x\,\forall y\;\big(Cousin(x,y)\Leftrightarrow \exists p\,\exists q\;(Parent(p,x)\land Sibling(p,q)\land Parent(q,y))\big)$

(e) All BIM students study AI and JAVA.

$\forall x\;\big(BIMStudent(x)\Rightarrow Studies(x,AI)\land Studies(x,JAVA)\big)$

A semantic network is a graph in which nodes are concepts or objects and labelled arcs are relations such as is-a and has.

Nodes and links

• Albatross --is-a--> Bird (c)
• Donald --is-a--> Bird (d)
• Tracy --is-a--> Albatross (e)
• Bird --is-a--> Animal (a)
• Bird --has--> Feathers (b)
• Bird --can--> Fly (b)
• Bird --lays--> Eggs (b)

Diagram

            Animal
               ^
               | is-a
             Bird ---has---> Feathers
          ^   ^   \--can---> Fly
     is-a |   | is-a \-lays-> Eggs
  Albatross  Donald
       ^
       | is-a
     Tracy

Because of inheritance, Tracy and Donald inherit the properties of Bird (feathers, fly, lay eggs) and of Animal.

Computer vision is the field of AI that enables computers to extract, analyse and understand information from images and videos, aiming to imitate human vision. Machine vision is the use of imaging (cameras, lighting, sensors) with processing to perform inspection and guidance in industrial automation, usually in a controlled environment.

Application areas

• Computer vision: face recognition, self-driving cars, medical image diagnosis, object detection, OCR, surveillance, augmented reality.
• Machine vision: product inspection and defect detection on assembly lines, barcode reading, robot guidance, packaging verification, measuring parts in manufacturing.

The figure is not reproduced here, so the method is shown on a representative road graph of the cities (edge costs in km; heuristic $h$ = straight-line distance to Kathmandu).

$h$: Dang 360, Butwal 250, Narayanghat 120, Pokhara 140, KTM 0 (all admissible).

(a) A* search with $f(n)=g(n)+h(n)$

Path: Dang -> Butwal -> Narayanghat -> KTM, cost $130+110+150=390$ km. Nodes expanded: 4 (Pokhara never expanded).

(b) Uniform Cost Search with $f(n)=g(n)$

Path: Dang -> Butwal -> Narayanghat -> KTM, cost 390 km. Nodes expanded: 5.

Comparison

Both find the optimal path, but A* expands fewer nodes because the heuristic guides the search towards Kathmandu.

Defining a problem. In AI, a problem is a situation in which an agent must find a sequence of actions that takes it from an initial state to a desired goal state. A well-defined problem has these components:

1. Initial state: where the agent starts.
2. Actions (operators): the set of possible actions in each state.
3. Transition model: the state that results from an action (successor function).
4. Goal test: checks whether a state is a goal.
5. Path cost: a numeric cost for each path (sum of step costs).

Together, the first three define the state space.

Criteria for defining a problem

• Define the problem precisely, including initial and final (goal) situations.
• Analyse the problem to find the features that affect the solution.
• Isolate and represent the task knowledge needed.
• Choose the best problem-solving technique and apply it.
• The formulation should be at the right level of abstraction, and the solution should be checkable and the cost measurable.

Constraint Satisfaction Problem vs Real World Problem

Examples. Map colouring: variables are regions, domain is {R, G, B}, constraint is that neighbours differ. Route finding: state is the current city, actions are driving to adjacent cities, goal is the destination, and cost is distance.