Thursday, 17 November 2011 00:07
Marinka
In this short post I would like to update you on some recent changes in the MF  Matrix Factorization Techniques for Data Mining Library.
Recently, the library MF  Matrix Factorization Techniques for Data Mining has been moved and renamed. It is now called Nimfa  A Python Library for Nonnegative Matrix Factorization or short, nimfa. The latest version with documentation, link to source code and working examples can be found at nimfa.biolab.si. Those of you still having old links, are kindly requested to update the new information  you will be automatically redirected to the new site if you visit old page.
Hope you like the new name.
Enjoy.
Last Updated on Sunday, 25 August 2013 21:36
Saturday, 24 September 2011 13:41
Marinka
I have always been fascinated by the world of fractals and have been deeply enthusiastic exploring the maths behind them. This post is announcing the support of the fractal dimension computation in the MF  Matrix Factorization for Data Mining library.
In the following paragraphs we shortly revise the most important concepts and definitions of the fractal dimension.
The embedding dimensionality of a data set is the number of attributes in the data set. The intrinsic dimensionality is defined as the actual number of dimensions in which the mdimensional original vectors can be embedded under the assumption that some distance in the reduced space is kept among them. Given a fractal as a selfsimilar set of points with selfsimilar pieces, where each is scaled down by a factor of , the fractal dimension of the object is defined as
.
Example: Sierpinski triangle (My seminar work for CG on Lsystems  figure 1 in Appendix of the Report document) consists of three selfsimilar parts and each is scaled down by a factor of two, therefore its fractal dimension is
For the finite set of points in a vector space, we say the set is statistically selfsimilar on a range of scaleson which the selfsimilarity is true. However in the theory selfsimilar object should have infinitely many points because each selfsimilar part is a scaleddown version of the original object. As a measure of the intrinsic fractal dimension of a data set, the slope of the correlation integral is used. The correlation integral for the data set is defined as
Given a data set which is statistically selfsimilar in the range, its correlation fractal dimension is
It has been shown that the correlation fractal dimension corresponds to the intrinsic dimension of a data set. Many properties hold for the correlation fractal dimension, see [1] and [2]. For us it is especially important, that the intrinsic dimensionality gives a lower bound on the number on attributes needed to keep the vital characteristics of the data set.
A fast algorithm for the computation of the intrinsic dimension of a data set presented in [2] is implemented in the MF  Matrix Factorization for Data Mining library. Intuitive explanation of the correlation fractal dimension is that is measures how the number of neighbor points increases with the increase of the distance. It therefore measures the spread of the data and the fractal dimension equal to the embedding dimension means that the spread of the points in the data set is maximum.
Of high importance is a Conjecture 1 in [1]: With all the parameters being equal, a dimensionality reduction method which achieves higher fractal dimension in the reduced space is better than the rest for any data mining task. Therefore correlation fractal dimension of a data set can be used:
 for determining the optimal number of dimensions in the reduced space,
 as a performance comparison tool between dimensionality reduction methods,
and all this can be done in way that is scalable to large data sets.
Recommended reading:
 Kumaraswamy, K., (2003). Fractal Dimension for Data Mining. Carnegie Mellon University.
 Jr, C. T., Traina, A., Wu, L., Faloutsos, C., (2010). Fast Feature Selection using Fractal Dimension. Science, 1(1), 316.
In [1] a concept of intrinsic fractal dimension of a data set is introduced and it is shown how fractal dimension can be used to aid in several data mining tasks. In [2] a fast O(n) algorithm to compute fractal dimension of a data set is presented. On top of that a fast, scalable algorithm to quickly select the most important attributes of the given set of ndimensional vectors is described.
Last Updated on Sunday, 25 August 2013 21:36
Friday, 26 August 2011 15:09
Marinka
Google Summer of Code 2011 has finished. On 22th of August it was firm "pencils down" date and today, on 26th of August, has been final evaluation deadline. Therefore, it is time for a small review to be published here on my blog.
I successfully completed the program and have met all the goals, outlined in the original project plan with some (2) additional factorization methods I have implemented. I have been very satisfied with the support and mentoring of both the organization and mentor.
The project, I have worked on, has been developing library MF  Matrix Factorization Techniques for Data Mining which includes a number of published matrix factorization algorithms, initialization methods, quality and performance measures and facilitates the combination of these to produce new strategies. The library contains examples of usage, applications of factorization methods on both synthetic and real world data sets are provided.
Matrix factorization methods have been shown to be a useful decomposition for multivariate data as low dimensional data representations are crucial to numerous applications in statistics, signal processing and machine learning.
An incomplete list of applications of matrix factorization methods includes:
 bioinformatics,
 environmetrics and chemometrics,
 image processing and computer graphics,
 text analysis,
 miscelllaneous, such as extracting speech features, transcription of polyphonic music passages, object characterization, spectral data analysis, multiway clustering, learning sound dictionaries, etc.
