Random Notes
  • Introduction
  • Reading list
  • Theory
    • Index
      • Impossibility of Distributed Consensus with One Faulty Process
      • Time, Clocks, and the Ordering of Events in a Distributed System
      • Using Reasoning About Knowledge to analyze Distributed Systems
      • CAP Twelve Years Later: How the “Rules” Have Changed
      • A Note on Distributed Computing
  • Operating System
    • Index
  • Storage
    • Index
      • Tachyon: Reliable, Memory Speed Storage for Cluster Computing Frameworks
      • Exploiting Commutativity For Practical Fast Replication
      • Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
      • Building Consistent Transactions with Inconsistent Replication
      • Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System
      • Spanner: Google's Globally-Distributed Database
      • Bigtable: A Distributed Storage System for Structured Data
      • The Google File System
      • Dynamo: Amazon’s Highly Available Key-value Store
      • Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
      • Replicated Data Consistency Explained Through Baseball
      • Session Guarantees for Weakly Consistent Replicated Data
      • Flat Datacenter Storage
      • Small Cache, Big Effect: Provable Load Balancing forRandomly Partitioned Cluster Services
      • DistCache: provable load balancing for large-scale storage systems with distributed caching
      • Short Summaries
  • Coordination
    • Index
      • Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
      • Paxos made simple
      • ZooKeeper: Wait-free coordination for Internet-scale systems
      • Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering
      • Keeping CALM: When Distributed Consistency is Easy
      • In Search of an Understandable Consensus Algorithm
      • A comprehensive study of Convergent and Commutative Replicated Data Types
  • Fault Tolerance
    • Index
      • The Mystery Machine: End-to-end Performance Analysis of Large-scale Internet Services
      • Gray Failure: The Achilles’ Heel of Cloud-Scale Systems
      • Capturing and Enhancing In Situ System Observability for Failure Detection
      • Check before You Change: Preventing Correlated Failures in Service Updates
      • Efficient Scalable Thread-Safety-Violation Detection
      • REPT: Reverse Debugging of Failures in Deployed Software
      • Redundancy Does Not Imply Fault Tolerance
      • Fixed It For You:Protocol Repair Using Lineage Graphs
      • The Good, the Bad, and the Differences: Better Network Diagnostics with Differential Provenance
      • Lineage-driven Fault Injection
      • Short Summaries
  • Cloud Computing
    • Index
      • Improving MapReduce Performance in Heterogeneous Environments
      • CLARINET: WAN-Aware Optimization for Analytics Queries
      • MapReduce: Simplified Data Processing on Large Clusters
      • Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks
      • Resource Management
      • Apache Hadoop YARN: Yet Another Resource Negotiator
      • Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center
      • Dominant Resource Fairness: Fair Allocation of Multiple Resource Types
      • Large-scale cluster management at Google with Borg
      • MapReduce Online
      • Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling
      • Reining in the Outliers in Map-Reduce Clusters using Mantri
      • Effective Straggler Mitigation: Attack of the Clones
      • Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
      • Discretized Streams: Fault-Tolerant Streaming Computation at Scale
      • Sparrow: Distributed, Low Latency Scheduling
      • Making Sense of Performance in Data Analytics Framework
      • Monotasks: Architecting for Performance Clarity in Data Analytics Frameworks
      • Drizzle: Fast and Adaptable Stream Processing at Scale
      • Naiad: A Timely Dataflow System
      • The Dataflow Model:A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale
      • Interruptible Tasks:Treating Memory Pressure AsInterrupts for Highly Scalable Data-Parallel Program
      • PACMan: Coordinated Memory Caching for Parallel Jobs
      • Multi-Resource Packing for Cluster Schedulers
      • Other interesting papers
  • Systems for ML
    • Index
      • A Berkeley View of Systems Challenges for AI
      • Tiresias: A GPU Cluster Managerfor Distributed Deep Learning
      • Gandiva: Introspective Cluster Scheduling for Deep Learning
      • Workshop papers
      • Hidden Technical Debt in Machine Learning Systems
      • Inference Systems
      • Parameter Servers and AllReduce
      • Federated Learning at Scale - Part I
      • Federated Learning at Scale - Part II
      • Learning From Non-IID data
      • Ray: A Distributed Framework for Emerging AI Applications
      • PipeDream: Generalized Pipeline Parallelism for DNN Training
      • DeepXplore: Automated Whitebox Testingof Deep Learning Systems
      • Distributed Machine Learning Misc.
  • ML for Systems
    • Index
      • Short Summaries
  • Machine Learning
    • Index
      • Deep Learning with Differential Privacy
      • Accelerating Deep Learning via Importance Sampling
      • A Few Useful Things to Know About Machine Learning
  • Video Analytics
    • Index
      • Scaling Video Analytics on Constrained Edge Nodes
      • Focus: Querying Large Video Datasets with Low Latency and Low Cost
      • NoScope: Optimizing Neural Network Queriesover Video at Scale
      • Live Video Analytics at Scale with Approximation and Delay-Tolerance
      • Chameleon: Scalable Adaptation of Video Analytics
      • End-to-end Learning of Action Detection from Frame Glimpses in Videos
      • Short Summaries
  • Networking
    • Index
      • Salsify: Low-Latency Network Video through Tighter Integration between a Video Codec and a Transport
      • Learning in situ: a randomized experiment in video streaming
      • Short Summaries
  • Serverless
    • Index
      • Serverless Computing: One Step Forward, Two Steps Back
      • Encoding, Fast and Slow: Low-Latency Video Processing Using Thousands of Tiny Threads
      • SAND: Towards High-Performance Serverless Computing
      • Pocket: Elastic Ephemeral Storage for Serverless Analytics
      • Fault-tolerant and Transactional Stateful Serverless Workflows
  • Resource Disaggregation
    • Index
  • Edge Computing
    • Index
  • Security/Privacy
    • Index
      • Differential Privacy
      • Honeycrisp: Large-Scale Differentially Private Aggregation Without a Trusted Core
      • Short Summaries
  • Misc.
    • Index
      • Rate Limiting
      • Load Balancing
      • Consistency Models in Distributed System
      • Managing Complexity
      • System Design
      • Deep Dive into the Spark Scheduler
      • The Actor Model
      • Python Global Interpreter Lock
      • About Research and PhD
