Compile R with GotoBLAS

I want to share my experience to use GotoBLAS as an external multithread library of R. I didn’t make through performance test with other libraries (such as ATLAS) but I did got lot of performance gains with GotoBLAS in using R.

1. GotoBLAS from http://www.tacc.utexas.edu/resources/software
Follow instructions in 02QuickInstall.txt.

2. CBLAS from http://www.netlib.org/blas/blast-forum/cblas.tgz
This is not required for using R but you may need this for using GSL(GNU Scientific Library)
a. If the architecture is Linux, type
$ ln –s Make.LINUX Make.in
b. In Make.in, Modify BLLIB, CBDIR and –fPIC –lpthread to LOADER option.
c. Type make all for building libraries and testing
d. After completing, go to lib/LINUX and type
$ ld -melf_x86_64 -shared -soname libgotocblas.so -o libgotocblas.so cblas_LINUX.a

Note. try to use –m64 or –m32 if you are working with powerpc

3. R from http://cran.r-project.org/
Run configure as follows:
$ export GOTOBLAS_LIB=PATH/TO/GOTOBLAS_LIB
$ mkdir build_goto; cd build_goto;
$ ../configure --prefix=$HOME/usr/R/ --with-blas="-L$GOTOBLAS_LIB -lgotoblas -lpthread" --enable-R-shlib --enable-R-static-lib --enable-BLAS-shlib

Create AVI from R plot

1. In R, save plots as postscript (or png) files by adding sequence number. For example,

postscript(sprintf("%04d.eps", i))

2. By using ImageMagick’s convert command line tool, convert images from eps to png (You may skip if you have png files)

for f in *.eps; do convert -rotate 90 $f png32:$f.png; done

You may want to add the following options:

-resize 1280x720 : change image size
-bordercolor white -border 0x0 : add white background

3. Create AVI by using ffmpeg

ffmpeg -r 15 -sameq -i %04d.eps.png out.avi

You can control frame rate (-r rate) and quality (-sameq or –b bitrate)

 

Note:

If you need speed-up in conversion, you may try to use a bash script parallel.sh in http://pebblesinthesand.wordpress.com/2008/05/22/a-srcipt-for-running-processes-in-parallel-in-bash/

Summary of the recommendation system survey paper

I’ve found a good survey paper about recommendation systems as follows:

Gediminas Adomavicius, Alexander Tuzhilin, "Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions," IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 6, pp. 734-749, June, 2005.

A short summary:

-. A short definition of recommendation system: a problem of extrapolation for predicting unknown values

-. 3 approaches: i) Content-based, ii) Collaborative, and iii) Hybrid

i) Content-based RS(Recommendation System): a user’s feature is computed solely based on the user’s activity history. Can have the following limitations:
a. Feature extraction can be hard in some domain, such as multimedia or image
b. Over specialization: Diversity is required. Randomness, genetic algorithms, or some adjustment (remove too similar, or too different outputs)
c. New user problem: No information to consider

Known algorithms: (Naive) Bayesian classifier, Rocchio, winnow, ANN, …

ii) Collaborative RS: a user’s feature is computed by a group of like-mined people or peers. Limitations:
a. New user problem [83][89] : The same with content-based RS
b. New item problem
c. Sparsity: a few workaround ideas -- use of demographic information, dimension reduction, …

Known algorithms: clustering, Bayesian network, SVD, maximum entropy, …

iii) Hybrid RS: utilize both content-based and collaborative system.

Flash 3D Engine: Sandy3D Vs. Papervision3D

Inspired by an article compared performance between Away3D vs. Papervision3D, I’ve just wanted to compare simple performance Sandy 3D (3.1 AS3) vs. Papervision 3D (2.0. Revision 849. Code name: Greate White) in rendering 1,000 objects.

As a result, the papervision3D is faster than Sandy3D by roughly 2~3 times or even more. My benchmark implementations of both Sandy and Papervision3D and source codes are available. 

Optimization advice of Sandy can be found here.

How to Parallelize

I’ve found a very good introduction about how to parallelize applications from http://www.cs.princeton.edu/courses/archive/spr08/cos598A/parallelization_course.pdf

Especially, a few tools are very helpful to analyze the code at the beginning stage:

1. gprof – profiler. Help to decide which part should look at. Consider to use a pthread wrapper available at http://sam.zoy.org/writings/programming/gprof.html

