Problem solving as search

Problem solving as search

Uninformed search

I/ Breath-first search
II/ Depth-first search

Depth-first search is not optimal and incomplete.

"Incomplete" means it can start down an infinite path and never return to try other possibilities.

Informed search

I/Best-first search approach

1. Greedy best-first search

"Greedy" means at each step it tries to get as close to the goal node as it can.

2. A* search

A* search tries to minimize the total estimated solution cost.

f(n)=g(n) + h(n)

h(n) represents the heuristic cost from the considering node to the goal.
g(n) represents the cost from the current node to the considering node.

A* search is both complete and optimal.

A* search is optimal if h(n) is an admissible heuristic. That means h(n) never overestimates the cost to reach the goal.

A* tends to run out of space faster than out of time as it keeps all the previous generated nodes.

Reference
Stuart Russel and Peter Norvig "Artificial intelligence: a modern approach", 2nd Ed, 2003.

Video compression

Parameters to affect digital video quality

1. Number of scan lines in each frame
2. Number of pixels in each scan line
3. Number of frames per second
4. Scanning techniques

Video compression makes use of two different compression techniques

1. Partial redundancy (intra-frame compression)
2. Temporal redundancy (inter-frame compression)

What is quadrature mirror filter (QMF) and conjugate quadrature filter (CQF)?

1. How does it work?
2. How is it designed?
3. Where is it applied?

1. The quadrature mirror filter (QMF) does not work in general. It has only two coefficients (unless the IIR filters are used).
2. The conjugate quadrature filter (CQF) can work with larger filters (usually even number of filter coefficients).

For example:

oooooo---h_1 ------- x_h_0() -------- g_1 ----
x(n)----ooooooooooooooooooooooooooooo---x(n)
oooooo---h_0 ------- x_h_1() -------- g_0 ----

Fig. Two-channel filter bank.

1. For QMF if h_0={a,b}
h_1={a,-b} is the same as h_0 but negate every other value.
g_0={a,b} is the same h_0.
g_1={-a,b} is -h_1.

2. For CQF if h_0={a,b}
h_1={b,-a} is the reversed version of h_0 and negate every other value.
g_0={b,a} is the reversed version of h_0.
g_1={-a,b} is the reversed version of h_1.

Simulated Annealing (SA) algorithms

1. Always accept the better state.
2. Accept the lower state with the probability e^(-Delta/T).
Delta = h(s_current)-h(s_new). T is the temperature parameter that is having its values decreased over each iteration.

*Note: The above algorithm tries to find the global maximum.

Properties

1. At the high temperature, there is a higher chance to accept the lower state.
2. At the low temperature, the SA algorithm behaves like greedy search.

Markov models and Hidden Markov Models (HMMs)

1. What is Markov model?

It consists of a set of states and a set of transition probabilities from one state to another.

2. How does it work? We represent the state transition probabilities in matrix form and compute the probability of the sequence as follows.

P(s1s2s3)=P(s3|s2)P(s2|s1)P(s1|start_state)

* Note: the conditional probabilities are the transition probabilities.

3. Where is it applied?

When we are given a Markov model, we can compute the probability of the sequence occurred, for example, P(s1s2s3). If we are given two models and each model represents for each class, then we can compute the probability of the sequence occurred for each class. After that, we can decide which class the sequence s1s2s3 belongs to based on the comparison of these two probabilities. The MM can be applied in speech recognition, classification of gene (DNA).

1. What is HMM?

It consists of transition probabilities; and states with the probability for each value belong to states.

2. Where is it applied? It can be applied in speech recognition.

3. How does it work?

Evolutionary algorithms

1. Select P in population.
2. Evaluate P.
3. If P satisfies the termination condition then stop
else select P' in P such that the fitness objective function achieves best.
4. Apply crossover or/and mutation operators to P' to reproduce P.
5. Go back to step 2.

Object-oriented design concepts

1. Polymorphism: a term used in object-oriented design to refer to the use of operations of the same name for a variety of purposes.

2. Inheritance: a term used in object-oriented design to refer to data and operations from the parent class used by its child classes.

3. Class: a template or pattern that defines the basic attributes, relationships and operations available to its objects.

4. Object: a container for a set of data and operations that act on this set.

5. Operation overriding: a term used in object-oriented design to refer to the situation in which a parent class provides an operation, but the inheriting child class defines its own version of that operation.

6. Overloading: a term used in object-oriented design to refer to operations in single class that have the same name. For example, two methods have the same name but different parameters.

7. Object-oriented design: a methodology that views the system as a collection of interacting objects, rather than functions, whose internal structure is hidden from the user.

8. Attribute: a characteristic or property of an object.

9. Accessor: a name for an operation that retrieves or "get" the value of an attribute.

10. Constructor: a set of instructions that creates an object and initialises its attributes.

11. Mutator: a name for an operation that provides or "sets" the value of an attribute.

12. Operation: a set of services that an object can perform.

13. Procedure-driven design: a design methodology based on the idea that the most important feature of a program is its processes or functions.

14. Data-driven design: a design methodology based on the idea that the data in a program is more stable than the processes involved.

15. Event-driven design: a design methodology based on the idea that an event can cause a program to change from one known state to another.

References
1. Lesley Anne Robertson, "Simple program design", 5th Ed, Thomson Learning, 2006.