Facial Recognition

Facial recognition is an interesting topic in Artificial Intelligence. In this subfield there is math being used from multiple topics, some heavy Linear Algebra and Bayesian Statistics. It is also important because facial recognition is used everywhere today, from Facebook identify your friends in a photo, to Google street view blurring out someones face. The heavy use of these algorithms brings up ethical issues, such as privacy concerns and data rights. Todays blog post however, will focus on the underlying technology that some of the algorithms are based on.

First and foremost, there must be way to mathematically break down someones face, in order to quantify it. One of the main ways this is done is through a method called principal component analysis (PCA). Without getting to much into the math, what principal component analysis does is it breaks down the face into a linear basis based off of pieces (or the features) of a humans face. By representing the face this way, you have a way of measuring the individual magnitude of the features a persons face. This allows us to have a possible unique representation of a face as a linear basis. PCA is closely related to using a Singular Valued Decomposition as a form of measurement. Note there are other methods, like independent component analysis or simply using the Eigen face (a face represented by Eigen values) that rely upon the same methodology of representing a face as a linear basis.

The second part to the aforementioned algorithms is using some sort of statistical analysis on the newly acquired linear basis.  The statistical can be some sort of Bayesian methodology, wether it be a simple Hidden Markov Model or a full featured network. Which can either be achieved though unsupervised or supervised data set processing, depending on the choice made by the developer. Like all training methods, the recogintion made by the algorithms is therefore dependent on the data sets used.

The only method I have seen found that tends to break from decomposing a face into a linear basis is a method called Dynamic Link Matching, which instead decomposes the face into a graph made by stretching the face over a 2d lattice layer by layer. However, this is still in some putting the information into layers (you could argue that is dimensions), simply this method is not concerned with maintaining orthogonality. It just creates a 'blob' which is then fed through a neural network, and has some similar statistical analysis run on it which matches it to the closest model. This method leverages the power a neural network gives simply by passing off the face as a 'blob' of information.

Some of the challenge facial recognitions has are still similar to the challenges humans have, such as poor viewing angles, improper lighting and an object obstructing someones face. This is because if you are missing any region of the face, the principal component analysis will be off. If the decomposition used is missing information about the domain, it is invalid. Only having one side of the face completely foils everything. Another thing that can throw off the principal component analysis is if someone is making a exaggerated gesture of their face. These algorithms assume that people faces are more less static, not changing very much.

Automated Planning

STRIPS was an automated planner developed at Stanford University and which paved the way for the beginnings of automated planning AI. Automated planning allows planners to make their way through an environment or a task using the same algorithm to solve completely different tasks. This can have many applications all over the world but is most commonly used for robotics.

               An automated planning algorithm needs to know certain information about the world it is functioning in to be able to plan correctly. The algorithm needs to be aware of actions that it is capable of doing. It can use these actions to choose what to do. It also needs to know what objects it is able to interact with. These objects can be chosen to be used with certain actions to be at certain states. Once the algorithm knows everything of everything around it, it can start planning for an optimal path to the goal.

Implementing these algorithms into robots is extremely helpful because it can teach robots to reach certain goals without needing a completely different algorithm to be coded for the environment it’s in. The robot just needs to know the actions that are doable in that environment and the objects it can interact with. For example, a robot working at a storage warehouse could be given the knowledge that there are boxes stacked around the warehouse and that they can be moved. If a box needs to be retrieved, the robot can go pick up the box and bring it to the destination. If the desired box is covered in a stack of other boxes, the robot must plan the best way to move the other boxes to get to the desired box. The robot will know the action of moving boxes and will know that there are boxes in the world that it can interact with.

               This same robot could then be reprogrammed to vastly different tasks. The actions and objects of this different domain would be taught to the robot. For example, the robot could have a knowledge of gardening. It could know the act of planting, watering, and weeding. It could then have a goal of always having a clean and watered garden bed. The same algorithm would be used to find the best way to plant all the seeds and watering them. The robot would also know of certain preconditions that would have to be fulfilled. For example; an area of dirt must have a seed in it for it to be watered. Or an area of dirt must have a weed in it for the robot to act in removing the weed. These algorithms can adapt to very different domains as long as they know the required objects and actions they will be dealing with. 

Expert Systems in the Business World

I was dubious about the efficacy of expert systems when we talked about them in class last week. It seemed to me that an expert system would be well suited for simple yes and no problems. Acting more as a reflex agent then something truly intelligent. I didn't see a great difference between having an expert system and having an extensive run book, or an elaborate flow diagram. Even though both of these are very useful, why bother turning them into expert systems, instead of just having them remain as searchable text.

In fact, it seemed like there would be only very special use cases where the cost of developing an expert system would be practical versus the savings it could generate. Expert systems are not simple to build at all, and require a large amount of man hours in setting up and maintaining them. Not to mention that the labor needed for them is very skilled, there is only a select subset of the population capable of programming them. In other words, you need an expert to build expert systems, and experts are expensive.

