2 min read

State Spaces: One general formulation of intelligent action is in terms of state space. A state contains all of the information necessary to predict the effects of an action and to determine if it is a goal state. State-space searching assumes that A state-space problem consists of

5 min read

Graph Searching: In this section, we abstract the general mechanism of searching and present it in terms of searching for paths in directed graphs. To solve a problem, first define the underlying search space and then apply a search algorithm to that search space. Many problem-solving tasks can be transformed into the problem of finding a path in a graph. Searching in graphs provides an appropriate level of abstraction within which to study simple problem solving independent of a particular domain. A (directed) graph consists of a set of nodes and a set of directed arcs between nodes. The idea is to find a path along these arcs from a start node to a goal node. The abstraction is necessary because there may be more than one way to represent a problem as a graph. Whereas the examples in this chapter are in terms of state-space searching, where nodes represent states and arcs represent actions, future chapters consider different ways to represent problems as graphs to search. Formalizing Graph Searching: A directed graph consists of

5 min read

A∗ Search: A∗ search is a combination of lowest-cost-first and best-first searches that considers both path cost and heuristic information in its selection of which path to expand. For each path on the frontier, A∗ uses an estimate of the total path cost from a start node to a goal node constrained to start along that path. It uses cost(p), the cost of the path found, as well as the heuristic function h(p), the estimated path cost from the end of p to the goal. For any path p on the frontier, define f (p) = cost(p) h(p). This is an estimate of the total path cost to follow path p then go to a goal node. If n is the node at the end of path p, this can be depicted as follows:

4 min read

A Generic Searching Algorithm: A generic algorithm to search for a solution path in a graph. The algorithm is independent of any particular search strategy and any particular graph. The intuitive idea behind the generic search algorithm, given a graph, a set of start nodes, and a set of goal nodes, is to incrementally explore paths from the start nodes. This is done by maintaining a frontier (or fringe) of paths from the start node that have been explored. The frontier contains all of the paths that could form initial segments of paths from a start node to a goal node. (See Figure 3.3 (on the next page), where the frontier is the set of paths to the gray shaded nodes.) Initially, the frontier contains trivial paths containing no arcs from the start nodes. As the search proceeds, the frontier expands into the unexplored nodes until a goal node is encountered. To expand the frontier, the searcher selects and removes a path from the frontier, extends the path with each arc leaving the last node, and adds these new paths to the frontier. A search strategy defines which element of the frontier is selected at each step. The generic search algorithm is shown in Figure 3.4. Initially, the frontier is the set of empty paths from start nodes. At each step, the algorithm advances the frontier by removing a path s0, . . . , sk from the frontier. If goal(sk) is true (i.e., sk is a goal node), it has found a solution and returns the path that was found, namely s0, . . . , sk. Otherwise, the path is extended by one more arc by finding the neighbors of sk. For every neighbor s of sk, the path s0, . . . , sk, s is added to the frontier. This step is known as expanding the node sk. This algorithm has a few features that should be noted:

3 min read

Introduction:-A typical example of a heuristic method for problem solving is the genetic approach used in what is known as genetic algorithms. Genetic algorithms solve complex combinatorial and organizational problems with many variants, by employing analogy with nature's evolution. Genetic algorithms were introduced by John Holland (1975) and further developed by him and other researchers. Nature’s diversity of species is tremendous. How does mankind evolve into the enormous variety of variants—in other words, how does nature solve the optimization problem of perfecting mankind? One answer to this question may be found in Charles Darwin's theory of evolution. The most important terms used in the genetic algorithms are analogous to the terms used to explain the evolutionary processes. They are: Genetic algorithms are usually illustrated by game problems. Such is a version of the "mastermind" game, in which one of two players thinks up a number (e.g., 001010) and the other has to find it out with a minimal number of questions. Each question is a hypothesis (solution) to which the first player replies With another number indicating the number of correctly guessed figures. This number is the criterion for the selection of the most promising or prospective variant which will take the second player to eventual success. If there is no improvement after a certain number of steps, this is a hint that a change should be introduced. Such change is called mutation. In this game success is achieved after 16 questions, which is four times faster than checking all the possible combinations, as there are 2⁶ = 64 possible variants. There is no need for mutation in this example. If it were needed, it could be introduced by changing a bit (a gene) by random selection. Mutation would have been necessary if, for example, there was 0 in the third bit of all three initial individuals, because no matter how the most prospective individuals are combined, by copying a precise part of their code we can never change this bit into 1.Mutation takes evolution out of a "dead end."

4 min read

Before proving the various properties of breadth-first search, we take on the somewhat easier job of analyzing its running time on an input graph G = (V, E). We use aggregate analysis, as we saw in Aggregate analysis. After initialization, no vertex is ever whitened, and thus the test in line 13 ensures that each vertex is enqueued at most once, and hence dequeued at most once. The operations of enqueuing and dequeuing take O(1) time, so the total time devoted to queue operations is O(V). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once. Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E). The overhead for initialization is O(V), and thus the total running time of BFS is O(V E). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G. At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph G = (V, E) from a given source vertex s ∈ V. Define the shortest-path distance δ(s, v) from s to v as the minimum number of edges in any path from vertex s to vertex v; if there is no path from s to v, then δ(s, v) = ∞. A path of length δ(s, v) from s to v is said to be a shortest path from s to v. Before showing that breadth-first search actually computes shortest-path distances, we investigate an important property of shortest-path distances. The procedure BFS builds a breadth-first tree as it searches the graph, as illustrated in Figure 22.3. The tree is represented by the π field in each vertex. More formally, for a graph G = (V, E) with source s, we define the predecessor subgraph of G as G_π = (V_π, E_π), where

3 min read

Heuristic Search: All of the search methods in the preceding section are uninformed in that they did not take into account the goal. They do not use any information about where they are trying to get to unless they happen to stumble on a goal. One form of heuristic information about which nodes seem the most promising is a heuristic function h(n), which takes a node n and returns a non-negative real number that is an estimate of the path cost from node n to a goal node. The function h(n) is an underestimate if h(n) is less than or equal to the actual cost of a lowest-cost path from node n to a goal. The heuristic function is a way to inform the search about the direction to a goal. It provides an informed way to guess which neighbor of a node will lead to a goal. There is nothing magical about a heuristic function. It must use only information that can be readily obtained about a node. Typically a trade-off exists between the amount of work it takes to derive a heuristic value for a node andhow accurately the heuristic value of a node measures the actual path cost from the node to a goal. A standard way to derive a heuristic function is to solve a simpler problem and to use the actual cost in the simplified problem as the heuristic function of the original problem. The h function can be extended to be applicable to (non-empty) paths. The heuristic value of a path is the heuristic value of the node at the end of the path. That is: h(no, . . . , nk) = h(nk) A simple use of a heuristic function is to order the neighbors that are added to the stack representing the frontier in depth-first search. The neighbors can be added to the frontier so that the best neighbor is selected first. This is known as heuristic depth-first search. This search chooses the locally best path, but it explores all paths from the selected path before it selects another path. Although it is often used, it suffers from the problems of depth-fist search. Another way to use a heuristic function is to always select a path on the frontier with the lowest heuristic value. This is called best-first search. It

6 min read

Mathematical game theory, a branch of economics, views any multi agent environment as a game, provided that the impact of each agent on the others is "significant," regardless of whether the agents are cooperative or competitive. 1 In AI, the most common games are of a rather specialized kind-what game theorists call deterministic, turn-taking, two-player, zero-sum games of perfect information (such as chess). In our terminology, this means deterministic, fully observable envirorunents in which two agents act alternately and in which the utility values at the end of the game are always equal and opposite. For example, if one player wins a game of chess, the other player necessarily loses. It is this opposition between the agents' utility functions that makes the situation adversarial. Games have engaged the intellectual faculties of humans-sometimes to an alanning degree-for as long as civilization has existed. For AI researchers, the abstract nature of games makes them an appealing subject for study. The state of a game is easy to represent, and agents are usually restricted to a small nwnber of actions whose outcomes are defined by precise rules. Physical games, such as croquet and ice hockey, have much more complicated descriptions, a much larger range of possible actions, and rather imprecise rules defining the legality of actions. With the exception of robot soccer, these physical games have not attracted much interest in the AI community. Games, tmlike most of the toy problems studied in Chapter 3, are interesting because they are too hard to solve. For example, chess has an average branching factor of about 35, and games often go to 50 moves by each player, so the search tree has about 35100 or 10154 nodes (although the search graph has "only" about 1 040 distinct nodes). Games, like the real world, therefore require the ability to make some decision even when calculating the optimal decision is infeasible. Games also penalize inefficiency severely. Whereas an implementation of A* search that is half as efficient will simply take twice as long to run to completion, a chess program that is half as efficient in using its available time probably will be beaten into the ground, other things being equal. Game-playing research has therefore spawned a number of interesting ideas on how to make the best possible use of time.

2 min read

Backtracking: We order the variables in some fashion, trying to place first the variables that are more highly constrained or with smaller ranges. This order has a great impact on the efficiency of solution algorithms and is examined elsewhere. We start assigning values to variables. We check constraint satisfaction at the earliest possible time and extend an assignment if the constraints involving the currently bound variables are satisfied. Example 2 Revisited: In our crossword puzzle we may order the variables as follows: 1ACROSS, 2DOWN, 3DOWN, 4ACROSS, 7ACROSS, 5DOWN, 8ACROSS, 6DOWN. Then we start the assignments:

4 min read

The minimax algorithm: The minimax algorithm (Figure 5.3) computes the minimax decision from the current state. It uses a simple recursive computation of the minimax values of each successor state, directly implementing the defining equations. The recursion proceeds all the way down to the leaves of the tree, and then the minimax values are backed up through the tree as the recursion unwinds. For example, in Figure 5.2, the algorithm first recurses down to the three bottomleft nodes and uses the UTILITY function on them to discover that their values are 3, 12, and 8, respectively. Then it takes the minimum of these values, 3, and returns it as the backedup value of node B. A similar process gives the backed-up values of 2 for C and 2 for D. Finally, we take the maximum of 3, 2, and 2 to get the backed-up value of 3 for the root node. The minimax algoritlun performs a complete depth-first exploration of the game tree. If the maximum depth of the tree is m and there are b legal moves at each point, then the time complexity of the minimax algoritlun is O(b m). The space complexity is O(lnn) for an algorithm that generates all actions at once, or 0( m) for an algorithm that generates actions one at a time. For real games, of course, the time cost is totally impractical, but this algorithm serves as the basis for the mathematical analysis of games and for more practical algorithms. Optimal decisions in multiplayer games: Many popular games allow more than two players. Let us examine how to extend the minimax idea to multiplayer games. This is straightforward from the technical viewpoint, but raises some interesting new conceptual issues.

5 min read

Uninformed Search Strategies: A problem determines the graph and the goal but not which path to select from the frontier. This is the job of a search strategy. A search strategy specifies which paths are selected from the frontier. Different strategies are obtained by modifying how the selection of paths in the frontier is implemented. This section presents three uninformed search strategies that do not take into account the location of the goal. Intuitively, these algorithms ignore where they are going until they find a goal and report success.

1 min read

Properties of Heuristics Dominance: h2 is said to dominate h1 iff h2(n) ≥ h1(n) for any node n. A* will expand fewer nodes on average using h2 than h1. Proof: Every node for which f(n) < C* will be expanded. Thus n is expanded whenever h(n) < f* - g(n) Since h2(n) ≥ h1(n) any node expanded using h2 will be expanded using h1. Using multiple heuristics: Suppose you have identified a number of non-overestimating heuristics for a problem: h1(n), h2(n), … , hk(n) Then max (h1(n), h2(n), … , hk(n)) is a more powerful non-overestimating heuristic. This follows from the property of dominance

5 min read

Depth-first search yields valuable information about the structure of a graph. Perhaps the most basic property of depth-first search is that the predecessor subgraph G_π does indeed form a forest of trees, since the structure of the depth-first trees exactly mirrors the structure of recursive calls of DFS-VISIT. That is, u = _π[v] if and only if DFS-VISIT(v) was called during a search of u's adjacency list. Additionally, vertex v is a descendant of vertex u in the depth-first forest if and only if v is discovered during the time in which u is gray. Another important property of depth-first search is that discovery and finishing times have parenthesis structure. If we represent the discovery of vertex u with a left parenthesis "(u" and represent its finishing by a right parenthesis "u)", then the history of discoveries and finishings makes a well-formed expression in the sense that the parentheses are properly nested. For example, the depth-first search of Figure 22.5(a) corresponds to the parenthesization shown in Figure 22.5(b). Another way of stating the condition of parenthesis structure is given in the following theorem.

