Saturday, February 19, 2011

A Simple example of Artificial Intelligence using Delphi The article explores Delphi approach to AI, using the pebble picking game.

Artificial Intelligence (AI) is an advance branch of science that studies the process of human thinking and attempts to apply the knowledge to simulate the same process in machines.

As computers are far ahead in the marathon of processing machines, AI is considered to be the branch of Computer Science than that of General Science. There have been many research and development in the field of Artificial Intelligence. The area of research include speech and pattern recognition, natural language processing, learning from previous experiences (learning by making and correcting mistakes!), reasoning under the situations providing limited or incomplete information etc. 

AI is practically applied in the field of computer games, expert systems, neural networks, robotics and many other fields of science and technology.

The game

In this article we will try to demonstrate a very simple practical example of artificial Intelligence programming in Delphi using Delphi arrays.

I have chosen a Nepali game named "GATTA TIPNE KHEL" (meaning pebble picking game) for this purpose. We can see small children playing this game in the playground. In this pebble picking game a pile of some pebbles is kept in the ground. One of the two players picks one, two or three pebbles at a time in his turn, leaving the pile for the other player to pick for his alternate turn. In this alternate picking process, the player who picks the last pebble(s) will be the loser and called to be a DOOM in Nepali. 

The main logic of the game is to leave the pile of pebbles with 13, 9, 5 or 1 pebble(s) for the opponent to pick. In the program the starting number of pebbles are set to 17, 21, 25, 29 … etc. so that computer could win always if it does not make a mistake. But in the real play computer seems to be gradually learning by correcting mistakes of the previously played games. At last it finds all its mistakes and corrects them to become an unbeatable champion. 

It seems computer simulates the psychological learning process of animal, learning by correcting and not repeating the mistakes. A multidimensional array of elements (1..4,1..3) is chosen as the instruction book for the computer to pick the pebbles. The instruction book contains four pages with three lines of instructions to pick pebbles. The first line instructs to pick a single pebble, the second line instructs to pick 2 and the third line instructs to pick 3 pebbles. At the beginning, computer chooses a random page and a random line of instruction to pick the pebble. 

When the game finishes, if computer looses the game, the last instruction is red-marked (erased) and the instruction will not be read in the future. After playing many games, all the instructions leading to a lost game will be red marked and there will be left only the instructions those lead to a win. Well, it is enough for the description of the game. Let us jump directly to the code... 

Download full game source code

Akash Mondal

IBM-Watson (Artificial Intelligence software)

Artificial intelligence (AI) is the intelligence of machines and the branch of computer science that aims to create it.
Watson is an artificial intelligence program developed by IBM designed to answer questions posed in natural language. Named after IBM's founder, Thomas J. Watson, IBM, who supposedly said that 
I think there is a world market for maybe five computers"
This quote is probably not true, but is nevertheless popular. Watson is being developed as part of the DeepQA research project. The program runs on POWER7 processor-based systems.
Watson is an application of advanced natural language processing, information retrieval, knowledge representation and reasoning, and machine learning technologies to the field of open domain question answering.
In Feb 2011, Watson competed on the television quiz show Jeopardy! As a test of its abilities. Jeopardy is a quiz show, but works slightly differently. The answer is given and you have to figure out the question. In a two-game, combined-point match aired in three Jeopardy! Episodes running from February 14–16, Watson bested Brad Rutter, the biggest all-time money winner on Jeopardy!, and Ken Jennings, the record holder for the longest championship streak. Watson received first prize of $1 million, while Ken Jennings and Brad Rutter received $300,000 and $200,000, respectively. Jennings and Rutter pledged to donate half their winnings to charity, while IBM divided Watson's winnings among two charities. This was the first man-versus-machine competition in Jeopardy!’s history...
The IBM team provided Watson with 200 million of documents, including dictionaries, encyclopaedias and other reference material that it could use to build its knowledge, such as bibles, novels and plays, content consuming 4 terabytes of hard disk storage. A standalone program, Watson does not utilize the Internet when playing the game show. This is similar to man memorizing stuff from his brain.
Rather than relying on a single algorithm, Watson uses thousands of algorithms simultaneously to understand the question being asked and find the correct path to the answer.
In other words, it must do more than what search engines like Google and Bing do, which is merely point to a document where you might find the answer. It has to pluck out the correct answer itself.
Three artificial-intelligence experts, including the leader of the Watson team, discuss the supercomputer's prospects as the more algorithms that independently arrive at the same answer, the more likely Watson is to be correct. Once Watson comes up with a small number of potential solutions, it is able to check against its database to ascertain if the solution made sense. In a sequence of 20 mock games, human participants were able to use the six to eight seconds it takes to read the clue to decide whether to buzz in with the correct answer. During that time, Watson is also able to evaluate the answer and determine if it is sufficiently confident in the result to buzz in...
By February 2010Watson was then able to buzz in and speak with an electronic voice, when it gave the responses in Jeopardy!'s question format
Originally Watson buzzed in electronically, but Jeopardy! requested that it physically press a button, as the human contestants would. Even with a robotic "finger" pressing the buzzer, Watson remained faster than its human competitors. Jennings noted, "If you're trying to win on the show, the buzzer is all," and that Watson "can knock out a microsecond-precise buzz every single time with little or no variation. Human reflexes can't compete with computer circuits in this regard." Also, Watson could avoid the time-penalty for accidentally buzzing in too early, because it was electronically notified when to buzz, whereas the human contestants had to anticipate the right moment.
According to IBM, "The goal is to have computers start to interact in natural human terms across a range of applications and processes, understanding the questions that humans ask and providing answers that human can understand and justify." The natural constraints present in games may provide an ideal environment for the development of computer intelligence.
Technologists have long regarded this sort of artificial intelligence as a holy grail, because it would allow machines to converse more naturally with people, letting us ask questions instead of typing keywords.

