Computer Science:Artificial Intelligence

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search
Merge-split-transwiki default.svg

A Wikibookian suggests that this book or chapter be merged into Artificial Intelligence.
Please discuss whether or not this merge should happen on the discussion page.

A central Artificial Intelligence wikibook has been started. Content from this book will eventually be merged into Artificial Intelligence. Please use that article's discussion page for discussion on the subject.

Contents

[edit] Introduction

While no consensual definition of Artificial Intelligence (AI) exists, AI is broadly characterized as the study of computations that allow for perception, reason and action.

We can divide the cognitive world into 3 domains - Intelligent, Normal and Below Normal. The average human being does Normal things. Intelligence is always demonstrated in NEW domains. The properties of a New domain are that the patterns in these domains are ambiguous and are incomplete. Therefore, Intelligence can be better understood as the ability to work efficiently with Incomplete, Ambiguous Patterns. Artificial Intelligence extends the computing power from an algorithmic domain to this Incomplete, Ambiguous patterns domain. (Algorithms have the property of Definiteness which cannot be satisfied in this domain.)

There are two major views of work in the field of AI: some people view AI as the quest for mechanisms, or algorithms, in which their output would be considered intelligent if performed by a human (i.e., a chess playing computer). Others view AI as a scientific discipline to understand the human mind, by modelling the cognitive processes humans go through.

With a bit of oversimplification, AI is:

  • simulated intelligent behavior
  • symbolic processing

Main techniques include:

  • rule-based or tree-based knowledge representation.
  • logic programming
  • heuristics

AI has influenced a number computer scientific areas:

  • databases
  • software engineering, include object-oriented design
  • distributed computing
  • graphics
  • user interfaces
  • simulation

[edit] Search

Search is a classical AI topic. Many AI problems reduce to searching for solutions in the problem state space. The basic idea:

  • initial state
  • apply an operator to transform state.

Example: symbolic integration

To find this integral: \int{{x^4 \over (1-x^2)^{5/2}} dx}, you can try different tricks, and not all will work.

Example: 8-puzzle

If a bunch of tiles are arranged like this:

\begin{bmatrix} 2 & 8 & 3 \\ 1 & 6 & 4 \\ 7 & \Box & 5 \end{bmatrix}

And this is the correct order:

\begin{bmatrix} 1 & 2 & 3 \\ 8 & \Box & 4 \\ 7 & 6 & 5 \end{bmatrix}

and the \Box is a blank tile you can slide around, then you can use search to figure it out. Each state will have at most four resulting states, because you can slide \Box up, left, right, and down.

[edit] Heuristic search

You can use DFS (Depth-first search) or BFS (Breadth-first search) to explore a graph, but it may require O(bm) node visits, but if you want to search more efficiently, it might be better to check out the promising leads first. With a heuristic search, at each step of the way, you use an evaluation function to choose which subtree to explore. You can think of a heuristic search like a "best-first" search.

It is important to remember that a heuristic search is best at finding a solution that is "good enough" rather than the perfect solution. Some problems are so big that finding the perfect solution is too hard.

To do a heuristic search you need an evaluation function that lets you rank your options.

[edit] Sliding tile puzzle aka 8-puzzle Example

This website has an example of a sliding tile puzzle if you are unfamiliar with what these are. Sliding tile puzzles (or 8-puzzles) provide a problem that can be solved more efficiently with a heuristic search (like A*) vs. DFS and BFS.

For the 8-puzzle, we could use this as a simple evaluation function:

f = g + w

where g is the distance from the root, and w is the number of misplaced tiles, not counting the \Box tile.

The evaluation function f = g + w would score the initial state

\begin{bmatrix} 5 & 4 & \Box \\ 6 & 1 & 8 \\ 7 & 3& 2 \end{bmatrix}

as

4 = 0 + 4

A better heuristic is known as the Manhattan distance. This heuristic value is determined by the sum of the distance for each tile from its goal location. This heuristic is admissible, such that it does not overestimate the cost to reach the goal node.

TODO: draw search tree for 8-puzzle and show heuristic search path solution, vs. DFS and BFS search solution.

The above evaluation function is just one possible guess. We could play with other evaluation functions, like:

f = g + p, where g is the same, and p is the sum of distances that each tile is from the root.

Or we could use f = g + p + 3S, where g and p are the same, and S is the sum of sequence scores Σs. s is calculated for each tile like so:

s = \begin{cases} 1, & \mbox{if the tile is the central tile} \\ 0, & \mbox{if the tile is the noncentral tile and is followed by the proper successor} \\ 2, & \mbox{if the tile is non-central and is not followed by its proper successor} \end{cases}

[edit] Tic Tac Toe and minimax

to be done later

n,mn,mn,mn

[edit] Knowledge discovery and machine learning

[edit] Probability

Example 1: tossing a coin once

ω1 = HEADS

ω2 = TAILS

\Omega = \left \{ \omega_1, \omega_2 \right \}

X(ω) can be a function like the number of heads. X(ω1) = 1, and X(ω2) = 0.

Example 2: tossing a coin twice.

\Omega = \left \{ HH, HT, TH, TT \right \}

Potential outputs from our X(ω) function:

X(\omega) = \left \{ 2, 1, 1, 0 \right \}

On to probability.

P(HH) should return the probability of getting two heads.

Often we denote P(X(ω) = x) as P(x).

[edit] Logarithms refresher

The logarithm L of a number N, in a given base B, is such that N = BL

For instance, make N = 8 and B = 2. Then, you would have L = 3, as you can see: log28 = 3

Another example:

log_2 ( \frac {1}{4} ) = log_2 ( 2^ {-2} ) = -2 log_2 ( 2^1 ) = -2

Retrieved from "http://en.wikibooks.org/wiki/Computer_Science:Artificial_Intelligence"