3 min read

N queens : Goal: Put n chess-game queens on an n x n board, with no two queens on the same row, column, or diagonal. Example: Chess board reconfigurations: Here, goal state is initially unknown but is specified by constraints that it must satisfy Hill climbing (or gradient ascent/descent) Iteratively maximize “value” of current state, by replacing it by successor state that has highest value, as long as possible. Note: minimizing a “value” function v(n) is equivalent to maximizing –v(n), thus both notions are used interchangeably. Hill climbing – example: Complete state formulation for 8 queens Successor function: move a single queen to another square in the same column Cost: number of pairs that are attacking each other. Minimization problem Hill climbing (or gradient ascent/descent) • Iteratively maximize “value” of current state, by replacing it by successor state that has highest value, as long as possible. Note: minimizing a “value” function v(n) is equivalent to maximizing –v(n), thus both notions are used interchangeably. • Algorithm: • No search tree is maintained, only the current state. • Like greedy search, but only states directly reachable from the current state are considered. • Problems:

3 min read

In a normal search problem, the optimal solution would be a sequence of actions leading to a goal state-a terminal state that is a win. In adversarial search, MIN has something to say about it. MAX therefore must find a contingent strategy, which specifies MAX's move in the initial state, then MAX's moves in the states resulting from every possible response by MIN, then MAX's moves in the states resulting from every possible response by MIN to those moves, and so on. This is exactly analogous to the AND-OR search algorithm (Figure 4.1 1) with MAX playing the role of OR and MIN equivalent to AND. Roughly speaking, an optimal strategy leads to outcomes at least as good as any other strategy when one is playing an infallible opponent. We begin by showing how to find this optimal strategy.

3 min read

Proof of Admissibility of A*: We will show that A* is admissible if it uses a monotone heuristic. A monotone heuristic is such that along any path the f-cost never decreases. But if this property does not hold for a given heuristic function, we can make the f value monotone by making use of the following trick (m is a child of n) f(m) = max (f(n), g(m) h(m)) o Let G be an optimal goal state o C* is the optimal path cost. o G2 is a suboptimal goal state: g(G2) > C* Suppose A* has selected G2 from OPEN for expansion. Consider a node n on OPEN on an optimal path to G. Thus C* ≥ f(n) Since n is not chosen for expansion over G2, f(n) ≥ f(G2) G2 is a goal state. f(G2) = g(G2) Hence C* ≥ g(G2). This is a contradiction. Thus A* could not have selected G2 for expansion before reaching the goal by an optimal path.

4 min read

Search Tree: Consider the explicit state space graph shown in the figure. One may list all possible paths, eliminating cycles from the paths, and we would get the complete search tree from a state space graph. Let us examine certain terminology associated with a search tree. A search tree is a data structure containing a root node, from where the search starts. Every node may have 0 or more children. If a node X is a child of node Y, node Y is said to be a parent of node X.

4 min read

Alpha-Beta Pruning: ALPHA-BETA pruning is a method that reduces the number of nodes explored in Minimax strategy. It reduces the time required for the search and it must be restricted so that no time is to be wasted searching moves that are obviously bad for the current player. The exact implementation of alpha-beta keeps track of the best move for each side as it moves throughout the tree. We proceed in the same (preorder) way as for the minimax algorithm. For the MIN nodes, the score computed starts with infinity and decreases with time. For MAX nodes, scores computed starts with -infinity and increase with time. The efficiency of the Alpha-Beta procedure depends on the order in which successors of a node are examined. If we were lucky, at a MIN node we would always consider the nodes in order from low to high score and at a MAX node the nodes in order from high to low score. In general it can be shown that in the most favorable circumstances the alpha-beta search opens as many leaves as minimax on a game tree with double its depth.

2 min read

Look Ahead: Forward checking checks only the constraints between the current variable and the future variables. So why not to perform full arc consistency that will further reduces the domains and removes possible conflicts? This approach is called (full) look ahead or maintaining arc consistency (MAC). The advantage of look ahead is that it detects also the conflicts between future variables and therefore allows branches of the search tree that will lead to failure to be pruned earlier than with forward checking. Also as with forward checking, whenever a new variable is considered, all its remaining values are guaranteed to be consistent with the past variables, so the checking an assignment against the past assignments is no necessary.

3 min read

Iterative-Deepening A* IDA* Algorithm: Iterative deepening A* or IDA* is similar to iterative-deepening depth-first, but with the following modifications: The depth bound modified to be an f-limit 1. Start with limit = h(start) 2. Prune any node if f(node) > f-limit 3. Next f-limit=minimum cost of any node pruned The cut-off for nodes expanded in an iteration is decided by the f-value of the nodes.\ Consider the graph in Figure 3. In the first iteration, only node a is expanded. When a is expanded b and e are generated. The f value of both are found to be 15. For the next iteration, a f-limit of 15 is selected, and in this iteration, a, b and c are expanded. This is illustrated in Figure 4.

2 min read

Greedy Search In greedy search, the idea is to expand the node with the smallest estimated cost to reach the goal. We use a heuristic function f(n) = h(n) h(n) estimates the distance remaining to a goal. Greedy algorithms often perform very well. They tend to find good solutions quickly, although not always optimal ones. The resulting algorithm is not optimal. The algorithm is also incomplete, and it may fail to find a solution even if one exists. This can be seen by running greedy search on the following example. A good heuristic for the route-finding problem would be straight-line distance to the goal. Figure 2 is an example of a route finding problem. S is the starting state, G is the goal state.

3 min read

Search Graphs: If the search space is not a tree, but a graph, the search tree may contain different nodes corresponding to the same state. It is easy to consider a pathological example to see that the search space size may be exponential in the total number of states. In many cases we can modify the search algorithm to avoid repeated state expansions. The way to avoid generating the same state again when not required, the search algorithm can be modified to check a node when it is being generated. If another node corresponding to the state is already in OPEN, the new node should be discarded. But what if the state was in OPEN earlier but has been removed and expanded? To keep track of this phenomenon, we use another list called CLOSED, which records all the expanded nodes. The newly generated node is checked with the nodes in CLOSED too, and it is put in OPEN if the corresponding state cannot be found in CLOSED. This algorithm is outlined below: Graph search algorithm

2 min read

Introduction: We have outlined the different types of search strategies. In the earlier chapter we have looked at different blind search strategies. Uninformed search methods lack problem-specific knowledge. Such methods are prohibitively inefficient in many cases. Using problem-specific knowledge can dramatically improve the search speed. In this chapter we will study some informed search algorithms that use problem specific heuristics. Review of different Search Strategies 1. Blind Search a) Depth first search b) Breadth first search c) Iterative deepening search d) Bidirectional search 2. Informed Search Graph Search Algorithm: We begin by outlining the general graph search algorithm below. Uniform-Cost Search (UCS): We will now review a variation of breadth first search we considered before, namely Uniform cost search. To review, in uniform cost search we enqueue nodes by path cost. Let g(n) = cost of the path from the start node to the current node n.

3 min read

Bi-directional search: Suppose that the search problem is such that the arcs are bidirectional. That is, if there is an operator that maps from state A to state B, there is another operator that maps from state B to state A. Many search problems have reversible arcs. 8-puzzle, 15-puzzle, path planning etc are examples of search problems. However there are other state space search formulations which do not have this property. The water jug problem is a problem that does not have this property. But if the arcs are reversible, you can see that instead of starting from the start state and searching for the goal, one may start from a goal state and try reaching the start state. If there is a single state that satisfies the goal property, the search problems are identical. How do we search backwards from goal? One should be able to generate predecessor states. Predecessors of node n are all the nodes that have n as successor. This is the motivation to consider bidirectional search. Algorithm: Bidirectional search involves alternate searching from the start state toward the goal and from the goal state toward the start. The algorithm stops when the frontiers intersect. A search algorithm has to be selected for each half. How does the algorithm know when the frontiers of the search tree intersect? For bidirectional search to work well, there must be an efficient way to check whether a given node belongs to the other search tree. Bidirectional search can sometimes lead to finding a solution more quickly. The reason can be seen from inspecting the following figure.

2 min read

First, the algorithm AC-4 initializes its internal structures which are used to remember pairs of consistent (inconsistent) values of incidental variables (nodes) - structure Si,a. This initialization also counts "supporting" values from the domain of incindental variable - structure counter(i,j),a - and it removes those values which have no support. Once the value is removed from the domain, the algorithm adds the pair <Variable,Value> to the list Q for re-revision of affected values of corresponding variables.

2 min read

Adversarial Search: We will set up a framework for formulating a multi-person game as a search problem. We will consider games in which the players alternate making moves and try respectively to maximize and minimize a scoring function (also called utility function). To simplify things a bit, we will only consider games with the following two properties: We also consider only perfect information games. Game Trees: The above category of games can be represented as a tree where the nodes represent the current state of the game and the arcs represent the moves. The game tree consists of all possible moves for the current players starting at the root and all possible moves for the next player as the children of these nodes, and so forth, as far into the future of the game as desired. Each individual move by one player is called a "ply". The leaves of the game tree represent terminal positions as one where the outcome of the game is clear (a win, a loss, a draw, a payoff). Each terminal position has a score. High scores are good for one of the player, called the MAX player. The other player, called MIN player, tries to minimize the score. For example, we may associate 1 with a win, 0 with a draw and -1 with a loss for MAX. Example : Game of Tic-Tac-Toe

4 min read

Path Consistency (K-Consistency): Given that arc consistency is not enough to eliminate the need for backtracking, is there another stronger degree of consistency that may eliminate the need for search? The above example shows that if one extends the consistency test to two or more arcs, more inconsistent values can be removed. A graph is K-consistent if the following is true: Choose values of any K-1 variables that satisfy all the constraints among these variables and choose any Kth variable. Then there exists a value for this Kth variable that satisfies all the constraints among these K variables. A graph is strongly K-consistent if it is J-consistent for all J<=K. Node consistency discussed earlier is equivalent to strong 1-consistency and arc-consistency is equivalent to strong 2-consistency (arc-consistency is usually assumed to include node-consistency as well). Algorithms exist for making a constraint graph strongly K-consistent for K>2 but in practice they are rarely used because of efficiency issues. The exception is the algorithm for making a constraint graph strongly 3-consistent that is usually refered as path consistency. Nevertheless, even this algorithm is too hungry and a weak form of path consistency was introduced.

2 min read

Informed Search: We have seen that uninformed search methods that systematically explore the state space and find the goal. They are inefficient in most cases. Informed search methods use problem specific knowledge, and may be more efficient. At the heart of such algorithms there is the concept of a heuristic function. Heuristics: Heuristic means “rule of thumb”. To quote Judea Pearl, “Heuristics are criteria, methods or principles for deciding which among several alternative courses of action promises to be the most effective in order to achieve some goal”. In heuristic search or informed search, heuristics are used to identify the most promising search path. Example of Heuristic Function: A heuristic function at a node n is an estimate of the optimum cost from the current node to a goal. It is denoted by h(n). h(n) = estimated cost of the cheapest path from node n to a goal node Example 1: We want a path from Kolkata to Guwahati Heuristic for Guwahati may be straight-line distance between Kolkata and Guwahati h(Kolkata) = euclideanDistance(Kolkata, Guwahati) Example 2: 8-puzzle: Misplaced Tiles Heuristics is the number of tiles out of place.

3 min read

Other Memory limited heuristic search: IDA* uses very little memory Other algorithms may use more memory for more efficient search. RBFS: Recursive Breadth First Search RBFS (node: N, value: F(N), bound: B)

3 min read

Properties of Depth First Search: Let us now examine some properties of the DFS algorithm. The algorithm takes exponential time. If N is the maximum depth of a node in the search space, in the worst case the algorithm will take time O(bd). However the space taken is linear in the depth of the search tree, O(bN). Note that the time taken by the algorithm is related to the maximum depth of the search tree. If the search tree has infinite depth, the algorithm may not terminate. This can happen if the search space is infinite. It can also happen if the search space contains cycles. The latter case can be handled by checking for cycles in the algorithm. Thus Depth First Search is not complete. Depth Limited Search: A variation of Depth First Search circumvents the above problem by keeping a depth bound. Nodes are only expanded if they have depth less than the bound. This algorithm is known as depth-limited search. Depth-First Iterative Deepening (DFID): First do DFS to depth 0 (i.e., treat start node as having no successors), then, if no solution found, do DFS to depth 1, etc.

4 min read

