[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

 

The Unsolvability Halting Problem

Definition

Halting problem is a famous problem in computer science. The problem is simply we want to prove and know whether a computer program will be halted or terminated or it will continue running forever.

Alan Turing proved that there is known solution for the halting problem. It is impossible to determine whether a program with an input will be terminated or it will run forever.

The proof used contradiction method to prove its unsolvability.

The Proof

  • Assume that we have a program P(X) that takes X as an input
  • The output of the program will be 0 or 1 where 1 indicates the program will halt and 0 indicates the program will continue forever
  • Assume we have another program Q that takes program P as its input, Q(P(X)) that output 0 or 1 where 1 indicates P(X) will run forever and 0 indicates it will halt
  • Assume we pass the program Q to itself (Recursion) as its parameter Q(Q)
  • Now, we have 2 cases
  • Case 1: If Q(Q) halts, then P(X) returns 1, which means Q(P(X)) will return 1 which indicates P(X) runs forever. Contradiction
  • Case 2: If Q(Q) runs forever, then P(X) returns 0, which means Q(P(X)) will return 0 which indicates P(X) halts. Contradiction

References
https://en.wikipedia.org/wiki/Halting_problem
 http://www.comp.nus.edu.sg/~cs5234/FAQ/halt.html