New York Times

D Sai Prashnath

Thursday, February 17, 2011

Adaptive Signal Control Technology

Outdated fixed interval signal timing contributes to traffic congestion. “Wait, go, stop, wait, wait some more” as said by most of the traffic policemen made most drivers have spent their time fuming at red lights. Even though if sometimes the intersection might be empty, yet the light stayed red for a maddening amount of time. Or perhaps the road is so congested that you have to wait three or more full light cycles before you can make a left turn.
Traditional time-of-day signal timing plans do not accommodate variable and unpredictable traffic demands. Special events, construction, or traffic incidents typically create havoc on traffic conditions. Time-of-day signal timing cannot accommodate other disruptions, such as crashes.
Adaptive Signal Control Technology (ASCT) can use real-time traffic information to reduce congestion by determining which lights should be red and which should be green. It helps improve the quality of service that travelers experience on local roads and highways.

Improving Traffic Flow
Adaptive Signal Control Technology (ASCT) captures current traffic demand data to adjust traffic signal timing to optimize traffic flow in coordinated traffic signal systems. By receiving and processing data from strategically placed sensors, ASCT can determine which lights should be red and which should be green.
The process is simple. First, traffic sensors collect data. Next, traffic data is evaluated and signal timing improvements are developed. Finally, ASCT implements signal timing updates. The process is repeated every few minutes to keep traffic flowing smoothly.
On average, ASCT improves travel time by more than 10%. In areas with particularly outdated signal timing, improvements can be 50% or more.

Its Requirements
Full-scale ASCT technologies are appropriate for large-scale systems of 100 or more traffic signals and on grid systems. These technologies are fully integrated into central systems that operate on a second-by-second basis and have substantial communications and detection systems overhead. They require a high level of operations and maintenance capability and often entail a traffic management center with 24-hour staffing.

The City of Los Angeles uses an Automated Traffic Surveillance and Control (ATSAC) system (a product of ASCT) that was developed in-house to meet the specific needs of the city. The system includes more than 17,000 detectors and is in use on 3,200 of the city’s 4,400 traffic signals. A study conducted in 2001 analyzed the effectiveness of the system, finding it improved travel time by 13%, decreased stops by 31%, and reduced delay by 21%.

At this time, AI created by humans has replaced them working at the signals and real-time management systems have been deployed on less than 1% of existing traffic signals nationwide. ASCT Manufacturer Company is now working to expand the use of these Artificial Intelligent technologies in California and across the country through the development and continued evaluation at low-cost.

Institute of Transportation Studies, University of California, Berkeley.


Thursday, February 10, 2011


