Chapter 3: Solving Problems by Searching
This chapter deals with uninformed search algorithms.
To define a problem for searching, the following components need to be described:
1. Initial state
2. Possible actions (i.e. possible ‘paths’ from the present state)
3. Goal test (i.e. how to identify whether a particular state is a goal state)
4. Path cost
The possible actions from a state are usually given by a successor function. For s state x, Successor(x) would give a set of <p,y> pairs where p is an action from state x and y is the resulting state that can be reached by performing p.
Uninformed Searches
Breadth-first Search
BFS is poor with respect to both time and space requirements. Optimal when all step costs are equal.
Uniform cost search
Same as BFS, except that instead of the shallowest node, the one with the least path cost will be expanded next. Thus the algorithm is optimal when the step costs are not equal.
Depth-first search
Modest memory requirements. Not optimal.
Backtracking search
Same as DFS, but saves more memory by expanding only one successor instead of one. e.g. If a, b, c, d are all possible successor nodes, DFS will expand all of them and then again follow a, and come back to b once a has fully been traversed. Backtracking search will not expand all four, but will only expand a, and will remember which to expand once a has been fully traversed (i.e. node b).
Depth limited search
A depth limit is introduced to DFS to prevent it from getting ‘lost’ in a very long or infinite subtree.
Iterative deepening depth first search
Depth limited search is performed repeatedly with increasing depth limits. While this may seem excessively wasteful intuitively, it is not too wasteful, since the nodes that get expanded repeatedly are the ones at near the root of the tree, and there are less nodes near the roots than near the leaves.
In general, this is the preferred search when there is a large search space and the depth of the solution is unknown.
Bidirectional search
Two searches run simultaneously expanding both from the initial state and the goal state. Depending on the problem, searching backwards from the goal states is not always easy.
Avoiding repeated states
If an algorithm does not detect repeated states, it may end up in an infinite loop. The general strategy is to maintain a list of already expanded states (called the closed list) and check each newly expanded states against the list.
Searching with partial information
If the environment is not fully observable or deterministic, then the following types of problems occur:
1. Sensorless problems
If the agent has no sensors, then the agent cannot know it’s current state, and hence would have to make many repeated action paths to ensure that the goal state is reached regardless of it’s initial state.
2. Contingency problems
This is when the environment is partially observable or when actions are uncertain. Then after each action the agent needs to verify what effects that action has caused. Rather than planning for every possible contingency after an action, it is usually better to start acting and see which contingencies do arise.
This is called interleaving of search and execution.
A problem is called adversarial if the uncertainty is caused by the actions of another agent.
3. Exploration problems
This can be considered an extreme case of contingency problems: when the states and actions of the environment is unknown, the agent must act to discover them.
Chapter 1: Introduction
Approaches to AI
The introductory chapter starts with a four-fold categorization of the approaches that have been taken in AI:
1. Thinking like Humans
Cognitive science pretty much sums up this category. The idea is to understand how humans make intelligent decisions (using neuroscience, psychology, etc) and model it on an artificial system.
2. Acting like Humans
Here the focus is on the results produced by humans. Any approach which has as it’s aim passing the Turing test can be considered in this category. AI approaches that can be seen as attempts to completely build an ‘artificial human’ are considered to be in this group: natural language processing, knowledge representation, automated reasoning, machine learning, vision, robotics, etc.
3. Thinking Rationally
The logicist tradition occupies this category. Focus: represent knowledge, make logical inferences on it to make decisions.
4. Acting Rationally
The main approach considered in the book. Any approach that attempts to build an agent whose actions can be considered rational can be considered to be in this category.
For the first two categories of approaches, success would be measured with respect to a human – which is quite a difficult task. With the latter two approaches, it would be measured to a more well defined rationality.
In my opinion, it is important to notice that the categorization is not absolute and there is considerable overlap; particularly, the last two categories do not have a clear boundary. From one perspective, to “think rationally” is to decide how to infer the most rational action to take, and hence, category 3 is included in category 4. On the other hand, if it can be considered that any agent that makes a rational action has implicitly made a rational decision, then category 4 is included in category 3.
The book cites the following example: “For example, recoiling from a hot stove is a reflex action that is usually more successful than a slower action taken after careful deliberation”. I disagree with this example, since the decision to recoil is a rational decision, taken after inferring that there is not enough time to engage in more complex decision making and that an action must be taken as quickly as possible. i.e. The example is a case of making logical inferences with temporal logic.
Question: To which category do neural network approaches fall?
Philosophy
Since Aristotle’s syllogisms there have been attempts to create formal reasoning systems. Philosophy discusses the limits and possiblities of logic, and also of AI.
Some important terms introduced are:
1. Dualism: the idea that there is a immaterial part to the universe, that the mind is not a manifestation of the physical brain. (Was this Descartes’ big mistake?)
2. Materialism: the physical universe is all that exists.
3. Empiricism: knowledge is distilled from one’s experiences.
4. Hume’s principle of induction: general rules are aquuired by exposure to repeated association between their elements. (Is this the same as pattern recognition?)
5. Logical positivism: all knowledge can be characterised by logical theories, and all meaningful statements of that logic system can be verified or falsified. Developed by the infamous Vienna Circle.
6. Confirmation Theory: attempts to understand how to do induction; i.e. how knowledge can be aquired from experience.
One good example of how Philosphy has lended to concrete AI systems is Newell and Simons’ General Problem Solver (GPS). The basic regression planning algorithm used in GPS is none other than the one proposed by Aristotle: consider what the outcome is, and plan backwards from it – see what actions lead to the outcome, and then what actions lead to those actions, and so on.
Goal based analysis is discussed in Philosophy with respect to the question of understanding the relation between thinking and acting.
Mathematics
The contribution from mathematics can roughly be categorised into three areas:
1. Logic
While philosophy gave birth to logic, the mathematical development of logic into a formal system was what enabled it to become a strong tool that can be used for AI.
2. Computation
Decidability
This is linked to logic and number theory. Of particular interest is Hilbert’s decision problem, which questions whether it was possible to find an algorithm to decide the truth value of any logical proposition involving the natural numbers – i.e. whether there were limits to the power of effective proof procedures.
Computability
Gรถdel’s findings tell that
1) any statement expressed in first order logic that is true can be proved of it’s truth
2) first order logic is not powerful enough to capture the principle of mathematical induction needed to characterise the natural numbers
3) incompleteness theorem: any language expressive enough to capture the natural numbers fully (i.e. describe all the properties of the natural numbers) has, in that language, statements that are true, but their truth cannot be established by an algorithm. This means that some functions on the natural numbers cannot be computed by an algorithm.
Turing brought the idea of computability – that is, to find which functions can be computed and which cannot. The Church-Turing thesis presents the idea of a Turing machine that is capable of computing any computable function.
Tractability
From a practical point of view, tractability is a much more useful concept to study, because even if a function is computable theoretically, it can be practically uncomputable because the resources required increase exponentially with respect to input size. Such problems are said to be intractable.
Although it has not been proven (it is one of the remaining Millenium problems) it is generally assumed that NP-complete problems are intractable.
3. Probability
The most important contribution from probability is Bayesian analysis, borne out of Baye’s theorem which shows how probabilities change when new conditions are added to an event. Bayesian analysis forms the basis of most approaches to dealing with uncertainity in AI.
Economics
1. Decision Theory
Utility theory investiages how decisions can be made leading to a peferred outcome; utility theory combines with probability results in decision theory, where decisions made under uncertain conditions can be investigated. Here probability captures the decision maker’s environment, and it is assumed that the decision maker’s world is not affected by others.
2. Game Theory
If the decision maker also needs to consider what the other decision makers are doing, then such problems are studied in game theory.
3. Operations Research
One important contribution from OR to AI is Markovian decision processes, where a number of sequencially made decisions are studied.
Note that decision theory, game theory and operations research are fields that are difficult to classify only as either mathematics or economics, as they are a hybrid of both.
Neuroscience
Neuroscience can help in discovering how our brains manage to function as intelligent agents. Particularly the invention of fMRI has been very helpful in monitoring brain activity.
Psychology
1. Behaviourism
Behaviourism rejects mental introspection and only considers objective results of a psychological experiment. While behaviourism has helped to understand animal (non-human) behaviour, it has been less successful at understanding human behaviour.
When you look at it, this should be expected from behaviourism. Behaviourism treats the intelligent-process of the agent as a black box and looks at only the inputs (percepts from the environment) and outputs (actions of the animal). It is reasonable to assume that the function which takes place inside the black box is simple and animals and much more complex in humans. Thus it would be easy the guess the function for animals, but not for humans.
2. Cognitive Psychology
Cognitive psychology, in contrast, attempts to understand exactly the functionality that is taking place inside the brain, and does not exclude mental introspection (e.g. examining a persons beliefs and goals). Such mental introspection can be considered to be parts of a virtual representation of the world created in the brain.
Cognitive science, where cognitive psychological models are developed as computed models, thus pay a lot of attention to how the external world can be represented in an intelligent agent.
Control Theory and Cybernetics
Control theory explores how an automated system can monitor and regulate itself. Cybernetics, from an AI perspective is mainly the application of control theory to computational models of cognition to produce AI.
Due to the different areas of mathematics used in control theory and AI, there is some gap between the two fields. Control theory is built using calculus and matrix algebra, whereas AI (at least traditionally) used logic and computation. The problems of language, vision and planning, that were considered from AI perspectives, fell outside the domain of control theory due to the different mathematical tools used.
Linguistics
Chomsky introduced the idea of syntactic structures, which could capture the potential of a language so that it could be modeled computationally. This introduced linguistics to AI, resulting in the field of natural language processing. The main obstacle in NLP is understanding the context and subjec matter of the language (which is required due to the ambigious nature of human language), and thus knowledge representation is the field devoted to studying how information about the world can be captured into a computational structure so the information can be utilized by an intelligent agent.
Stuart Russell & Peter Norvig : Artificial Intelligence: A Modern Approach (2nd Edition)
In preparation for grad school this fall, I took out my Russell and Norvig text to refresh my knowledge and I decided to post my notes on this blog.
AI notes 