2. helgrind – To detect race conditions

GCC 4.3.2 Compilation and OpenMP

 

In order to try OpenMP3.0, I had been trying to install gcc-4.3.2 on an x86_64 Linux box without any luck. I got the following error in building gcc-4.3.2

/usr/bin/ld: crti.o: No such file: No such file or directory

It turns out that I need 32bit libc for cross-compilation which I can’t install since I’m not a superuser. The workaround is to disable this feature by using “--disable-multilib” option as follow:

./configure –-disable-multilib
make

After installation, if you meet the following error in compiling OpenMP file:

gcc: libgomp.spec: No such file or directory,

find libgomp.spec under /path/to/gcc/lib64 and make a symbolic link under /path/to/gcc/lib/gcc/x86_64-unknown-linux-gnu/4.3.2 (See [2])

Reference:
[1] gcc-help mailing list
[2] OpenMP in 30 Minutes

Collective Collaborative Tagging System (Abstract)

Currently in the Internet many collaborative tagging sites exist, but there is the need for a service to integrate the data from the multiple sites to form a large and unified set of collaborative data from which users can have more accurate and richer information than from a single site. In our paper, we have proposed a collective collaborative tagging (CCT) service architecture in which both service providers and individual users can merge folksonomy data (in the form of keyword tags) stored in different sources to build a larger, unified repository. We have also examined a range of algorithms that can be applied to different problems in folksonomy analysis and information discovery. These algorithms address several common problems for online systems: searching, getting recommendations, finding communities of similar users, and finding interesting new information by trends. Our contributions are to a) systematically examine the available public algorithms’ application to tag-based folksonomies, and b) to propose a service architecture that can provide these algorithms as online capabilities.

cross-domain problem in making ajax call by using XMLHttpRequest

I’ve just faced with a cross-domain problem in making a mash-up site by using ajax call. In particular, I’m developing an igoogle gadget which should use cross-domain calls to retrieve data from a server outside of google domain.

I’ve found a good article to workaround this problem: http://developer.yahoo.com/javascript/howto-proxy.html

Among the solutions suggested in the article, I’m very pleased with JSONP approaches. Intuition of JSONP approach is that cross-domain problems will not occur for <script> tag. By exploiting this, call a cross-domain function, which designed to return json data enclosed in a function call, by using "src” attribute of <script> tag. Details can be found at http://bob.pythonmac.org/archives/2005/12/05/remote-json-jsonp/

Summary of “Evaluation Collaborative Filtering Recommender Systems”

The following is a short summary of:
J. Herlocker, J. Konstan, L. Terveen, and J. Riedl. Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems (TOIS), 22(1):5--53, 2004.

Commonly observed user tasks from recommender systems are as follow:
-. Annotation in context : Uses a recommender in an existing context. E.g., Overlay prediction information on top of existing links
-. Find good items : Video recommender, Item recommender, etc
-. Find All Good Items : purpose is to lower false negative rate
-. Recommend sequence : can be interesting
-. Find credible recommender : making the system more credible

Ratings can be explicit (users rate directly) or implicit (inferred from users behavior or preferences)

Commonly used evaluation metrics are:
1. Predictive accuracy
-. MAE (Mean Absolute Error) = (\sum (p_i – r_i))/N
-. MSE (Mean Square Error) = (\sum (p_i – r_i)^2)/N
-. RMSE (Root Mean Square Error) = \sqrt (MSE)
2. Classification accuracy
-. Precision : the ratio of relevant items selected to number of items selected
-. Recall : the ratio of relevant items selected to total number of relevant items available (Note: Precision and recall are inversely related.)
-. MAP(Mean Average Precision, aka F1) = 2PR/(P+R)

Netflix Prize for the best collaborative filtering algorithm

Collaborative filtering, also known as social tagging, is much more popular these days in the Internet but it’s not so clear yet how much and what kind of information we can extract from the system. Regarding this problem, I think Netflix prize would be a great challenge to make those questions clear out.

@. What to predict?

Simple. From the training set, provided by Netflix, which contains over 100M movie 1-to-5 scale ratings, we need to predict unknown movie ratings for the given qualifying set. More specifically, each data in the training set is quadruple of <user, movie, date of grade, grade> and the qualifying set is given <user, movie, date of grade, unknown grade>. We need to fill out the unknown grades by prediction and submit them for evaluation.

