Machine Learning

Question 1

Association Rules

Answer 1

Detect relationships or associations between specific values of categorical variables in large data sets.

Market basket analysis: uncover hidden patterns in large data sets, such as “customers who order product A often also order product B or C” or “employees who said positive things about initiative X also frequently complain about issue Y but are happy with issue Z.”

Question 2

Bayes Theorem

Answer 2

P(A | B) = P(B | A) * P(A) / P(B); P(A) being the number of instances of a given value divided by the total number of instances; P(B) is often ignored since this equation is typically used in a probability ratio that compares two different values for A, with P(B) being the same for both

Question 3

Bayesian Networks

Answer 3

A graphical formalism for representing the structure of a probabilistic model:

• Show the ways in which the random variables may depend on each other
• Good at representing domains with a causal structure
• Edges in the graph determine which variables directly influence which other variables
• Factorization structure of the joint probability distribution
• Encoding a set of conditional independence assumptions

Question 4

Boosting

Answer 4

AdaBoost can be interpreted as a sequential procedure for minimizing the exponential loss on the training set with respect to the coefficients of a particular basis function expansion. This leads to generalizations of the algorithm to different loss functions.

Question 5

Clustering: Canopy

Answer 5

…

Question 6

Classification

Answer 6

We are trying to predict results in a discrete output. In other words, we are trying to map input variables into discrete categories.

Question 7

Cluster Analysis

Answer 7

Methods to assign a set of objects into groups. These groups are called clusters and objects in a cluster are more similar to each other than to those in other clusters. Well known algorithms are hierarchical clustering, k-means, fuzzy clustering, supervised clustering.

Question 8

Cluster Analysis: Distance Metrics Between Items

Answer 8

1. Euclidean distance: The geometric distance between objects in the multidimensional space. The shortest path between two objects. It is used to obtain sphere-shaped clusters. 2. City block (Manhattan) distance. It corresponds to the sum of distances along each dimension and is less sensitive to outliers. It is used to obtain diamond-shaped clusters. 3. Cosine similarity measure. It is calculated by measuring the cosine of angle between two objects. It is used mostly to compute the similarity between two sets of transaction data.

Question 9

Cluster Analysis: Distance Measures Between Clusters

Answer 9

In hierarchical clustering: 1. Average linkage: It is the average distance between all the points in two clusters. 2. Single linkage: It is the distance between nearest points in two clusters 3. Complete linkage: It is the distance between farthest points in two clusters.

Question 10

Cluster Analysis: Hierarchical Clustering

Answer 10

…

Question 11

Cluster Analysis: Gaussian Mixture Models (GMM)

Answer 11

An unsupervised learning technique for clustering that generates a mixture of clusters from the full data set using a Gaussian (normal) data distribution model for each cluster. The GMM’s output is a set of cluster attributes (mean, variance, and centroid) for each cluster, thereby producing a set of characterization metadata that serves as a compact descriptive model of the full data collection.

Question 12

Cluster Analysis: K-Means Overview

Answer 12

What: K-means is one of the most widely used clustering techniques because of its simplicity and speed. It partitions the data into a user specified number of clusters, k. Why: Simplicity, speed. It is fast for large data sets, which are common in segmentation.

Question 13

Cluster Analysis: K-Means: Cautions

Answer 13

Clusters may converge to a local minimum. Due to this issue, the clusters that are obtained might not be the right ones. To avoid this, it might be helpful to run the algorithm with different initial cluster centroids and compare the results.

Question 14

Cluster Analysis: K-Means: Scaling Options

Answer 14

Note that each iteration needs N × k comparisons, which determines the time complexity of one iteration. The number of iterations required for convergence varies and may depend on N, but as a first cut, this algorithm can be considered linear in the dataset size. The k-means algorithm can take advantage of data parallelism. When the data objects are distributed to each processor, step 3 can be parallelized easily by doing the assignment of each object into the nearest cluster in parallel.

Question 15

Cluster Analysis: K-Means: How

Answer 15

