atbrox http://atbrox.com Thu, 02 Sep 2010 04:44:43 +0000 en hourly 1 http://wordpress.org/?v=3.0.1 Recommended Mapreduce Workshop http://feedproxy.google.com/~r/atbrox/~3/-pVkq904OSo/ http://atbrox.com/2010/08/31/recommended-mapreduce-workshop/#comments Tue, 31 Aug 2010 08:02:43 +0000 Amund Tveit http://atbrox.com/?p=1390

If you are interested in Hadoop or Mapreduce, I would like to recommend participating or submitting your paper to the First International Workshop on Theory and Practice of Mapreduce (MAPRED’2010) (held in correspondance with the 2nd IEEE International Conference on Cloud Computing Technology and Science).

(I just joined the workshop as a program committee member)

Best regards,

Amund Tveit (co-founder of Atbrox)

]]> http://atbrox.com/2010/08/31/recommended-mapreduce-workshop/feed/ 0 http://atbrox.com/2010/08/31/recommended-mapreduce-workshop/ Word Count with MapReduce on a GPU – A Python Example http://feedproxy.google.com/~r/atbrox/~3/K52GkHF9sVs/ http://atbrox.com/2010/08/20/word-count-with-mapreduce-on-a-gpu-a-python-example/#comments Fri, 20 Aug 2010 12:01:57 +0000 Amund Tveit http://atbrox.com/?p=1304

Atbrox is startup company providing technology and services for Search and Mapreduce/Hadoop. Our background is from Google, IBM and research.

GPU – Graphical Processing Unit like the NVIDIA Tesla – is fascinating hardware, in particular regarding extreme parallelism (hundreds of cores) and memory bandwidth (tens of Gigabytes/second). The main programming languages for programming GPUs are C-based OpenCL and Nvidia’s Cuda, in addition there are wrappers to those in many languages, for the following example we use Andreas Klöckner’s PyCuda for Python.

Word Count with PyCuda and MapReduce

One of the classic mapreduce examples is word frequency count (i.e. individual word frequencies), but let us start with an even simpler example – word count, i.e. how many words are there in a (potentially big) string?

In python the default approach would perhaps be to do:

wordcount = len(bigstring.split())

But assuming that you didn’t have split() or that split() was too slow, what would you do?

How to calculate word count?
If you have the string mystring = "this is a string" you could iterate through it and count the number of spaces, e.g. with 

sum([1 for c in mystring if c == ' '])

(notice the one-off error), and perhaps split it up and parallelize it somehow. However, if there are several spaces in a row in the string this algorithm will fail, and it doesn’t use the GPU horsepower.

The MapReduce approach
Assuming you still have mystring = "this is a string", try to align the string almost with itself, i.e. have one string being all characters in mystring except the last – "this is a strin" == mystring[:-1] (called prefix from here), and another string with all characters in mystring except the first – "his is a string" == mystring[1:] (called suffix from here), and align those two like this:

this is a strin # prefix
his is a string # suffix

you can see that counting all occurences of when the character in the upper string (prefix) is whitespace and the corresponding character in the lower string (suffix) is non-white will give the correct count of words (with the same one-off as above that can be fixed by checking that first character is non-whitespace). This way of counting also deals with multiple spaces in a row (as the above one doesn’t). This can be expressed in Python with Map() and Reduce() as:

mystring = "this is a string"
prefix = mystring[:-1]
suffix = mystring[1:]
mapoutput = map(lambda x,y: (x == ' ')*(y != ' '), prefix, suffix)
reduceoutput = reduce(lambda x,y: x+y, mapoutput)
sum = reduceoutput + (mystring[0] != ' ') # fix one off-error

Mapreduce with PyCuda

PyCuda supports using python and numpy library with Cuda, and it also has library to support mapreduce type calls on data structures loaded to the GPU (typically arrays), under is my complete code for calculating word count with PyCuda, I used the complete works by Shakespeare as test dataset (downloaded as Plain text) and replicated it hundred times so in total 493820800 bytes (~1/2 Gigabyte) that I uploaded to our Nvidia Tesla C1060 GPU and run word count on (the results were compared with unix command line wc and len(dataset.split()) for smaller datasets).

import pycuda.autoinit
import numpy
from pycuda import gpuarray, reduction
import time

def createCudaWordCountKernel():
    initvalue = "0"
    mapper = "(a[i] == 32)*(b[i] != 32)" # 32 is ascii code for whitespace
    reducer = "a+b"
    cudafunctionarguments = "char* a, char* b"
    wordcountkernel = reduction.ReductionKernel(numpy.float32, neutral = initvalue,
                                            reduce_expr=reducer, map_expr = mapper,
                                            arguments = cudafunctionarguments)
    return wordcountkernel

