Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Parallel and Large Scale Machine Learning with ...

Parallel and Large Scale Machine Learning with scikit-learn

Talk by Olivier Grisel @ogrisel at Data Science London @ds_ldn 07/03/13

Data Science London

March 09, 2013
Tweet

More Decks by Data Science London

Other Decks in Technology

Transcript

  1. About me • Regular contributor to scikit-learn • Interested in

    NLP, Computer Vision, Predictive Modeling & ML in general • Interested in Cloud Tech and Scaling Stuff • Starting my own ML consulting business: http://ogrisel.com jeudi 7 mars 13
  2. Outline • The Problem and the Ecosystem • Scaling Text

    Classification • Scaling Forest Models • Introduction to IPython.parallel & StarCluster • Scaling Model Selection & Evaluation jeudi 7 mars 13
  3. Parts of the Ecosystem ——— Multiple Machines with Multiple Cores

    ——— Single Machine with Multiple Cores multiprocessing jeudi 7 mars 13
  4. The Problem Big CPU (Supercomputers - MPI) Simulating stuff from

    models Big Data (Google scale - MapReduce) Counting stuff in logs / Indexing the Web Machine Learning? often somewhere in the middle jeudi 7 mars 13
  5. Cross Validation A B C A B C Subset of

    the data used to train the model Held-out test set for evaluation jeudi 7 mars 13
  6. Cross Validation A B C A B C A C

    B A C B B C A B C A jeudi 7 mars 13
  7. Model Selection the Hyperparameters hell param_1 in [1, 10, 100]

    param_2 in [1e3, 1e4, 1e5] Find the best combination of parameters that maximizes the Cross Validated Score jeudi 7 mars 13
  8. Grid Search (1, 1e3) (10, 1e3) (100, 1e3) (1, 1e4)

    (10, 1e4) (100, 1e4) (1, 1e5) (10, 1e5) (100, 1e5) param_2 param_1 jeudi 7 mars 13
  9. (1, 1e3) (10, 1e3) (100, 1e3) (1, 1e4) (10, 1e4)

    (100, 1e4) (1, 1e5) (10, 1e5) (100, 1e5) jeudi 7 mars 13
  10. Parallel ML Use Cases • Stateless Feature Extraction • Model

    Assessment with Cross Validation • Model Selection with Grid Search • Bagging Models: Random Forests • In-Loop Averaged Models jeudi 7 mars 13
  11. Embarrassingly Parallel ML Use Cases • Stateless Feature Extraction •

    Model Assessment with Cross Validation • Model Selection with Grid Search • Bagging Models: Random Forests • In-Loop Averaged Models jeudi 7 mars 13
  12. Inter-Process Comm. Use Cases • Stateless Feature Extraction • Model

    Assessment with Cross Validation • Model Selection with Grid Search • Bagging Models: Random Forests • In-Loop Averaged Models jeudi 7 mars 13
  13. (Count|TfIdf)Vectorizer Scalability Issues • Builds an In-Memory Vocabulary from text

    tokens to integer feature indices • A Big Python dict: slow to (un)pickle • Large Corpus: ~10^6 tokens • Vocabulary == Statefulness == Sync barrier • No easy way to run in parallel jeudi 7 mars 13
  14. >>> from sklearn.feature_extraction.text ... import TfidfVectorizer >>> vec = TfidfVectorizer()

    >>> vec.fit(["The cat sat on the mat."]) >>> vec.vocabulary_ {u'cat': 0, u'mat': 1, u'on': 2, u'sat': 3, u'the': 4} jeudi 7 mars 13
  15. The Hashing Trick • Replace the Python dict by a

    hash function: • Does not need any memory storage • Hashing is stateless: can run in parallel! >>> from sklearn.utils.murmurhash import * >>> murmurhash3_bytes_u32('cat', 0) % 10 9L >>> murmurhash3_bytes_u32('sat', 0) % 10 0L jeudi 7 mars 13
  16. >>> from sklearn.feature_extraction.text ... import HashingVectorizer >>> vec = HashingVectorizer()

    >>> out = vec.transform([ ... "The cat sat on the mat."]) >>> out.shape (1, 1048576) >>> out.nnz # number of non-zero elements 5 jeudi 7 mars 13
  17. Loading 20 newsgroups dataset for all categories 11314 documents -

    22.055MB (training set) 7532 documents - 13.801MB (testing set) Extracting features from the training dataset using a sparse vectorizer done in 12.881007s at 1.712MB/s n_samples: 11314, n_features: 129792 Extracting features from the test dataset using the same vectorizer done in 4.043470s at 3.413MB/s n_samples: 7532, n_features: 129792 TfidfVectorizer jeudi 7 mars 13
  18. Loading 20 newsgroups dataset for all categories 11314 documents -

    22.055MB (training set) 7532 documents - 13.801MB (testing set) Extracting features from the training dataset using a sparse vectorizer done in 5.281561s at 4.176MB/s n_samples: 11314, n_features: 65536 Extracting features from the test dataset using the same vectorizer done in 3.413027s at 4.044MB/s n_samples: 7532, n_features: 65536 HashingVectorizer jeudi 7 mars 13
  19. HashingVectorizer on Amazon Reviews • Music reviews: 216MB XML file

    140MB raw text / 174,180 reviews: 53s • Books reviews: 1.3GB XML file 900MB raw text / 975,194 reviews: ~6min • https://gist.github.com/ogrisel/4313514 jeudi 7 mars 13
  20. Partition the Text Data Labels 1 Text Data 1 Labels

    2 Text Data 2 Labels 3 Text Data 3 jeudi 7 mars 13
  21. Vectorizer in Parallel Labels 1 Text Data 1 Labels 2

    Text Data 2 Labels 3 Text Data 3 vec vec vec Labels 1 Vec Data 1 Labels 2 Vec Data 2 Labels 3 Text Data 3 jeudi 7 mars 13
  22. Train Linear Models in Parallel Labels 1 Text Data 1

    Labels 2 Text Data 2 Labels 3 Text Data 3 vec vec vec Labels 1 Vec Data 1 Labels 2 Vec Data 2 Labels 3 Text Data 3 clf_1 clf_2 clf_2 clf_3 jeudi 7 mars 13
  23. Collect Models and Average clf = ( clf_1 + clf_2

    + clf_3 ) / 3 jeudi 7 mars 13
  24. >>> clf = clone(clf_1) >>> clf.coef_ += clf_2.coef_ >>> clf.coef_

    += clf_3.coef_ >>> clf.intercept_ += clf_2.intercept_ >>> clf.intercept_ += clf_3.intercept_ >>> clf.coef_ /= 3; clf.intercept_ /= 3 Averaging Linear Models jeudi 7 mars 13
  25. >>> clf = clone(clf_1) >>> clf.coef_ += clf_2.coef_ >>> clf.coef_

    += clf_3.coef_ >>> clf.intercept_ += clf_2.intercept_ >>> clf.intercept_ += clf_3.intercept_ >>> clf.coef_ /= 3; clf.intercept_ /= 3 Averaging Linear Models jeudi 7 mars 13
  26. >>> clf = clone(clf_1) >>> clf.coef_ += clf_2.coef_ >>> clf.coef_

    += clf_3.coef_ >>> clf.intercept_ += clf_2.intercept_ >>> clf.intercept_ += clf_3.intercept_ >>> clf.coef_ /= 3; clf.intercept_ /= 3 Averaging Linear Models jeudi 7 mars 13
  27. >>> clf = clone(clf_1) >>> clf.coef_ += clf_2.coef_ >>> clf.coef_

    += clf_3.coef_ >>> clf.intercept_ += clf_2.intercept_ >>> clf.intercept_ += clf_3.intercept_ >>> clf.coef_ /= 3; clf.intercept_ /= 3 Averaging Linear Models jeudi 7 mars 13
  28. Tricks • Try: ExtraTreesClassifier instead of: RandomForestClassifier • Faster to

    train • Sometimes better generalization too • Both kind of Forest Models are naturally embarrassingly parallel models. jeudi 7 mars 13
  29. Partition Replicate the Dataset All Labels All Data All Labels

    All Data All Labels All Data jeudi 7 mars 13
  30. Train Forest Models in Parallel clf_1 clf_2 clf_2 clf_3 All

    Labels All Data All Labels All Data All Labels All Data Seed each model with a different random_state integer! jeudi 7 mars 13
  31. Collect Models and Combine clf = ( clf_1 + clf_2

    + clf_3 ) Forest Models naturally do the averaging at prediction time. >>> clf = clone(clf_1) >>> clf.estimators_ += clf_2.estimators_ >>> clf.estimators_ += clf_3.estimators_ jeudi 7 mars 13
  32. Partition Replicate Partition the Dataset Labels 1 Data 1 Labels

    2 Data 2 Labels 3 Data 3 jeudi 7 mars 13
  33. Train Forest Models in Parallel clf_1 clf_2 clf_2 clf_3 Labels

    1 Data 1 Labels 2 Data 2 Labels 3 Data 3 jeudi 7 mars 13
  34. Collect Models and Sum clf = ( clf_1 + clf_2

    + clf_3 ) >>> clf = clone(clf_1) >>> clf.estimators_ += clf_2.estimators_ >>> clf.estimators_ += clf_3.estimators_ jeudi 7 mars 13
  35. Warning • Models trained on the partitioned dataset are not

    exactly equivalent of models trained on the unpartitioned dataset • If very much data: does not matter much in practice: Gilles Louppe & Pierre Geurts http://www.cs.bris.ac.uk/~flach/ jeudi 7 mars 13
  36. multiprocessing >>> from multiprocessing import Pool >>> p = Pool(4)

    >>> p.map(type, [1, 2., '3']) [int, float, str] >>> r = p.map_async(type, [1, 2., '3']) >>> r.get() [int, float, str] jeudi 7 mars 13
  37. multiprocessing • Part of the standard lib • Simple API

    • Cross-Platform support (even Windows!) • Some support for shared memory • Support for synchronization (Lock) jeudi 7 mars 13
  38. multiprocessing: limitations • No docstrings in the source code! •

    Very tricky to use the shared memory values with NumPy • Bad support for KeyboardInterrupt • fork without exec on POSIX jeudi 7 mars 13
  39. • transparent disk-caching of the output values and lazy re-evaluation

    (memoization) • easy simple parallel computing • logging and tracing of the execution jeudi 7 mars 13
  40. >>> from os.path.join >>> from joblib import Parallel, delayed >>>

    Parallel(2)(delayed(join)('/ect', s) ... for s in 'abc') ['/ect/a', '/ect/b', '/ect/c'] joblib.Parallel jeudi 7 mars 13
  41. Usage in scikit-learn • Cross Validation cross_val(model, X, y, n_jobs=4,

    cv=3) • Grid Search GridSearchCV(model, n_jobs=4, cv=3).fit(X, y) • Random Forests RandomForestClassifier(n_jobs=4).fit(X, y) jeudi 7 mars 13
  42. >>> from joblib import Parallel, delayed >>> import numpy as

    np >>> Parallel(2, max_nbytes=1e6)( ... delayed(type)(np.zeros(int(i))) ... for i in [1e4, 1e6]) [<type 'numpy.ndarray'>, <class 'numpy.core.memmap.memmap'>] joblib.Parallel: shared memory (dev) jeudi 7 mars 13
  43. (1, 1e3) (10, 1e3) (100, 1e3) (1, 1e4) (10, 1e4)

    (100, 1e4) (1, 1e5) (10, 1e5) (100, 1e5) Only 3 allocated datasets shared by all the concurrent workers performing the grid search. jeudi 7 mars 13
  44. Problems with multiprocessing & joblib • Current Implementation uses fork

    without exec under Unix • Break some optimized runtimes: • OpenBlas • Grand Central Dispatch under OSX • Will be fixed in Python 3 at some point... jeudi 7 mars 13
  45. Multiple Machines with Multiple Cores — — — — —

    — — — — — — — — — — — jeudi 7 mars 13
  46. Working in the Cloud • Launch a cluster of machines

    in one cmd: $ starcluster start mycluster -s 3 \ -b 0.07 --force-spot-master $ starcluster sshmaster mycluster • Supports Spot Instances provisioning • Ships blas, atlas, numpy, scipy • IPython plugin, Hadoop plugin and more jeudi 7 mars 13
  47. [global] DEFAULT_TEMPLATE=ip [key mykey] KEY_LOCATION=~/.ssh/mykey.rsa [plugin ipcluster] SETUP_CLASS = starcluster.plugins.ipcluster.IPCluster

    ENABLE_NOTEBOOK = True [plugin packages] setup_class = pypackage.PyPackageSetup packages = msgpack-python, scikit-learn [cluster ip] KEYNAME = mykey CLUSTER_USER = ipuser NODE_IMAGE_ID = ami-999d49f0 NODE_INSTANCE_TYPE = c1.xlarge DISABLE_QUEUE = True SPOT_BID = 0.10 PLUGINS = packages, ipcluster jeudi 7 mars 13
  48. $ starcluster start -s 3 --force-spot-master demo_cluster StarCluster - (http://star.mit.edu/cluster)

    (v. 0.9999) Software Tools for Academics and Researchers (STAR) Please submit bug reports to [email protected] >>> Using default cluster template: ip >>> Validating cluster template settings... >>> Cluster template settings are valid >>> Starting cluster... >>> Launching a 3-node cluster... >>> Launching master node (ami: ami-999d49f0, type: c1.xlarge)... >>> Creating security group @sc-demo_cluster... SpotInstanceRequest:sir-d10e3412 >>> Launching node001 (ami: ami-999d49f0, type: c1.xlarge) SpotInstanceRequest:sir-3cad4812 >>> Launching node002 (ami: ami-999d49f0, type: c1.xlarge) SpotInstanceRequest:sir-1a918014 >>> Waiting for cluster to come up... (updating every 5s) >>> Waiting for open spot requests to become active... 3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Waiting for all nodes to be in a 'running' state... 3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Waiting for SSH to come up on all nodes... 3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Waiting for cluster to come up took 5.087 mins >>> The master node is ec2-54-243-24-93.compute-1.amazonaws.com jeudi 7 mars 13
  49. >>> Configuring cluster... >>> Running plugin starcluster.clustersetup.DefaultClusterSetup >>> Configuring hostnames...

    3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Creating cluster user: ipuser (uid: 1001, gid: 1001) 3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Configuring scratch space for user(s): ipuser 3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Configuring /etc/hosts on each node 3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Starting NFS server on master >>> Configuring NFS exports path(s): /home >>> Mounting all NFS export path(s) on 2 worker node(s) 2/2 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Setting up NFS took 0.151 mins >>> Configuring passwordless ssh for root >>> Configuring passwordless ssh for ipuser >>> Running plugin ippackages >>> Installing Python packages on all nodes: >>> $ pip install -U msgpack-python >>> $ pip install -U scikit-learn >>> Installing 2 python packages took 1.12 mins jeudi 7 mars 13
  50. >>> Running plugin ipcluster >>> Writing IPython cluster config files

    >>> Starting the IPython controller and 7 engines on master >>> Waiting for JSON connector file... /Users/ogrisel/.starcluster/ipcluster/SecurityGroup:@sc-demo_cluster-us-east-1.json 100% || Time: 00:00:00 0.00 B/s >>> Authorizing tcp ports [1000-65535] on 0.0.0.0/0 for: IPython controller >>> Adding 16 engines on 2 nodes 2/2 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% >>> Setting up IPython web notebook for user: ipuser >>> Creating SSL certificate for user ipuser >>> Authorizing tcp ports [8888-8888] on 0.0.0.0/0 for: notebook >>> IPython notebook URL: https://ec2-54-243-24-93.compute-1.amazonaws.com:8888 >>> The notebook password is: zYHoMhEA8rTJSCXj *** WARNING - Please check your local firewall settings if you're having *** WARNING - issues connecting to the IPython notebook >>> IPCluster has been started on SecurityGroup:@sc-demo_cluster for user 'ipuser' with 23 engines on 3 nodes. To connect to cluster from your local machine use: from IPython.parallel import Client client = Client('/Users/ogrisel/.starcluster/ipcluster/SecurityGroup:@sc-demo_cluster-us- east-1.json', sshkey='/Users/ogrisel/.ssh/mykey.rsa') See the IPCluster plugin doc for usage details: http://star.mit.edu/cluster/docs/latest/plugins/ipython.html >>> IPCluster took 0.679 mins >>> Configuring cluster took 3.454 mins >>> Starting cluster took 8.596 mins jeudi 7 mars 13
  51. MapReduce? [ (k1, v1), (k2, v2), ... ] mapper mapper

    mapper [ (k3, v3), (k4, v4), ... ] reducer reducer [ (k5, v6), (k6, v6), ... ] jeudi 7 mars 13
  52. Why MapReduce does not always work Write a lot of

    stuff to disk for failover Inefficient for small to medium problems [(k, v)] mapper [(k, v)] reducer [(k, v)] Data and model params as (k, v) pairs? Complex to leverage for Iterative Algorithms jeudi 7 mars 13
  53. When MapReduce is useful for ML • Data Preprocessing &

    Feature Extraction • Parsing, Filtering, Cleaning • Computing big JOINs & Aggregates • Random Sampling • Computing ensembles on partitions jeudi 7 mars 13
  54. The AllReduce Pattern • Compute an aggregate (average) of active

    node data • Do not clog a single node with incoming data transfer • Traditionally implemented in MPI systems jeudi 7 mars 13
  55. AllReduce 0/3 Initial State Value: 2.0 Value: 0.5 Value: 1.1

    Value: 3.2 Value: 0.9 Value: 1.0 jeudi 7 mars 13
  56. AllReduce 1/3 Spanning Tree Value: 2.0 Value: 0.5 Value: 1.1

    Value: 3.2 Value: 0.9 Value: 1.0 jeudi 7 mars 13
  57. AllReduce 2/3 Upward Averages Value: 2.0 Value: 0.5 Value: 1.1

    (1.1, 1) Value: 3.2 (3.1, 1) Value: 0.9 (0.9, 1) Value: 1.0 jeudi 7 mars 13
  58. AllReduce 2/3 Upward Averages Value: 2.0 (2.1, 3) Value: 0.5

    (0.7, 2) Value: 1.1 (1.1, 1) Value: 3.2 (3.1, 1) Value: 0.9 (0.9, 1) Value: 1.0 jeudi 7 mars 13
  59. AllReduce 2/3 Upward Averages Value: 2.0 (2.1, 3) Value: 0.5

    (0.7, 2) Value: 1.1 (1.1, 1) Value: 3.2 (3.1, 1) Value: 0.9 (0.9, 1) Value: 1.0 (1.38, 6) jeudi 7 mars 13
  60. AllReduce 3/3 Downward Updates Value: 2.0 (2.1, 3) Value: 0.5

    (0.7, 2) Value: 1.1 (1.1, 1) Value: 3.2 (3.1, 1) Value: 0.9 (0.9, 1) Value: 1.38 jeudi 7 mars 13
  61. AllReduce 3/3 Downward Updates Value: 1.38 Value: 1.38 Value: 1.1

    (1.1, 1) Value: 3.2 (3.1, 1) Value: 0.9 (0.9, 1) Value: 1.38 jeudi 7 mars 13
  62. AllReduce 3/3 Downward Updates Value: 1.38 Value: 1.38 Value: 1.38

    Value: 1.38 Value: 1.38 Value: 1.38 jeudi 7 mars 13
  63. AllReduce Final State Value: 1.38 Value: 1.38 Value: 1.38 Value:

    1.38 Value: 1.38 Value: 1.38 jeudi 7 mars 13
  64. Killall IPython engines on StarCluster [plugin ipcluster] SETUP_CLASS = starcluster.plugins.ipcluster.IPCluster

    ENABLE_NOTEBOOK = True NOTEBOOK_DIRECTORY = notebooks [plugin ipclusterrestart] SETUP_CLASS = starcluster.plugins.ipcluster.IPClusterRestartEngines jeudi 7 mars 13
  65. $ starcluster runplugin ipclusterrestart demo_cluster StarCluster - (http://star.mit.edu/cluster) (v. 0.9999)

    Software Tools for Academics and Researchers (STAR) Please submit bug reports to [email protected] >>> Running plugin ipclusterrestart >>> Restarting 23 engines on 3 nodes 3/3 |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| 100% jeudi 7 mars 13