Powered by GitBook
On this page
  • Learning = Representation + Evaluation + Optimization
  • Generalization
  • Overfitting
  • Dimensions
  • Feature Engineering
  • Data
  • Learn multiple models

Was this helpful?

  1. Machine Learning
  2. Index

A Few Useful Things to Know About Machine Learning

https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf

PreviousAccelerating Deep Learning via Importance SamplingNextIndex

Last updated 5 years ago

Was this helpful?

Learning = Representation + Evaluation + Optimization

To choose from thousands of learning algorithm, we need to realize that they consist of three components:

  • Representation: It is basically the space of allowed models (the hypothesis space).

  • Evaluation: (A.k.a Objective function or scoring function) It is used to distinguish good classifier from bad ones.

  • Optimization: It is a method to search among the classifiers in the language for the highest-scoring one. Worded differently, optimization is how you search the space of represented models to obtain better evaluations.

Generalization

The fundamental goal of machine learning is to generalize beyond the examples in the training set. The most common mistake among machine learning is to test the training data and have the illusion of success. Even if you keep some of the data to yourself as test data, contamination of your classifier by test data can occur in insidious ways, for example, if you use test data to tune parameters and do a lot of tuning. Finally, To cope with the reduction in training data, we can use cross validation.

Overfitting

Overfitting refers to a model that models the training data too well. For example, when your learner outputs a classifier that is 100% accurate on the training data but only 50% accurate on the test data, it clearly has overfit. To better understand overfitting, we can decompose generalization error into bias and variance.

  • Bias: The simplifying assumptions made by a model to make the target function easier to learn.

    • Low Bias: Suggests less assumptions about the form of the target function.

    • High-Bias: Suggests more assumptions about the form of the target function

    For example, a linear learner has high bias, whereas decision trees is an example of low-bias machine learning algorithm.

  • Variance: The amount that the estimate of the target function will change if different training data was used. Machine learning algorithms that have a high variance are strongly influenced by the specifics of the training data.

    • Low Variance: Suggests small changes to the estimate of the target function with changes to the training dataset.

    • High Variance: Suggests large changes to the estimate of the target function with changes to the training dataset.

    For example, decision trees suffer from high variance: decision trees learned on different training sets generated by the same phenomenon are often very different, which in fact should be very similar.