A supervised learning agent needs to be told the correct move for each position it encounters, but such feedback is seldom available. In the absence of feedback from a teacher, an agent can learn a transition model for its own moves and can perhaps leam to predict the opponents moves, but without some feedback about what is good and what is bad, the agent will have no grounds for deciding which move to make. The agent needs to know that sometrung good has happened when it (accidentally) checkmates the opponent, and that something bad has happened when it is checkmated-or vice versa, if the game is suicide chess. This kind of feedback is called a reward, or reinforcement. In games like chess, the reinforcement is received only at the end of the game. In other environments, the rewards come more frequently. In ping-pong, each point scored can be considered a reward; when learning to crawl, any forward motion is an acruevement. Our framework for agents regards the reward as part of the input percept, but the agent must be "hardwired" to recognize that part as a reward rather than as just another sensory input. Thus, animals seem to be hardwired to recognize pain and hunger as negative rewards and pleasure and food intake as positive rewards. Reinforcement has been carefully studied by animal psychologists for over 60 years. An optimal policy is a policy that maximizes the expected total reward. The task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the envirorunent. prior knowledge of either. Imagine playing a new game whose rules you do not know; after a hundred or so moves, your opponent announces, "You lose." This is reinforcement leaming in a nutshell.

5 min read

To keep things simple, we start with the case of a passive learning agent using a state-based representation in a fully observable environment. In passive learning, the agent's policy 1r is fixed: in state 8, it always executes the action 1r(8) . Its goal is simply to learn how good the policy is-that is, to learn the utility function U'��" ( 8 ). We will use as our example the 4 x 3 world introduced in Chapter 17. Figure 21.1 shows a policy for that world and the corresponding utilities. Clearly, the passive learning task is similar to the policy evaluation task, part of the poli cy iteration algorithm described in Section 17.3. The main difference is that the passive learning agent does not know the transition model P(8' 1 8, a), which specifies the probability of reaching state 81 from state 8 after doing action a; nor does it know the reward function R( 8 ), which specifies the reward for each state. Figure 21.1 (a) A policy 1r for the 4 X 3 world; this policy happens to be optimal with rewards of R( s) = - 0.04 in the nonterminal states and no discounting. (b) The utilities of the states in the 4 X 3 world, given policy 1r

2 min read

Introduction to Bayesian Network: Lot of domain question can be answered by the joint probability distribution, but it become hard to control when number of variable increase. In fact specifying probability for atomic event requires a large amount of data and cannot be done when they are not sufficient For the fully joint distribution the individual probability of variables are needed but their independence and conditional independence among each other can greatly reduce their probabilities. So here the Bayesian Network, a type of data structure comes into the picture, which is used as a better method to represent dependencies among variables and specify more briefly any full joint probability distribution

4 min read

Decision Trees Rooted trees can be used to model problems in which a series of decisions leads to a solution. For instance, a binary search tree can be used to locate items based on a series of comparisons, where each comparison tells us whether we have located the item, or whether we should go right or left in a subtree. A rooted tree in which each internal vertex corresponds to a decision, with a subtree at these vertices for each possible outcome of the decision, is called a decision tree. The possible solutions of the problem correspond to the paths to the leaves of this rooted tree. Example 1 illustrates an application of decision trees. EXAMPLE 1 Suppose there are seven coins, all with the same weight, and a counterfeit coin that weighs less than the others. How many weighings are necessary using a balance scale to determine which of the eight coins is the counterfeit one? Give an algorithm for finding this counterfeit coin. Solution: There are three possibilities for each weighing on a balance scale. The two pans can have equal weight, the first pan can be heavier, or the second pan can be heavier. Consequently, the decision tree for the sequence of weighings is a 3-ary tree. There are at least eight leaves in the decision tree because there are eight possible outcomes (because each of the eight coins can be the counterfeit lighter coin), and each possible outcome must be represented by at least one leaf. The largest number of weighings needed to determine the counterfeit coin is the height of the decision tree. From Corollary 1 of Section 11.1 it follows that the height of the decision tree is at least log3 8 = 2. Hence, at least two weighings are needed. It is possible to determine the counterfeit coin using two weighings. The decision tree that illustrates how this is done is shown in Figure 3. THE COMPLEXITY OF COMPARISON-BASED SORTING ALGORITHMS Many different sorting algorithms have been developed. To decide whether a particular sorting algorithm is efficient, its complexity is determined. Using decision trees as models, a lower bound for the worst-case complexity of sorting algorithms that are based on binary comparisons can be found. We can use decision trees to model sorting algorithms and to determine an estimate for the worst-case complexity of these algorithms. Note that given n elements, there are n! possible orderings of these elements, because each of the n! permutations of these elements can be the correct order. The sorting algorithms studied in this book, and most commonly used sorting algorithms, are based on binary comparisons, that is, the comparison of two elements at a time. The result of each such comparison narrows down the set of possible orderings. Thus, a sorting algorithm based on binary comparisons can be represented by a binary decision tree in which each internal vertex represents a comparison of two elements. Each leaf represents one of the n! permutations of n elements.

4 min read

Supervised Learning: An abstract definition of supervised learning as follows. Assume the learner is given the following data: The aim is to predict the values of the target features for the test examples and as-yet-unseen examples. Typically, learning is the creation of a representation that can make predictions based on descriptions of the input features of new examples. If e is an example, and F is a feature, let val(e,F) be the value of feature F in example e.

5 min read

In classification, being able to correctly classify all training examples is not the problem. For example, consider the problem of predicting a Boolean feature based on a set of examples. Suppose that there were two agents P and N. Agent P claims that all of the negative examples seen were the only negative examples and that every other instance is positive. Agent N claims that the positive examples in the training set were the only positive examples and that every other instance is negative. Both of these agents correctly classify every example in the training set but disagree on every other example. Success in learning should not be judged on correctly classifying the training set but on being able to correctly classify unseen examples. Thus, the learner must generalize go beyond the specific given examples to classify unseen examples. A standard way to measure success is to divide the examples into a training set and a test set. A representation is built using the training set, and then the predictive accuracy is measured on the test set. Of course, this is only an approximation of what is wanted; the real measure is its performance on some future task.

2 min read

Semantic Networks: A semantic network is often used as a form of knowledge representation. It is a directed graph consisting of vertices which represent concepts and edges which represent semantic relations between the concepts. The following semantic relations are commonly represented in a semantic net. Example: The physical attributes of a person can be represented as in the following figure using a semantic net

3 min read

Neural Networks: Artificial neural networks are among the most powerful learning models. They have the versatility to approximate a wide range of complex functions representing multi-dimensional input-output maps. Neural networks also have inherent adaptability, and can perform robustly even in noisy environments. An Artificial Neural Network (ANN) is an information processing paradigm that is inspired by the way biological nervous systems, such as the brain, process information. The key element of this paradigm is the novel structure of the information processing system. It is composed of a large number of highly interconnected simple processing elements (neurons) working in unison to solve specific problems. ANNs, like people, learn by example. An ANN is configured for a specific application, such as pattern recognition or data classification, through a learning process. Learning in biological systems involves adjustments to the synaptic connections that exist between the neurons. This is true of ANNs as well. ANNs can process information at a great speed owing to their highly massive parallelism. Neural networks, with their remarkable ability to derive meaning from complicated or imprecise data, can be used to extract patterns and detect trends that are too complex to be noticed by either humans or other computer techniques. A trained neural network can be thought of as an "expert" in the category of information it has been given to analyse. This expert can then be used to provide projections given new situations of interest and answer "what if" questions. Other advantages include: Biological Neural Networks: Much is still unknown about how the brain trains itself to process information, so theories abound. In the human brain, a typical neuron collects signals from others through a host of fine structures called dendrites. The neuron sends out spikes of electrical activity through a long, thin stand known as an axon, which splits into thousands of branches. At the end of each branch, a structure called a synapse converts the activity from the axon into electrical effects that inhibit or excite activity from the axon into electrical effects that inhibit or excite activity in the connected neurones. When a neuron receives excitatory input that is sufficiently large compared with its inhibitory input, it sends a spike of electrical activity down its axon. Learning occurs by changing the effectiveness of the synapses so that the influence of one neuron on another changes.

2 min read

Naive Bayes models: Probably the most common Bayesian network model used in machine learning is the naive Bayes model. In this model, the “class” variable C (which is to be predicted) is the root and the “attribute” variables Xi are the leaves. The model is “naive” because it assumes that the attributes are conditionally independent of each other, given the class. (The model in Figure 20.2(b) is a naive Bayes model with just one attribute.) Assuming Boolean variables, the parameters are The maximum-likelihood parameter values are found in exactly the same way as for Figure 20.2(b). Once the model has been trained in this way, it can be used to classify new examples for which the class variable C is unobserved. With observed attribute values x1; : : : ; xn, the probability of each class is given by

2 min read

Inference in a Semantic Net: Basic inference mechanism: follow links between nodes. Two methods to do this: Intersection search -- the notion that spreading activation out of two nodes and finding their intersection finds relationships among objects. This is achieved by assigning a special tag to each visited node. Many advantages including entity-based organisation and fast parallel implementation. However very structured questions need highly structured networks. Inheritance -- the isa and instance representation provide a mechanism to implement this. Inheritance also provides a means of dealing with default reasoning. E.g. we could represent:

2 min read

Artificial Neural Networks: Artificial neural networks are represented by a set of nodes, often arranged in layers, and a set of weighted directed links connecting them. The nodes are equivalent to neurons, while the links denote synapses. The nodes are the information processing units and the links acts as communicating media. There are a wide variety of networks depending on the nature of information processing carried out at individual nodes, the topology of the links, and the algorithm for adaptation of link weights. Some of the popular among them include: Perceptron: This consists of a single neuron with multiple inputs and a single output. It has restricted information processing capability. The information processing is done through a transfer function which is either linear or non-linear.

4 min read

Review of Probability Theory: The primitives in probabilistic reasoning are random variables. Just like primitives in Propositional Logic are propositions. A random variable is not in fact a variable, but a function from a sample space S to another space, often the real numbers. For example, let the random variable Sum (representing outcome of two die throws) be defined thus: Sum(die1, die2) = die1 die2 Each random variable has an associated probability distribution determined by the underlying distribution on the sample space Continuing our example : P(Sum = 2) = 1/36, P(Sum = 3) = 2/36, . . . , P(Sum = 12) = 1/36

1 min read

Decision Tree Construction: There are different ways to construct trees from data. We will concentrate on the top-down, greedy search approach: Basic idea: 1. Choose the best attribute a* to place at the root of the tree. Saperate training set D into subsets {D1, D2.......... , Dk} where each subsets Di containing examples having the same value for a*

1 min read

e.g If we know that Fred is a bird we might deduce that Fred can fly. Later we might discover that Fred is an emu. The following properties should be possessed by a knowledge representation system. Representational Adequacy -- the ability to represent the required knowledge; Inferential Adequacy - the ability to manipulate the knowledge represented to produce new knowledge corresponding to that inferred from the original;

2 min read

Probabilistic Reasoning: Using logic to represent and reason we can represent knowledge about the world with facts and rules, like the following ones: bird(tweety). fly(X) :- bird(X). We can also use a theorem-prover to reason about the world and deduct new facts about the world, for e.g., ?- fly(tweety). Yes However, this often does not work outside of toy domains - non-tautologous certain rules are hard to find.

2 min read

Learning hidden Markov models: Our final application of EM involves learning the transition probabilities in hidden Markov models (HMMs). Recall from Chapter 15 that a hidden Markov model can be represented by a dynamic Bayes net with a single discrete state variable, as illustrated in Figure 20.11. Each data point consists of an observation sequence of finite length, so the problem is to learn the transition probabilities from a set of observation sequences (or possibly from just one long sequence). We have already worked out how to learn Bayes nets, but there is one complication: in Bayes nets, each parameter is distinct; in a hidden Markov model, on the other hand, the individual transition probabilities from state i to state j at time t, ijt =P(Xt 1 =jjXt =i), are repeated across time—that is, ijt =ij for all t. To estimate the transition probability from state i to state j, we simply calculate the expected proportion of times that the system undergoes a transition to state j when in state i: Again, the expected counts are computed by any HMM inference algorithm. The forward– backward algorithm shown in Figure 15.4 can be modified very easily to compute the necessary probabilities. One important point is that the probabilities required are those obtained by smoothing rather than filtering; that is, we need to pay attention to subsequent evidence in estimating the probability that a particular transition occurred. As we said in Chapter 15, the evidence in a murder case is usually obtained after the crime (i.e., the transition from state i to state j) occurs.