Besides two data sets, the training and qualifying set, Netflix provides the probe set which is a problem set with answers. With this, we can roughly estimate the accuracy without consulting with the scoring oracle.

@. How to predict?

Hard. However, we can learn from the front-runners, posted at the Leaderboard. The first annual progress winner is BellKor and they wrote about their algorithm.

@. Number-wise story

#. of data in the training set = 100,480,507
#. of users in the training set = 480,189
#. of movies in the training set = 17,770
#. of data to predict in the qualifying set = 2,817,131
#. of data in the probe set = 1,408,395

@. Research problems

As a student, trying to apply machine learning algorithms to various applications, it is interesting to study:

1. What kind of machine learning algorithms can be applied to analyze the Netflix collaborative filtering data? Furthermore, Can we find more general algorithms can be used for the data in the net?
2. How such computations can be expedited by using parallel, multi-core platform? Interestingly, is it possible to use other computing powers, such as cloud computing?
3. Can we improve accuracy by adding other information easily accessible from the Internet? What kind of infrastructure of the Internet can help this? Web2.0 or else?

@. Reading list

J. Herlocker, J. Konstan, L. Terveen, and J. Riedl. Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems (TOIS), 22(1):5--53, 2004.

R. Bell, Y. Koren, and C. Volinsky. Modeling relationships at multiple scales to improve accuracy of large recommender systems. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 95--104, 2007

R. Bell and Y. Koren. Improved Neighborhood-based Collaborative Filtering. KDD-Cup and Workshop.

R. M. Bell and Y. Koren, Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights, Proc. IEEE International Conference on Data Mining (ICDM'07), 2007

Possible useful papers can be found from the Internet. I will keep this list up-to-date, as I read through.

PMPP workshop at NCSA

I attended PMPP (Programming Massively Parallel Processors Agenda) workshop at NCSA last week (July 10th, 2008). It was great opportunity to see what we can do with parallel processors and modern powerful GPUs. Recently Multi-core or many-core has been drawing great attentions in various research communities and people are still struggling to find a way to maximize its capabilities in the coming 80-core era. In other side, Peoples have been also trying to utilize GPUs as a parallel computing unit. Modern GPUs are equipped  with tens of, or hundreds of cores, which can be used for computing intensive jobs. The workshop was about all of these: Multicores and GPUs.

Here are some highlights:

• Parallel GPU: Mostly two venders, nVidia and ATI, are actively developing this market by continually supplying powerful hardware and SDKs. nVidia provides CUDA and ATI does Stream SDK for programming kits.
• nVidia's parallel GPU with CUDA: Lightweight threads running on nVidia GPU (8 to 240 cores). Designed with parallel execution in mind, while general CPU is not. GPU can be considered as massively parallel manycore machine.
• Autotuning for multicore : Multicore tuning parameter spaces are so huge to investigate one by one. We can overcome this by systematic approaches. Details can be seen from the papers by Samuel Williams and Kaushik Datta. In their paper, many multicore tuning techniques are introduced.
• Cell broadband engine (Cell BE): Interesting demonstration was shown by Hema Reddy from IBM. Look at this article and clip. I saw the more interesting clip in the workshop but I can't find the exact one in the Internet.
• Multicore/GPU researchers : look at Pedro Trancoso, John Stone, and

MDS graph of Connotea

MDS graph with Connotea data by using GGobi.

Status report for 02/07/2008 to 02/13/2008

I have been doing tag analysis to find underlying relationships between tags, users, and resources in folksonomies. I think there are possibly two different approaches: i) frequency analysis based on resource vectors spanning over the term space and ii) graph-based analysis based on tag graphs.

In the frequency analysis, we can use Principal Component Analysis(PCA) or Independent Component Analysis(ICA). Similar approaches have been done in the field of IR. An example can be found in here, where PCA and ICA were used for tag-advertising matching.

With PCA and ICA, I produced the following figures:

 

(a) PCA with Tag-graph

(b) ICA with Tag-graph (number of component = 3)

It is very interesting that we can see some tag relationships (or tag clusters) in both two pictures but reasonable interpretation is not so easy to get. I think it's a good starting point to cluster terms for extract meaningful information. I will keep working on those graph.