1. Initialization: The algorithm is initialized by picking the initial k cluster representatives or “centroids”. These initial seeds can be sampled at random from the dataset, or by taking the results of clustering a small subset of the data;
2. Data Assignment. Each data point is assigned to its closest centroid, with ties broken arbitrarily. This results in a partitioning of the data.;
3. Recompute and reset the location of the “means”. Each cluster representative is relocated to the center (mean) of all data points assigned to it.;

Now repeat step 3 and 4 until the convergence criterion is met (e.g., the assignment of objects to clusters no longer changes over multiple iterations) or maximum iteration is reached.

Question 16

Cluster Analysis: K-Means: 4 Key Steps

Answer 16

1: Initialization of k centroids; 2: Data points assigned to nearest centroid; 3: Relocation of each mean to the center of it’s points; 4: Repeat step 2 and 3 until assignments no longer change

Question 17

KNN

Answer 17

K-Nearest Neighbors algorithm (for classification), K-Means (for clustering), K-itemsets (for association rule mining - see A, above), K-Nearest Neighbors Data Distributions (for outlier detection), KD-trees (for indexing and rapid search of high-dimensional data), and more KDD (Knowledge Discovery from Data) things.

Question 18

KNN

Answer 18

K-NN is an algorithm that can be used when you have a bunch of objects that have been classified or labeled in some way, and other similar objects that haven’t gotten classified or labeled yet, and you want a way to automatically label them.

Question 19

Conditional Random Fields

Answer 19

…

Question 20

Confusion Matrix

Answer 20

A matrix showing the predicted and actual classifications. A confusion matrix is of size LxL, where L is the number of different label values. Rows for each of the actual values cross-tabbed against columns of the predicted values.

Question 21

Optimization: Convex optimization

Answer 21

…

Question 22

Correlation

Answer 22

the analysis of data to determine a relationship between variables and whether that relationship is negative (- 1.00) or positive (+1.00).

Question 23

Correlation: Pearson

Answer 23

1) Find items which can be compared; 2) Calculate the sum for each set of those items; 3) Calculate the sum of squares for each set of those items; 4) Calculate the sum of the products for each set of those items; 5) Use the values from 2-4 to calculate the coefficient

Question 24

Correlation: Pearson

Answer 24

a measure of how well two sets of data fit on a straight line; Gives a value between -1 and 1 with 1 meaning the sets vary in an identical way; Tends to give better results than Euclidean distance scores when data isn’t well normalized, i.e. it corrects for grade inflation

Question 25

Cost Function

Answer 25

A measurement of the cost to the performance task of making a prediction Y’ when the actual label is y. The use of accuracy to evaluate a model assumes uniform costs of errors and uniform benefits of correct classifications. Example: “Squared error function”.

Question 26

Cross-validation

Answer 26

A method for estimating the accuracy of an inducer by dividing the data into k mutually exclusive subsets, or folds, of approximately equal size. The inducer is trained and tested k times. Each time it is trained on the data set minus a fold and tested on that fold. The accuracy estimate is the average accuracy for the k folds.

Question 27

Decision Trees

Answer 27

A tree of questions to guide an end user to a conclusion based on values from a single vector of data. The classic example is a medical diagnosis based on a set of symptoms for a particular patient. A common problem in data science is to automatically or semi-automatically generate decision trees based on large sets of data coupled to known conclusions. Example algorithms are CART and ID3. (Submitted by Michael Malak)

Question 28

Decision Trees

Answer 28

each node in the tree tests an attribute, decisions are represented by the edges leading away from that node with leaf nodes representing the final decision for all instances that reach that leaf node

Question 29

Decision Trees: Dealing with missing values

Answer 29

1) have a specific edge for no value; 2) track the number of instances that follow each path and assign that instance to the most popular edge; 3) give instances weights and split the instance evenly down each possible edge. Once the value has reached the leaf nodes, recombine it using the weights

Question 30

Decision Trees: Pruining

Answer 30

since decision trees are often created by continuously splitting the instances until there is no more information gain, it is possible that some splits were done with too little information gain and result in overfitting of the model to the training data. Basic idea is to check child nodes to see if combining them with their parent would result in an increase in entropy below some threshold