3 min read

Frames: Frames are descriptions of conceptual individuals. Frames can exist for "real" objects such as "The Watergate Hotel" sets of objects such as "Hotels", or more "abstract" objects such as "Cola-Wars" or "Watergate". A Frame system is a collection of objects. Each object contains a number of slots. A slot represents an attribute. Each slot has a value. The value of an attribute can be another object. Each object is like a C struct. The struct has a name and contains a bunch of named values (which can be pointers) Frames are essentially defined by their relationships with other frames. Relationships between frames are represented using slots. If a frame f is in a relationship r to a frame g, then we put the value g in the r slot of f. For example, suppose we are describing the following genealogical tree: The frame describing Adam might look something like: Adam: sex: Male spouse: Beth child: (Charles Donna Ellen)

4 min read

A supervised learning agent needs to be told the correct move for each position it encounters, but such feedback is seldom available. In the absence of feedback from a teacher, an agent can learn a transition model for its own moves and can perhaps leam to predict the opponents moves, but without some feedback about what is good and what is bad, the agent will have no grounds for deciding which move to make. The agent needs to know that sometrung good has happened when it (accidentally) checkmates the opponent, and that something bad has happened when it is checkmated-or vice versa, if the game is suicide chess. This kind of feedback is called a reward, or reinforcement. In games like chess, the reinforcement is received only at the end of the game. In other environments, the rewards come more frequently. In ping-pong, each point scored can be considered a reward; when learning to crawl, any forward motion is an acruevement. Our framework for agents regards the reward as part of the input percept, but the agent must be "hardwired" to recognize that part as a reward rather than as just another sensory input. Thus, animals seem to be hardwired to recognize pain and hunger as negative rewards and pleasure and food intake as positive rewards. Reinforcement has been carefully studied by animal psychologists for over 60 years. An optimal policy is a policy that maximizes the expected total reward. The task of reinforcement learning is to use observed rewards to learn an optimal (or nearly optimal) policy for the envirorunent. prior knowledge of either. Imagine playing a new game whose rules you do not know; after a hundred or so moves, your opponent announces, "You lose." This is reinforcement leaming in a nutshell.

2 min read

Decision Tree Pruning: Practical issues while building a decision tree can be enumerated as follows: 1) How deep should the tree be? 2) How do we handle continuous attributes? 3) What is a good splitting function? 4) What happens when attribute values are missing? 5) How do we improve the computational efficiency The depth of the tree is related to the generalization capability of the tree. If not carefully chosen it may lead to overfitting. A tree overfits the data if we let it grow deep enough so that it begins to capture “aberrations” in the data that harm the predictive power on unseen examples:

1 min read

Perceptron: Definition: It’s a step function based on a linear combination of real-valued inputs. If the combination is above a threshold it outputs a 1, otherwise it outputs a –1. A perceptron draws a hyperplane as the decision boundary over the (n-dimensional) input space.

5 min read

Introduction: The key concepts in statistical learning, are data and hypotheses. Here, the data are evidence—that is, instantiations of some or all of the random variables describing the domain. The hypotheses are probabilistic theories of how the domain works, including logical theories as a special case. Let us consider a very simple example. Our favorite Surprise candy comes in two flavors: cherry (yum) and lime (ugh). The candy manufacturer has a peculiar sense of humor and wraps each piece of candy in the same opaque wrapper, regardless of flavor. The candy is sold in very large bags, of which there are known to be five kinds—again, indistinguishable from the outside: h1: 100% cherry h2: 75% cherry 25% lime h3: 50% cherry 50% lime h4: 25% cherry 75% lime h5: 100% lime

3 min read

Problem Solving vs. Planning: A simple planning agent is very similar to problem-solving agents in that it constructs plans that achieve its goals, and then executes them. The limitations of the problem-solving approach motivates the design of planning systems. To solve a planning problem using a state-space search approach we would let the: In searches, operators are used simply to generate successor states and we can not look "inside" an operator to see how it’s defined. The goal-test predicate also is used as a "black box" to test if a state is a goal or not. The search cannot use properties of how a goal is defined in order to reason about finding path to that goal. Hence this approach is all algorithm and representation weak.

3 min read

Introduction to Learning: Machine Learning is the study of how to build computer systems that adapt and improve with experience. It is a subfield of Artificial Intelligence and intersects with cognitive science, information theory, and probability theory, among others. Classical AI deals mainly with deductive reasoning, learning represents inductive reasoning. Deductive reasoning arrives at answers to queries relating to a particular situation starting from a set of general axioms, whereas inductive reasoning arrives at general axioms from a set of particular instances. Classical AI often suffers from the knowledge acquisition problem in real life applications where obtaining and updating the knowledge base is costly and prone to errors. Machine learning serves to solve the knowledge acquisition bottleneck by obtaining the result from data by induction. Machine learning is particularly attractive in several real life problem because of the following reasons: Recently, learning is widely used in a number of application areas including,

1 min read

Candidate Elimination Algorithm: Consistency vs Coverage In the following example, h1 covers a different set of examples than h2, h2 is consistent with training set D, h1 is not consistent with training set D Version Space:

4 min read