As for the next step, I'm going to do analysis with graph-based methods.

Status report for 12/13/2007 to 12/19/2007

1. Listing up papers for Oral Qual.

I've been making a reading list for oral qualify exam. The focus of my oral exam will be (1) Folksonomies and Web 2.0 architecture, (2) Machine Learning, and (3) Multicore and parallel programming of machine learning algorithms.

 

2. Paper reading - HMM

I've been reading a paper about Hidden Markov Models:

L. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition," Proc IEEE, vol. 77, pp. 257-286, 1989.

A short summary is as follow:

-. HMM: A Markov chain with hidden states. HMM can be used to guess a transitions between hidden states based on the observation

-. The basic 3 problems in HMM: (a) Given a HMM model, compute probability of an observation sequence, (b) Given the observation sequence, guess a probable state sequence, and (c) Adjust HMM model parameters to maximize P(Observations|HMM Model)

-. Viterbi Algorithm can be used to solve the problem of type (b)

-. Expecation-Maximization algorithm can be applied to (c)

Status report for 11/08/2007 to 11/14/2007

I've been reading a paper about ranking in folksonomy, called FolkRank, proposed in Trend detection in folksonomies, Information Retrieval in Folksonomies: Search and Ranking.

FolkRank is based on well-known PageRank algorithm used in Google (The Anatomy of a Large-Scale Hypertextual Web Search Engine and The PageRank Citation Ranking: Bringing Order to the Web).

In a nut shell, the basic idea of PageRank is that a page is important if there are many pages linking to it. This can be formulated by the following matrix equation:

R(u) = c \sum R(v)/N or R(u) = c \sum R(v)/N + cE(u)

where

u is a web page and v is a page referring u,

R(u) and R(v) are PageRank of u and v repectively,

N is a number of all links in page u, and

E(u) is called a source of rank.

 

Folksonomy can also be represented as a graph by using the similar concept of PageRank but a few exceptions:

• Folksonomy graph is undirected, while web graph in PageRank is directed.
• Nodes are heterogeneous and the graph is triadic, while in PageRank the nodes are homogeneous.

I think it's a good start to begin with applying PageRank algorithm to folksonomy recommendation system. For this purpose, I'm planing to dig into more details on the PageRank algorithm and find some sample code for better understand.

Status report for 11/01/2007 to 11/07/2007

1. I made a reading list about folksonomy at my CGL blog or del.icio.us. I will update the list frequently by adding related articles.

2. Characteristics of Folksonomy Network

The folksonomy networks show the following characteristics:

a. Small-world Network

Almost similar with a random network but having much larger clustering co-efficient factor. I.e., Small shortest path but a larger clustering coefficient.

b. Scale-free Network

A scale-free network is a network in which any two nodes can be connected no matter what the system size is. This is because there is a node called "hub"which is a highly connected node than any others. In folksonomies, popular keywords can act like this hub and thus the network shows scale-free network properties.

A scale-free network shows the following rules:

(1) Power law : Degree distribution follows the Yule-Simon distribution, which is called a power law: P(k) ~ k^(-r), where k is a degree of connectivity of a node and P(k) is it's probability

(2) Preferential Attachment : A way to build a scale-free network. The idea is to make a connection with a more connected node.

3. Next step

a. Build a simple graph by using CITEAM tag data

b. Find some algorithms about recommendation

Reading list about folksonomy analysis