def createBigDataset(filename):
    print "reading data"
    dataset = file(filename).read()
    print "creating a big dataset"
    words = " ".join(dataset.split()) # in order to get rid of \t and \n
    chars = [ord(x) for x in words]
    bigdataset = []
    for k in range(100):
        bigdataset += chars
    print "dataset size = ", len(bigdataset)
    print "creating numpy array of dataset"
    bignumpyarray = numpy.array( bigdataset, dtype=numpy.uint8)
    return bignumpyarray

def wordCount(wordcountkernel, bignumpyarray):
    print "uploading array to gpu"
    gpudataset = gpuarray.to_gpu(bignumpyarray)
    datasetsize = len(bignumpyarray)
    start = time.time()
    wordcount = wordcountkernel(gpudataset[:-1],gpudataset[1:]).get()
    stop = time.time()
    seconds = (stop-start)
    estimatepersecond = (datasetsize/seconds)/(1024*1024*1024)
    print "word count took ", seconds*1000, " milliseconds"
    print "estimated throughput ", estimatepersecond, " Gigabytes/s"
    return wordcount

if __name__ == "__main__":
    bignumpyarray = createBigDataset("dataset.txt")
    wordcountkernel = createCudaWordCountKernel()
    wordcount = wordCount(wordcountkernel, bignumpyarray)

Results

python wordcount_pycuda.py
reading data
creating a big dataset, about 1/2 GB of Shakespeare text
dataset size =  493820800
creating numpy array of dataset
uploading array to gpu
word count took  38.4578704834  milliseconds
estimated throughput  11.9587084015  Gigabytes/s (95.67 Gigabit/s)
word count =  89988104.0

Improvement Opportunities?
There are plenty of improvement opportunities, in particular fixing the creation of numpy array – bignumpyarray = numpy.array( bigdataset, dtype=numpy.uint8) – which took almost all of the total time.

It is also interesting to notice that this approach doesn’t gain from using combiners like in Hadoop/Mapreduce (a combiner is basically a reducer that sits on the tail of the mapper and creates partial results in the case of associative and commutative reducer methods, it can for all practical purposes be compared to an afterburner on a jet motor).

Atbrox on LinkedIn

Best regards,

Amund Tveit (Atbrox co-founder)

]]> http://atbrox.com/2010/08/20/word-count-with-mapreduce-on-a-gpu-a-python-example/feed/ 4 http://atbrox.com/2010/08/20/word-count-with-mapreduce-on-a-gpu-a-python-example/ Statistics about Hadoop and Mapreduce Algorithm Papers http://feedproxy.google.com/~r/atbrox/~3/sVx3K1TXCP0/ http://atbrox.com/2010/05/25/statistics-about-hadoop-and-mapreduce-algorithm-papers/#comments Tue, 25 May 2010 16:11:50 +0000 Amund Tveit http://atbrox.com/?p=1045

