Close to the End

Ok, it has been almost 9 months since my last post. I knew it was going to be difficult to find time to update it, but not that difficult. Anyway, I have still one more week left of my sabbatical, and there are still a couple of interesting things to discuss.

One of my previous posts was about NMF. That turned to be a very good source of new ideas. We developed the idea further, and proposed an algorithm to do multimodal indexing that works pretty well. We published three papers on the topic [1,2,3], and we were invited to submit an extended version to a journal. Also we used it as a basis to our submission to the ImageCLEF competition.

I think there are still many things we can do with NMF. Among others: to extend it to a semi-supervised mutimodal setting, to explore more efficient alternatives (José Guillermo is actively working on that), and to exploit its relationships with other methods. The next figure illustrates the last point:

As it can be seen, that it relates with a wide set of different algorithms that range from semisupervised learning to latent space embedding. I think these are very nice theoretical results, but also they have a good potential to widen the application alternatives of NMF.

Other things had happened since I came back from USA: I stayed in Colombia for three months and I went to Paris, for other three months. I was working on very interesting things here in Paris. I'm going back to Colombia tomorrow. My courses started already thanks to the collaboration of Edwin, David and Pacho, however I have to take on this week. I hope I'll have the time to, at least, make one or two more posts.

[1] González, F. A., Caicedo, J. C., Nasraoui, O., and Ben-Abdallah, J. 2010. NMF-based multimodal image indexing for querying by visual example. In Proceedings of the ACM international Conference on Image and Video Retrieval (Xi'an, China, July 05 - 07, 2010). CIVR '10. ACM, New York, NY, 366-373. DOI= http://doi.acm.org/10.1145/1816041.1816094
[2] Ben-Abdallah, J.,  Caicedo, J. C., González, F. A., Nasraoui, O., Multimodal Image Annotation Using Non-negative Matrix Factorization, In Proceedings of the IEEE Web Intelligence Conference (Toronto, Canada, Aug. 31, 2010), IEEE-WIC 2010. IEEE (to appear).
[3] Camargo, J.,  Caicedo, J. C., González, F. A., Multimodal Image Collection Visualization using Non-negative Matrix Factorization, in Proceedings fo the European Conference in Digital Libraries (Glasgow,UK, September 2010), LNCS Springer (to appear).

Nonnegative Matrix Factorization

The general problem of matrix factorization is to decompose a matrix X in two matrix factors A and B:

X_{m\times n}=A_{m\times r}B_{r\times n}

This could be accomplished by different methods. One of those is SVD. In that case X=U\Sigma V, so A=U\Sigma^{\frac{1}{2}} and B=\Sigma^{\frac{1}{2}}V.

This is used to solve different problems such as Latent Semantic Analysis (LSA). In this case, X is a term-document matrix. The columns of A can be interpreted as the elements of a basis for the latent space, which is r-dimensional. The columns of B are the codifying vectors, i.e., they correspond to the representation of the documents in the latent space. The problem of applying SVD to find the latent space, is that the codifying vectors could have, in general, negative values. This means that some documents are represented, not only by the presence of latent factors, but also by their absence.

To solve this problem, an additional restriction may be imposed to the basis vectors and codifying vectors, all their entries must be positive. This is called Nonnegative Matrix Factorization (NMF). Notice that in the case of SVD, the restriction is that the basis vectors must be orthogonal. This is accomplished by the Eigendecomposition. In NMF this restriction does not apply.

There are different ways to find a NMF [2], the most obvious one is to minimize:

||X-AB|| ^{2}

An alternative objetive function is:

D(X|AB)=\sum_{ij}\left(X_{ij}\log\frac{X_{ij}}{(AB)_{ij}}-X_{ij}+(AB)_{ij}\right)

In both cases, the constraint is A,B \ge 0.

Both objective functions are not convex, so there is not an algorithm that guarantees to find the global optimum. A gradient-descent technique could be applied. Lee and Seung [1,2] proposed an iterative algorithm using recursive updating rules for A and B that have a good compromise between speed and ease of implementation.

So, why is this important? Well, there are many reasons. First, it has been shown that the latent representation produced by NMF is better than LSI and spectral clustering for tasks such as document clustering [3]. Second, the NMF algorithm is more efficient than SVD, which requires to calculate a Eigendecomposition, this allows to scale NMF even to problems with n and m in the order of millions. Finally, efficient matrix factorization algorithms (not exactly NMF, but related) have been used to successfully address challenging problems such as the Netflix Prize [4,5]. So it is not difficult to foresee an increased interest in this technique and its application to different IR, ML and recommender system problems.

What does this mean for us? Well, we have to look at it and apply to the problems that we are addressing. Some of the ideas:

1. Use NMF to perform combined visual-textual latent semantic indexing. We were working on doing this using Kernel-LSI, however we had scalability problems. Also, the literature suggests an improved performance of NMF over conventional LSI. NMF could be a very interesting alternative. 
2. According to [3], NMF not only performs dimensionality reduction but does clustering very well. So, it would be interesting to evaluate NMF as an alternative to do simultaneous visualization and summarization of document collections.
3. In order to work efficiently, NMF requires a sparse representation (this is the case, for bag-of-features representation for both text and images). However, we have expended a good deal of time working with kernel-based representation. The question is if it is possible to apply NMF when one only has a kernel matrix. [6] suggests that the answer is yes, but we have to check it carefully.
4. Also, it is interesting to see how to maintain a NMF when the X matrix is changing dynamically (new elements arriving, the object-similarity function changes, etc.). We were thinking about this problem for dynamic visualization of image collections. The solution was not obvious for SVD but it is possible that NMF makes the problem easier to tackle.

Finally, even if you are not interested on the details of NMF, I suggest to take a look to [3] it is a very interesting read. It describes how the winning team was able to deal with the Netflix problem. There are many lessons to learn from it.

[1] D. D. Lee and S. H. Seung, “Learning the parts of objects by non-negative matrix factorization,” Nature, vol. 401, no. 6755, pp. 788–791, October 1999. [Online]. Available: http://dx.doi.org/10.1038/44565
[2] D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” Advances in neural information processing systems, pp. 556–562, 2001. [Online]. Available: http://hebb.mit.edu/people/seung/papers/nmfconverge.pdf
[3] W. Xu, X. Liu, and Y. Gong, “Document clustering based on non-negative matrix factorization,” in SIGIR ’03: Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval. New York, NY, USA: ACM, 2003, pp. 267–273. [Online]. Available: http://portal.acm.org/citation.cfm?id=860485

[4] G. Takács, I. Pilászy, B. Németh, and D. Tikk, “Scalable collaborative filtering approaches for large recommender systems,” J. Mach. Learn. Res., vol. 10, pp. 623–656, 2009. [Online]. Available: http://portal.acm.org/citation.cfm?id=1577069.1577091
[5] Y. Koren, R. Bell, and C. Volinsky, "Matrix factorization techniques for recommender systems," Computer, vol. 42, no. 8, pp. 30-37, 2009. [Online]. Available: http://dx.doi.org/10.1109/MC.2009.263
[6] D. Zhang, Z.-H. Zhou, and S. Chen, “Non-negative matrix factorization on kernels,” 2006, pp. 404–412. [Online]. Available: http://www.springerlink.com/content/am285016220235t5
[7] C. Ding, X. He, and H. D. Simon, “On the equivalence of nonnegative matrix factorization and spectral clustering,” in Proc. SIAM Data Mining Conf, 2005, pp. 606–610. [Online]. Available: http://citeseerx.ist.psu.edu/viewdoc/down…
[8] C. Ding, T. Li, and W. Peng, “Nonnegative matrix factorization and probabilistic latent semantic indexing: equivalence, chi-square statistic, and a hybrid method,” in AAAI’06: Proceedings of the 21st national conference on Artificial intelligence. AAAI Press, 2006, pp. 342–347. [Online]. Available: http://portal.acm.org/citation.cfm?id=1597594

MS eScience wrap-up

Yesterday, I arrived back from Pittsburgh. MS eScience Workshop 2009 ended last saturday. In general the event was interesting and productive. I made good contacts (more about that below), learnt new things and visited one of the most important CS schools in the world (CMU).

I had my presentation last saturday after lunch. Already some people had left since this was the last day of the conference and the track was in the big conference room, so the room was not crowded at all. I got good questions and, in general, I can say that the presentation went well.

One important thing of an event like this is the possibility of making new contacts. It is nice to meet new people, but also it could be very helpful to start collaboration relationships. Some of the contacts:

• Daron Green (Senior Director of Microsoft External Research). I met him in Argentina last May. This time we met again and he explained me how things work in MSER and what we are supposed to do to get funding from Microsoft for our research.
• Jaime Puente (Senior Research Director of Microsoft External Research). He coordinates MSER engagement in Latin America, so he is very important contact for us. I was talking to him regarding the possibility of proposing a joint project MS-UN and he was very receptive.
• Oscar Naim (Research Program Manager). He is involved in the development of Zentity. We discussed about the possibility of integrating our work with this tool. I think this could work, but we have to check better the interoperability of Zentity. We have to start reviewing it ASAP.
• Julio López (Systems Scientist Faculty). Julio is a Colombian who studied his PhD at CMU and now he is a faculty member at the CS Department. He works on HPC particularly data-intensive supercomputing (Hadoop and related stuff, this is very interesting for us). He is very open and he's willing to do collaborative work with us. We also were talking about his process to go to CMU. This is interesting information for any one that wants to go there as a student or as an intern. 
• Joel Robertson (Founder and Director of Robertson Technologies). His company developed a software, NxOpinion, a software for medical decision support, that had been deployed to developing countries. We were talking about the possibility of testing this technology in Colombia.

Microsoft eScience Workshop 2009

Today the Microsoft eScience Workshop 2009 started officially. Yesterday we had some tutorials, but the event itself starts today. Right now, I'm attending the opening talk by Tony Hey, he's the MS vice president of External Research. I met him last May in Buenos Aires in the MS Faculty Summit Latinoamerica. He is very nice and showed interest about what we are doing.

The most important happening of the event so far is the release of the book The Fourth Paradigm by MS External Research:

The book includes different essays from scientist and engineers about the new way of doing science based on computer processing of huge amount of data. The third paradigm had to do also with computer support, but for simulation. The fourth paradigm is more about making sense out of the data using machine learning, data mining, visualization. So this is very related to what we are working on. One good think of the book is that it has been opened up to the public with a community commons license (yes MS releasing open stuff... hell is freezing ;) ).