It is nowadays a common notion that vast amounts of capital are traded through the Stock Markets all around the world. National economies are strongly linked and heavily influenced of the performance of their Stock Markets. Moreover, recently the Markets have become a more accessible investment tool, not only for strategic investors but for common people as well. Consequently they are not only related to macroeconomic parameters, but they influence everyday life in a more direct way. Therefore they constitute a mechanism which has important and direct social impacts. The characteristic that all Stock Markets have in common is the uncertainty, which is related with their short and long-term future state. This feature is undesirable for the investor but it is also unavoidable whenever the Stock Market is selected as the investment tool. The best that one can do is to try to reduce this uncertainty. Stock Market Prediction (or Forecasting) is one of the instruments in this process.

The Stock Market prediction task divides researchers and academics into two groups those who believe that we can devise mechanisms to predict the market and those who believe that the market is efficient and whenever new information comes up the market absorbs it by correcting itself, thus there is no space for prediction (EMH). Furthermore they believe that the Stock Market follows a Random Walk, which implies that the best prediction you can have about tomorrow's value is today's value.
In literature a number of different methods have been applied in order to predict Stock Market returns. These methods can be grouped in four major categories: i) Technical Analysis Methods, ii) Fundamental Analysis Methods, iii) Traditional Time Series Forecasting and iv) Machine Learning Methods. Technical analysts, known as chartists, attempt to predict the market by tracing patterns that come from the study of charts which describe historic data of the market. Fundamental analysts study the intrinsic value of an stock and they invest on it if they estimate that its current value is lower that its intrinsic value. In Traditional Time Series forecasting an attempt to create linear prediction models to trace patterns in historic data takes place. These linear models are divided in two categories: the univariate and the multivariate regression models, depending on whether they use one of more variables to approximate the Stock Market time series. Finally a number of methods have been developed under the common label Machine Learning these methods use a set of samples and try to trace patterns in it (linear or non-linear) in order to approximate the underlying function that generated the data.
Investment Theories:An investment theory suggests what parameters one should take into account before placing his (or her) capital on the market. Traditionally the investment community accepts two major theories: the Firm Foundation and the Castles in the Air. Reference to these theories allows us to understand how the market is shaped, or in other words how the investors think and react. It is this sequence of 'thought and reaction' by the investors that defines the capital allocation and thus the level of the market.

There is no doubt that the majority of the people related to stock markets is trying to achieve profit. Profit comes by investing in stocks that have a good future (short or long term future). Thus what they are trying to accomplish one way or the other is to predict 16 the future of the market. But what determines this future? The way that people invest their money is the answer; and people invest money based on the information they hold. Therefore we have the following schema:

The factors that are under discussion on this schema are: the content of the 'Information' component and the way that the 'Investor' reacts when having this info.

On the other hand, according to the Castles in the Air theory the investors are triggered by information that is related to other investors' behavior. So for this theory the only concern that the investor should have is to buy today with the price of 20 and sell tomorrow with the price of 30, no matter what the intrinsic value of the firm he (or she) invests on is.

Prediction Methods:The prediction of the market is without doubt an interesting task. In the literature there are a number of methods applied to accomplish this task. These methods use various approaches, ranging from highly informal ways (e.g. the study of a chart with the fluctuation of the market) to more formal ways (e.g. linear or non-linear regressions). We have categorized these techniques as follows:

1.Technical Analysis:
"Technical analysis is the method of predicting the appropriate time to buy or sell a stock used by those believing in the castles-in-the-air view of stock pricing". The idea behind technical analysis is that share prices move in trends dictated by the constantly changing attributes of investors in response to different forces. Using technical data such as price, volume, highest and lowest prices per trading period the technical analyst uses charts to predict future stock movements. Price charts are used to detect trends, these trends are assumed to be based on supply and demand issues which often have cyclical or noticeable patterns.

From the study of these charts trading rules are extracted and used in the market environment. The technical analysts are known and as 'chartists'. Most chartists believe that the market is only 10 percent logical and 90 percent psychological. The chartist's belief is that a careful study of what the other investors are doing will shed light on what the crowed is likely to do in the future.

This is a very popular approach used to predict the market, which has been heavily criticized. The major point of criticism is that the extraction of trading rules from the study of charts is highly subjective therefore different analysts might extract different trading rules by studying the same charts. Although it is possible to use this methodology to predict the market on daily basis we will not follow this approach on this study due to its subjective character.