Example using synthetic data set is intended as demonstration of the MF library since all currently implemented factorization algorithms with different initialization methods and specific settings are ran. Others include applications on real world data sets in:
 bioinformatics,
 text analysis,
 image processing,
 recommendation systems.
I will outline only the most important content of the MF library here (for any details refer to documentation (or code)), as this is project review and not library reference (references to articles are provided in the documentation).
 Matrix Factorization Methods
 BD  Bayesian nonnegative matrix factorization Gibbs sampler [Schmidt2009]
 BMF  Binary matrix factorization [Zhang2007]
 ICM  Iterated conditional modes nonnegative matrix factorization [Schmidt2009]
 LFNMF  Fisher nonnegative matrix factorization for learning Local features [Wang2004], [Li2001]
 LSNMF  Alternative nonnegative least squares matrix factorization using projected gradient method for subproblems [Lin2007]
 NMF  Standard nonnegative matrix factorization with Euclidean / KullbackLeibler update equations and Frobenius / divergence / connectivity cost functions [Lee2001], [Brunet2004]
 NSNMF  Nonsmooth nonnegative matrix factorization [Montano2006]
 PMF  Probabilistic nonnegative matrix factorization [Laurberg2008], [Hansen2008]
 PSMF  Probabilistic sparse matrix factorization [Dueck2005], [Dueck2004], [Srebro2001], [Li2007]
 SNMF  (SNMF/L, SNMF/R) Sparse nonnegative matrix factorization based on alternating nonnegativity constrained least squares [Park2007]
 SNMNMF  Sparse network regularized multiple nonnegative matrix factorization [Zhang2011]
 Quality and Performance Measures
 Distance
 Residuals
 Connectivity matrix
 Consensus matrix
 Entropy of the fitted NMF model [Park2007]
 Dominant basis components computation
 Explained variance
 Feature score computation representing its specificity to basis vectors [Park2007]
 Computation of most basis specific features for basis vectors [Park2007]
 Purity [Park2007]
 Residual sum of squares  can be used for rank estimate [Hutchins2008], [Frigyesi2008]
 Sparseness [Hoyer2004]
 Cophenetic correlation coefficient of consensus matrix  can be used for rank estimate [Brunet2004]
 Dispersion [Park2007]
 Selected matrix factorization method specific
 Fitted factorization model tracker across multiple runs
 Residuals tracker across multiple factorizations / runs
 Different factorization models