At Carnegie Mellon University

Yesterday I arrived to Pittsburgh. I'm attending the Miscrosoft eScience Workshop (I'll talk about it in a later post). I'm presenting a paper from the Renata project. Microsoft is covering all the expenses of the trip, so I cannot complain.

The conference is hosted by CMU at the Gates Center for Computer Science at Carnegie Mellon University. A new building that was donated by, guess who..., Bill Gates. The building is nice with an interesting architecture. Is it better than our new "Edificio de Ciencia y Tecnología"? well, from the architecture point of view I don't know, but this building has plenty of space for students and professors. The offices and rooms are really nice and the common spaces are very roomy and comfortable. And, obviously, it cost much more money.

The CMU CS School is one of the most important in the world. It is a full school, not just a Department. In fact, it has a Department of Machine Learning. It has one of the big guns of ML, e.g., Tom Mitchell, Christos Faloutsos, etc.While I write this post, I'm sitting on a desk at the 8th floor where the ML Department is:

The first office in the hall is Tom Mitchell's. ;-)

Any way, it is interesting to be here. Though I'll be busy with the eScience workshop, so I don't think I'll be able to meet anybody.

Visit to WSU

Last week I was visiting the Department of Computer Science at the Wayne State University in Detroit. I was kindly invited by the Department's Chair, Dr. Farshad Fotouhi, and by Prof. Andrian Marcus to give a talk in the CS Graduate Seminar. In the page of the seminar you can find the slides and the audio of the talk, not the video, but you are not missing nothing interesting though ;-) (I just found that the name of the University and Bogotá are not well written... :-/ I gotta tell them to fix it).

Despite the visit was short, it was really productive. We discussed about a possible joint graduate program between both departments and explored other possibilities to collaborate. I received good comments from the presentation and I think we caused a good impression. Actually it was not difficult to prepare the presentation since we are working in many different interesting things. I gotta said, we are doing a great work, but I'm sure we can do much better.

Leydi and Jacobo came along. We stayed at Andi's house and we had a really good time in Detroit. I met Jairo Hernán Aponte, a professor from our Deepartment, who is working with Andi. They are doing a very interesting work in Software Evolution in the Severe Group. He was a very good host along with Sonia, another Andi's student; they took me around the WSU campus for a very interesting tour.

Starting the Blog

Ok, so finally I found some time to start the Blog I was promising a while ago. It is not that I have not anything else to do (actually I have a presentation to finnish, a paper to work on, abstracts to review and several e-mails to answer), but finally the task reached the top of the priority queue.

So, to put it short: I arrived 1.5 months ago to Louisville, I'm working at the Knowledge Discovery & Web Mining Lab at the University of Louisville, and finally I have settled down and have been able to do some productive work. I have been traveling as well, and I will talk about it in the next posts.