Another issue would be getting the subject matter experts to cooperate with the programmer. It would not be surprising if some experts do not want a computer to know what they know; job security is an important aspect to some people. What happens for issues where experts disagree on how a situation should be resolved, if it happens once it might not be very problematic, but if it happens continuously one experts knowledge might need to be excluded from the system. Actually getting the knowledge is out of someone's brain is a much bigger issue then we made it seem. This is known as the knowledge acquisition problem, and it actually has deeper roots as a philosophical issue.

I see an expert system as having an inherent lack of flexibility, one mistruth in the knowledge base could pollute all possible solutions. Finding these would take up most of the developers time, again leading to more overhead. Trusting a knowledge base as complete is dangerous as things can change quickly, or Simpsons Paradox could take hold in a knowledge base. There is a strong reliance on the fact that the knowledge bases can be exhaustive. Yet, after studying state spaces for half a semester, one realizes just how large "exhaustive" can mean.

Even with my skepticism expert systems have seen some interest over the last forty years. Perhaps the most intriguing application of the expert system is the multiple attempts for medical diagnosis. There is a compelling reason for experts to want to help build the system, saving lives. And any cost involved in development can be justified due to the fact saving one life outweighs any monetary cost. The question is why didn't they catch on then? I haven't been able to find any argument as to why. It isn't clear if the business reasons were at fault, or if they in fact just didn't work. Maybe the reason was that people are just distrust-worthy of a computer as a doctor.

Is Art For Humans Only?

Google's Deep Dream is amazing, if you haven't seen any of the pictures it generates I recommend checking it out. To talk about the results of Deep Dream is simple, it is psychedelic art.

Deep Dream was essentially made as a way to visualize what happens in a convolutional neural network. At the time of conception (and still now) much of what happens inside a neural network is invisible to us, a black box function analyzing data. The goal of Deep Dream was to visualize what happens by measuring change via a picture. By training it to recognize faces and classify images the neural network could output what it thought it was recognizing. However, what this led to was crazy art, Dali-esque images on landscapes and backgrounds. I could speak more here about neural networks and back propagation, but I would rather focus on another aspect of this program.

Ignoring the fact that Deep Dream doesn't actually do anything, it is still interesting as a thought exercise about what is art, and does this qualify?

In class we have had the discussion numerous times about what is intelligence and how do we classify it, and I think that art is a very poignant topic. It doesn't have a pure function for existence, it is more of an existential quest. The fact that we can have computers create art (or something close to it) is a very strong indication to me about how far artificial intelligence has come. You could argue that Deep Dream still needs a seed image, and that might not be wrong. But I think the process it follows greatly mirrors the human creative process.

The fact Deep Dream had to train on large amounts of data to be able to "create" this images is just like an artist has to train for years before they master their medium. Not to mention, years of living as a human also trains the brain in some way to process things visually. And then is having a seed image truly that different from an idea? Every artist has to start from some idea, some initial concept that motivates them to bring the brush to the canvas, or charcoal to paper. The style might be similar for every picture, but aren't all artists famous for a style they pioneered?

I think from some perspectives Deep Dream has more in common with a humans creative process then people would like to admit.

Note I don't think Deep Dream is totally there in all aspects yet; however, it is quite a significant step towards artificial intelligence. It isn't measuring things in purely in what is the lowest cost to get from A to B, instead it is actually creating something novel and interesting.

Sentiment Analysis - a brief intro

One of the more interesting challenges being posed in NLP today is sentiment analysis. Sentiment analysis is the process of using text analysis and computational linguistics to extract information about that selected piece of language. Generally, the information being extracted is being tested against a predetermined sentiment; henceforth, why it is called sentiment analysis. An example of this might be running a communication letter through an analysis machine to determine the writers feelings towards the recipient of the letter. Another example might be examining a political article to measure the authors bias; if they are left leaning or conversly if they are right leaning.

Sentiment analysis is used in today mostly by companies on strongly controlled sanitized data sets. When given an easily measurable goal, sentiment analysis shines. If company want to measure reviews based of service in restaurants and they have a larger data set, say ten thousand reviews, it is easy to pick out say a positive review like "the food was delicious, and the service was prompt", versus a negative review like "meal was bland". The company can then draw conclusions about menus and service based off of the results of the analysis. Of course, the business value of the information is in the eye of the beholder, and it largely depends on the initial collection and categorization of the data.

Some of the techniques used for sentiment analysis are: pre-weighted techniques, statistical methods, and hybrid approach of the former two. By pre-weighted, that means that words have a pre-decided value attached to them. One generally also has a knowledge base to draw from, where all the values are stored and any relations between them. While, on the other hand statistical methods use techniques like support vector machines, or latent semantic analysis. The details behind both these methods are more complex; they both rely on statistical inference to judge the classification of a word. (Note: both these methods are worthy of their own blog posts, very fascinating stuff)

One the classical problems that sentiment analysis faces is a problem all NLP has, context. To cover what context is very quickly, when speaking (or reading) any language there is always some level of an implied situation. For example, if I said "I went down to the local store", there are some implied items to the recipient of the sentence. Firstly, we both probably have an agreed idea of what local means. A computer could possibly have a pre-progammed value of what local is, but it would have to differ greatly based off of many variables. For example, local in New York city probably differs from what local is to Durham NH. In addition, what type of store it is might be clear to a human based off of previous conversation, but the machine lacks the clues inferred from the context.