Underneath are statistics about which 20 papers (of about 80 papers) were most read in our 3 previous postings about mapreduce and hadoop algorithms (the postings have been read approximately 5000 times). The list is ordered by decreasing reading frequency, i.e. most popular at spot 1.

  1. MapReduce-Based Pattern Finding Algorithm Applied in Motif Detection for Prescription Compatibility Network
    authors: Yang Liu, Xiaohong Jiang, Huajun Chen , Jun Ma and Xiangyu Zhang – Zhejiang University

  2. Data-intensive text processing with Mapreduce
    authors: Jimmy Lin and Chris Dyer – University of Maryland

  3. Large-Scale Behavioral Targeting
    authors: Ye Chen (eBay), Dmitry Pavlov (Yandex Labs) and John F. Canny (University of California, Berkeley)

  4. Improving Ad Relevance in Sponsored Search
    authors: Dustin Hillard, Stefan Schroedl, Eren Manavoglu, Hema Raghavan and Chris Leggetter (Yahoo Labs)

  5. Experiences on Processing Spatial Data with MapReduce
    authors: Ariel Cary, Zhengguo Sun, Vagelis Hristidis and Naphtali Rishe – Florida International University

  6. Extracting user profiles from large scale data
    authors: Michal Shmueli-Scheuer, Haggai Roitman, David Carmel, Yosi Mass and David Konopnicki – IBM Research, Haifa

  7. Predicting the Click-Through Rate for Rare/New Ads
    authors: Kushal Dave and Vasudeva Varma – IIIT Hyderabad

  8. Parallel K-Means Clustering Based on MapReduce
    authors: Weizhong Zhao, Huifang Ma and Qing He – Chinese Academy of Sciences

  9. Storage and Retrieval of Large RDF Graph Using Hadoop and MapReduce
    authors: Mohammad Farhan Husain, Pankil Doshi, Latifur Khan and Bhavani Thuraisingham – University of Texas at Dallas

  10. Map-Reduce Meets Wider Varieties of Applications
    authors: Shimin Chen and Steven W. Schlosser – Intel Research

  11. LogMaster: Mining Event Correlations in Logs of Large-scale Cluster Systems
    authors: Wei Zhou, Jianfeng Zhan, Dan Meng (Chinese Academy of Sciences), Dongyan Xu (Purdue University) and Zhihong Zhang (China Mobile Research)

  12. Efficient Clustering of Web-Derived Data Sets
    authors: Luıs Sarmento, Eugenio Oliveira (University of Porto), Alexander P. Kehlenbeck (Google), Lyle Ungar (University of Pennsylvania)

  13. A novel approach to multiple sequence alignment using hadoop data grids
    authors: G. Sudha Sadasivam and G. Baktavatchalam – PSG College of Technology

  14. Web-Scale Distributional Similarity and Entity Set Expansion
    authors: Patrick Pantel, Eric Crestan, Ana-Maria Popescu, Vishnu Vyas (Yahoo Labs) and Arkady Borkovsky (Yandex Labs)

  15. Grammar based statistical MT on Hadoop
    authors: Ashish Venugopal and Andreas Zollmann (Carnegie Mellon University)

  16. Distributed Algorithms for Topic Models
    authors: David Newman, Arthur Asuncion, Padhraic Smyth and Max Welling – University of California, Irvine

  17. Parallel algorithms for mining large-scale rich-media data
    authors: Edward Y. Chang, Hongjie Bai and Kaihua Zhu – Google Research

  18. Learning Influence Probabilities In Social Networks
    authors: Amit Goyal, Laks V. S. Lakshmanan (University of British Columbia) and Francesco Bonchi (Yahoo! Research)

  19. MrsRF: an efficient MapReduce algorithm for analyzing large collections of evolutionary trees
    authors: Suzanne J Matthews and Tiffani L Williams – Texas A&M University

  20. User-Based Collaborative-Filtering Recommendation Algorithms on Hadoop
    authors: Zhi-Dan Zhao and Ming-sheng Shang

    Atbrox on LinkedIn

    Best regards,

    Amund Tveit (Atbrox co-founder)

    ]]> http://atbrox.com/2010/05/25/statistics-about-hadoop-and-mapreduce-algorithm-papers/feed/ 0 http://atbrox.com/2010/05/25/statistics-about-hadoop-and-mapreduce-algorithm-papers/ Towards Cloud Supercomputing http://feedproxy.google.com/~r/atbrox/~3/ArbDGwB7C2Q/ http://atbrox.com/2010/05/24/towards-cloud-supercomputing/#comments Sun, 23 May 2010 22:00:29 +0000 Amund Tveit http://atbrox.com/?p=1054

    Atbrox is startup company providing technology and services for Search and Mapreduce/Hadoop. Our background is from Google, IBM and research.

    Update 2010-July-13: Can remove towards from the title of this posting today, Amazon just launched cluster compute instances with 10GB network bandwidth between nodes (and presents a run that enters top 500 list at 146th place, I estimate the run to cost ~$20k).

    The Top 500 list is for supercomputers what Fortune 500 is for companies. About 80% of the list are supercomputers built by either Hewlett Packard or IBM, other major supercomputing vendors on the list include Dell, Sun (Oracle), Cray and SGI. Parallel linpack benchmark result is used as the ranking function for the list position (a derived list – green 500 – also includes power-efficiency in the ranking).

    Trends towards Cloud Supercomputing
    To our knowledge the entire top 500 list is currently based on physical supercomputer installations and no cloud computing configurations (i.e. virtual configurations lasting long enough to calculate the linpack benchmark), that will probably change within in a few years. There are however trends towards cloud-based supercomputing already (in particular within consumer internet services and pharmaceutical computations), here are some concrete examples:

    1. Zynga (online casual games, e.g. Farmville and Mafia Wars)
      Zynga uses 12000 Amazon EC2 nodes (ref: Manager of Cloud Operations at Zynga)

    2. Animoto (online video production service)
      Animoto scaled from 40 to 4000 EC2 nodes in 3 days (ref: CTO, Animoto)

    3. Myspace (social network)
      Myspace simulated 1 million simultaneous users using 800 large EC2 nodes (3200 cores) (ref: highscalability.com)

    4. New York Times
      New York Times used hundreds of EC2 nodes to process their archives in 36 hours (ref: The New York Times Archives + Amazon Web Services = TimesMachine)

    5. Reddit (news service)
      Reddit uses 218 EC2 nodes (ref: I run reddit’s servers)

    Examples with (rough) estimates

    1. Justin.tv (video service)
      In october 2009 Justin.tv users watched 50 million hours of video, and they cost (reported earlier) was about 1 penny per user-video-hour, a very rough estimate would be monthly costs of 50M/0.01 = 500k$, i.e. 12*500k$ = 6M$ anually. Assuming that half their costs are computational, this would be about 3M$/(24*365*0.085) ~ 4029 EC2 nodes 24×7 through the year, but since they are a video site bandwidth is probably a significant fraction of the cost, so cutting the rough estimate in half to around 2000 EC2 nodes.
      (ref: Watching TV Together, Miles Apart and Justin.tv wins funding, opens platform)

    2. Newsweek
      Newsweek saves up to $500.000 per year by moving to the cloud, assuming they cut their spending in half by using the cloud that would correspond to $500.000/(24h/day*365d/y*0.085$/h) ~ 670 EC2 nodes 24×7 through the year (probably a little less due to storage and bandwidth costs)
      (ref: Newsweek.com Explores Amazon Cloud Computing)

    3. Recovery.gov
      Recory.gov saves up to $420.000 per year by moving to the cloud, assuming they cut their spending in half by using the cloud that would correspond to $420.000/(24h/day*365d/y*0.085$/h) ~ 560 EC2 nodes 24×7 through the year (probably a little less due to storage and bandwidth costs). (ref: Feds embrace cloud computing; move Recovery.gov to Amazon EC2)

    Other examples of Cloud Supercomputing

    1. Pharmaceutical companies Eli Lilly, Johnson & Johnson and Genentech
      Offloading computations to the cloud (ref: Biotech HPC in the Cloud and The new computing pioneers)

    2. Pathwork Diagnostics
      Using EC2 for cancer diagnostics (ref: Of Unknown Origin: Diagnosing Cancer in the Cloud)

    Best regards,

    Amund Tveit

    ]]>     http://atbrox.com/2010/05/24/towards-cloud-supercomputing/feed/ 0 http://atbrox.com/2010/05/24/towards-cloud-supercomputing/     Mapreduce & Hadoop Algorithms in Academic Papers (3rd update) http://feedproxy.google.com/~r/atbrox/~3/UjoLBtFnjFM/ http://atbrox.com/2010/05/08/mapreduce-hadoop-algorithms-in-academic-papers-may-2010-update/#comments Sat, 08 May 2010 16:14:41 +0000 Amund Tveit http://atbrox.com/?p=971

    Atbrox is startup company providing technology and services for Search and Mapreduce/Hadoop. . Our background is from Google, IBM and research. Contact us if you need help with algorithms for mapreduce

    This posting is the May 2010 update to the similar posting from February 2010, with 30 new papers compared to the prior posting, new ones are marked with *.

    Motivation
    Learn from academic literature about how the mapreduce parallel model and hadoop implementation is used to solve algorithmic problems.

    Which areas do the papers cover?

    Who wrote the above papers?
    Companies: China Mobile, eBay, Google, Hewlett Packard and Intel, Microsoft, Wikipedia, Yahoo and Yandex.
    Government Institutions and Universities: US National Security Agency (NSA)
    , Carnegie Mellon University, TU Dresden, University of Pennsylvania, University of Central Florida, National University of Ireland, University of Missouri, University of Arizona, University of Glasgow, Berkeley University and National Tsing Hua University, University of California, Poznan University, Florida International University, Zhejiang University, Texas A&M University, University of California at Irvine, University of Illinois, Chinese Academy of Sciences, Vrije Universiteit, Engenharia University, State University of New York, Palacky University, University of Texas at Dallas

    Atbrox on LinkedIn

    Best regards,
    Amund Tveit (Atbrox co-founder)

    ]]>     http://atbrox.com/2010/05/08/mapreduce-hadoop-algorithms-in-academic-papers-may-2010-update/feed/ 10 http://atbrox.com/2010/05/08/mapreduce-hadoop-algorithms-in-academic-papers-may-2010-update/     Initial Thoughts on Yahoo’s Ranking Challenge http://feedproxy.google.com/~r/atbrox/~3/jhu-QCPFDyY/ http://atbrox.com/2010/02/28/initial-thoughts-on-yahoos-ranking-challenge/#comments Sat, 27 Feb 2010 23:15:09 +0000 Amund Tveit http://atbrox.com/?p=855

    Atbrox is startup company providing technology and services for Search and Mapreduce/Hadoop. Our background is from Google, IBM and Research.

    Yahoo recently announced the Learning to Rank Challenge – a pretty interesting web search challenge (as the somewhat similar Netflix Prize Challenge also was).

    Data and Problem
    The data sets contains (to my interpretation) per line:

    1. url – implicitly encoded as line number in the data set file
    2. relevance – low number=high relevance and vice versa
    3. query – represented as an id
    4. features – up to several hundreds

    and the problem is to find a function that gives relevance numbers per url per query id.

    Initial Observation
    In dataset 1 there are ~473k URLs and ~19k queries. At first I thought this meant that there are in average 473/19 ~ 24 relevance numbers for each query (see actual distribution of counts in figure below), i.e. corresponding to search result 1 to 24, but it seems like there are several URLs per unique query that has the same relevance (e.g. URLx and URLy both can have relevance 2 for queryZ). The paper Learning to Rank with Ties seems potentially relevant to deal with this.

    Multiple URLs that shares relevance for a unique query can perhaps be due to:

    1. similar/duplicate content between the URLs?
    2. a frequent query (due to sampling of examples?)
    3. uncertainty about which URL to select for particular a relevance and query?
    4. there is a tie, i.e. they are equally relevant

    Potential classification approach?
    From a classification perspective there are several (perhaps naive?) approaches that could be tried out:

    1. Use relevance levels as classes (nominal regression) and use a multiclass-classifier
    2. Train classifier as binary competition within query, i.e. relevance 1 against 2, 3, .., and relevance n against n+1, .. (probably get some sparsity problems due to this)
    3. Binary competition across queries, but is problematic due to that a relevance of 4 for one query could be more relevant than a relevance of 1 for a another query (and there is no easy way to determine that directly from the data), but if the observation related to multiple URLs per relevance level per query (see above) is caused by uncertainty one could perhaps use 1/(number of URLs per relevance level per query) as a weight to either:
      1. support training across queries, e.g. a URL for a query with relevance 1 is better that another query of relevance 1 with 37 URLs of that relevance, this approach could perhaps be used somehow using regression? The problem is to compare against different relevance levels, e.g. is a relevance 2 for a query with 1 url more confident than one of relevance 1 for a query with 37 URLs?
      2. use a classifier that supports weighing examples and the approach in 1 or 2.

    More about ranking with machine learning?
    Check out the learning to rank bibliography.

    Related articles by Zemanta
    Enhanced by Zemanta

    Best regards,

    Amund Tveit

    ]]>     http://atbrox.com/2010/02/28/initial-thoughts-on-yahoos-ranking-challenge/feed/ 0 http://atbrox.com/2010/02/28/initial-thoughts-on-yahoos-ranking-challenge/     So, what is Hadoop? http://feedproxy.google.com/~r/atbrox/~3/kZIQgRnxtAE/ http://atbrox.com/2010/02/17/hadoop/#comments Wed, 17 Feb 2010 21:39:10 +0000 Amund Tveit http://atbrox.com/?p=727

    Atbrox is startup company providing technology and services for Search and Mapreduce/Hadoop. Our background is from Google, IBM and Research.

    Hadoop is a set of open source technologies that supports reliable and cost-efficient ways of dealing with large amounts of data. Given the vast amounts of business critical and required data companies gather (e.g. required due to Sarbanes–Oxley (SOX) or EU Data Retention Directive), Hadoop becomes increasingly relevant.

    Hadoop Technologies

    Several Hadoop technologies are inspired by Google’s infrastructure.

    1. Processing and Storage

    1.1 Processing – Mapreduce
    Mapreduce can be used to process and extract knowledge from arbitrary amounts of data, e.g. web data, measurement data or financial transactions – Visa reduced their processing time for transactional statistics from 1 month to 13 minutes with Hadoop. In order to use Mapreduce developers need to parallelize their problem and program against an API – here for an example of machine learning with Hadoop. Hadoop’s Mapreduce is inspired by the paper MapReduce: Simplified Data Processing on Large Clusters.

    1.2 File Storage – HDFS
    HDFS is scalable and distributed file system. It supports configurable degree of replication for reliable storage even when running on cheap hardware. HDFS is inspired by the paper The Google File System

    1.3 Database – HBase
    HBase is a distributed database that supports storing billions of rows with millions of columns that runs on top of HDFS. HBase can replace traditional databases if they get problems scaling or become to expensive licence-wise, see this presentation about Hbase. HBase is inspired by the paper Bigtable: A Distributed Storage System for Structured Data

    2. Data Analysis

    Mapreduce can be used to analyze all kinds of data (e.g. text, multimedia, numerical data) and have high flexibility, but for more structured data the following Hadoop Technologies can be used:

    2.1 Pig
    SQL-like language/system running on top of Mapreduce. Pig is developed by Yahoo and inspired by the paper Interpreting the Data: Parallel Analysis with Sawzall

    2.2 Hive
    Datawarehouse running on top of Hadoop, developed by Facebook. Query language is very similar to SQL.

    3. Distributed Systems Development

    3.1 Avro
    Avro is used for efficient serialization of data and communication between services. It is in several ways similar to Google’s protocolbuffers and Facebook’s Thrift.

    3.2 Zookeeper
    Coordination between distributed processes. It is inspired by the paper The Chubby lock service for loosely-coupled distributed systems

    3.3 Chukwa
    Monitoring of distributed systems.

    Do you need help with Hadoop/Mapreduce?
    A good start could be to read this book, or contact Atbrox if you need help with development or parallelization of algorithms for Hadoop/Mapreduce – info@atbrox.com. See our posting for an example parallelizing and implementing a machine learning algorithm for Hadoop/Mapreduce.

    Best regards,

    Amund Tveit

    ]]>     http://atbrox.com/2010/02/17/hadoop/feed/ 0 http://atbrox.com/2010/02/17/hadoop/     Mapreduce & Hadoop Algorithms in Academic Papers (updated) http://feedproxy.google.com/~r/atbrox/~3/ZU_alB_G58o/ http://atbrox.com/2010/02/12/mapreduce-hadoop-algorithms-in-academic-papers-updated/#comments Fri, 12 Feb 2010 19:19:37 +0000 Amund Tveit http://atbrox.com/?p=662

    The newest and most up-to-date version (May 2010) this blog post is available at http://mapreducebook.org

    Atbrox is startup company providing technology and services for Search and Mapreduce/Hadoop. Our background is from from Google, IBM and Research.

    This posting is an update to the similar posting from October 2009, roughly doubling the numbers of papers from the previous posting, the new ones are marked with *

    Motivation
    Learn from academic literature about how the mapreduce parallel model and hadoop implementation is used to solve algorithmic problems.

    Which areas do the papers cover?

    Who wrote the above papers? (section added 20100307)
    Companies: China Mobile, eBay, Google, Hewlett Packard and Intel, Microsoft, Wikipedia, Yahoo and Yandex.
    Government Institutions and Universities: US National Security Agency (NSA)
    , Carnegie Mellon University, TU Dresden, University of Pennsylvania, University of Central Florida, National University of Ireland, University of Missouri, University of Arizona, University of Glasgow, Berkeley University and National Tsing Hua University, University of California, Poznan University, Florida International University, Zhejiang University, Texas A&M University, University of California at Irvine, University of Illinois, Chinese Academy of Sciences, Vrije Universiteit, Engenharia University, State University of New York, Palacky University, University of Texas at Dallas

    Do you need help with Hadoop/Mapreduce?
    A good start could be to read this book, or contact Atbrox if you need help with development or parallelization of algorithms for Hadoop/Mapreduce – info@atbrox.com. See our previous posting for an example parallelizing and implementing a machine learning algorithm for Hadoop/Mapreduce

    ]]>     http://atbrox.com/2010/02/12/mapreduce-hadoop-algorithms-in-academic-papers-updated/feed/ 6 http://atbrox.com/2010/02/12/mapreduce-hadoop-algorithms-in-academic-papers-updated/     Parallel Machine Learning for Hadoop/Mapreduce – A Python Example http://feedproxy.google.com/~r/atbrox/~3/qoTnKURhfes/ http://atbrox.com/2010/02/08/parallel-machine-learning-for-hadoopmapreduce-a-python-example/#comments Mon, 08 Feb 2010 21:27:37 +0000 Amund Tveit http://atbrox.com/?p=572

    Atbrox is startup providing technology and services for Search and Mapreduce/Hadoop. Our background is from from Google, IBM and Research.

    Update 2010-June-17 Code for this posting is now on github -http://github.com/atbrox/Snabler

    This posting gives an example of how to use Mapreduce, Python and Numpy to parallelize a linear machine learning classifier algorithm for Hadoop Streaming. It also discusses various hadoop/mapreduce-specific approaches how to potentially improve or extend the example.

    1. Background

    Classification is an everyday task, it is about selecting one out of several outcomes based on their features, e.g

    • In recycling of garbage you select the bin based on the material, e.g. plastic, metal or organic.
    • When purchasing you select the store from based e.g. on its reputation, prior experience, service, inventory and prices

    Computational Classification – Supervised Machine Learning – is quite similar, but requires (relatively) well-formed input data combined with classification algorithms.

    1.1 Examples of classification problems

    • Finance/Insurance
      • Classify investment opportunities as good or not e.g. based on industry/company metrics, portfolio diversity and currency risk.
      • Classify credit card transactions as valid or invalid based e.g. location of transaction and credit card holder, date, amount, purchased item or service, history of transactions and similar transactions
    • Biology/Medicine
    • Internet
    • Production Systems (e.g. in energy or petrochemical industries)
      • Classify and detect situations (e.g. sweet spots or risk situations) based on realtime and historic data from sensors

    1.2 Classification Algorithms

    Classification algorithms comes in various types (e.g. linear, nonlinear, discriminative etc), see my prior postings Pragmatic Classification: The Very Basics and Pragmatic Classification of Classifiers.

    Key takeaways about classifiers:

    1. There is no silver bullet classifier algorithm or feature extraction method.
    2. Classification algorithms tend to be computationally hard to train, this encourages using a parallel approach, in this case with Hadoop/Mapreduce.

    2. Parallel Classification for Hadoop Streaming

    The classifier described belongs to a familiy of classifiers which have in common that they can mathematically be described as Tikhonov Regularization with a Square loss function, this family includes Proximal SVM, Ridge Regression, Shrinkage Regression and Regularized Least-Squares Classification. (note: If you replace the Square Loss function with a Hinge-Loss function you get Support Vector Machine classification). The implemented classifier – proximal SVM – is from the paper Incremental Support Vector Machine Classification, referred to as the paper below.

    2.1 training data

    The classifier assumes numerical training data, where each class is either -1.0 og +1.0 (negative or positive class), and features are represented as vectors of positive floating point numbers. In the algorithm below are:

    D - a matrix of training classes, e.g. [[-1.0, 1.0, 1.0, .. ]]