Question 31

Decision Trees: Replicated subtree problem

Answer 31

because only a single attribute is tested at a node, it is possible that two copies of the same subtree will need to be placed in a tree if the attributes from that subtree were not tested in the root node

Question 32

Decision Trees: Testing nominal values

Answer 32

if a node has edges for each possible value of that nominal value, then that value will not be tested again further down the tree. If a node groups the values into subsets with an edge per subset, then that attribute may be tested again

Question 33

Decision Trees: Testing numeric values

Answer 33

can be tested for less than, greater than, equal to, within some range. Can result in just two edges or multiple edges. Can also have an edge that represents no value. May be tested multiple times in a single path

Question 34

Deep Learning

Answer 34

Refers to a class of methods that includes neural networks and deep belief nets. Useful for finding a hierarchy of the most significant features, characteristics, and explanatory variables in complex data sets. Particularly useful in unsupervised machine learning of large unlabeled datasets. The goal is to learn multiple layers of abstraction for some data. For example, to recognize images, we might want to first examine the pixels and recognize edges; then examine the edges and recognize contours; examine the contours to find shapes; the shapes to find objects; and so on.

Question 35

Elastic Nets

Answer 35

…

Question 36

Ensemble Learning

Answer 36

Machine learning approach that combines the results from many different algorithms, whose combined vote (from the ensemble) provides a more robust and accurate predictive output than any single algorithm can muster.

Question 37

Factor Analysis

Answer 37

used as a variable reduction technique to identify groups of clustered variables. (submitted by Vincent Granville)

Question 38

Feature Scaling

Answer 38

different features will have different effects on the accuracy of classifications. A scaling factor can be used for each feature to reduce its effect on the classification, possibly to 0. These scales can be optimized to not only improve classifications, but to also show the relative importance of the features.

Question 39

Feature Scaling

Answer 39

Mean normalization of data to speed up gradient descend

Question 40

Feature Selection

Answer 40

…

Question 41

Gaussian Mixture Models

Answer 41

…

Question 42

Gini Impurity

Answer 42

1: measures the expected error rate if one of the results from a set is randomly applied to one of the items in the set.

Question 43

Boosting: Gradient Boosted Decision Trees

Answer 43

…

Question 44

Gradient Descent

Answer 44

An iterative optimization algorithm for finding a local minimum. At each iteration, gradient descent operates by moving the current solution in the direction of the negative gradient of the function (the direction of “steepest descent”). Also known as steepest descent.

Question 45

Graph Databases

Answer 45

they use graph structures (a finite set of ordered pairs or certain entities), with edges, properties and nodes for data storage. It provides index-free adjacency, meaning that every element is directly linked to its neighbour element.

Question 46

HDPs or other Bayesian non-parametric model

Answer 46

…

Question 47

Hidden Layer

Answer 47

The second layer of a three-layer network where the input layer sends its signals, performs intermediary processing

Question 48

Hidden Markov Models

Answer 48

…

Question 49

Hyperplane

Answer 49

A hyperplane in an n-dimensional Euclidean space is a flat, n-1 dimensional subset of that space that divides the space into two disconnected parts. First think of a line line. Now pick a point. That point divides the real line into two parts (the part above that point, and the part below that point). The real line has 1 dimension, while the point has 0 dimensions. So a point is a hyperplane of the real line. Now think of the two-dimensional plane. Now pick any line. That line divides the plane into two parts (“left” and “right” or maybe “above” and “below”). The plane has 2 dimensions, but the line has only one. So a line is a hyperplane of the 2d plane. Notice that if you pick a point, it doesn’t divide the 2d plane into two parts. So one point is not enough. Now think of a 3d space. Now to divide the space into two parts, you need a plane. Your plane has two dimensions, your space has three. So a plane is the hyperplane for a 3d space.

Question 50

Kernel

Answer 50

replacing the dot-product function with a new function that returns what the dot product would have been if the data had first been transformed to a higher dimensional space. Usually done using the radial-basis function

