Artificial Intelligence

Overview: Agents, Problems, and Intelligence

An intelligent agent perceives its environment through sensors, chooses actions through a program, and acts through actuators. A thermostat, a chess program, and a self-driving car are all agents in this broad sense, differing in how complex their environment is. Environments can be fully or partially observable, deterministic or stochastic, static or dynamic, discrete or continuous, and single-agent or multi-agent. A problem is well defined when you can state the initial state, the actions available in each state, the transition model that says what each action does, the goal test, and the path cost. Search then becomes the process of generating a sequence of actions from the initial state to a goal state. The distinction between a solution and an optimal solution matters throughout: a solution is any path to a goal, while an optimal solution has the lowest total cost. Algorithms are judged by completeness, whether they are guaranteed to find a solution if one exists; optimality, whether they find the lowest-cost solution; time complexity, how long they take as the problem grows; and space complexity, how much memory they need. These four criteria, not vague claims of cleverness, are how you compare search methods in an exam.

AI search & knowledge representation

Uninformed search uses no estimate of distance to the goal. Breadth-first search expands nodes level by level, using a queue. It is complete and optimal when every step costs the same, but its space requirement grows exponentially with depth, which is its main weakness. Depth-first search expands the deepest node first, using a stack or recursion. It needs far less memory, but it is not complete in infinite spaces and not optimal, because it may return the first solution it finds rather than the cheapest. Depth-limited search caps the depth to avoid infinite descent, and iterative deepening repeats depth-limited search with increasing limits, combining the memory advantage of depth-first search with the completeness and optimality of breadth-first search for uniform costs. Uniform-cost search expands the node with the lowest path cost so far, using a priority queue; it is complete and optimal provided step costs are positive, and it is the search analogue of Dijkstra algorithm.

Informed search adds a heuristic function h(n), an estimate of the cost from node n to the nearest goal. Greedy best-first search expands the node with the lowest h(n), which can be very fast when the heuristic points the right way but is neither complete in general nor optimal, because it ignores the cost already paid. A* search expands the node with the lowest f(n) = g(n) + h(n), where g(n) is the cost from the start to n. If h(n) never overestimates the true remaining cost, the heuristic is admissible, and A* is optimal. If h is also consistent, meaning the estimated cost from a node is no greater than the step cost plus the estimate from the successor, then A* never needs to reopen a node. The quality of the heuristic decides everything: a heuristic of zero reduces A* to uniform-cost search, while a perfect heuristic goes straight to the goal.

Game playing uses minimax: the maximising player chooses the move with the highest value, the minimising opponent chooses the lowest, and leaf nodes are scored by an evaluation function when the game tree is too large to search to the end. Alpha-beta pruning speeds up minimax without changing its result. Alpha is the best value the maximiser can guarantee so far, beta is the best value the minimiser can guarantee so far, and a branch is pruned when it cannot improve on those bounds: if a minimising node already offers the maximiser less than alpha, the maximiser will never choose that branch, and symmetrically for beta. Pruning is safe precisely because the pruned branches could not affect the final choice at the root. With good move ordering, alpha-beta can roughly double the searchable depth in the same time.

Knowledge representation asks how facts and rules are stored so reasoning is possible. Propositional logic deals with whole statements that are true or false, combined with AND, OR, NOT, and implication. It is simple and decidable, but it cannot express general statements about all objects without listing every case. First-order logic adds objects, predicates, variables, and quantifiers: for all and there exists. A statement such as every student is a person becomes a quantified formula rather than a long list. Inference in first-order logic often uses resolution: convert statements to clause form, negate the goal, and repeatedly resolve pairs of clauses that contain complementary literals, deriving a contradiction if the goal follows. Unification finds substitutions that make two expressions identical, which is what lets a general rule apply to a specific case. Semantic networks represent knowledge as a graph of nodes for concepts and labelled arcs for relations such as is-a and has-part; inheritance lets a specific concept inherit properties of a general one, so a fact about birds applies to sparrows unless overridden. Frames are structured records with slots and default values, useful for stereotyped situations such as a classroom or a restaurant visit; a frame for a lecture might have slots for teacher, subject, room, and time. Scripts are frame-like structures for sequences of events, describing the expected scenes, roles, and props in a familiar activity such as visiting a restaurant, from entering to paying. Logic is precise but can be awkward for default and procedural knowledge; networks, frames, and scripts are intuitive but need care to keep their semantics precise. Reasoning under uncertainty extends all of this: Bayesian reasoning updates beliefs with evidence using probabilities, so a prior belief combined with a likelihood gives a posterior belief, and Bayes networks represent conditional dependencies between variables. Fuzzy logic replaces sharp true or false membership with degrees of membership, so a person can be tall to degree 0.8 rather than simply tall or not tall, which suits vague concepts such as hot, fast, or large.

Machine learning basics