Introduction: Our development of statistical learning methods begins with the simplest task: parameter learning with complete data. A parameter learning task involves finding the numerical parameters for a probability model whose structure is fixed. For example, we might be interested in learning the conditional probabilities in a Bayesian network with a given structure. Data are complete when each data point contains values for every variable in the probability model being learned. Complete data greatly simplify the problem of learning the parameters of a complex model. We will also look briefly at the problem of learning structure. Maximum-likelihood parameter learning: Discrete models Suppose we buy a bag of lime and cherry candy from a new manufacturer whose lime–cherry proportions are completely unknown—that is, the fraction could be anywhere between 0 and 1. In that case, we have a continuum of hypotheses. The parameter in this case, which we call , is the proportion of cherry candies, and the hypothesis is h. (The proportion of limes is just 1 - .) If we assume that all proportions are equally likely a priori, then a maximumlikelihood approach is reasonable. If we model the situation with a Bayesian network, we need just one random variable, Flavor (the flavor of a randomly chosen candy from the bag). It has values cherry and lime, where the probability of cherry is  (see Figure 20.2(a)). Now suppose we unwrap N candies, of which c are cherries and `=N - c are limes. According to Equation (3), the likelihood of this particular data set is

4 min read

Learning Bayesian networks with hidden variables: To learn a Bayesian network with hidden variables, we apply the same insights that worked for mixtures of Gaussians. Figure 20.10 represents a situation in which there are two bags of candies that have been mixed together. Candies are described by three features: in addition to the Flavor and the Wrapper, some candies have a Hole in the middle and some do not. Figure 20.9 Graphs showing the log-likelihood of the data, L, as a function of the EM iteration. The horizontal line shows the log-likelihood according to the true model. (a) Graph for the Gaussian mixture model in Figure 20.8. (b) Graph for the Bayesian network in Figure 20.10(a).

3 min read

Introduction to Planning: The purpose of planning is to find a sequence of actions that achieves a given goal when performed starting in a given state. In other words, given a set of operator instances (defining the possible primitive actions by the agent), an initial state description, and a goal state description or predicate, the planning agent computes a plan. What is a plan? A sequence of operator instances, such that "executing" them in the initial state will change the world to a state satisfying the goal state description. Goals are usually specified as a conjunction of goals to be achieved.

3 min read

Introduction:- The hidden layer allows ANN to develop its own internal representation of input-output mapping. The complex internal representation capability allows the hierarchical network to learn any mapping and not just the linearly separable ones. Algorithm for Training Network • Basic algorithm loop structure

2 min read

Introduction: The preceding section dealt with the fully observable case. Many real-world problems have hidden variables (sometimes called latent variables) which are not observable in the data that are available for learning. For example, medical records often include the observed symptoms, the treatment applied, and perhaps the outcome of the treatment, but they seldom contain a direct observation of the disease itself!6 One might ask, “If the disease is not observed, why not construct a model without it?” The answer appears in Figure 20.7, which shows a small, fictitious diagnostic model for heart disease. There are three observable predisposing factors and three observable symptoms (which are too depressing to name). Assume that each variable has three possible values (e.g., none, moderate, and severe). Removing the hidden variable from the network in (a) yields the network in (b); the total number of parameters increases from 78 to 708. Thus, latent variables can dramatically reduce the number of parameters required to specify a Bayesian network. This, in turn, can dramatically reduce the amount of data needed to learn the parameters. Hidden variables are important, but they do complicate the learning problem. In Figure 20.7(a), for example, it is not obvious how to learn the conditional distribution for HeartDisease, given its parents, because we do not know the value of HeartDisease in each case; the same problem arises in learning the distributions for the symptoms. This section

5 min read

Bayesian parameter learning: Maximum-likelihood learning gives rise to some very simple procedures, but it has some serious deficiencies with small data sets. For example, after seeing one cherry candy, the maximum-likelihood hypothesis is that the bag is 100% cherry (i.e., =1:0). Unless one’s hypothesis prior is that bags must be either all cherry or all lime, this is not a reasonable conclusion. The Bayesian approach to parameter learning places a hypothesis prior over the possible values of the parameters and updates this distribution as data arrive. The candy example in Figure 20.2(a) has one parameter, θ: the probability that a randomly selected piece of candy is cherry flavored. In the Bayesian view, θ is the (unknown) value of a random variable Θ; the hypothesis prior is just the prior distribution P(Θ). Thus, P(Θ = θ) is the prior probability that the bag has a fraction  of cherry candies. If the parameter  can be any value between 0 and 1, then P(Θ) must be a continuous distribution that is nonzero only between 0 and 1 and that integrates to 1. The uniform density P(θ) = U[0; 1](θ) is one candidate. It turns out that the uniform density is a member of the family of beta distributions. Each beta distribution is defined by two hyperparameters4 a and b such that

6 min read

Unsupervised clustering: Learning mixtures of Gaussians Unsupervised clustering is the problem of discerning multiple categories in a collection of objects. The problem is unsupervised because the category labels are not given. For example, suppose we record the spectra of a hundred thousand stars; are there different types of stars revealed by the spectra, and, if so, how many and what are their characteristics? We are all familiar with terms such as “red giant” and “white dwarf,” but the stars do not carry these labels on their hats—astronomers had to perform unsupervised clustering to identify these categories. Other examples include the identification of species, genera, orders, and so on in the Linnæan taxonomy of organisms and the creation of natural kinds to categorize ordinary objects. Unsupervised clustering begins with data. Figure 20.8(a) shows 500 data points, each of which specifies the values of two continuous attributes. The data points might correspond to stars, and the attributes might correspond to spectral intensities at two particular frequencies. Next, we need to understand what kind of probability distribution might have generated the data. Clustering presumes that the data are generated from a mixture distribution, P. Such a distribution has k components, each of which is a distribution in its own right. A data point is generated by first choosing a component and then generating a sample from that component. Let the random variable C denote the component, with values 1; : : : ; k; then the mixture

3 min read

Taxonomy of Learning Systems: Several classification of learning systems are possible based on the above components as follows: Goal/Task/Target Function:: Prediction: To predict the desired output for a given input based on previous input/output pairs. E.g., to predict the value of a stock given other inputs like market index, interest rates etc. Categorization: To classify an object into one of several categories based on features of the object. E.g., a robotic vision system to categorize a machine part into one of the categories, spanner, hammer etc based on the parts’ dimension and shape.

2 min read

Extending Semantic Nets: Here we will consider some extensions to Semantic nets that overcome a few problems or extend their expression of knowledge. Partitioned Networks Partitioned Semantic Networks allow for: Basic idea: Break network into spaces which consist of groups of nodes and arcs and regard each space as a node. Consider the following: Andrew believes that the earth is flat. We can encode the proposition the earth is flat in a space and within it have nodes and arcs the represent the fact (next figure). We can the have nodes and arcs to link this space the the rest of the network to represent Andrew's belief.

1 min read

Multi-Layer Perceptrons: In contrast to perceptrons, multilayer networks can learn not only multiple decision boundaries, but the boundaries may be nonlinear. The typical architecture of a multi-layer perceptron (MLP) is shown below. To make nonlinear partitions on the space we need to define each unit as a nonlinear function (unlike the perceptron). One solution is to use the sigmoid unit. Another reason for using sigmoids are that they are continuous unlike linear thresholds and are thus differentiable at all points.

3 min read

Perceptron Learning: Learning a perceptron means finding the right values for W. The hypothesis space of a perceptron is the space of all weight vectors. The perceptron learning algorithm can be stated as below. a. Yes. Quit b. No. Go back to Step 2. There are two popular weight update rules. i) The perceptron rule, and ii) Delta rule

5 min read

To keep things simple, we start with the case of a passive learning agent using a state-based representation in a fully observable environment. In passive learning, the agent's policy 1r is fixed: in state 8, it always executes the action 1r(8) . Its goal is simply to learn how good the policy is-that is, to learn the utility function U'��" ( 8 ). We will use as our example the 4 x 3 world introduced in Chapter 17. Figure 21.1 shows a policy for that world and the corresponding utilities. Clearly, the passive learning task is similar to the policy evaluation task, part of the poli cy iteration algorithm described in Section 17.3. The main difference is that the passive learning agent does not know the transition model P(8' 1 8, a), which specifies the probability of reaching state 81 from state 8 after doing action a; nor does it know the reward function R( 8 ), which specifies the reward for each state. Figure 21.1 (a) A policy 1r for the 4 X 3 world; this policy happens to be optimal with rewards of R( s) = - 0.04 in the nonterminal states and no discounting. (b) The utilities of the states in the 4 X 3 world, given policy 1r

3 min read

Concept Learning: Definition: The problem is to learn a function mapping examples into two classes: positive and negative. We are given a database of examples already classified as positive or negative. Concept learning: the process of inducing a function mapping input examples into a Boolean output. Examples: Example: Classifying Mushrooms Representation of instances: Features:

2 min read

Introduction: The candidate elimination algorithm keeps two lists of hypotheses consistent with the training data: (i) The list of most specific hypotheses S and, (ii) The list of most general hypotheses G. This is enough to derive the whole version space VS.

2 min read

Splitting Functions: What attribute is the best to split the data? Let us remember some definitions from information theory. A measure of uncertainty or entropy that is associated to a random variable X is defined as H(X) = - Σ pi log pi where the logarithm is in base 2. This is the “average amount of information or entropy of a finite complete probability scheme”. We will use a entropy based splitting function. Consider the previous example:

4 min read

Interleaving vs. Non-Interleaving of Sub-Plan Steps: Given a conjunctive goal, G1 ^ G2, if the steps that solve G1 must either all come before or all come after the steps that solve G2, then the planner is called a non-interleaving planner. Otherwise, the planner allows interleaving of sub-plan steps. This constraint is different from the issue of partial-order vs. total-order planners. STRIPS is a non-interleaving planner because of its use of a stack to order goals to be achieved. Partial-Order Planner (POP) Algorithm function pop(initial-state, conjunctive-goal, operators) // non-deterministic algorithm plan = make-initial-plan(initial-state, conjunctive-goal); loop: begin if solution?(plan) then return plan; (S-need, c) = select-subgoal(plan) ; // choose an unsolved goal choose-operator(plan, operators, S-need, c); // select an operator to solve that goal and revise plan resolve-threats(plan); // fix any threats created end end function solution?(plan) if causal-links-establishing-all-preconditions-of-all-steps(plan) and all-threats-resolved(plan) and all-temporal-ordering-constraints-consistent(plan) and all-variable-bindings-consistent(plan) then return true; else return false; end function select-subgoal(plan) pick a plan step S-need from steps(plan) with a precondition c that has not been achieved; return (S-need, c); end procedure choose-operator(plan, operators, S-need, c) // solve "open precondition" of some step choose a step S-add by either Step Addition: adding a new step from operators that has c in its Add-list or Simple Establishment: picking an existing step in Steps(plan) that has c in its Add-list; if no such step then return fail; add causal link "S-add --->c S-need" to Links(plan); d temporal ordering constrainS-add < S-need" to Orderings(plan); adt " if S-add is a newly added step then begin add S-add to Steps(plan); add "Start < S-add" and "S-add < Finish" to Orderings(plan); end end procedure resolve-threats(plan) foreach S-threat that threatens link "Si --->c Sj" in Links(plan) begin // "declobber" threat choose either Demotion: add "S-threat < Si" to Orderings(plan) or Promotion: add "Sj < S-threat" to Orderings(plan); if not(consistent(plan)) then return fail; end

1 min read

Planning as Search: There are two main approaches to solving planning problems, depending on the kind of search space that is explored: Situation-Space Search: In situation space search

2 min read

Interpreting frames: A frame system interpreter must be capable of the following in order to exploit the frame slot representation: Access Paths One advantage of a frame based representation is that the (conceptual) objects related to a frame can be easily accessed by looking in a slot of the frame (there is no need, for example, to search the entire knowledge-base). We define an access path, in a network of frames, as a sequence of frames each directly accessible from (i.e. appearing in a slot of) its predecessor. A sequence of predicates defines an access path iff any variable appearing as the first argument to a predicate has appeared previously in the sequence. For example, ``John's parent's sister'' can be expressed in Algernon as the path:

3 min read

Logic Based Planning Situation Calculus: Situation calculus is a version of first-order-logic (FOL) that is augmented so that it can reason about actions in time. Example: The action "agent-walks-to-location-y" could be represented by: (Ax)(Ay)(As)(at(Agent,x,s) -> at(Agent,y,result(walk(y),s))

2 min read

Total-Order vs. Partial-Order Planners: Any planner that maintains a partial solution as a totally ordered list of steps found so far is called a total-order planner, or a linear planner. Alternatively, if we only represent partial-order constraints on steps, then we have a partial-order planner, which is also called a non-linear planner. In this case, we specify a set of temporal constraints between pairs of steps of the form S1 < S2 meaning that step S1 comes before, but not necessarily immediately before, step S2. We also show this temporal constraint in graph form as S1 > S2 STRIPS is a total-order planner, as are situation-space progression and regression planners Partial-order planners exhibit the property of least commitment because constraints ordering steps will only be inserted when necessary. On the other hand, situation-space progression planners make commitments about the order of steps as they try to find a solution and therefore may make mistakes from poor guesses about the right order of steps.

3 min read

Algorithm to Find a Maximally-Specific Hypothesis: Algorithm to search the space of conjunctions: Algorithm: For each value a in h If example X and h agree on a, do nothing Else generalize a by the next more general constraint 3. Output hypothesis h

4 min read

Simple Sock/Shoe Example: In the following example, we will show how the planning algorithm derives a solution to a problem that involves putting on a pair of shoes. In this problem scenario, Pat is walking around his house in his bare feet. He wants to put some shoes on to go outside. Note: There are no threats in this example and therefore is no mention of checking for threats though it a necessary step To correctly represent this problem, we must break down the problem into simpler, more atomic states that the planner can recognize and work with. We first define the Start operator and the Finish operator to create the minimal partial order plan. As mentioned before, we must simplify and break down the situation into smaller, more appropriate states. The Start operator is represented by the effects: ~LeftSockOn, ~LeftShoeOn, ~RightSockOn, and ~RightShoeOn. The Finish operator has the preconditions that we wish to meet: LeftShoeOn and RightShoeOn. Before we derive a plan that will allow Pat to reach his goal (i.e. satisfying the condition of having both his left and right shoe on) from the initial state of having nothing on, we need to define some operators to get us there. Here are the operators that we will use and the possible state (already mentioned above).

1 min read

NOTE the following:

2 min read

Mathematical formulation of the inductive learning problem Inductive Bias Inductive Learning Framework

3 min read

Planning Systems: Classical Planners use the STRIPS (Stanford Research Institute Problem Solver) language to describe states and operators. It is an efficient way to represent planning algorithms. Representation of States and Goals: States are represented by conjunctions of function-free ground literals, that is, predicates applied to constant symbols, possibly negated. An example of an initial state is:

4 min read

Learning Bayes net structures: So far, we have assumed that the structure of the Bayes net is given and we are just trying to learn the parameters. The structure of the network represents basic causal knowledge about the domain that is often easy for an expert, or even a naive user, to supply. In some cases, however, the causal model may be unavailable or subject to dispute—for example, certain corporations have long claimed that smoking does not cause cancer—so it is important to Figure 20.6 A Bayesian network that corresponds to a Bayesian learning process. Posterior distributions for the parameter variables Θ, Θ1, and Θ2 can be inferred from their prior distributions and the evidence in the Flavor i and Wrapper i variables.

2 min read

Regression Planning Algorithm: The work through of the regression algorithm for the Blocks World example is shown below.

3 min read

Plan-Space Planning Algorithms: An alternative is to search through the space of plans rather than a space of situations. That is, we start with a simple, incomplete plan, which we call a partial plan. Then we consider ways of expanding the partial plan until we come up with a complete plan that solves the problem. We use this approach when the ordering of sub-goals affects the solution. Here one starts with a simple, incomplete plan, a partial plan, and we look at ways of expanding the partial plan until we come up with a complete plan that solves the problem. The operators for this search are operators on plans: adding a step, imposing an ordering that puts one step before another, instantiating a previously unbound variable, and so on. Therefore the solution is the final plan. Two types of operators are used:

1 min read

Concept Learning as Search: We will see how the problem of concept learning can be posed as a search problem. We will illustrate that there is a general to specific ordering inherent to any hypothesis space. Consider these two hypotheses: h1 = (red,?,?,humid,?,?) h2 = (red,?,?,?,?,?) We say h2 is more general than h1 because h2 classifies more instances than h1 and h1 is covered by h2. For example, consider the following hypotheses

2 min read

Maximum-likelihood parameter learning: Continuous models: Continuous probability models such as the linear-Gaussian model were introduced in Section 14.3. Because continuous variables are ubiquitous in real-world applications, it is important to know how to learn continuous models from data. The principles for maximumlikelihood learning are identical to those of the discrete case. Let us begin with a very simple case: learning the parameters of a Gaussian density function on a single variable. That is, the data are generated as follows: The parameters of this model are the mean µ and the standard deviation . (Notice that the normalizing “constant” depends on σ, so we cannot ignore it.) Let the observed values be x1; : : : ; xN. Then the log likelihood is

5 min read

The general form of the EM algorithm: We have seen several instances of the EM algorithm. Each involves computing expected values of hidden variables for each example and then recomputing the parameters, using the expected values as if they were observed values. Let x be all the observed values in all the examples, let Z denote all the hidden variables for all the examples, and let  be all the parameters for the probability model. Then the EM algorithm is This equation is the EM algorithm in a nutshell. The E-step is the computation of the summation, which is the expectation of the log likelihood of the “completed” data with respect to the distribution P (Z = z | x; θ⁽ⁱ⁾), which is the posterior over the hidden variables, given the data. The M-step is the maximization of this expected log likelihood with respect to the parameters. For mixtures of Gaussians, the hidden variables are the Zij s, where Zij is 1 if example j was generated by component i. For Bayes nets, the hidden variables are the values of the unobserved variables for each example. For HMMs, the hidden variables are the i!j transitions. Starting from the general form, it is possible to derive an EM algorithm for a specific application once the appropriate hidden variables have been identified.

2 min read

DEFINITION 3 Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise. Table 3 displays the truth table for p ∨ q.

2 min read

Rules of Inference: Here are some examples of sound rules of inference. Each can be shown to be sound once and for all using a truth table. The left column contains the premise sentence(s), and the right column contains the derived sentence. We write each of these derivations as A |- B , where A is the premise and B is the derived sentence. In addition to the above rules of inference one also requires a set of equivalences of propositional logic like “A /\ B” is equivalent to “B /\ A”. A number of such equivalences were presented in the discussion on propositional logic.'

2 min read

Introduction: A proposition is a sentence, written in a language, that has a truth value (i.e., it is true or false) in a world. A proposition is built from atomic propositions using logical connectives. An atomic proposition, or just an atom, is a symbol (page 114) that starts with a lower-case letter. Intuitively, an atom is something that is true or false. For example, ai is fun, lit l1, live outside, and sunny can all be atoms. In terms of the algebraic variables of the preceding chapter, an atom can be seen as a statement that a variable has a particular value or that the value is in a set of values. For example, the proposition classtimeAfter3 may mean ClassTime > 3, which is true when the variable ClassTime has value greater than 3 and is false otherwise. It is traditional in propositional calculus not to make the variable explicit and we follow that tradition. A direct connection exists to Boolean variables (page 113), which are variables with domain {true, false}. An assignment X = true is written as the proposition x, using the variable name, but in lower case. So the proposition happy can mean there exists a Boolean variable Happy, where happy means Happy = true. Propositions can be built from simpler propositions using logical connectives. A proposition is either ¬p (read “not p”)—the negation of p p ∧ q (read “p and q”)—the conjunction of p and q p ∨ q (read “p or q”)—the disjunction of p and q p → q (read “p implies q”)—the implication of q from p p ← q (read “p if q”)—the implication of p from q p ↔ q (read “p if and only if q” or “p is equivalent to q”)

3 min read

A hidden Markov model (HMM) an augmentation of the Markov chain to include observations. Just like the state transition of the Markov chain, an HMM also includes observations of the state. These observations can be partial that different states can map to the same observation and noisy that the same state can stochastically map to different observations at different times. The assumptions behind an HMM are that the state at time t 1 only depends on the state at time t, as in the Markov chain. The observation at time t only depends on the state at time t. The observations are modeled using the variable O_t for each time t whose domain is the set of possible observations. The belief network representation of an HMM is depicted in Figure 6.14. Although the belief network is shown for four stages, it can proceed indefinitely.

1 min read

Bayesian networks: A simple, graphical notation for conditional independence assertions and hence for compact specification of full joint distributions Syntax: P(Xi|Parents(Xi)) In the simplest case, conditional distribution represented as a conditional probability table (CPT) giving the distribution over Xi for each combination of parent values Example: Topology of network encodes conditional independence assertions:

4 min read

Knowledge Representation and Reasoning: Intelligent agents should have capacity for: Representation of knowledge and the reasoning process are central to the entire field of artificial intelligence. The primary component of a knowledge-based agent is its knowledge-base. A knowledge-base is a set of sentences. Each sentence is expressed in a language called the knowledge representation language. Sentences represent some assertions about the world. There must mechanisms to derive new sentences from old ones. This process is known as inferencing or reasoning. Inference must obey the primary requirement that the new sentences should follow logically from the previous ones. Logic is the primary vehicle for representing and reasoning about knowledge. Specifically, we will be dealing with formal logic. The advantage of using formal logic as a language of AI is that it is precise and definite. This allows programs to be written which are declarative - they describe what is true and not how to solve problems. This also allows for automated reasoning techniques for general purpose inferencing.

6 min read

Some Proof Strategies: From the early sixties people have looked for strategies that would simplify the search problem in theorem proving. Here are some of the strategies suggested. 1. Unit Preference: When we apply resolution if one of the premises is a unit clause (it has a single literal), the resolvent will have one less literal than the largest of the premises, thus getting closer to the desired goal {}. Thus it appears desirable to use resolution between clauses one of which is the unit clause. This unit preference is applied both when selecting from the OPEN set (i.e. at the leaves of the tree) and when we at an OR node we select an element of OTHERS to resolve with it. 2. Set of Support Strategy When we use the Set of Support Strategy we have: NEXT-OPEN(OPEN, C, {D1, .., Dp}) is the union of OPEN, {C}, and {D1,..,Dp} NEXT-OTHERS(OTHERS, C, {D1,..,Dp}) is OTHERS. In simple words, the set of support strategy uses the OPEN set as its set of support. Each application of resolution has as a premise an element of the set of support and adds that premise and the resolvent to the set of support. Usually the INITIAL set (i.e. the initial set of support) consists of all the clauses obtained by negating the intended "theorem". The set of support strategy is complete if

4 min read

Forward chaining: An alternative mode of inference in Horn clauses is forward chaining . In forward chaining, one of the resolvents in every resolution is a fact. (Forward chaining is also known as "unit resolution.") Forward chaining is generally thought of as taking place in a dynamic knowledge base, where facts are gradually added to the knowledge base Gamma. In that case, forward chaining can be implemented in the following routines.

5 min read

First Order Logic: Syntax: Let us first introduce the symbols, or alphabet, being used. Beware that there are all sorts of slightly different ways to define FOL. 1 Alphabet o Constants:

2 min read

AND/OR Trees: We will next show the use of AND/OR trees for inferencing in Horn clause systems. The problem is, given a set of axioms in Horn clause form and a goal, show that the goal can be proven from the axioms. An AND/OR tree is a tree whose internal nodes are labeled either "AND" or "OR". A valuation of an AND/OR tree is an assignment of "TRUE" or "FALSE" to each of the leaves. Given a tree T and a valuation over the leaves of T, the values of the internal nodes and of T are defined recursively in the obvious way: The above is an unconstrained AND/OR tree. Also common are constrained AND/OR trees, in which the leaves labeled "TRUE" must satisfy some kind of constraint. A solution to a constrained AND/OR tree is a valuation that satisfies the constraint and gives the tree the value "TRUE".

5 min read

Semantics: Before we can continue in the "syntactic" domain with concepts like Inference Rules and Proofs, we need to clarify the Semantics, or meaning, of First Order Logic. An L-Structure or Conceptualization for a language L is a structure M= (U,I), where: I(F): UxU..xU -> U and to each n-ary predicate symbol P of L a subset of UxU..xU. The set of functions (predicates) so introduced form the Functional Basis (Relational Basis) of the conceptualization. Given a language L and a conceptualization (U,I), an Assignment is a map from the variables of L to U. An X-Variant of an assignment s is an assignment that is identical to s everywhere except at x where it differs. Given a conceptualization M=(U,I) and an assignment s it is easy to extend s to map each term t of L to an individual s(t) in U by using induction on the structure of the term. Then

5 min read

Propositional Logic Inference: Let KB = { S1, S2,..., SM } be the set of all sentences in our Knowledge Base, where each Si is a sentence in Propositional Logic. Let { X1, X2, ..., XN } be the set of all the symbols (i.e., variables) that are contained in all of the M sentences in KB. Say we want to know if a goal (aka query, conclusion, or theorem) sentence G follows from KB. Model Checking: Since the computer doesn't know the interpretation of these sentences in the world, we don't know whether the constituent symbols represent facts in the world that are True or False. So, instead, consider all possible combinations of truth values for all the symbols, hence enumerating all logically distinct cases:

1 min read

Figure 5.7: An algorithm for debugging missing answers 1: procedure DebugMissing(g, KB) 2: Inputs 3: KB a knowledge base 4: g an atom: KB  g and g is true in the intended interpretation 5: Output 6: atom for which there is a clause missing 7: if there is a definite clause g ← a1 ∧ . . . ∧ ak ∈ KB such that all ai are true in the intended interpretation then 8: select ai that cannot be proved 9: DebugMissing(ai, KB) 10: else 11: return g

6 min read

Rule Based Systems: Instead of representing knowledge in a relatively declarative, static way (as a bunch of things that are true), rule-based system represent knowledge in terms of a bunch of rules that tell you what you should do or what you could conclude in different situations. A rule-based system consists of a bunch of IF-THEN rules, a bunch of facts, and some interpreter controlling the application of the rules, given the facts. Hence, this are also sometimes referred to as production systems. Such rules can be represented using Horn clause logic. There are two broad kinds of rule system: forward chaining systems, and backward chaining systems. In a forward chaining system you start with the initial facts, and keep using the rules to draw new conclusions (or take certain actions) given those facts. In a backward chaining system you start with some hypothesis (or goal) you are trying to prove, and keep looking for rules that would allow you to conclude that hypothesis, perhaps setting new subgoals to prove as you go. Forward chaining systems are primarily data-driven, while backward chaining systems are goal-driven. We'll look at both, and when each might be useful. Horn Clause Logic: There is an important special case where inference can be made substantially more focused than in the case of general resolution. This is the case where all the clauses are Horn clauses. Definition: A Horn clause is a clause with at most one positive literal.

3 min read

Pure Prolog: We are now ready to deal with (pure) Prolog, the major Logic Programming Language. It is obtained from a variation of the backward chaining algorithm that allows Horn clauses with the following rules and conventions: These rules make for very rapid processing. Unfortunately: The Pure Prolog Inference Procedure is Sound but not Complete This can be seen by example. Given we are unable to derive in Prolog that P(A,C) because we get caught in an ever deepening depth-first search. A Prolog "program" is a knowledge base Gamma. The program is invoked by posing a query Phi. The value returned is the bindings of the variables in Phi, if the query succeeds, or failure. The interpreter returns one answer at a time; the user has the option to request it to continue and to return further answers.

4 min read

Unification For example: [G(x y)/z].[A/x B/y C/w D/z] is [G(A B)/z A/x B/y C/w]. Composition is an operation that is associative and non commutative

2 min read

Propositional Definite Clauses: The language of propositional definite clauses is a sublanguage of propositional calculus that does not allow uncertainty or ambiguity. In this language, propositions have the same meaning as in propositional calculus, but not all compound propositions are allowed in a knowledge base. The syntax of propositional definite clauses is defined as follows: Note that a definite clause is a restricted form of a clause. For example, the definite clause a ← b ∧ c ∧ d. is equivalent to the clause a∨¬b∨¬c∨¬d. In general, a definite clause is equivalent to a clause with exactly one positive literal (non-negated atom). Propositional definite clauses cannot represent disjunctions of atoms (e.g., a ∨ b) or disjunctions of negated atoms (e.g., ¬c∨¬d).

3 min read

Herbrand Universe: It is a good exercise to determine for given formulae if they are satisfied/valid on specific L-structures, and to determine, if they exist, models for them. A good starting point in this task, and useful for a number of other reasons, is the Herbrand Universe for this set of formulae. Say that {F01 .. F0n} are the individual constants in the formulae [if there are no such constants, then introduce one, say, F0]. Say that {F1 .. Fm} are all the non 0-ary function symbols occurring in the formulae. Then the set of (constant) terms obtained starting from the individual constants using the non 0-ary functions, is called the Herbrand Universe for these formulae. For example, given the formula (P x A) OR (Q y), its Herbrand Universe is just {A}. Given the formulae (P x (F y)) OR (Q A), its Herbrand Universe is {A (F A) (F (F A)) (F (F (F A))) ...}. Reduction to Clausal Form: In the following we give an algorithm for deriving from a formula an equivalent clausal form through a series of truth preserving transformations. We can state an (unproven by us) theorem: Theorem: Every formula is equivalent to a clausal form We can thus, when we want, restrict our attention only to such forms. Deduction An Inference Rule is a rule for obtaining a new formula [the consequence] from a set of given formulae [the premises]. A most famous inference rule is Modus Ponens:

4 min read

Soundness, Completeness, Consistency, Satisfiability: A Logic D is Sound iff for all sets of formulae GAMMA and any formula A: A Logic D is Complete iff for all sets of formulae GAMMA and any formula A: A Logic D is Refutation Complete iff for all sets of formulae GAMMA and any formula A:

3 min read

Non-Monotonic Reasoning: First order logic and the inferences we perform on it is an example of monotonic reasoning. In monotonic reasoning if we enlarge at set of axioms we cannot retract any existing assertions or axioms. Humans do not adhere to this monotonic structure when reasoning: Default Reasoning: This is a very common from of non-monotonic reasoning. Here We want to draw conclusions based on what is most likely to be true. We have already seen examples of this and possible ways to represent this knowledge. We will discuss two approaches to do this: DO NOT get confused about the label Non-Monotonic and Default being applied to reasoning and a particular logic. Non-Monotonic reasoning is generic descriptions of a class of reasoning. Non-Monotonic logic is a specific theory. The same goes for Default reasoning and Default logic.

5 min read

Resolution: We have introduced the inference rule Modus Ponens. Now we introduce another inference rule that is particularly significant, Resolution. Since it is not trivial to understand, we proceed in two steps. First we introduce Resolution in the Propositional Calculus, that is, in a language with only truth valued variables. Then we generalize to First Order Logic. Resolution in the Propositional Calculus: In its simplest form Resolution is the inference rule: {A OR C, B OR (NOT C)} ---------------------- A OR B More in general the Resolution Inference Rule is: In symbols:

2 min read

Choice between forward and backward chaining Forward chaining is often preferable in cases where there are many rules with the same conclusions. A well-known category of such rule systems are taxonomic hierarchies. E.g. the taxonomy of the animal kingdom includes such rules as: animal(X) :- sponge(X). animal(X) :- arthopod(X). animal(X) :- vertebrate(X). ... vertebrate(X) :- fish(X). vertebrate(X) :- mammal(X) ... mammal(X) :- carnivore(X) ... carnivore(X) :- dog(X). carnivore(X) :- cat(X). ... (I have skipped family and genus in the hierarchy.) Now, suppose we have such a knowledge base of rules, we add the fact "dog(fido)" and we query whether "animal(fido)". In forward chaining, we will successively add "carnivore(fido)", "mammal(fido)", "vertebrate(fido)", and "animal(fido)". The query will then succeed immediately. The total work is proportional to the height of the hierarchy. By contast, if you use backward chaining, the query "~animal(fido)" will unify with the first rule above, and generate the subquery "~sponge(fido)", which will initiate a search for Fido through all the subdivisions of sponges, and so on. Ultimately, it searches the entire taxonomy of animals looking for Fido. In some cases, it is desirable to combine forward and backward chaining. For example, suppose we augment the above animal with features of these various categories: breathes(X) :- animal(X). ... backbone(X) :- vertebrate(X). has(X,brain) :- vertebrate(X). ... furry(X) :- mammal(X). warm_blooded(X) :- mammal(X). ... If all these rules are implemented as forward chaining, then as soon as we state that Fido is a dog, we have to add all his known properties to Gamma; that he breathes, is warm-blooded, has a liver and kidney, and so on. The solution is to mark these property rules as backward chaining and mark the hierarchy rules as forward chaining. You then implement the knowledge base with both the forward chaining algorithm, restricted to rules marked as forward chaining, and backward chaining rules, restricted to rules marked as backward chaining. However, it is hard to guarantee that such a mixed inference system will be complete.

3 min read

Soundness and Completeness: These notions are so important that there are 2 properties of logics associated with them. ``A sound inference procedure infers things that are valid consequences''

4 min read

Proof as Search: Up to now we have exhibited proofs as if they were found miraculously. We gave formulae and showed proofs of the intended results. We did not exhibit how the proofs were derived. We now examine how proofs can actually be found. In so doing we stress the close ties between theorem proving and search. A General Proof Procedure: We use binary resolution [we represent clauses as sets] and we represent the proof as a tree, the Proof Tree. In this tree nodes represent clauses. We start with two disjoint sets of clauses INITIAL and OTHERS. [NOTE 3: One may decide, instead of resolving C on its ith literal with all possible element of OTHERS, to select one compatible element of OTHERS and to resolve C with it, putting this resolvent and C back into OPEN. We would call a rule for selecting an element of OTHERS a Search Rule.] Repeat from 2

2 min read

Introduction: Backward chaining (a la Prolog) is more like finding what initial conditions form a path to your goal. At a very basic level it is a backward search from your goal to find conditions that will fulfil it. Backward chaining is used for interrogative applications (finding items that fulfil certain criteria) - one commercial example of a backward chaining application might be finding which insurance policies are covered by a particular reinsurance contract. CONCLUSIONS (HYPOTHESES) ) ASSERTIONS: The pseudocode that follows is for a naive implementation of backward chaining.

4 min read

Herbrand Revisited: We have presented the concept of Herbrand Universe HS for a set of clauses S. Here we meet the concept of Herbrand Base, H(S), for a set of clauses S. H(S) is obtained from S by considering the ground instances of the clauses of S under all the substitutions that map all the variables of S into elements of the Herbrand universe of S. Clearly, if in S occurs some variable and the Herbrand universe of S is infinite then H(S) is infinite. [NOTE: Viceversa, if S has no variables, or S has variables and possibly individual constants, but no other function symbol, then H(S) is finite. If H(S) is finite then we can, as we will see, decide if S is or not satisfiable.] [NOTE: it is easy to determine if a finite subset of H(S) is satisfiable: since it consists of ground clauses, the truth table method works now as in propositional cases.]

2 min read

Truth Maintenance Systems: A variety of Truth Maintenance Systems (TMS) have been developed as a means of implementing Non-Monotonic Reasoning Systems. Basically TMSs: Justification-Based Truth Maintenance Systems (JTMS)

4 min read

Introduction: Named after the Alan Mathison Turing - An english computer scientist and mathematician. Turing test: Abandoning the philosophical question of what it means for an artificial entity to think or have intelligence, Alan Turing developed an empirical test of artificial intelligence, which is more appropriate to the computer scientist endeavoring to implement artificial intelligence on a computer. The Turing test is an operational test; that is, it provides a concrete way to determine whether the entity is intelligent. The test involves a human interrogator who is in one room, another human being in second room, and an artificial entity in a third room. The interrogator is allowed to communicate with both the other human and the artificial entity only with a textual device such as a terminal. The interrogator is asked to distinguish the other human from the artificial entity based on answers to questions posed by the interrogator. If the interrogator cannot do this, the Turing test is passed and we say that the artificial entity is intelligent.

6 min read

Artificial intelligence (AI) is the field that studies the synthesis and analysis of computational agents that act intelligently. Let us examine each part of this definition. An agent is something that acts in an environment – it does something. Agents include worms, dogs, thermostats, airplanes, robots, humans, companies, and countries. We are interested in what an agent does; that is, how it acts. We judge an agent by its actions. An agent acts intelligently when An agent typically cannot observe the state of the world directly; it has only a finite memory and it does not have unlimited time to act. A computational agent is an agent whose decisions about its actions can be explained in terms of computation. That is, the decision can be broken down into primitive operation that can be implemented in a physical device. This computation can take many forms. In humans this computation is carried out in “wetware”; in computers it is carried out in “hardware.” Although there are some agents that are arguably not computational, such as the wind and rain eroding a landscape, it is an open question whether all intelligent agents are computational. The central scientific goal of AI is to understand the principles that make intelligent behavior possible in natural or artificial systems.

5 min read

A Brief History of AI: Throughout human history, people have used technology to model themselves. There is evidence of this from ancient China, Egypt, and Greece that bears witness to the universality of this activity. Each new technology has, in its turn, been exploited to build intelligent agents or models of mind. Clockwork, hydraulics, telephone switching systems, holograms, analog computers, and digital computers have all been proposed both as technological metaphors for intelligence and as mechanisms for modeling mind.

3 min read

Introduction:-Knowledge refers to stored information or models used by a person or machine to interpret, predict, and appropriately respond to the outside world.The primary characteristics of knowledge representation are twofold: (1) what information is actually made explicit; and (2) how the information is physically encoded for subsequent use. By the very nature of it, therefore, knowledge representation is goal directed. In real-world applications of "intelligent" machines, it can be said that a good solution depends on a good representation of knowledge. So it is with neural networks that represent a special class of intelligent machines. Typically, however, the possible forms of representation from the inputs to internal network parameters are highly diverse, which tends to make the development of a satisfactory solution by means of a neural network a real design challenge. A major task for a neural network is to learn a model of the world (environment) in which it is embedded and to maintain the model sufficiently consistent with the real world so as to achieve the specified goals of the application of interest. Knowledge of the world consists of two kinds of information:

4 min read

Typical AI problems: While studying the typical range of tasks that we might expect an “intelligent entity” to perform, we need to consider both “common-place” tasks as well as expert tasks. Examples of common-place tasks include – Recognizing people, objects. – Communicating (through natural language). – Navigating around obstacles on the streets These tasks are done matter of factly and routinely by people and some other animals. Expert tasks include: These tasks cannot be done by all people, and can only be performed by skilled specialists. Now, which of these tasks are easy and which ones are hard? Clearly tasks of the first type are easy for humans to perform, and almost all are able to master them. The second range of tasks requires skill development and/or intelligence and only some specialists can perform them well. However, when we look at what computer systems have been able to achieve to date, we see that their achievements include performing sophisticated tasks like medical diagnosis, performing symbolic integration, proving theorems and playing chess. On the other hand it has proved to be very hard to make computer systems perform many routine tasks that all humans and a lot of animals can do. Examples of such tasks include navigating our way without running into things, catching prey and avoiding predators. Humans and animals are also capable of interpreting complex sensory information. We are able to recognize objects and people from the visual image that we receive. We are also able to perform complex social functions.

2 min read

The AI Cycle: Almost all AI systems have the following components in general: Figure 1 shows the relationship between these components. An AI system has a perception component that allows the system to get information from its environment. As with human perception, this may be visual, audio or other forms of sensory information. The system must then form a meaningful and useful representation of this information internally. This knowledge representation maybe static or it may be coupled with a learning component that is adaptive and draws trends from the perceived data.

3 min read

Limits of AI Today: Today’s successful AI systems operate in well-defined domains and employ narrow, specialized knowledge. Common sense knowledge is needed to function in complex, open-ended worlds. Such a system also needs to understand unconstrained natural language. However these capabilities are not yet fully present in today’s intelligent systems. What can AI systems do: Today’s AI systems have been able to achieve limited success in some of these tasks. Limitations of Artificial Intelligence: The ultimate goal of research in AI and Robotics is to produce an android which can interact meaningfully with human beings. A huge amount of research effort is being exerted in order to achieve this aim and a lot of progress has already been made. Researchers have manufactured androids that can walk on two legs, that can climb stairs, that can grasp objects without breaking or dropping them, that can recognise faces and a variety of physical objects, that can imitate what they see human beings doing and so on. It is hard to make robots that can do these things and I have no desire to belittle the scientific achievements that have already been made, but even if a robot succeeds in doing all these things as well as a human being it will still lack at least one essential human ability, namely that of learning from other people by accepting what they say and by believing what they have written. The ultimate goal of AI cannot be achieved until we have implemented in a computer system the ability to acquire information from testimony.

5 min read

Introduction: An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through effectors. A human agent has eyes, ears, and other organs for sensors, and hands, legs, mouth, and other body parts for effectors. A robotic agent substitutes cameras and infrared range finders for the sensors and various motors for the effectors. A software agent has encoded bit strings as its percepts and actions. An agent acts in an environment.

5 min read

Intelligent Agents: An Intelligent Agent must sense, must act, must be autonomous (to some extent),. It also must be rational. AI is about building rational agents. An agent is something that perceives and acts. A rational agent always does the right thing. Rationality: Perfect Rationality assumes that the rational agent knows all and will take the action that maximizes her utility. Human beings do not satisfy this definition of rationality. Rational Action is the action that maximizes the expected value of the performance measure given the percept sequence to date. However, a rational agent is not omniscient. It does not know the actual outcome of its actions, and it may not know certain aspects of its environment. Therefore rationality must take into account the limitations of the agent. The agent has too select the best action to the best of its knowledge depending on its percept sequence, its background knowledge and its feasible actions. An agent also has to deal with the expected outcome of the actions where the action effects are not deterministic. Bounded Rationality: “Because of the limitations of the human mind, humans must use approximate methods to handle many tasks.” Herbert Simon, 1972 Evolution did not give rise to optimal agents, but to agents which are in some senses locally optimal at best. In 1957, Simon proposed the notion of Bounded Rationality: that property of an agent that behaves in a manner that is nearly optimal with respect to its goals as its resources will allow. Under these promises an intelligent agent will be expected to act optimally to the best of its abilities and its resource constraints.

5 min read

Introduction: The job of AI is to design the agent program: a function that implements the agent mapping from percepts to actions. We assume this program will run on some sort of computing device, which we will call the architecture. Obviously, the program we choose has to be one that the architecture will accept and run. The architecture might be a plain computer, or it might include special-purpose hardware for certain tasks, such as processing camera images or filtering audio input. It might also include software that provides a degree of insulation between the raw computer and the agent program, so that we can program at a higher level. In general, the architecture makes the percepts from the sensors available to the program, runs the program, and feeds the program’s action choices to the effectors as they are generated. The relationship among agents, architectures, and programs can be summed up as follows: agent = architecture program Most of this book is about designing agent programs, although Chapters 24 and 25 deal directly with the architecture. Before we design an agent program, we must have a pretty good idea of the possible percepts and actions, what goals or performance measure the agent is supposed to achieve, and what sort of environment it will operate in.5 These come in a wide variety. Figure 2.3 shows the basic elements for a selection of agent types. It may come as a surprise to some readers that we include in our list of agent types some programs that seem to operate in the entirely artificial environment defined by keyboard input and character output on a screen. “Surely,” one might say, “this is not a real environment, is it?” In fact, what matters is not the distinction between “real” and “artificial” environments, but the complexity of the relationship among the behavior of the agent, the percept sequence generated by the environment, and the goals that the agent is supposed to achieve. Some “real” environments are actually quite simple. For example, a robot designed to inspect parts as they come by on a conveyer belt can make use of a number of simplifying assumptions: that the lighting is always just so, that the only thing on the conveyer belt will be parts of a certain kind, and that there are only two actions—accept the part or mark it as a reject.

3 min read

Introduction: In the simplest case of an agent reasoning about what it should do, the agent has a state-based model of the world, with no uncertainty and with goals to achieve. This is either a flat (non-hierarchical) representation or a single level of a hierarchy. The agent can determine how to achieve its goals by searching in its representation of the world state space for a way to get from its current state to a goal state. It can find a sequence of actions that will achieve its goal before it has to act in the world. This problem can be abstracted to the mathematical problem of finding a path from a start node to a goal node in a directed graph. Many other problems can also be mapped to this abstraction, so it is worthwhile to con this level of abstraction. Most of this chapter explores various algorithms for finding such paths. This notion of search is computation inside the agent. It is different from searching in the world, when it may have to act in the world, for example, an agent searching for its keys, lifting up cushions, and so on. It is also different from searching the web, which involves searching for information. Searching in this chapter means searching in an internal representation for a path to a goal.

5 min read

We will find that different aspects of driving suggest different types of agent program. We will consider four types of agent program: Simple reflex agents Agents that keep track of the world The option of constructing an explicit lookup table is out of the question. The visual input from a single camera comes in at the rate of 50 megabytes per second (25 frames per second, 1000 1000 pixels with 8 bits of color and 8 bits of intensity information). So the lookup table for an hour would be 260 60 50M entries. However, we can summarize portions of the table by noting certain commonly occurring input/output associations. For example, if the car in front brakes, and its brake lights come on, then the driver should notice this and initiate braking. In other words, some processing is done on the visual input to establish the condition we call “The car in front is braking”; then this triggers some established connection in the agent program to the action “initiate braking”. We call such a connection a condition–action rule7 written as if car-in-front-is-braking then initiate-braking Humans also have many such connections, some of which are learned responses (as for driving) and some of which are innate reflexes (such as blinking when something approaches the eye). In the course of the book, we will see several different ways in which such connections can be learned and implemented. Figure 2.7 gives the structure of a simple reflex agent in schematic form, showing how the condition–action rules allow the agent to make the connection from percept to action. (Do not worry if this seems trivial; it gets more interesting shortly.) We use rectangles to denote

2 min read

Agent Performance: An agent function implements a mapping from perception history to action. The behaviour and performance of intelligent agents have to be evaluated in terms of the agent function. The ideal mapping specifies which actions an agent ought to take at any point in time. The performance measure is a subjective measure to characterize how successful an agent is. The success can be measured in various ways. It can be measured in terms of speed or efficiency of the agent. It can be measured by the accuracy or the quality of the solutions achieved by the agent. It can also be measured by power usage, money, etc. Examples of Agents

4 min read

Agent architectures: We will next discuss various agent architectures. Table based agent: In table based agent the action is looked up from a table based on information about the agent’s percepts. A table is simple way to specify a mapping from percepts to actions. The mapping is implicitly defined by a program. The mapping may be implemented by a rule based system, by a neural network or by a procedure. There are several disadvantages to a table based system. The tables may become very large. Learning a table may take a very long time, especially if the table is large. Such systems usually have little autonomy, as all actions are pre-determined. Percept based agent or reflex agentIn percept based agents,

3 min read

Goal-based agents: Knowing about the current state of the environment is not always enough to decide what to do. For example, at a road junction, the taxi can turn left, right, or go straight on. The right decision depends on where the taxi is trying to get to. In other words, as well as a current state description, the agent needs some sort of goal information, which describes situations that are desirable— for example, being at the passenger’s destination. The agent program can combine this with information about the results of possible actions (the same information as was used to update internal state in the reflex agent) in order to choose actions that achieve the goal. Sometimes this will be simple, when goal satisfaction results immediately from a single action; sometimes, it will be more tricky, when the agent has to consider long sequences of twists and turns to find a way to achieve the goal. Search (Chapters 3 to 5) and planning are the subfields of AI devoted to finding action sequences that do achieve the agent’s goals.

5 min read

In this section we introduced several different kinds of agents and environments. In all cases, however, the nature of the connection between them is the same: actions are done by the agent on the environment, which in turn provides percepts to the agent. First, we will describe the different types of environments and how they affect the design of agents. Then we will describe environment programs that can be used as testbeds for agent programs. Properties of environments: Environments come in several flavors. The principal distinctions to be made are as follows: Accessible vs. inaccessible. If an agent’s sensory apparatus gives it access to the complete state of the environment, then we say that the environment is accessible to that agent. An environment is effectively accessible if the sensors detect all aspects that are relevant to the choice of action. An accessible environment is convenient because the agent need not maintain any internal state to keep track of the world. Deterministic vs. nondeterministic.: If the next state of the environment is completely determined by the current state and the actions selected by the agents, then we say the environment is deterministic. In principle, an agent need not worry about uncertainty in an accessible, deterministic environment. If the environment is inaccessible, however, then it may appear to be nondeterministic. This is particularly true if the environment is complex, making it hard to keep track of all the inaccessible aspects. Thus, it is often better to think of an environment as deterministic or nondeterministic from the point of view of the agent.

2 min read

Utility-based agents: Goals alone are not really enough to generate high-quality behavior. For example, there are many action sequences that will get the taxi to its destination, thereby achieving the goal, but some are quicker, safer, more reliable, or cheaper than others. Goals just provide a crude distinction between “happy” and “unhappy” states, whereas a more general performance measure should allow a comparison of different world states (or sequences of states) according to exactly how happy they would make the agent if they could be achieved. Because “happy” does not sound very scientific, the customary terminology is to say that if one world state is preferred to another, then it has higher utility for the agent. Utility is therefore a function that maps a state9 onto a real number, which describes the associated degree of happiness. A complete specification of the utility function allows rational decisions in two kinds of cases where goals have trouble. First, when there are conflicting goals, only some of which can be achieved (for example, speed and safety), the utility function specifies the appropriate trade-off. Second, when there are several goals that the agent can aim for, none of which can be achieved with certainty, utility provides a way in which the likelihood of success can be weighed up against the importance of the goals. An agent that possesses an explicit utility function therefore can make rational decisions, but may have to compare the utilities achieved by different courses of actions. Goals, although cruder, enable the agent to pick an action right away if it satisfies the goal. In some cases, moreover, a utility function can be translated into a set of goals, such that the decisions made by a goal-based agent using those goals are identical to those made by the utility-based agent. The overall utility-based agent structure appears in Figure 2.12. Actual utility-based agent programs appear in Chapter 5, where we examine game-playing programs that must make fine distinctions among various board positions; where we tackle the general problem of designing decision-making agents.

3 min read

Regression Algorithms: In statistics, regression analysis includes any techniques for modeling and analyzing several variables, when the focus is on the relationship between a dependent variable and one or more independent variables. More specifically, regression analysis helps one understand how the typical value of the dependent variable changes when any one of the independent variables is varied, while the other independent variables are held fixed. These are statistical algorithms predicting real valued labels but having both supervised & un-supervised learning. PCA (Principle Component Analysis) Principal component analysis (PCA) is a mathematical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated variables into a set of values of uncorrelated variables called principal components. The number of principal components is less than or equal to the number of original variables. This transformation is defined in such a way that the first principal component has as high a variance as possible (that is, accounts for as much of the variability in the data as possible), and each succeeding component in turn has the highest variance possible under the constraint that it be orthogonal to (uncorrelated with) the preceding components. Principal components are guaranteed to be independent only if the data set is jointly normally distributed. PCA was invented in 1901 by Karl Pearson. Now it is mostly used as a tool in exploratory data analysis and for making predictive models.

3 min read

Natural Language Processing: Natural Language Processing (NLP) is the process of computer analysis of input provided in a human language (natural language), and conversion of this input into a useful form of representation. The field of NLP is primarily concerned with getting computers to perform useful and interesting tasks with human languages. The field of NLP is secondarily concerned with helping us come to a better understanding of human language. – written text – speech – lexical, syntactic, semantic knowledge about the language – discourse information, real world knowledge

1 min read

Clustering Algorithms KPCA (Kernel Principle Component Analysis): Kernel principal component analysis (kernel PCA) is an extension of principal component analysis (PCA) using techniques of kernel methods. Using a kernel, the originally linear operations of PCA are done in a reproducing kernel Hilbert space with a non-linear mapping. Kernel PCA has been demonstrated to be useful for novelty detection and image de-noising K-means Clustering: K-means clustering is a method of cluster analysis which aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean.

4 min read

Classification Algorithms: Classification algorithms are Statistical algorithms, having supervised learning and predicting categorical labels. Following are the few types of classification algorithms: Support Vector Machines: A Support Vector Machine (SVM) performs classification by constructing an N-dimensional hyper plane that optimally separates the data into two categories. A support vector machine (SVM) is a concept in computer science for a set of related supervised learning methods that analyze data and recognize patterns, used for classification and regression analysis. The standard SVM takes a set of input data and predicts, for each given input, which of two possible classes the input is a member of, which makes the SVM a non-probabilistic binary linear classifier. Given a set of training examples, each marked as belonging to one of two categories, an SVM training algorithm builds a model that assigns new examples into one category or the other. An SVM model is a representation of the examples as points in space, mapped so that the examples of the separate categories are divided by a clear gap that is as wide as possible.

4 min read

Pattern Recognition Methodologies: There are four major methodologies in pattern recognition; these are statistical approach, syntactic approach, template matching & neural network. Statistical Approach: Typically, statistical pattern recognition systems are based on statistics and probabilities. In these systems, features are converted to numbers which are placed into a vector to represent the pattern. This approach is most intensively used in practice because it is the simplest to handle. In this approach, patterns to be classified are represented by a set of features defining a specific multidimensional vector: by doing so, each pattern is represented by a point in the multidimensional features space. To compare patterns, this approach uses measures by observing distances between points in this statistical space. Syntactic Approach: Also called structural pattern recognition systems, these systems are based on the relation between features. In this approach, patterns are represented by structures which can take into account more complex relations between features than numerical feature vectors used in statistical PRSs. Patterns are described in hierarchical structure composed of sub-structures composed themselves of smaller sub-structures. The shape is represented with a set of predefined primitives called the codebook and the primitives are called code words. For example, given the code words on the left of figure, the shape on the right of the figure can be represented as the following string S, when starting from the pointed codeword on the figure:

2 min read

Pattern Recognition Algorithms For pattern recognition, various researches & various algorithms have been proposed. The types of pattern recognition are governed by its design cycle. As we know, it consists of basic elements like “visual perception”, “feature extraction” & “classification”. There are various different techniques and algorithms to implement these basic elements. So what technique is chosen for each element in design cycle tells the algorithm characteristic of pattern recognition. Algorithms for pattern recognition depend on the type of label output, on whether learning is supervised or unsupervised, and whether the algorithm is statistical or non-statistical in nature. Statistical algorithm can be further categorized as generative or discriminative. Before going various types of algorithms, let first understand few definitions.

3 min read

Introduction: In Artificial Intelligence Science, Machine Perception is defined as the ability of machine to process visual input data and deduce the aspects of world. Having capability of analyzing visual input data from input device like camera and having capability of making decision on input visual data, gives birth to “PATTERN RECOGNITION SYSTEM” on machines, which is the biggest trait of Human beings. Human ability to recognize patterns is remarkable. A Human can recognize face out of thousand faces, irrespective of varying illumination intensity, varying facial rotation, varying facial expressions, varying facial biometrical changes, varying facial scaling and even with occluded face images. Pattern Recognition is still an ongoing wide research study, which tries to make machine as intelligent as human being for recognizing patterns. Before understanding the system and related algorithms, let’s first understand the basic definitions. Pattern: A pattern is defined by the common denominator among the multiple instances of an entity. For example, commonality in all fingerprint images defines the fingerprint pattern; thus, a pattern could be a fingerprint image, a handwritten cursive word, a human face, a speech signal, a bar code, or a web page on the Internet.

1 min read

Natural Language Understanding The steps in natural language understanding are as follows:

1 min read

Natural Language Generation: The steps in natural language generation are as follows.

3 min read

Usage & Application: Pattern recognition is used in any area of science and engineering that studies the structure of observations. It is now frequently used in many applications in manufacturing industry, health care and military. Examples include: Example of pattern recognition application with its input pattern and pattern class.

1 min read

Example 2: Show that the grammar S ® S | S, S ® a is ambiguous. Solution: In order to show that G is ambiguous, we need to find a wÎL(G), which isambiguous. Assume w = abababa.

1 min read

Steps in Language Understanding and Generation: Morphological Analysis

1 min read

Sequence Labeling Algorithms: Sequence labeling is a type of pattern recognition task that involves the algorithmic assignment of a categorical label to each member of a sequence of observed values. A common example of a sequence labeling task is part of speech tagging, which seeks to assign a part of speech to each word in an input sentence or document. These types of algorithms predicting sequence of categorical labels and real valued labels. These algorithms support both supervised and un-supervised learning. Supervised Learning for categorical labels: Hidden Markov Model (HMM), Maximum Entropy Markov Model (MEMM) & Conditional Random Fields (CRF) Parsing Algorithms: Parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens (for example, words), to determine its grammatical structure with respect to a given (more or less) formal grammar. The algorithm supports both supervised & unsupervised learning and predicting tree structured labels.