Question 51

Lagrange

Answer 51

…

Question 52

LDA

Answer 52

…

Question 53

Linear Algebra

Answer 53

gives a single number from two vectors by multiplying each value in the first vector by the corresponding value in the second vector and adding them all together

Question 54

Classification: Linear Binary

Answer 54

Binary classification problems arise when we seek to separate two sets of data points in R^n, each corresponding to a given class. We seek to separate the two data sets using simple ‘‘boundaries’’, typically hyperplanes. Once the boundary is found, we can use it to predict the class a new point belongs to, by simply checking on which side of the boundary it falls.

Question 55

Linear Regression

Answer 55

Trying to fit a linear continuous function to the data. Univariate or Multivariate.

Question 56

Logistic Regression

Answer 56

A kind of regression analysis often used when the dependent variable is dichotomous and scored 0 or 1. It is usually used for predicting whether something will happen or not, such as graduation, business failure, or heart attack-anything that can be expressed as event/non-event. Independent variables may be categorical or continuous in logistic regression analysis.

Question 57

Machine Learning

Answer 57

Analytics in which computers “learn” from data to produce models or rules that apply to those data and to other similar data. Predictive modeling techniques such as neural nets, classification and regression trees (decision trees), naive Bayes, k-nearest neighbor, and support vector machines are generally included. One characteristic of these techniques is that the form of the resulting model is flexible, and adapts to the data. Statistical modeling methods that have highly structured model forms, such as linear regression, logistic regression and discriminant analysis are generally not considered part of machine learning. Unsupervised learning methods such as association rules and clustering are also considered part of machine learning.

Question 58

Machine Learning

Answer 58

A computer program is said to learn from from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

Question 59

Matrix Factorization/SVD

Answer 59

…

Question 60

Measure Theory

Answer 60

…

Question 61

Model Evaluation: Adjusted R^2 (R-Square)

Answer 61

The method preferred by statisticians for determining which variables to include in a model. It is a modified version of R^2 which penalizes each new variable on the basis of how many have already been admitted. Due to its construct, R^2 will always increase as you add new variables, which result in models that over-fit the data and have poor predictive ability. Adjusted R^2 results in more parsimonious models that admit new variables only if the improvement in fit is larger than the penalty, which improves the ultimate goal of out-of-sample prediction. (Submitted by Santiago Perez)

Question 62

Model Evaluation: Decision tables

Answer 62

simplest way of expressing output from machine learning, cells in table represent the resulting decision based on the row and column which represent the conditions

Question 63

Model Evaluation: Mis-classification error

Answer 63

Define Test error as summed error for classification (false prediction)

Question 64

Model Evaluation: Negative class

Answer 64

Negative means not having the symptoms

Question 65

Model Evaluation: Positive class

Answer 65

presence of something we are looking for - 1

Question 66

Model Evaluation: Precision

Answer 66

Of all predicted positives, how many are positive?

Question 67

Model Evaluation: Recall

Answer 67

Of all positives how many were predicted as positive?

Question 68

Model Evaluation: True negative

Answer 68

Hypotheses correctly predicts negative output.

Question 69

Model Evaluation: True positive

Answer 69

Hypotheses correctly predicts positive output.

Question 70

Model Selection Algorithm

Answer 70

algorithm that automatically selects a good model function for a dataset.

Question 71

Monte-Carlo Simulation

Answer 71

Computing expectations and probabilities in models of random phenomena using many randomly sampled values. Akin to compute probability of winning a given roulette bet (say black) by repeatedly placing it and counting success ratio. Useful in complex models characterized by uncertainty. (submitted by Renato Vitolo)

Question 72

Multiclass-Classification: One-vs-all

Answer 72

Multiclass classification. Reducing a classification problem with multiple features that have to be predicted to a simple classification problem by looking at one feature at a time. Then to determin the final prediction we take the max of all the predicted values.

Question 73

Naïve Bayes

Answer 73

…

Question 74

Natural Language Processing

Answer 74

a field of computer science involved with interactions between computers and human languages