(Also available at http://del.icio.us/yyalli/folksonomy)

Formal Model, Graph

• The Complex Dynamics of Collaborative Tagging, HT 07
• Network Properties of Folksonomies, WWW 07
• Mining Association Rules in Folksonomies, Data Science and Classification
• Ontologies are us: A unified model of social networks and semantics, Web Semant. 5, 1 (Mar. 2007)
• Folksonomy as a Complex Network
• Trend detection in folksonomies, LNCS, 2006
• A Social Networking Model of a Web Community,

Semantic Web

• Bridging the Gap Between Folksonomies and the Semantic Web: An Experience Report, ESWC 07

Pattern, Structure

• Towards Better Understanding of Folksonomic Patterns, HT 07
• HT06, tagging paper, taxonomy, Flickr, academic article, to read, HT 06

Recommendation, Ranking, Trend

• Tag Recommendations in Folksonomies, LNCS, 2007
• Trend detection in folksonomies
• Recommending Smart Tags in a Social Bookmarking System
• Information Retrieval in Folksonomies: Search and Ranking
• Harvesting social knowledge from folksonomies, HT 06

Tag Generation

• P-TAG: large scale automatic generation of personalized annotation tags for the web, WWW 07

PageRank

• The Anatomy of a Large-Scale Hypertextual Web Search Engine, Sergey Brin and Lawrence Page, 1998
• The PageRank Citation Ranking: Bringing Order to the Web, 1998

Clustering (referred from Filippo Menczer's class material)

• Web Page Recommender System based on Folksonomy Mining for ITNG ’06 Submissions, ITNG '06, 2006
• Finding related pages in the World Wide Web, Computer Networks, 1999
• Self-Organization and Identification of Web Communities, IEEE Computer, 2002
• Finding replicated Web collections, ACM SIGMOD '00, 2000
• Community structure in social and biological networks, PNAS, 2002
• Defining and identifying communities in networks, PNAS, 2004

Learning and Classification (referred from Filippo Menczer's class material)

• Text Categorization with Support Vector Machines: Learning with Many Relevant Features, 1997
• Support Vector Machines, 1998
• A Tutorial on Support Vector Machines for Pattern Recognition, 1998
• A re-examination of text categorization methods, ACM SIGIR, 1999

Status report for 10/04/2007 to 10/10/2007

 

I have been searching articles about folksonomies in the Internet. Among them the followings are useful to understand:

• Folksonomies - Cooperative Classification and Communication Through Shared Metadata : Pros and cons about folksonomies. Future research areas.
• Ontology of Folksonomy : Roles of ontologies and folksonomies.

Some researches about folksonomy applications by using machine learning algorithms.

• Visualizing Folksonomies using Machine Learning Algorithms
• Learning from a Visual Folksonomy: Automatically Annotating Images from Flickr
• Optimizing web search using social annotations

I have also started reading an introductory machine learning book, "Introduction to machine learning" by Ethem Alpaydin. During the next week, I will search and read more papers about folksonomies and machine learning.

Status Report for 06/07/07 to 06/13/07

Issues in using NWS
1. Hostnames
NWS’s memory service, which provides memory service to store NWS sensors’ data, saves data based on NWS sensors’ hostnames. (A hostname is a system name returned by gethostname or ‘hostname -–fqdn’) This can be problem when a master and sensors installed in different clusters and a sensor’s hostname is not a public domain name, i.e., internal hostname. For example, BigRed's hostname is not for publicly accessible from the Internent, rather hostnames are for only internal uses. In this case, NWS’s information extractor, nws_extract , can not show correct data to a user. If the memory service is in the same cluster with sensors, it will be ok but no other sensors outside clusters will be allowed.

2. Manager nodes and computing nodes
NWS’s bandwidth measurement may be incorrect depending on cluster’s topology. For instance, NCSA’s TeraGrid cluster consists of four manager nodes, which have all public hostnames and thus can be accessible from the Internet, and hundreds of computing nodes, whose hostname is not known unless submitting a job. To measure bandwidth before knowing which node will run a job can be difficult. To overcome this possible problem, knowledge on a cluster’s topology or managing policy will be required, if possible, by contacting a help desk.

Status Report for 05/31/07 to 06/06/07

NWS installation in TeraGrid

I've installed a NWS client in a few TeraGrid clusters and in my local machine to measure network bandwidth information between them. To sum up, we need to run the followings for a master node and a client node

a. Mater node
nws_nameserver
nws_memory
nws_sensor

b. Client node
nws_sensor

To start measuring, we need to submit the following command:

start_activity -f file_name name_server

To extract measured values, type the following:

nws_extract -N name_server -f time,measurement band from_node to_node

Here is some outputs for network bandwidth:

## Units: Megabits/second
## E.g.,
## 1181197165 (<= This is time) 6.148710000(<= This is bandwidth, Megabits/second)
## Network bandwidth between a.ufo.edu and b.ufo.edu
$ nws_extract -N nameserver.ufo.edu -f time,measurement,source,destination band a.ufo.edu b.ufo.edu
Time Measure Source Destination
1181197165 6.148710000 a.ufo.edu b.ufo.edu
1181197285 6.142370000
1181197405 6.135040000