Machine learning learns a mapping from inputs to outputs from data, rather than from hand-written rules. In supervised learning, each training example carries the correct answer. Regression predicts a continuous value, such as a price or a temperature; classification predicts a discrete label, such as spam or not spam. A decision tree splits data by asking, at each node, the question that best separates the classes, usually judged by information gain or impurity reduction; it is easy to interpret but can overfit if grown too deep, and pruning or depth limits control this. The k-nearest neighbours method classifies a new point by the majority label of its k closest training points under some distance measure; it needs no training phase beyond storing the data, but it is sensitive to irrelevant features, to the choice of k, and to feature scaling, and it can be slow at prediction time. A support vector machine finds the hyperplane that separates classes with the largest margin, the gap between the boundary and the nearest training points, called support vectors; the kernel trick lets it handle non-linear boundaries by implicitly mapping data into a higher-dimensional space. In unsupervised learning, no labels are given. Clustering groups similar points together. K-means chooses k initial centres, assigns each point to the nearest centre, recomputes each centre as the mean of its points, and repeats until stable; it is simple and fast but needs k in advance, is sensitive to initial centres and outliers, and assumes roughly spherical clusters. Hierarchical clustering builds a tree of clusters, either by merging the closest clusters bottom-up or splitting top-down, and the resulting dendrogram can be cut at any level to choose the number of clusters.

Generalisation is the central problem: a model must perform on new data, not just on data it has seen. Overfitting means the model has memorised noise and detail in the training data, so training accuracy is high but test accuracy is low. Underfitting means the model is too simple to capture the pattern, so both training and test accuracy are low. The bias-variance view explains the trade-off: bias is error from wrong assumptions that make the model too rigid, variance is error from sensitivity to the particular training sample, and total error combines bias, variance, and irreducible noise. Simple models have high bias and low variance; complex models have low bias and high variance; the best model balances the two. Data is therefore split into a training set for fitting, a validation set for choosing settings such as depth or k, and a test set, used once, for an honest final estimate. Cross-validation repeats the split to reduce the luck of any single split. Evaluation needs more than accuracy when classes are imbalanced. Precision is the fraction of predicted positives that are truly positive; recall is the fraction of true positives that were found; F1 is their harmonic mean, which punishes a model that is good on one and poor on the other. A confusion matrix of true positives, false positives, true negatives, and false negatives is the source of all four measures.

Neural networks build learning from simple units. A perceptron takes weighted inputs, sums them, adds a bias, and passes the result through an activation function to produce an output; it can learn only linearly separable problems, which is a famous limitation that a single layer cannot overcome. A multilayer perceptron stacks layers: an input layer, one or more hidden layers, and an output layer, so hidden units can learn intermediate features and the network can represent non-linear mappings. Activation functions decide the non-linearity: the sigmoid squashes values between 0 and 1 but can saturate and slow learning, the hyperbolic tangent squashes between minus 1 and 1, and ReLU outputs the input if positive and zero otherwise, which is simple and widely used but can leave units permanently inactive, the dying ReLU problem. Training uses backpropagation: a forward pass computes predictions, a loss function measures error, and gradients are propagated backwards through the network by the chain rule, telling each weight how much it contributed to the error; gradient descent then adjusts each weight slightly against its gradient, with the learning rate controlling the step size. Too large a learning rate overshoots, too small learns slowly. Deep learning simply means networks with many layers, which can learn hierarchical features from raw data, at the cost of needing large datasets and heavy computation.

NLP & expert systems

Natural language processing must turn strings of characters into meaning, and ambiguity appears at every level. Tokenisation splits text into tokens, usually words and punctuation; it is not trivial, because punctuation, contractions, and multi-word names need rules or learned models. Normalisation may lower-case text and remove stop words, and stemming chops words to a root form, so running and runs both become run, while lemmatisation maps words to their dictionary form using vocabulary knowledge, so better becomes good. Morphological analysis handles prefixes, suffixes, and inflections. Syntactic analysis, or parsing, assigns grammatical structure: a sentence is broken into phrases such as noun phrases and verb phrases according to a grammar, and a parse tree shows that structure. Semantic analysis then assigns meaning, resolving word senses: bank can mean a river edge or a financial institution, and only context decides. Pragmatic analysis considers the speaker intent and context beyond the sentence itself. Ambiguity is therefore classified as lexical, when a word has several meanings; syntactic, when a sentence has several parse trees, as in a sentence about seeing a person with a telescope; semantic, when scope or reference is unclear; and pragmatic, when the intended speech act is unclear. Classical NLP used rules and grammars; statistical and neural methods learn patterns from large text collections, and modern language models predict and generate text from context, but the underlying pipeline of tokenise, analyse, and interpret remains the right way to think about exam questions on NLP stages.

An expert system captures the knowledge of a human specialist for a narrow domain and applies it to new cases. Its architecture has four main parts. The knowledge base stores facts and rules, often as if-then rules elicited from the expert. The inference engine applies those rules to the facts of a case, by forward chaining from facts toward conclusions, or by backward chaining from a hypothesised goal back to the facts needed to support it. Working memory holds the facts of the current case and intermediate conclusions. The explanation facility justifies a conclusion by showing the rules used, which matters because users must trust and check expert advice, especially in medicine or engineering. Knowledge acquisition, extracting knowledge from experts and encoding it, is the classic bottleneck: experts often find their tacit knowledge hard to state, rules can conflict, and maintaining a large rule base is expensive. Expert systems excel in narrow, well-understood domains with clear rules, and fail where knowledge is broad, tacit, or rapidly changing, which is one reason modern AI often combines rule-based components with learned models.

Uninformed search methods compared

Greedy best-first search versus A* search

Supervised versus unsupervised learning

Overfitting versus underfitting