Question 75

Network Analytics

Answer 75

viewing relationships among the nodes in terms of the network or graph theory, meaning analysing connections between nodes in a network and the strength of the ties.

Question 76

Network Analytics

Answer 76

The science of describing and, especially, visualizing the connections among objects. The objects might be human, biological or physical. Graphical representation is a crucial part of the process; Wayne Zachary’s classic 1977 network diagram of a karate club reveals the centrality of two individuals, and presages the club’s subsequent split into two clubs. The key elements are the nodes (circles, representing individuals) and edges or links (lines representing connections).

Question 77

Neural Networks

Answer 77

Interconnected neural cells. With experience, networks can learn, as feedback strengthens or inhibits connections that produce certain results. Computer simulations of neural networks show analogous learning.

Question 78

Neural Networks

Answer 78

In neuronal networks the process of calculating the subsequent layers of the network. Each layer depends on the calculations done on the layer before it.

Question 79

Neural Networks: Random Initialization

Answer 79

Symmetry breaking for neural networks is achieved by:

Question 80

Optimization: genetic algorithms

Answer 80

starts with a set of random solutions called the “population”. Costs are calculated for all these solutions and the best solutions are saved (called “elitism”). The other solutions are discarded and are replaced using two methods. The first is “mutation” where simple random changes are made to the elite solutions. The second is “crossover” or “breeding” where two elite solutions are combined, such as by replacing random values in one with values in the other. This is repeated either for a set number of iterations or until several iterations have passed with no improvement.

Question 81

Optimization: hill climbing

Answer 81

starts with a random solution and looks at the set of neighboring solutions for those that are better, this is repeated continuously until no neighboring solution has a lower cost. Major drawback is that it will get stuck in a local minimum

Question 82

Optimization: Information gain

Answer 82

difference between the current entropy and the weighted-average entropy of the two new groups. Used when deciding which attribute to use when splitting instances in a decision tree

Question 83

Optimization: random-restart hill climbing

Answer 83

running a hill climbing algorithm several times using new random initial input to attempt to reach the global minimum

Question 84

Optimization: simulated annealing

Answer 84

similar to hill climbing, but adds a new variable “temperature” which starts high and gradually cools. With each iteration one variable is randomly changed in a certain direction. The new cost is compared to the old cost and is accepted if the new cost is lower. If the new cost is higher, it may be accepted based on a probability that is computed from the current “temperature”. As the temperature cools, it gets less and less likely that the worse solution would be accepted.

Question 85

Optimization: when do optimization algorithms fail?

Answer 85

when there is no clear slope in the change in cost function as the values are varied. This is because these algorithms all attempt to follow that slope toward a global minimum.

Question 86

Overfitting

Answer 86

When the model describes an error or noise instead of the actual model. A problem that occurs when data-mining is used to create overly complex models that are not suited to making accurate predictions. “High variance”. If we have too many features the learned hypothesis may fit the training set very well, but fails to generalzie to new examples.

Question 87

Partial differential equations

Answer 87

…

Question 88

P-values

Answer 88

…

Question 89

Quadratic programming

Answer 89

…

Question 90

Random Forests

Answer 90

A decision tree classifier that produces a “forest of trees”, yielding highly accurate models, essentially by iteratively randomizing one input variable at a time in order to learn if this randomization process actually produces a less accurate classifier. If it doesn’t, then that variable is ousted from the model.

Question 91

Receiver-Operator Curves

Answer 91

…

Question 92

Recommendation Systems: Content-based filtering

Answer 92

Gathers information (e.g., demographics, genre, keywords, preferences, survey responses) to generate a profile for each user or item. Users are matched to items based on their profiles. Example: Pandora’s Music Genome Project.

Question 93

Recommendation Systems: Collaborative filtering

Answer 93