Relevant links:
Join the GSoC next year! It is a great opportunity to spend the summer learning something new and having fun at the same time.
Last Updated on Sunday, 25 August 2013 21:36
Thursday, 04 August 2011 16:50
Marinka
It has been some time since my last post, but here is the new one. Perhaps the title sounds a bit inappropriate, but indeed it is well suited. Read till the end, where I explain it for those not figuring it yet (or consider it a puzzle :))
So, what have I been up to lately? Despite summer holidays I have been involved in quite a few projects.
First, GSoC Matrix Factorization Techniques for Data Mining project for Orange has been progressing well. Code is almost finished, no major changes in framework, factorization/initialization methods, quality measures, etc. are expected. Project is on schedule and has not diverged from initial plan, all intended techniques (plus a few additional I have found interesting along research) are implemented. I have been doing some testing, and have yet to provide more use cases/examples along with thorough explanation and example data sets. I will not go into details here, as implemented methods' descriptions with paper references are published at Orange wiki project site. The project is great, a mix of linear algebra, optimization methods, statistics and probability, numerical methods (analysis if you want to read some convergence or derivation proofs) with intensive applications in data mining, machine learning, computer vision, bioinformatics etc. and I have been really enjoying working on it, here is my post at Orange blog. The Orange and its GSoCers have been spotlighted at Google Open Source Blog.
Next, there is some image processing; segmentation, primary and secondary object detection, object tracking, morphology measures, filters etc. (no details).
Minor for keeping contact with MS world, Sharepoint Server 2010 (SP 10). I have some experience with it (and its previous version MOSS 2007), both in administration and especially in code. This time it was not about coding workflows using Win Workflow Foundation, developing Web parts/sites/custom content types/web services (...) but providing an insite publishing hierarchy for data in custom lists and integration with Excel Services (not with new 365 Cloud service). Obstacles were limited server access (hosting plan), old versions of software and usual MS stuffs (:)). In SP 10 these are SPFieldLookups filters and cascading lookups, data connections between sites/lists/other content. As always there are some nice workarounds which have resolved all issues.
Last (not least) I have been catching up with all the reading material I was forced to put aside during the year (well not entirely true: the more I read, the more should be read, so the pile of papers in iBooks and Mendeley app is not getting any smaller :)).
Here we are, what about the post's title? The sunrise problem was introduced by Laplace (french mathematician known for Bayesian interpretation of probability, Laplace transform, Laplace equation, differential operator, work in mechanics and physics). Is the probability that the sun will rise tomorrow 1 if we can infer from the observed data that is has risen every day on record? :) So what is the answer of the question in the title? The inferred probability depends on the record  whether we take the past experience of one person, humanity, or the Earth history. This is the reference class problem  with Bayes any probability is the conditional probability given what a person knows. Simple principle emerged from this, addone or Laplacian smoothing (Example: Doing spam email classification with a bag of words model or text classification with multinomial model, this allows the assignment of positive probabilities to words which do not occur in the sample) and corresponds to the expected value of the posterior.
Last Updated on Wednesday, 30 January 2013 23:42
Friday, 08 July 2011 09:19
Marinka
Impressions from Google Scholars' Retreat 2011, which took place last month in Zurich, Switzerland, where the Retreat for the EMEA region was organized, are great. It has really been a valuable experience to meet many Googlers, other scholars and their research work.
Below is this year logo.
Let me mention just a few workshops and talks I have attended during the Retreat:
 Keynote speech
 Working in Industry
 Product Design Workshop
 Career Panel
 Poster Show
 Android Technical Talk
 Open source and Google Support of its Advancement in the Community (Details: Open source community at Google, development model and how Google uses it and supports advancement of this community.)
 Google Web API (Details: Generic principles of Google Web APIs and the tools Google provide for learning and experimenting with them. Focus on interaction with these tools for research, be it to harvest data or to help present data in an efficient way.)
 *Privacy, the Ultimate Interdisciplinary Challenge (Details: The questions of deletion and digital rights management, online reputation and selfrepresentation, the right to be forgotten.)
 *Google.org  Using Google's Strengths to Address Global Challenges (Details: Google.org is tasked with using Google's strengths in technology and the Internet to address global challenges. The session covered development of Google Flu Trends as well as more recent work including Google Earth Engine and Google Crisis Response.)
 *Street View 3D (Details: Many problems arise when developing such a product, such as augmenting the panoramas with 3D features for better navigation and a more immersive experience.)
 *Priority Inbox (Details: Because importance is highly personal, email importance is predicted by learning a peruser statistical model, updated as frequently as possible. The challenges include inferring the importance of mail without explicit user labeling; finding learning methods that deal with nonstationary and noisy training data; constructing models that reduce training data requirements; storing and processing terabytes of peruser feature data; predicting in a distributed and faulttolerant way.)