A - a matrix with feature vectors, e.g. [[2.9, 3.3, 11.1, 2.4], .. ]
e - a vector filled with ones, e.g [1.0, 1.0, .., 1.0]
E = [A -e]
mu = scalar constant # used to tune classifier
D - a diagonal matrix with -1.0 or +1.0 values (depending on the class)

    2.2 the classifier algorithm

    Training the classifier can be done with right side of the equation (13) from paper

    (omega, gamma) = (I/mu + E.T*E).I*(E.T*D*e)

    Classification of an incoming feature vector x can then be done by calculating:

    x.T*omega - gamma

    which returns a number, and the sign of the number corresponds to the class, i.e. positive or negative.

    2. Parallelization of the classifier with Hadoop Streaming and Python

    Expression (16) in the paper has a nice property, it supports increments (and decrements), in the example there are 2 increments (and 2 decrements), but by induction there can be as many as you want:

    (omega, gamma) = (I/mu + E_.T*E_1 + .. + E_i.T*E_i).I*
                 (E_1.T*D_1*e + .. + E_i.T*D_i*e)

    where

    E.T*E = E_1.T*E_1 + .. + E_i.T*E_i

    and

    E.T*De = E_1.T*D_1*e + .. + E_i.T*D_i*e

    This means that we can parallelize the calculation of E.T*E and E.T*De, by having Hadoop mappers calculate each of the elements of the sums in as in the Python map() code below (sent to reducers as tuples)

    map() and reduce() - dataflow - basic case

    2.3 – the mapper

    def map(key, value):
   # input key= class for one training example, e.g. "-1.0"
   classes = [float(item) for item in key.split(",")]   # e.g. [-1.0]
   D = numpy.diag(classes)

   # input value = feature vector for one training example, e.g. "3.0, 7.0, 2.0"
   featurematrix = [float(item) for item in value.split(",")]
   A = numpy.matrix(featurematrix)

   # create matrix E and vector e
   e = numpy.matrix(numpy.ones(len(A)).reshape(len(A),1))
   E = numpy.matrix(numpy.append(A,-e,axis=1)) 

   # create a tuple with the values to be used by reducer
   # and encode it with base64 to avoid potential trouble with '\t' and '\n' used
   # as default separators in Hadoop Streaming
   producedvalue = base64.b64encode(pickle.dumps( (E.T*E, E.T*D*e) )    

   # note: a single constant key "producedkey" sends to only one reducer
   # somewhat "atypical" due to low degree of parallism on reducer side
   print "producedkey\t%s" % (producedvalue)

    2.4 – the Reducer

    def reduce(key, values, mu=0.1):
  sumETE = None
  sumETDe = None

  # key isn't used, so ignoring it with _ (underscore).
  for _, value in values:
    # unpickle values
    ETE, ETDe = pickle.loads(base64.b64decode(value))
    if sumETE == None:
      # create the I/mu with correct dimensions
      sumETE = numpy.matrix(numpy.eye(ETE.shape[1])/mu)
    sumETE += ETE

    if sumETDe == None:
      # create sumETDe with correct dimensions
      sumETDe = ETDe
    else:
      sumETDe += ETDe

    # note: omega = result[:-1] and gamma = result[-1]
    # but printing entire vector as output
    result = sumETE.I*sumETDe
    print "%s\t%s" % (key, str(result.tolist()))

    2.5 – Mapper and Reducer Utility Code

    Code used to run map() and reduce() methods, inspired by iterator/generator approach from this mapreduce tutorial.

    def read_input(file, separator="\t"):
    for line in file:
        yield line.rstrip().split(separator)

    def run_mapper(map, separator="\t"):
    data = read_input(sys.stdin,separator)
    for (key,value) in data:
        map(key,value)

    def run_reducer(reduce,separator="\t"):
    data = read_input(sys.stdin, separator)
    for key, values in groupby(data, itemgetter(0)):
        reduce(key, values)

    3. Finished?

    Assume your running time goes through the roof even with the above parallel approach, what to do?

    3.1 Mapper Increment Size really makes a difference!

    Since there is only 1 reducer in the presented implementation, it is useful to let mappers do most of the job. The size of the (increment) matrices – E.T*E and E.T*D*e given as input to the reducer is independent of number of training data, but dependent on the number of classification features. The workload on the reducer is also dependent on the number of matrices received by the mappes (i.e. increment size), e.g. if you have a 1000 mappers having one billion examples with 100 features each, the reducer would need to do a sum of one trillion 101×101 matrices and one trillion 101×1 vectors if the mapper sent one matrix pair per training example, but if each mapper only sent one pair of E.T*E and E.T*D*e representing all the mappers billion training examples the reducer would only need to summarize 1000 matrix pairs.

    3.2 Avoid stressing the reducer

    Add more (intermediate) reducers (combiners) that calculates partial sums of matrices. In the case of many small increments (and correspondingly many matrices) it can be useful to add an intermediate step that (in parallel) calculates sums of E.T*E and E.T*D*e before sending the sums to the final reducer, this means that the final reducer gets fewer matrices to summarize before calculating the final answer, see figure below.
    flow with intermediate mapreduce step

    3.3 Parallelize (or replace) the matrix inversion in the reduction step

    If someone comes along with a training data set with a very high feature-dimension (e.g. recommender systems, bioinformatics or text classification), the matrix inversion in the reducer can become a real bottleneck since such algorithms typically are O(n^3) (and lower bound of Omega(n^2 lg n)), where n is the number of features. A solution to this can be to use or develop hadoop/mapreduce-based parallel matrix inversion, e.g. Apache Hama, or don’t invert the matrix...

    3.4 Feature Dimensionality Reduction

    Another approach when having training data with high feature-dimension could be to reduce feature-dimensionality, for more info check out Latent Semantic Indexing (and Analysis), Singular Value Decomposition or t-Distributed Stochastic Neighbor Embedding

    3.5 Reduce IO between mappers and reducers with compression

    Twitter presented using LZO compression (on the Cloudera blog) to speed up Hadoop. Inspired by this one could in the case of high feature dimension, i.e. large E.T*E and E.T*D*e matrices, compress the output in the mapper and decompress in the reducer by replacing base64encoding/decoding and pickling above with:

    producedvalue = base64.b64encode(lzo.compress(pickle.dumps( (E.T*E, E.T*D*e) ), level=1)

    and

    ETE, ETDe = pickle.loads(lzo.decompress(base64.b64decode(value)))

    3.6 Do more work with approximately the same computing resources

    The D matrix above represents binary classification with a value of +1 or -1 representing each class. It is quite common to have classification problems with more than 2 classes. Supporting multiple classes is usually done by training by several classifiers, either 1-against-all (1 classifier trained per class) or 1-against-1 (1 classifier trained per unique pair of classes), and the run a tournament of them against each other and pick the most confident. In the case of 1-against-all classification the mapper could probably send multiple E.T*D_c*e – with one D_c per class and keep the same E.T*E, the reducer would then need to calculate (I/mu + E.TE).I once and independently multiply with several E.T*D_c*e sums to create a set of (omega,gamma) classifiers. For 1-against-1 classification it becomes somewhat more complicated, because it involves creating several E matrices since in the 1-against-1 case only the rows in E where the 2 classes competing occur are relevant.

    4. Code

    (Early) Python code of the algorithm presented above can be found at http://github.com/atbrox/Snabler (open source with Apache Licence). Please let me know if you want to contribute to the project, e.g. from mapreduce and hadoop algorithms in academic papers.

    5. More resources about machine learning with Hadoop/Mapreduce?

    Do you need help with Hadoop/Mapreduce?
    A good start could be to read this book, or contact Atbrox if you need help with development or parallelization of algorithms for Hadoop/Mapreduce – info@atbrox.com.

    ]]>     http://atbrox.com/2010/02/08/parallel-machine-learning-for-hadoopmapreduce-a-python-example/feed/ 0 http://atbrox.com/2010/02/08/parallel-machine-learning-for-hadoopmapreduce-a-python-example/     Atbrox Customer Case Study – Scalable Language Processing with Elastic Mapreduce (Hadoop) http://feedproxy.google.com/~r/atbrox/~3/8sx94xca6LM/ http://atbrox.com/2009/11/14/atbrox-customer-case-study-scalable-language-processing-with-elastic-mapreduce-hadoop/#comments Sat, 14 Nov 2009 07:04:32 +0000 Amund Tveit http://atbrox.com/?p=507

    We developed a tool for scalable language processing for our customer Lingit using Amazon’s Elastic Mapreduce.

    More details: http://aws.amazon.com/solutions/case-studies/atbrox/

    Contact us if you need help with Hadoop/Elastic Mapreduce.

    ]]>     http://atbrox.com/2009/11/14/atbrox-customer-case-study-scalable-language-processing-with-elastic-mapreduce-hadoop/feed/ 2 http://atbrox.com/2009/11/14/atbrox-customer-case-study-scalable-language-processing-with-elastic-mapreduce-hadoop/