[Python] U-V Decomposition using Swarm Optimization

Recently, I have implemented U-V decomposition technique for Recommendation Systems using Particle Swarm Optimization.

U-V decomposition is an optimization problem for a matrix. Here, our matrix elements represent some users review about movies.

M

We have 5 users and 5 movies. Each row represents a user’s review for each movie. There are some missing values from the matrix which means that the user hasn’t put his/her review on that movie.

You can check the code here https://github.com/AhmedHani/CS624-ML/tree/master/Implementations/U-V%20Decomposition . Later, I will write another post to explain my code.

Input: Matrix 5×5 with unknown reviews

Intermediate output: Matrix U and V which multiplication gives a new matrix without unknown reviews

Output: Matrix 5×5 without unknown values.

 

References 

– The matrix example is taken from the book http://infolab.stanford.edu/~ullman/mmds/book.pdf at chapter 9

 

Introduction to Ant Colony Optimization (ACO)

Ants are awesome, their co-operation and coordination are really impressive, these behaviors pushed the scientists to discover and study more about ants, and how these creatures communicate with each other to preform these behaviors which help them to accomplish their tasks and missions.

Stigmergy, an indirect communication that the ants use to communicate with each other, you can imagine it as a kind of mechanism that an ant affects the environment(the ground) by it to tell other ants to do a specific task or move, this helps the ants to achieve self-organization.

Biologists found something interesting, some of ants species use something called Trail of pheromones, ants spread them on the path they walk on, other ants sense this trail and follow the same path as an influence for them. By using this trail of pheromones, ants can follow each other to reach a source of food, then return back to their colony. The amount of the pheromones is directly proportional to the intensity of the ants, which means that the higher of pheromones on a path, the more of ants walk on that path.

Scientists decide to do an experiment to fully understand the trail of pheromones, they put some ants on a dynamic environment in which new paths added to it in the run time to see the ants’ behaviors, see the following figure

EXPThe figure contains before-after adding a new shorter path from nest to food source, initially ants were on the nest, before adding a shorter path there was only one path to get the source food, so that all ants walked on it, after each of ants’ walk they left the trail of pheromones, and that helped ants to follow each other. After adding a new shorter path, it was expected that the ants will change their path immediately, but they continue use the longer path, after many trips from the nest to the source food, the ants changed their way to the shorter path.

Scientists explained that ants always follow the trail of pheromones, the longer path has much pheromones than the shorter path so the ants continued to follow that path, after many iterations, they changed their path to the shorter one because some of ants explored the new path and found it shorter, so more and more ants took a decision to use the new path, and for each trip on it they left the “Trail of pheromones” which made all ants to follow the new path, regarding the pheromones on the longer path, the scientists found that the pheromones always evaporate after several minutes and that made all ants to ignore the longer path.

Well, it the time to simulate this in a mathematical perspective by creating a probabilistic model (Stochastic model), assume that the probability that an ant at a decision position i ∈ [p1, p2] chooses a path a where a ∈ [s, l] is pia(t), s denotes short path and l is the long path, the amount of pheromones at time t is denoted as φia(t)

The probability that an ant reaches from the nest to the source using short or long path is pis(t) + pil(t) = 1, according to the experiment, they concluded that the amount of the pheromones is proportional to the intensity of the ants, so the probability that an ant chooses the short path is:

Formula

where α = 2 which is concluded from the experiment .. as the amount of pheromones changes and evolves during the time, this evolution can be described using differential equations:

is / dt = ΨPjs(tts) + ΨPis(t)            ======> (i = a, j = b; i = b, j = a)
il / dt = ΨPjl(t – (r . ts)) + ΨPil(t)          ======> (i = a, j = b; i = b, j = a)

Ψ: is a constant
r: is the ratio between the long and short paths

Note that, this model represents that ants are spreading pheromones in both trips (from nest to food, and from food to nest)

These equations inspired the scientists to use ants’ behaviors to get a minimum cost path in a simple graph.

Build A Simple Ant Colony

Problems appeared when they tried to use ants’ behavior (described above), we can conclude them in two points ..

[1]Loops generation
– Ants in their trip, they spread pheromones forward (from nest to food) and backward (from food to nest),
this may causes a loop that traps the ants, due to forward pheromone trail, increasing amount of pheromones in loop’s path attracts all ants to follow only the loop’s paths.

[2]Ignoring short paths
– If an ant survive from the loop, the pheromones trails on the short paths will be evaporated, that makes the ant ignores them

The solution is to create some behaviors that help them to find minimum cost path in simple graph without only depending on trails of pheromones, these behaviors are..

[1]Probabilistic solution constructed by pheromone trails
[2]Deterministic backward path with pheromone updating (loops are eliminated)
[3]Evaluation for a generated solution in each iteration

Next, we will discuss each of these behaviors.

[1]Probabilistic solution constructed by pheromone trails
– In the forward trip, ant chooses probabilistically a path according to the amount of pheromones on this path which has been spreaded by the other ants, ants in the forward trip don’t spread any pheromones.

[2]Deterministic backward path with pheromone updating (loops are eliminated)
– When an ant is in the destination node (source food), before it starts its backward trip, it memorizes the paths and eliminates all loops from them, ants in the backward trip spread trails of pheromones. This with the probabilistic solution eliminate the loops generation problem.

[3]Evaluation for a generated solution in each iteration
– Ants in their trip, they memorize the paths they talk and the cost from the start node to the end node, depends on that, they spread the pheromones according to the quality of the solution, the higher amount of pheromones the better of the solution.
– Controlling the pheromones evaporation rate leads to avoid the poor solutions

Implementing all these behaviors leads to build a simple ant colony optimization algorithm (S-ACO) to find the minimum cost path on a simple graph. The next post will about this algorithm.

References: Marco Dorigo and Thomas Stützle ant colony optimization book