2.Fundamental Analysis:
"Fundamental analysis is the technique of applying the tenets of the firm foundation theory to the selection of individual stocks". The analysts that use this method of prediction use fundamental data in order to have a clear picture of the firm (industry or market) they will choose to invest on. They are aiming to compute the 'real' value of the asset that they will invest in and they determine this value by studying variables such as the growth, the dividend payout, the interest rates, the risk of investment, the sales level, the tax rates an so on. Their objective is to calculate the intrinsic value of an asset (e.g. of a stock). Since they do so they apply a simple trading rule. If the intrinsic 21 value of the asset is higher than the value it holds in the market, invest in it. If not, consider it a bad investment and avoid it. The fundamental analysts believe that the market is defined 90 percent by logical and 10 percent by physiological factors. This type of analysis is not possible to fit in the objectives of our study. The reason for this is that the data it uses in order to determine the intrinsic value of an asset does not change on daily basis. Therefore fundamental analysis is helpful for predicting the market only in a long-term basis.

3.Traditional Time Series Prediction:
The Traditional Time Series Prediction analyzes historic data and attempts to approximate future values of a time series as a linear combination of these historic data. In econometrics there are two basic types of time series forecasting: univariate (simple regression) and multivariate (multivariate regression). These types of regression models are the most common tools used in econometrics to predict time series. The way they are applied in practice is that firstly a set of factors that influence (or more specific is assumed that influence) the series under prediction is formed. These factors are the explanatory variables xi of the prediction model.

Then a mapping between their values xit and the values of the time series yt (y is the to-be explained variable) is done, so that pairs {xit , yt} are formed. These pairs are used to define the importance of each explanatory variable in the formulation of the to-be explained variable. In other words the linear combination of xi that approximates in an optimum way y is defined. Univariate models are based on one explanatory variable (I=1) while multivariate models use more than one variable (I>1). Regression models have been used to predict stock market time series. A good example of the use of multivariate regression is the work of Pesaran and Timmermann (1994) .

They attempted prediction of the excess returns time series of S&P 500 and the Dow Jones on monthly, quarterly and annually basis. The data they used was from Jan 1954 until Dec 1990. Initially they used the subset from Jan 1954 until Dec 1959 to adjust the coefficients of the explanatory variables of their models, and then applied the models to predict the returns for the next year, quarter and month respectively.

Machine Learning Methods:
Several methods for inductive learning have been developed under the common label "Machine Learning". All these methods use a set of samples to generate an approximation of the underling function that generated the data. The aim is to draw conclusions from these samples in such way that when unseen data are presented to a model it is possible to infer the to-be explained variable from these data. The methods we discuss here are: The Nearest Neighbor and the Neural Networks Techniques. Both of these methods have been applied to market prediction; particularly for Neural Networks there is a rich literature related to the forecast of the market on daily basis.

The experiment consisted of three phases (Figure A). In the first phase a genetic algorithm (GA) searched the space of NNs with different structures and resulted a generation with the fittest of all networks searched based on a metric which was either: TheilA or TheilB or TheilC or MAE. The GA search was repeated three times for each metric. Then the best three networks were selected from each repetition of the GA search and for each one of the metrics.

The output of the first phase was a set of thirtysix network structures. In the second phase for each one of the thirty-six resulting network structures we applied the following procedure. We trained (on Training1 set) and validated (on Validation1 set) the network. Then we used the indicated number of epochs from the validation procedure and based on it we retrained the network on the Training1 plus the Validation1 set. Finally we tested the performance of the network on unseen data (Validation2 set).

This procedure was repeated 50 times for each network structure for random initializations of its weights. From the nine networks for each performance statistic, we selected the most stable in terms of standard deviation of their performance. Thus the output of the second phase was a set of four network structures. During the third phase for each one of these four networks we applied the following procedure 50 times. We trained each network on the first half of the Training Set and we used the remaining half for validation. Then, using the indicated epochs by the validation procedure, we retrained the network on the complete Training Set. Finally we tested the network on the Test Set calculating all four metrics.

The performance for each network on each metric was measured again in terms of standard deviation and mean of its performance over 50 times that it was trained, validated and tested.