Based on past user behavior. Each user’s history of behaviors (ratings, purchases, or viewing history) is used to make associations between users with similar behavior and between items of interest to the same users. Example: Netflix. Methods: 1. Neighborhood-based methods, based on user-user or item-item distances; 2. Latent factor or reduced- dimension models, which automatically discover a small number of descriptive factors for users and items; 3. Low-rank matrix factorization is the best-known example of reduced-dimension models and is among the most flexible and successful methods underlying recommendation systems. There are many variants of matrix factorization, including probabilistic and Bayesian versions. Restricted Boltzmann machines, a type of deep learning neural network, are another state-of-the-art approach.

Question 94

Recommendation Systems: Companies using them

Answer 94

Retailers: Amazon, Target; Movies + Music Sites: Netflix, last.fm, Pandora; Social networks: Facebook, Twitter; Grocery stores: Tesco; Content publishers: Ad networks: Yahoo!, Google; CRM: Next-best offer in marketing decision making

Question 95

Recommendation Systems: Collaborative filtering: Matrix Factorization

Answer 95

….Probabilistic and Bayesian versions, Restricted Boltzmann machines, a type of deep learning neural network, are another state-of-the-art approach.

Question 96

Regression Analysis

Answer 96

We are trying to predict results within a continuous output, meaning that we are trying to map input variables to some continuous function.

Question 97

Regression Analysis

Answer 97

to define the dependency between variables. It assumes a one-way causal effect from one variable to the response of another variable.

Question 98

Regression Trees

Answer 98

a single regression equation is much smaller and less complex than a regression tree, but tends to also be much less accurate.

Question 99

Regression Trees

Answer 99

decision trees which predict numeric quantities. The leaf nodes of these trees have a numeric quantity instead of a class. This numeric quantity is often decided by taking the average of all training set values to which the leaf node applies

Question 100

Regularization

Answer 100

A way of applying Occam’s Razor to real problems. Penalizing the higher-order parameters to avoid overfitting and getting a simpler hypothesis.

Question 101

Regularization: Parameter

Answer 101

lambda - controlls the trade-off between fitting the data well & keeping the parameters small.

Question 102

Sigmoid Function

Answer 102

an S-shaped mathamatical curve is often used to describe the activation function of a neuron over time

Question 103

Stepwise Regression

Answer 103

Variable selection process for multivariate regression. In forward stepwise selection, a seed variable is selected and each additional variable is inputed into the model, but only kept if it significantly improves goodness of fit (as measured by increases in R^2). Backwards selection starts with all variables, and removes them one by one until removing an additional one decreases R^2 by a non-trivial amount. Two deficiencies of this method are that the seed chosen disproportionately impacts which variables are kept, and that the decision is made using R^2, not Adjusted R^2. (submitted by Santiago Perez)

Question 104

Supervised Learning

Answer 104

We are given a data set and already know what our correct output should look like, having the idea that there is a relationship between the input and the output. Categorized into “regression” and “classification” problems.

Question 105

Supervised Learning

Answer 105

use training data to first build a model which is later used to classify instances

Question 106

Support Vector Machine

Answer 106

can extrapolate information from one dimensional data (input space) and some information about weights & correlative relationships to another dimension (feature space)

Question 107

Support Vector Machine

Answer 107

divide an instance space by finding the line that is as far as possible from both classes. This line is called the “maximum-margin hyperplane”

Question 108

Support Vector Machine

Answer 108

when determining the maximum-margin hyperplane for a support vector machine, only the points near the hyperplane are important. These points near the boundary are called the support vectors

Question 109

Support Vector Machine

Answer 109

Powerful Jedi machine learning classifier. Among classification algorithms used in supervised machine learning, SVM usually produces the most accurate classifications. Read more about SVM in this article “The Importance of Location in Real Estate, Weather, and Machine Learning.”

Question 110

Support Vector Machine: Kernels

Answer 110

since support vector machines use dot-products (just like linear classifiers) when determining the hyperplane, they can be turned into a non-linear classifier by replacing the dot-product with a kernel such as the radial-basis function

Question 111

Support Vector Machine: libsvm

Answer 111

open source library for SVMs written in C++ (w/a Java version as well). Trains an SVM model, makes predictions, and tests predictions w/in a dataset with support for kernel methods such as the radial-basis function

Question 112