The goal of any supervised machine learning algorithm is to achieve low bias and low variance. However, we need to keep in mind that increasing the bias will always decrease the variance. and increasing the variance will decrease the bias. For example, SVMs has low bias and high variance, but the trade-off can be changed by increasing the C parameter in front of the slack variable term that influences the number of violations of the margin allowed in the training data which increases the bias but decreases the variance.

The lesson here is that, contrary to intuition, a more powerful learner is not necessarily better than a less powerful one. In other words, strong false assumption(e.g. the frontier is linear) can be better than weak true ones, because a learner with the latter needs more data to avoid overfitting.

Note: Contrary to intuition, there is no necessary connection between the number of parameters of a model and its tendency to overfit.

How to cope with overfitting?

Besides the well-known cross validation approach, adding a regularization term to the evaluation function can also help. It can, for example, penalize classifiers with more structure. thereby favoring smaller ones with less room to overfit. Another option is to perform a statistical significance test like chi-square before adding new structure, to decide whether the distribution of the class really is different with and without this structure.

However, we should be cautious about a particular technique that "solve" the overfitting problem. It is easy to avoid overfitting (variance) by falling into the opposite error of underfitting (bias). Simultaneously avoiding both requires learning a perfect classifier, and short of knowing it in advance there is no single technique that will always do best (no free lunch).

Dimensions

Another big problem in machine learning is the "the curse of dimensionality". Many Ml algorithms work fin in low dimensions become intractable when the input is high-dimensional. Moreover, generalizing correctly becomes exponentially harder as the dimensionality (number of features) of the examples grows, because a fixed-size training set covers a dwindling fraction of the input space.

The key takeaway is that: although we might think that gathering more features never hurts, since at worst they provide no new information about the class, but in fact their benefits may be outweighed by the curse of dimensionality.

Feature Engineering

One of the most important factor in ML is the feature used. Often the raw data is not in a form that is amenable to learning, but you can construct features from it that are. It is surprisingly time-consuming to gather data, integrate it. clean it and preprocess it.

Feature engineering is difficult because it is domain-specific, while learners can be largely general purpose. Although it is possible to automate the feature engineering process, features that look irrelevant in isolation may be relevant in combination.

Data

It’s not who has the best algorithm that wins. It’s who has the most data. - Andrew Ng

As a rule As a rule of thumb, a dumb algorithm with lots and lots of data beats a clever one with modest amounts of it.[1] However, it brings the problem of scalability. Even though in principle, more data means that more complex classifiers can be learned, in practice simpler classifiers wind up being used, because complex ones takes too long to learn.

The takeaway is that it pays to try the simplest learner first(e.g. naive Bayes). Besides, learners can be divided into two major types: those whose representation has a fixed size, like linear classifiers, and those whose representation can grow with the data, like decision trees. Fixed-size learners can only take advantage of so much data. Variable size learners can in principle learn any function given sufficient data, but in practice they may not, because of limitations of the algorithm or computational cost.

Learn multiple models

If instead of selecting the best variation found, we combine many variations, the result are better and at little extra effort for the user. Such method is often called model ensembles.(e.g. bagging)

[1] However, this also brings up an interesting research direction(e.g. parameter servers). Since we can improve accuracy by using more data and larger model, we don't need to come up with new machine learning algorithm but, instead, we can try to build systems that can are capable of handling huge data and model size.

From Google's paper