High-context and low-context are both found in languages, cultures have developed efficient communication with both methods. This strongly dictates what is implied when someone talks, and how much they actually have to say when communicating a point. Strangely enough, it is not clear which of high-context or low-context languages are easier to handle when parsing; because, both come with their own set of problems. In a high context language, where context is frequently implied but not mentioned, assuming the wrong context would be fatal. Where as in a low context language, context may switch without a sentiment analysis machine realizing it several times.

For example, if you ran all of Stephen Colbert's articles through a political sentiment analysis machine, it would come back with very right leaning scores. Similar to Rush Limbaugh, or some one on that side of the spectrum. The machine would lack the context to know when an article is satire, it doesn't have the context of the fact that Mr. Colbert is a comedian. Much of what he says is sardonic in nature. The machine lacks any notion of hyperbole or sarcasm; those human behaviors seem to be confusing even to other humans.

But still, the subtleties of human interaction in communication is still what makes sentiment analysis and NLP an interesting field. Or - I should say that is what makes humans interesting. There is much more to sentiment analysis then I have had time to go over today, I recommend anyone interested to do some of their own research. This is a loosely defined area where people have not come to a conclusion on best way to do things.

Genetic Algorithms

An interesting application of heuristics is something called a genetic algorithm, even though we have yet to talk about these in class (and probably will not), the topic is still very interesting.

It belongs to the evolutionary family of algorithms; meaning that as this algorithm runs it has continuous changes. The way a genetic algorithm works is by having an initial population of possible solutions and each can be represented as a "genome" (this allows for change of the organism). This population also needs to have a way to be evaluated for “fitness” of the genome when compared to the solution. The final ingredient is allowing the population to have a way to change, be it randomly or through interactions. Then by using the idea of mutation on the entire population, you can force evolution of the potential solutions. The population is subject to change iteration by iteration as the algorithm runs. On every new iteration the algorithm attempts to produce a new population that is (possibly) a better fit to the solution. Eventually, if all goes well there will be a solution found deemed to be acceptable set by the algorithms tolerance level. Or, you could simply run out of computation time.

This is particularly good for problems where one might have no idea in what part of the domain the optimal (or acceptable) solution may belong to. By using an initial stochastic distribution of the population throughout a search space, through evolution the algorithm has a higher chance of converging to a local minima/maixima in the solution. It should be noted that this technique is best used when a optimal solution isn’t needed, only one that is good enough to the user. In many cases like that it might be impossible to brute force an optimal solution, or simply take too much time.

Some of the downsides to this method is that the structure of the population and the evaluation method have to be defined by the programmer. Therefore any bias is hardcoded in from the start, and may be missing any crucial connections that weren’t known at the time. Of course, this problem seems to be present in all forms of research and design. Another problem of notice is that they tend to be used in discrete solution sets, looking for a solution. Which is a problem of setting up a finite domain for the solution, some things may not be well formed for this.

This class of algorithm sees great use everywhere, even though some new methods of thinking in evolutionary techniques have risen to prominence over the last decade. It still continues to work very well for many problems. Because, in this algorithms heart it is a optimization technique, so any problem well posed as a function is suited for genetic algorithms. It excels at things like scheduling tasks and financial analysis. It just has a much cooler sounding name then multivariable-optimization.

I think an interesting idea for a final project might be implementing a genetic algorithm. Finding an interesting problem to implement it on is another problem though.

Adversarial Search

Adversarial Search

Adversarial search, or Minimax search, is an algorithm to try to result with the best outcome of a situation while also accounting for the actions of an opponent. It is similar to other simpler search algorithms in that it creates a tree of the possible states and tries to walk down it. At every other level of the tree, the algorithm must account for the opponent. In most cases when the opponent is choosing, you expect the opponent to choose the worst outcome for you and the best outcome for them. This search has many uses and is applied in many games.

In games where minimax is applicable there can only be two players. A good example of a game for this is the game of checkers. It is a simple game so it is possible for a computer to compute all the possible moves in the game. If played correctly, the game is actually impossible to lose. A minimax algorithm is a great algorithm to use for this game. You can quantify the goals of the game. For example, if you win the game, you get infinite points. If you lose the game, you lose infinity points. If you lose a piece, you lose a point. If the opponent loses a piece, you gain a point. The minimax algorithm can then look down the tree to see where the possible moves are that would give it the most points.

We can assume that the opponent wants us to get the least number of points possible as well. To apply this to checkers for example, we wouldn’t want to move our piece in front of the opponent’s piece. This would allow for the opponent to immediately jump and remove our piece, decreasing our number of points.

There is a slight oddity of behavior though when encountered with a board that is impossible to win. Say you only have one piece left that is in a corner. The entire rest of the board, save a few empty spaces around you, are your opponent’s pieces. The algorithm won’t choose to fight as long as possible. It will just accept defeat and choose any path that might or might not lead straight towards your loss. This might not really matter because you’ve already analyzed every possible play on the board and have concluded that there is no way for you to win. But it is an interesting habit nonetheless.