[ammai] week16 J. Lin and A. Kolcz, “Large-scale machine learning at twitter,” SIGMOD 2012

Paper:

[ammai] week 15 Mairal et al. Online dictionary learning for sparse coding. ICML 2009

Paper:
Mairal et al. Online dictionary learning for sparse coding. ICML 2009
 Sparse coding is widely used in machine learning, neuroscience,signal processing, and statistics. This paper focuses on learning the basis set, also called dictionary, to adapt it to specific data, and is proven works well in image processing domains.


    The following is the algorithm..

     In conclusion,this paper contributes:
    1.Change the dictionary learning problem into the optimization of a smoothing non-convex objective  function.

    2.The online iterative algorithm the author proposed has solved this problem by efficiently minimizing the quadratic surrogate function of the empirical cost by the set of constraints.

    3.The algorithm is faster than previous approaches to dictionary learning on both small and large datasets of natural images which means it's scalable.

[ammai] week14 Hive - A Warehousing Solution Over a Map-Reduce Framework

Paper:
Ashish Thusoo, Joydeep Sen Sarma, Namit Jain, Zheng Shao, Prasad Chakka, Suresh Anthony, Hao Liu, Pete Wyckoff, Raghotham Murthy: Hive - A Warehousing Solution Over a Map-Reduce Framework. VLDB, 2009.

      To deal with large amount of data/images, there's a tool OpenMP helping us do the map-reduce. But, the map-reduce programming model is low level and is hard to maintain and develop under their settings.

      In this paper, it promote a top level data warehousing solution called Hive. It supports queries expressed in a SQL-like language - HiveQL, which are compiled into map-reduce jobs executed on Hadoop.

    The following figure is the architecture of Hive.
      

    

     In conclusion, there are several component:
1.Hive had given a external interface for both user command line and web UI.
2.The Hive Thrift Server exposes a simple client API to execute HiveQL statements. Thrift is a
framework for cross-language services; a server written in one language can also support clients in other languages. The Thrift Hive clients generated in different languages are used to build common drivers like JDBC (java), ODBC (C++), and scripting drivers written in php, perl, python etc.
3.The Metastore is the system catalog. All other components of Hive interact with the metastore.
4.The Driver manages the life cycle of a HiveQL statement during compilation, optimization and execution.
5.The Compiler is invoked by the driver upon receiving a HiveQL statement. The compiler translates this
statement into a plan which consists of a DAG of mapreduce jobs.
6.The driver submits the individual map-reduce jobs from the DAG to the Execution Engine in a topological order.

    In metastore, the storage system should be optimized for online transactions with random accesses and updates.The metastore uses either a traditional relational database (like MySQL, Oracle) but not HDFS.

[ammai] week 13 A global geometric framework for nonlinear dimensionality reduction

Paper:
J.B. Tenenbaum, "A global geometric framework for nonlinear dimensionality reduction," Science, 2000 (ISOMAP)

This work (ISOMAP) aims to reduce the high-dimensional data to low dimension.The most difference between ISOMAP and others reduction algorithms (ex: PCA , MDS) is that it is capable of discovering the nonlinear degrees of freedom that underline complex natural observations.

The following are the steps that how it works:

It measures the distance in two ways. With near neighbors,it use Euclidean distance while measuring the distance to non-neighbors in shortest path found from Step 1 to represent the distance. After the distance is determined,ISOMAP applies the MDS to find the meaningful dimension. 

ISOMAP's global coordinates provide a simple way to analyze and manipulate high-dimensional observations in terms of their intrinsic nonlinear degrees of freedom.

[ammai] week 12 Nonlinear dimensionality reduction by locally linear embedding

Paper:
"Nonlinear dimensionality reduction by locally linear embedding" Roweis & Saul, Science, 2000.
   

    Locally linear embedding (also known as LLE) is a clever scheme for finding low-dimensional global coordinates when the data lie on a manifold embedded in a high-dimensional space.The trick is to do a di erent linear dimensionality reduction at each point (because locally a manifold looks linear) and then combine these with minimal discrepancy.

    The LLE procedure has three steps: it builds a neighborhood for each point in the data; finds the weights for linearly approximating the data in that neighborhood; and finally fi nds the low-dimensional coordinates best reconstructed by those weights. This low-dimensional coordinates are then returned.

The following figure shows what I mentioned before.

    The experiments is shown as following:

    One important application is in image retrieval. In image retrieval , the feature's dimension  describing the image might be large with nonlinear distribution. If we apply the LLE to the features,we can find the correlation and can reduct the dimension while preserving meanings.

[ammai] week 11 A Survey on Transfer Learning

Paper:
S. J. Pan and Q. Yang, “A Survey on Transfer Learning,” IEEE TKDE, 2010.

Transfer learning is the improvement of learning in a new task through the transfer of knowledge from a  related task that has already been learned. Now it is used in the computer-based machine learning task.
The need for transfer learning may arise when the data can be easily outdated. In this case, the labeled data
obtained in one time period may not follow the same distribution in a later time period.

[ammai] week9/10 Semi-Supervised Hashing for Scalable Image Retrieval

Paper:
    J. Wang et al, "Semi-Supervised Hashing for Scalable Image Retrieval," CVPR, 2010.


     
     SSH(Semi-Supervised Hashing) is based on two idea:
     (1) distribute the similar label images to the closer hash
     (2) make each hash bucket balanced.

     Assume that  is the images pairs set in which have same label, and  is the images pairs set where have different labels. The following objective function is main to the first criterion: for pairs with same label, maximize the probability such that they have fall into the closer buckets; for pairs with different, minimize such probability.
     Besides, they add a regularization to constraint such that each bucket size should be balanced: hash functions should be orthogonal.

      Because this work uses is going to learn a projection matrix W for hashing, so J becomes...

      And the author transform the constraint into a soft one like....

     ,which can maximize the variance of mapping space.

     

     The result is terrific in author's experiments as followed....

    

     SSH can maintain the semantic meanings consistency, unlike LSH method, and do not require too much time like supervised learning methods like RBM and SH.