Wednesday, February 9, 2011

Artificial Intelligence –The CYC Project

Artificial Intelligence (AI) is an advance branch of science that studies the process of human thinking and attempts to apply the knowledge to simulate the same process in machines.
     As computers are far ahead in the marathon of processing machines, AI is considered to be the branch of Computer Science than that of General Science. There have been many research and development in the field of Artificial Intelligence. The area of research include speech and pattern recognition, natural language processing, learning from previous experiences (learning by making and correcting mistakes!), reasoning under the situations providing limited or incomplete information etc. AI is practically applied in the field of computer games, expert systems, neural networks, robotics and many other fields of science and technology.
        CYC (the name comes from "encyclopaedia") is the largest experiment yet in symbolic AI. The project began at the Microelectronics and Computer Technology Corporation in Texas in 1984 under the direction of Douglas Lenat, with an initial budget of U.S.$50 million, and is now Cycorp Inc. The goal is to build a KB(knowledge base) containing a significant percentage of the common sense knowledge of a human being like facts, rules of thumb, and heuristics for reasoning about the objects and events of everyday life. Lenat hopes that the CYC project will culminate in a KB that can serve as the foundation for future generations of expert systems. His expectation is that when expert systems are equipped with common sense they will achieve an even higher level of performance and be less prone to errors of the sort just mentioned.
By "common sense", AI researchers mean that large corpus of worldly knowledge that human beings use to get along in daily life. A moment's reflection reveals that even the simplest activities and transactions presuppose a mass of trivial-seeming knowledge: to get to a place one should (on the whole) move in its direction; one can pass by an object by moving first towards it and then away from it; one can pull with a string, but not push; pushing something usually affects its position; an object resting on a pushed object usually but not always moves with the pushed object; water flows downhill; city dwellers do not usually go outside undressed; causes generally precede their effects; time constantly passes and future events become past events ... and so on and so on. A computer that is to get along intelligently in the real world must somehow be given access to millions of such facts. Winograd, the creator of SHRDLU, has remarked "It has long been recognised that it is much easier to write a program to carry out abstruse formal operations than to capture the common sense of a dog".
      The CYC project involves "hand-coding" many millions of assertions. By the end of the first six years, over one million assertions had been entered manually into the KB. The Cyc KB is divided into many (currently thousands of) "microtheories", each of which is essentially a bundle of assertions that share a common set of assumptions; some microtheories are focused on a particular domain of knowledge, a particular level of detail, a particular interval in time, etc. The microtheory mechanism allows Cyc to independently maintain assertions which are prima facie contradictory, and enhances the performance of the Cyc system by focusing the inferencing process. Lenat describes CYC as "the complement of an encyclopaedia": the primary goal of the project is to encode the knowledge that any person or machine must have before they can begin to understand an encyclopaedia. At the present time, the Cyc KB contains nearly five hundred thousand terms, including about fifteen thousand types of relations, and about five million facts (assertions) relating these terms. New assertions are continually added to the KB through a combination of automated and manual means. Additionally, term-denoting functions allow for the automatic creation of millions of non-atomic terms and CYC adds a vast number of assertions to the KB by itself as a product of the inferencing process.
CYC uses its common-sense knowledge to draw inferences that would defeat simpler systems. For example, CYC can infer "Shaun is wet" from the statement "Shaun is finishing a marathon run", employing its knowledge that running a marathon entails high exertion, that people sweat at high levels of exertion, and that when something sweats it is wet.
       One of the major problems CYC are facing is issues in knowledge representation, for example how basic concepts such as those of substance and causation are to be analyzed and represented within the KB.
       AI engineers might learn more about biological processes of relevance to understanding the nature of knowledge, they ultimately will be able to develop a machine with human capability that is not biological or organic. This strategy has considerable support, but unfortunately, the thrust has been to ignore the differences between human knowledge and computer programs and instead to tout existing programs as "intelligent." Emphasizing the similarities between people and computer models, rather than the differences, is an ironic strategy for AI researchers to adopt, given that one of the central accomplishments of AI has been the formalization of means-ends analysis as a problem- solving method: Progress in solving a problem can be made by describing the difference between the current state and a goal state and then making a move that attempts to bridge that gap.


References :

Prajul Bagri