Text analytics

Answer 112

A broader term that includes the preparation of text for mining, the mining itself, and specialized applications such as sentiment analysis. Preparing text for analysis involves automated parsing and interpretation (natural language processing), then quantification (e.g. identifying the presence or absence of key terms). Wikipedia

Question 113

Time Series Analysis

Answer 113

A set of (t, x) values where x is usually a scalar (though could be a vector) and the t values are usually sampled at regular intervals (though some time series are irregularly sampled). In the case of regularly sampled time series, the t is usually dropped from the actual data, replaced with just a t0 (start time) and delta-t that apply to the whole series. (Submitted by Michael Malak)

Question 114

Underfitting

Answer 114

Coefficients are generally biased (as well as inconsistent) “high bias” fitting a line to a curve

Question 115

Unsupervised Learning

Answer 115

Allows us to approach problems with little or no idea what our results should look like. We can derive structure from data where we don’t necessarily know the effect of the variables.

Question 116

Unsupervised Learning

Answer 116

don’t use training data and only find structure within the data, such as in clustering where the instances are placed into groups. Other examples include non-negative matrix factorization and self-organizing maps

Question 117

WEKA

Answer 117

Free data mining package, for data exploration, profiling, mining, and visual analytics, containing hundreds of machine learning algorithms, techniques, and methods.

Question 118

Stochastic Process

Answer 118

A collection of random variables, representing the evolution of some system of random values over time. This is the probabilistic counterpart to a deterministic process (or deterministic system). Instead of describing a process which can only evolve in one way (as in the case, for example, of solutions of an ordinary differential equation), in a stochastic or random process there is some indeterminacy: even if the initial condition (or starting point) is known, there are several (often infinitely many) directions in which the process may evolve. Examples: Markov chains, stock market fluctuations, EKG, brownian motion, random walks

Question 119

Random Walks

Answer 119

A mathematical formalization of a path that consists of a succession of random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the financial status of a gambler can all be modeled as random walks, although they may not be truly random in reality. The term random walk was first introduced by Karl Pearson in 1905.

Question 120

Markov Models

Answer 120

Markov models are a kind of probabilistic model often used in language modeling. The observations are assumed to follow a Markov chain, where each observation is independent of all past observations given the previous one. In a Markov chain, a system transitions stochastically from one state to another. It is a memoryless process, in the sense that the distribution over the next state depends only on the current state, and not on the state at any past time. Markov chains are useful models of many natural processes and the basis of powerful techniques in probabilistic inference and randomized algorithms. A famous Markov chain is the so-called “drunkard’s walk”, a random walk on the number line where, at each step, the position may change by +1 or ?1 with equal probability. From any position there are two possible transitions, to the next or previous integer. The transition probabilities depend only on the current position, not on the manner in which the position was reached. For example, the transition probabilities from 5 to 4 and 5 to 6 are both 0.5, and all other transition probabilities from 5 are 0. These probabilities are independent of whether the system was previously in 4 or 6.

Question 121

Stochastic Gradient Descent (SGD)

Answer 121

Stochastic gradient descent (SGD) is an iterative optimization algorithm that can be applied to functions that are a linear combination of differentiable functions. These types of functions often arise when the full objective function is a linear combination of objective functions at each data point, e.g. a least squares objective function. While batch gradient descent uses the full gradient of the function, SGD approximates the full gradient by using the gradient at each of the functions in the linear combination, e.g. the gradient of the objective function at each data point. SGD is often used to optimize non-convex functions, e.g. those that arise in neural networks.

Question 122

Differentiable Function

Answer 122

In calculus (a branch of mathematics), a differentiable function of one real variable is a function whose derivative exists at each point in its domain. As a result, the graph of a differentiable function must have a (non-vertical) tangent line at each point in its domain, be relatively smooth, and cannot contain any breaks, bends, or cusps.

Question 123

Sensitivity

Answer 123

aka Recall or True positive rate. Percent of actual Positives that were correctly predicted.

Question 124

Precision

Answer 124

Percent of predicted Positives that were correct.

