Prediction with Neural Networks September 25, 2007
Posted by nhabibi in Artificial Intelligence, Neural Network.1 comment so far
An artificial neural network (ANN), often just called a “neural network” (NN), is a mathematical model or computational model based on Biological neural networks. It consists of an interconnected group of artificial neurons. In a neural network model, simple nodes are connected together to form a network of nodes — hence the term “neural network”.
In most cases an ANN is an adaptive system that changes the strength (weights) of the connections in the network, based on information that flows through the network during the learning phase.
The utility of artificial neural network models lies in the fact that they can be used to infer a function from observations. This is particularly useful in applications where the complexity of the data or task makes the design of such a function by hand impractical.
(Source: Wikipedia)
ANN has application in many areas, like Stock Market Prediction. We’ve investigated the efficiency of ANN for predicting the low and high monthly stock price, by using some technical indicators, and prices of previous months, as ANN input.
The ANN is a feedforward one with Backpropagation learning algorithm. We have predicted low and high monthly price for some companies in S&P500. Prices are gotten from Yahoo! Finance. Several technical indicators are applied and results are analyzed. Implementation is done with NeuroSolutions software. You can find our paper here.
More information:
- M. Hagan et al., “Neural Network Design”
- In depth description of Technical Indicators
- S&P500 list
AntNet September 23, 2007
Posted by nhabibi in Artificial Intelligence, Internet, Machine Learning.2 comments
AntNet routing algorithm is a mobile agents system that is based on Ant Colony Optimization (ACO) method (refer to perevious post). Informally, the AntNet algorithm and its main characteristics can be summarized as follows:
- At regular intervals, and concurrently with the data traffic, from each network node mobile agents are asynchronously launched towards randomly selected destination nodes.
- Agents act concurrently and independently, and communicate in an indirect way, through the information they read and write locally to the nodes.
- Each agent searches for a minimum cost path joining its source and destination nodes.
- Each agent moves step-by-step towards its destination node. At each intermediate node a greedy stochastic policy is applied to choose the next node to move to. The policy makes use of (i) local agent-generated and maintained information, (ii) local problem-dependent heuristic information, and (iii) agent-private information.
-While moving, the agents collect information about the time length, the congestion status and the node identifiers of the followed path.
- Once they have arrived at the destination, the agents go back to their source nodes by moving along the same path as before but in the opposite direction.
- During this backward travel, local models of the network status and the local routing table of each visited node are modified by the agents as a function of the path they followed and of its goodness.
- Once they have returned to their source node, the agents die.
(Source: AntNet original paper)
OPNET, is a network simulator that can be used to design networks with different size and components, and to implement, test and evaluate protocols.
I implemented AntNet by OPNET. The difficult point was learning OPNET! It’s a little tricky, but very well-defined and powerful. (Of course when you learned! 
) The best starting point is OPNET tutorials, inside software. In short, you first define network packets, links and nodes separately and then integrate them. Protocols can be coded in C/C++.
My report describe AntNet algorithm in detail and its implementation by OPNET, in Persian.
More information:
G. Caro & M. Dorigo paper: AntNet: Distributed Stigmergetic Control for communication networks
PS:
1-A network specialist says that AntNet is not applicable for large networks, like internet, due to high volume of routing related messages. I think it’s true.
2- What a long post! Didn’t you get bored?
Swarm Intelligence September 22, 2007
Posted by nhabibi in Artificial Intelligence, Soft Computing.1 comment so far
Swarm intelligence (SI) is an artificial intelligence technique based around the study of collective behavior in decentralized, self-organized systems.
SI systems are typically made up of a population of simple agents interacting locally with one another and with their environment. Although there is normally no centralized control structure dictating how individual agents should behave, local interactions between such agents often lead to the emergence of global behavior. Examples of systems like this can be found in nature, including ant colonies, bird flocking, bacterial growth, and fish schooling.
(source: Wikipedia)
Several SI-based algorithms are proposed, like Ant Colony Optimization (ACO), Particle Swarm Intelligence (PSO), Stochastic Diffusion Search (SDS), etc. These algorithms are applied to an impressive number of optimization problems.
ACO is based on the behavior of real ants for finding food. This behavior can be described as follow (a little long, but intresting ):
In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food.
Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high as it is laid on the path as fast as it can evaporate. Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.
Thus, when one ant finds a good (short, in other words) path from the colony to a food source, other ants are more likely to follow that path, and positive feedback eventually leaves all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with “simulated ants” walking around the graph representing the problem to solve.
(see a good example here.)
You can find my report about Swarm Intelligence here. It introduces SI in general, and Ant Colony Optimization in detail. Also, an ACO-based for Traveling Salesperson problem and a ACO-based routing algorithm, are described.
More information:
- M. Dorigo & G. D. Caro’s paper, the original paper on ACO
- M. Dorigo home page
Hidden Markov Model September 21, 2007
Posted by nhabibi in Artificial Intelligence, Pattern Recognition.1 comment so far
A Hidden Markov Model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to determine the hidden parameters from the observable parameters. The extracted model parameters can then be used to perform further analysis, for example for pattern recognition applications.
In a regular Markov model, the state is directly visible to the observer, and therefore the state transition probabilities are the only parameters. In a hidden Markov model, the state is not directly visible, but variables influenced by the state are visible. Each state has a probability distribution over the possible output tokens. Therefore the sequence of tokens generated by an HMM gives some information about the sequence of states.
HMM has application in many fields that need to recognize patterns statistically, such as speech recognition, optical character recognition, cryptanalysis, boinformatics, etc.
I ignore describing Hidden Markov Model’s mathematic details here. My report, in Persian, introduces HMM in detail and describes its application in Speech Recognition briefly.
More information:
- A good tutorial from Leeds university
- L. R. Rabiner’s paper on Hidden Markov Model
- HMM Wikipedia page
Fuzzy & Data Minig September 20, 2007
Posted by nhabibi in Artificial Intelligence, Data Mining, Fuzzy, Soft Computing.1 comment so far
Fuzzy sets are sets whose elements have degrees of membership. Fuzzy sets have been introduced by Professor Lotfali Askarzadeh (1965) as an extension of the classical notion of set.
In classical set theory, an element either belongs or does not belong to the set. By contrast, fuzzy set theory an element belongs to the set, with membership degree in interval [0-1].
An example:
Assume that we have four students with bellow scores in biology exam:
Richard, 20
frank, 18
Anna, 14
Juli, 11
We want to define “A = set of Good Student in Biology Class“:
1- in classical set theory: A = {Richard, Frank}
2- in fuzzy set theory: A = { (Richard,1) , (Mark,0.7) , (Anna,0.3) , (Juli,0.1) }
In fact, we have associated a membership degree to each member, according to goodness of their score.
Fuzzy logic is derived from fuzzy set theory dealing with reasoning that is approximate rather than precisely deduced from classical predicate logic.
Fuzzy concept has application in many areas, specially in control systems.
In many topics, after proposing an algorithm, the fuzzy version of the algorithm is proposed and evaluated against the original one.
Here, is our report, in Persian, that introduces data mining in general, Apriori algorithm to extract association rules, a fuzzy-based Apriori algorithm, Decision Tree and fuzzy-based Decision Tree.
More information:
- Zadeh’s 1965 paper on Fuzzy Sets (It has more that 5000 citations till now!)
Detections in Arial Images September 18, 2007
Posted by nhabibi in Artificial Intelligence, Machine Vision.add a comment
Aerial photography is the taking of photographs from the air with a camera mounted, or hand held, on an aircraft, helicopter, balloon, rocket, kite, skydiver or similar vehicle.The use of aerial photography for military purposes was expanded during World War I.
According to photography place, different objects can be present in an aerial image. For example in an urban sense, there are roads, highways, buildings, humans, vehicles, etc.
Vehicle detection in aerial images, has several applications, for example traffic control, urban planning, approximating and simulating air pollution, data gathering for GIS, etc.
You can find a report on Vehicle Detection in aerial images, in Persian, here.
I’ve implemented a program in MATLAB to detect highways and vehicles in grayscale images. This program, has some constraints and assumptions, like any other machine vision system. It’s possible to improve it and add more features. You can find the project report, in Persian, here.
If you are interested in source codes, please contact me.
Machine Vision September 17, 2007
Posted by nhabibi in Artificial Intelligence, Machine Vision.add a comment
Machine Vision is concerned with computational understanding and use of the information present in visual images. In part, computer vision is analogous to the transformation of visual sensation into visual perception in biological vision. The goal of computer vision is primarily to enable engineering systems to model and manipulate the environment by using visual sensing.
MV is an interesting and practical field, but complicated.
For implementing MV algorithms, MATLAB is common. It has a rich Image Processing toolbox. Also, I’ve tried Java 2D API. It’s a little tricky, but ?
PS: In my opinion, the MV and Image Processing pages on wikipedia, aren’t good enough, of course as an exception.
Genetic Algorithm March 21, 2007
Posted by nhabibi in Artificial Intelligence, Machine Learning, Soft Computing.add a comment
Genetic Algorithm (GA) is a search technique to find true or approximate solution, inspired by evolutionary biology such as inheritance, mutation and recombination.
The concept is very simple. Assume we have a problem and a pool of solutions (search space). Typically solution are represented by 1s and 0s.
Each individual has a fitness, according to a defined criteria.
GA does many iterations and terminates when reaches a satisfactory fitness level.
Definitions:
mutate ==> changing 1 to 0 and vise versa in a bit string
crossover ==> combining 2 string (parents) and generating
2 new ones (offspring)
The steps in summary are:
while (max fitness of current generation is below of desired fitness) {
1- select probabilistically some individuals from current population
2- recombine them 2 by 2 (crossover)
3- mutate some of them
4- replace new generation with old one
}
You can see a graphical representation of GA in GA viewer.
An implementation of GA in Java, for playTennis problem: Java Class – Example file for testing
Note: It’s not well-documented, I wrote it quickly!
Combinatorial Optimization December 22, 2006
Posted by nhabibi in Artificial Intelligence, Computer-Science Term.1 comment so far
Combinatorial optimization is a branch of optimization in applied mathematics and computer science that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering.
Combinatorial optimization algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances(NP-hard problems). Combinatorial optimization algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.
Examples of these problems are:
Source: Wikipedia
