Page 191 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 10: Matching Techniques

AI technologies extend from the word “Technology” which stems from the Greek word “technos”, Notes
which means “art” and “skill.” A sophisticated technology is then a cumulative building of
learned and well-refined skills and processes. In the AI area, these processes have manifested
themselves in a number of well-recognized and maturing areas including Neural Networks,
Expert Systems, Automatic Speech Recognition, Genetic Algorithms, Intelligent Agents, Natural
Language Processing, Robotics, Logic Programming, and Fuzzy Logic. Each of these areas will
be examined in some depth here, but it is first important to understand that the importance of
these individual areas has changed over the last two decades. These changes have been based
upon the progress in each area, and the needs that each area meets. For example, in the early
1980s robotics was a large thrust in artificial intelligence. At that time benefits could be seen in
manufacturing applications. In the late 1990s, the blossoming of the Internet pushed the importance
of intelligent agents forward for performing routine tasks and complex searches. At the same
time, throughout the 1980s and 1990s, orders of magnitude advances in computer processing
power have allowed hurdles in speech recognition and image processing to be overcome. The
maturity of each of these technology areas also differs. Expert Systems and Automatic Speech
Recognition are among the most mature while Natural Language Processing and Intelligent
Agents remain in early stages of development. In the next few paragraphs, the basis for each of
these technologies will be reviewed. In addition examples where the technologies have been
effectively utilized will be presented.

10.1 Structures Used in Matching

In computer science, pattern matching is the act of checking a perceived sequence of tokens for
the presence of the constituents of some pattern. In contrast to pattern recognition, the match
usually has to be exact. The patterns generally have the form of either sequences or tree structures.
Uses of pattern matching include outputting the locations (if any) of a pattern within a token
sequence, to output some component of the matched pattern, and to substitute the matching
pattern with some other token sequence. Sequence patterns (e.g., a text string) are often described
using regular expressions and matched using techniques such as backtracking.
Tree patterns are used in some programming languages as a general tool to process data based
on its structure, e.g., Haskell, ML and the symbolic mathematics language Mathematica have
special syntax for expressing tree patterns and a language construct for conditional execution
and value retrieval based on it. For simplicity and efficiency reasons, these tree patterns lack
some features that are available in regular expressions. Often it is possible to give alternative
patterns that are tried one by one, which yields a powerful conditional programming construct.
Pattern matching sometimes include support for guards.

The simplest pattern in pattern matching is an explicit value or a variable.

Example: Consider a simple function definition in Haskell syntax (function parameters
are not in parentheses but are separated by spaces, = is not assignment but definition):
f 0 = 1
Here, 0 is a single value pattern. Now, whenever f is given 0 as argument the pattern matches
and the function returns 1. With any other argument, the matching and thus the function fail. As
the syntax supports alternative patterns in function definitions, we can continue the definition
extending it to take more generic arguments:
f n = n * f (n-1)
Here, the first n is a single variable pattern, which will match absolutely any argument and bind
it to name n to be used in the rest of the definition. Patterns are tried in order so the first

LOVELY PROFESSIONAL UNIVERSITY 185