Beside that there were some very informative talks on business visions of Google, ways of involvement with Google, office tours (I liked the slides between the floors :)) and lots of small talk with Googlers.
Last Updated on Thursday, 09 July 2015 15:09
Wednesday, 15 June 2011 13:12
Marinka
One of the courses I attended this semester has been Computer Graphics (CG).
I have spent some time studying algorithmic botany and especially Lsystems, formal grammars for describing fractal objects. These can be used for generation of objects in biology, botany, and even buildings and entires cities. Rome Reborn is an example of such project, in which formal grammars were used for the creation of the 3D digital model illustrating the urban development of ancient Rome.
So I have decided to visualize some of the 3D fractal objects using OpenGL and LWJGL library. Below are links to short report and presentation. Take a look :)
Those of you who are interested, great book on this topic by the father of algorithmic botany, Aristid Lindenmayer. Prusinkiewicz, Przemyslaw; Aristid Lindenmayer (1990). The Algorithmic Beauty of Plants (The Virtual Laboratory).SpringerVerlag. ISBN 0387972978
Last Updated on Wednesday, 23 July 2014 16:06
Thursday, 02 June 2011 23:23
Marinka
Yet another great news concering my (little) involvement with Google. I have written few weeks ago about being accepted to the Google Summer of Code 2011 with the project on matrix factorizations techniques in data mining for the Orange platform.
Nevertheless, Google has announced Google Anita Borg Scholarship Recipients and Finalists, a Scholarship for which I have applied this year and I am among 147 undergraduate and graduate students worldwide being chosen. Just for clarification  this is completely unrelated to the GSoC (the only common denominator being the Google itself), the scholarship however being awarded based on the strength of candidates’ academic performance, leadership experience and demonstrated passion for computer science.
Scholars from Europe have Scholars' Retreat at European Google centre at Zurich in June and I am very much looking forward to this event to meet some fascinating people. The retreat will include workshops, speakers, panelists, breakout sessions and social activities scheduled over a couple of days.
 (Official Google Blog with published results of the Scholars's selection process) link
 (Official Google Students Blog with published announcement of the Scholars's) link
 (Faculty News) link in Slovene
Last Updated on Wednesday, 25 December 2013 02:58
Saturday, 07 May 2011 17:32
Marinka
Google Team has shared a new Chrome experiment, called the WebGL Globe, namely the visualization platform for geographic data that runs in WebGL enabled browsers  Chrome, Firefox. (Check http://www.doesmybrowsersupportwebgl.com/ if your browser supports the WebGL standard).
To speed up the visualization of 3D geometry, they have used vertex shader and took advantage of GLSL with two fragment shaders. 3D data spikes are drawn with Three.js, JS library for building lightweight 3D graphics.
I have embedded simple globe showing Google search traffic. Try it or try more examples that shipped with this cool open source project. Or create your own globe using the JSON data format.
Here is post of Official Google Code Blog. Nice job :)
Last Updated on Wednesday, 30 January 2013 23:39
Sunday, 24 April 2011 08:21
Marinka
Constrained LS Problems
Subset Selection Using SVD
Total LS
Comparing Subspaces Using SVD
Some Modified Eigenvalue Problems
Updating the QR Factorization
Last Updated on Wednesday, 30 January 2013 23:43
Wednesday, 06 April 2011 23:53
Marinka
This year I have applied for the Google Summer of Code, namely the Orange project.
Will see if I will be accepted. :)
Update 25.04.2011: Google has announced the results. My proposal has been accepted and am looking forward to start working. :)
Some links to articles in Slovenian news:
Project title: Matrix Factorization Techniques for Data Mining
Description: Matrix factorization is a fundamental building block for many of current data mining approaches and factorization techniques are widely used in applications of data mining. Our objective is to provide the Orange community with a unifed and efficient interface to matrix factorization algorithms and methods. For that purpose we will develop a scripting library which will include a number of published factorization algorithms and initialization methods and will facilitate the combination of these to produce new strategies. Extensive documentation with working examples that will demonstrate real applications, commonly used benchmark data and visualization methods will be provided to help with the interpretation and comprehension of the results.
Main factorization techniques and their variations planned to be included in the library are: Bayesian decomposition (BD) together with linearly constrained and variational BD using Gibbs sampling, probabilistic matrix factorization (PMF), Bayesian factor regression modeling (BFRM), family of nonnegative matrix factorizations (NMF) including sparse NMF, nonsmooth NMF, local factorization with Fisher NMF, leastsquares NMF. Different multiplicative and update algorithms for NMF will be analyzed which minimize LS error or generalized KL divergence. Further nonnegative matrix approximations (NNMA) with extensions will be implemented. For completeness algorithms such as NCA, ICA and PCA could be added to the library.
Here is proposal document.
Last Updated on Sunday, 25 August 2013 21:33

