[CS logo]

CSPP 56553 - Artificial Intelligence
Winter 2004
Assignment #1: Due January 21, 2004

Note: Please include the names of any collaborators in the submitted homework.

Problem 1: Speech Recognition as Search

A large number of interesting real world problems can be cast as search problems. Speech recognition is one such problem, and the combination of good search algorithms and dramatic increases in computing power have made speech recognition systems practical.

Search Problem Formulation

Give a rigorous formulation of speech recognition as a search problem. Specifically, give a start state, a goal test, successor function, and path cost measure.

Assume that the problem is restricted to finding the best sequence of "phonemes" (basic speech sounds) for a single sentence as part of a dictation application.

Speech Recognition Cost

There are approximately 50 distinct phonemes in the English language. Average English sentence length, in good writing style, is about 15 words. According to one source, there are an average of 7.8 phonemes per word.

How much time and space would a breadth-first search through this space consume?

Is this practical for a typical system?

Would simply switching to depth-first search resolve resource issues, if any?

Speech Recognition Search Strategies

A

Many practical speech recognition systems employ a combination of A* search and beam search to reduce the cost of searching in this space. A* requires an admissible heuristic to ensure optimal search. Suggest a heuristic for this search process. Demonstrate that it is an admissible heuristic.

B

The basic idea of beam search is to arbitrarily reduce the branching factor for difficult problems. Specifically, when a node is expanded, only the w best successors are retained and added to the queue. While often implemented as part of breadth-first search, the notion of a fixed width beam is generally applicable.

In general, A* is an optimal and optimally efficient search strategy. Is this optimality guarantee preserved in combination with beam search? Why or why not?

Problem 2: Systematic Search

Do Problem 3.9 in Artificial Intelligence: A Modern Approach (AIMA) (p. 90).

Note: Programming option: Complete the implementation in part b.

Note: NON-Programming option: Answer the question about repeated states in part B. Then substitute Problem 3.8 a and b.

Problem 3: Game Search

Do Problem 6.1 from AIMA (p. 189) To spare you some pain and agony, we have provided the search tree requested in part b. Please complete parts a,c,d and e as in the text.