Question 125

Specificity

Answer 125

aka True negative rate. Percent of actual Negatives that were correctly predicted.

Question 126

Accuracy

Answer 126

Percent of all predictions that were correct.

Question 127

Generative Approach

Answer 127

Models the measurements in each class. It is more work, but it can exploit more prior knowledge, needs less data, is more modular, and can handle missing or corrupted data. Methods include mixture models and Hidden Markov Models.

Question 128

Discriminative Approach

Answer 128

Focuses only on discriminating one class from another. It can be more efficient once trained and requires fewer modeling assumptions. Methods include logistic regression, generalized linear classifiers, and nearest-neighbor.

Question 129

Discriminative vs. Generative

Answer 129

Discriminative models learn to discriminate between different inputs. For example, classifying images as containing a dog or not containing a dog is a discriminative task. An example of a discriminative model is a support-vector machine. Generative models usually involve probabilities and their distinguishing feature is that you can generate new data from them. For example, if you tried to estimate the probability distribution over images containing dogs and a different distribution over images not containing dogs, you would have generatively modeled the situation. You could use these distributions to sample new images of dogs (or new images not containing dogs). If you wanted to use this generative model for a discriminative task, you could: given an image, you could see which of the two distributions assigns higher probability to that image and then choose that as your result. Thus, there is a distinction here between discriminative model and discriminative task: it may be possible to use generative models for discriminative tasks.

Question 130

Frequentist vs. Bayesian

Answer 130

The Bayesian view is essentially that everything should be done with Bayes’ rule: computing posterior probabilities by multiplying priors with likelihoods. In a Bayesian approach, you usually have a posterior distribution over models. Then, if you want to use this model for something, like making a prediction, you integrate over your posterior distribution of models to get a sort of “expected value” of the thing you are trying to predict. Frequentist is often used to mean not Bayesian. In a frequentist approach, you typically find a “best” solution (i.e., model) to the problem you are trying to solve. You then use this best model to make the prediction. I believe there is a relationship between the frequentist approach and discriminative models, and likewise for the Bayesian approach and generative models.

Question 131

Probabilistic Graphical Model (a.k.a. Graphical Model)

Answer 131

Ways of encoding the structure (independencies) of a probability distribution into a picture. The two main types of graphical models are directed graphical models and undirected graphical models, probability distributions represented by directed and undirected graphs respectively. Each node in the graph represents a random variable, and a connection between two nodes indicates a possible dependence between the random variables. So, for example, a fully disconnected graph would represent a fully independent set of random variables, meaning the distribution could be fully factored as P(x,y,z,…)=P(x)P(y)P(z)… Note that the graphs represent structures, not probabilities themselves.

Question 132

Kernel Trick

Answer 132

Adding non-linear features to the representation of our data can make linear models much more powerful. However, often we don’t know which features to add, and adding many features (like all possible interactions in a 100 dimensional feature space) might make computation very expensive. The Kernel Trick is a clever mathematical trick that allows us to learn a classifier in a higher dimensional space without actually computing the new, possibly very large representation. It works by directly computing the distance (more precisely, the scalar products) of the data points for the expanded feature representation, without ever actually computing the expansion. There are two ways to map your data into a higher dimensional space that are commonly used with support vector machines: the polynomial kernel, which computes all possible polynomials up to a certain degree of the original features (like feature1 ** 2 * feature2 ** 5), and the radial basis function (rbf) kernel, also known as Gaussian kernel. The Gaussian kernel is a bit harder to explain, as it corresponds to an infinite dimensional feature space. One way to explain the Gaussian kernel is that it considers all possible polynomials of all degrees, but the importance of the features decreases for higher degrees.

Question 133

Cross-validation

Answer 133

Cross-validation based on k-folds splits your data into a number k of folds (portions of your data) of equal size. Then, each fold is held out in turn as a test set and the others are used for training. Each iteration uses a different fold as a test, which produces an error estimate. The process continues until all the k-folds are used once as a test set and you have a k number of error estimates that you can compute into a mean error estimate (the cross-validation score)