Blog

CSP, Pattern Recognition

Subhajit Ghosh
Bookmark and Share

What is Pattern Recognition? Why is it needed?  
Pattern Recognition is a technique of sensing a repetitive occurrence in any situation. It can be very useful in problem solving.
Say we want to count the number of x in the following diagram 
x       x       x        x       x        x        x        x         x         x
x       x       x        x       x        x        x        x         x         x 
x       x       x        x       x        x        x        x         x         x 
x       x       x        x       x        x        x        x         x         x 
x       x       x        x       x        x        x        x         x         x 
We see there is a pattern in the way the ‘x’ is placed – uniformly across all columns in every row. What would an intelligent person do? Would he count all the singleton ‘x’ beginning from the first row and ending with the last?  The answer, as you have rightly guessed, is NO. The person would count the number of ‘x’ in any row and multiply it with the number of rows. In our above figure, it should be 10 (number of x in each row) multiplied by 5 (number of rows) which gives the number of x to be equal to 50. 
For problems of much larger sizes and complexity, detecting patterns can help in finding solution faster making it an efficient one. That is why Pattern Recognition is so useful in Computational problem solving.


CSP: Constraint Satisfaction Problem

In real life problem solving and applications, we are asked to provide the best solution keeping certain constraints in mind. Let us consider an example. Each year the National Film Awards jury has to pick a certain film as the best film of that year. How would the assessing Jury arrive at a reasonably good judgement? Do they have to watch each and every single film that year? Simple logic says that if the Jury members decide to watch three films per day it will take them the whole year (India makes over a thousand films each year) to view all of them. How does one handle such a solution demanding situation?

As with all complex problems, we need to use good heuristics in this case because evaluation of all possible entity is simply infeasible. Let us say that at the outset the National Jury need to be provided a list of best fifty films that year which can possible make the final grade. Depending on the size of various regional film industries, the selection number from that industry can be fixed and local film critics/Local Jury member can allocate scores/grades and select the best from that industry. A criteria could be set that LFSR (Local Film Score Rating) should be 0.6 and above on a scale of 1.

Similarly the apex film jury can allocate NFSR (National Film Score Rating) and based on summative score of LFSR & NFSR the best film can be chosen. We may further set additional criteria that NFSR >0.7 and LFSR+NFSR>0.8. These criteria becomes essential to filter and set standards so that the winning film is worthy of the prestigious honor.

Let us assume that the decision is arrived at through the opinion of ten jury members, five at local level represented by LJ1, LJ2, LJ3, LJ4, LJ5 and five at National levels are represented by NJ1, NJ2, NJ3, NJ4 & NJ5 …

So, now we basically have to compute the following:
Maximize (LFSR+NFSR)   where   LJ1+LJ2+LJ3+LJ4+LJ5= LFSR
                                                     &      NJ1+NJ2+NJ3+NJ4+NJ5= NFSR
Subject to       (LFSR/5)> 0.6
                           (NFSR/5)> 0.7
                           ((LFSR+NFSR)/10)>0.8       
 
 
 
 

More By  :  Subhajit Ghosh

  • Views: 1443
  • Comments: 0





Name *
Email ID
 (will not be published)
Comment
Verification Code*

Can't read? Reload

Please fill the above code for verification.