1
Q
Hidden Markov Model
A
1) A statistical model that assumes that the system it’s modelling on is a Markov process with unobservable states.
2) A 5-tuple of S (a set of possible latent states), Σ (set of all observations), T (a transition matrix between hidden states), E (transition probability of selecting an element in element given a state s ∈ S), π (initial distribution over states)
3) Example of use: speech recognition
2
Q
Markov Process
A
- A continuous-time process
- A sequence that obeys the Markov property.
3
Q
Markov Chain
A
- A discrete-time process
- A set of parameters that allow the representation of a Markov process
- A triple of Σ (set of possible states), E (transition matrix), π (initial distribution over the states)
4
Q
First-order Markov Chain
A
p(xn+1 || xp, xn-1,…,x1, x0)
5
Q
Markov Property
A
A sequence in which the distribution for xn+1 depends only on a few events
6
Q
Latent variable
A
A variable that can’t be seen or measured in the data
7
Q
Probability
A
Number between 0 and 1 which measures the chance of an event occurring
8
Q
Conditional probability
A
- Chance of observing an event y given that an event x has occurred
- p(y|x) = p(x,y)/p(x)
9
Q
Joint probability
A
- Chance that a collection of events occur together
- p(x = X, y = Y, z = Z) = p(x,y,z)
10
Q
Marginal probability
A
- Chance of observing a random variable in a particular state when at least two events are observed simultaneously
11
Q
Random variable
A
A variable whose value is subject to uncertainty or chance
12
Q
Discrete random variable
A
A random variable that can only take a countable number of values. For example, a coin toss
13
Q
Continuous random variable
A
A random variable where the data can take infinitely many values. For example, measuring computation time
14
Q
Bayes Theorem
A
- P(A|B) = P(B|A) P(A)/P(B)
- P(A|B) = likelihood of A given B
- P(B|A) = likelihood of B given A
- P(A) = prior
- P(B) = evidence
15
Q
Supervised classification
A
- Determining a class of unlabelled data using a model that is learned by examining labelled data
- For example: spam detection
16
Q
Unsupervised classification
A
- Determining a class of unlabelled data using a model that is learned by examining unlabelled data
- For example: neural networks
17
Q
Closed form solution
A
- A formula that can be derived directly, that gives the optimum results for the parameters directly based on the data
- In the context of lines, a solution where when fitting a straight line, it is possible to compute the optimal values for m and c directly rather than search for them
18
Q
Regression
A
- Fitting a model to a set of data, in order to explore the relationship between dependent and independent variables.
- For example, tuning parameters of a simulation to match real measurements
19
Q
Uniform distribution
A
- P(X = x|N) = 1/N, x = 1,2,3,…,N
- Where N is an integer
- Equal chance of each outcome
- For example, rolling a die
20
Q
Binomial coefficient
A
21
Q
Binomial distribution
A
- The distribution of the number of successes in a fixed number of independent Bernoulli trials
> X = 1 with probability p
> X = 0 with probability 1 - p
> 0 <= p <= 1
> EX = 1p + 0(1 - p) = p
> VarX = p(1 - p)
- n Bernoulli trials
> Ai = {X = 1 on the ith trial}, i = 1,2,..,n
22
Q
Negative binomial distribution
A
The distribution of the number of trials needed to get a fixed number of successes
- x = number of trials
- p = chance of success
- r = successes
23
Q
Poisson distribution
A
- Often used to model waiting for an event
- Single parameter λ is referred to as the intensity
- P(X ≥ x) = 1 - P(X ≤ x - 1)
- P(X ≥ 1) = 1 - P(X = 0)
- Example:
> Website accessed on average 5 times every 3 minutes
> Probability of no accesses in the next minute?
> Random variable X = number of accesses in a minute
> Poisson distribution, λ = 5/3
> P (no accesses in the next minute) = P(X=0)
> (e-5/3)(5/3)0/0! = e-5/3
24
Q
Hypergeometric distribution
A
- No replacement, unlike binomial distribution
- N = Total population
- M = Number of successes
- K = Sample size
- x = Number of successes in sample
- P(X > x) = 1 - P(X = x)
25
Geometric distribution
- The simplest of the waiting time distributions
- A special case of the negative binomial, it's the distribution for the number of trials needed to get the first success
- n = number of trials
- p = probability of success
26
Feature vector
An n-dimensional vector of numerical features that represent an object (for example, occurrence of a word).
27
Confusion Matrix
A matrix that visualises the performance of an algorithm.
- One dimension is the correct label
- The other is the label that was predicted
- Values in the diagonal indicate a correct prediction. Values elsewhere indicate a wrong prediction.
28
Support Vector Machine
- Find a hyperplane in an n-dimensional space that divides the two classes with as much space as possible
- The hyperplane can be written as w∙x - b = 0
- Select two parallel hyperplanes that fit between the data with as large a distance as possible
\> w∙x - b = 1
\> w∙x - b = -1
29
Multivariate Normal Distribution
30
Gaussian Mixture Model
- A weighted sum of each of the Multivariate Gaussians
- Can be used for supervised and unsupervised classification
- Can be created if training data is partitioned by:
\> Labelling the data
\> Finding number of Gaussians, and the mean and covariance for each
\> Assume number of Gaussians is equal to the number of classes
31
Gaussian Distribution
- Defined by two parameters: mean (µ) and variance (σ2)
- In a set X1,...,Xn:
\> Mean is determined by sum of values / number of values
\> Variance is determined by the formula: (Σ(x - µ)2)/n
32
Maximum likelihood approach
33
Statistical independence
- Events that can occur together but are unrelated
- p(x|y) = p(x)
34
Conditional independence
- p(x|y,z) = p(x|z)
- This means if z is known, knowing y gives no new information about x
- It is still possible that p(x|y) ≠ p(x), so x and y both depend on z
35
Central Limit Theorem
- When independent random variables are summed, their normaized sum tends toward a normal distribution, even if the original variables themselves are not normally distributed.
- This means statistical and probability methods that work for normal distributions can be applicable to a range of problems that use other distributions
36
Overfitting
- Choosing a polynomial that would fit every data point with low error but not fit the points in between
37
Regularisation
- Introduction a term into the objective function
- Prevents over-fitting
38
Objective function
A function that is desired to maximise or minimise
39
Simulated annealing
- A stochastic search algorithm
- Example: travelling salesman problem, find the route with the lowest mileage that connects all points
- Preferable to gradient descent because:
\> Finds the true global minimum rather than a local one
Technique:
1) Starts at a random initial placement, with a high 'temperature'
2) Generate a random move, higher temperature means a bigger move
3) Calculate the change in the score based on the move made
4) Depending on the change in score, accept or reject the move. The probability of acceptance depends on the
current temperature
5) Lower the temperature value and loop from step 2
40
Gradient descent
- General concept: take steps proportional to the negative of the gradient of the function at the current point
- Step size is determined by the Taylor expansion
- Direction:
41
Taylor Expansion
- Note: if the distance value is too large then it could miss the minimum.
- Note: if the distance value is too small then it's very slow
42
Brute Force
- Looks at every point in the feature space
- Often the space is continuous, it has to be quantised
Advantages:
- Conceptually simple
- Doesn't get stuck in local extrema
Disadvantages:
- May miss a solution
- Very expensive, especially in high dimensions
43
Parametric density function
- Use functions with a fixed form and parameters that are found using the data
44
Mixture Model
- A parametric density function
- Does not have to be all Gaussians
45
Non-parametric density function
- Do not assume an underlying functional form (in other words, have an unknown number of parameters)
46
Kernel density estimation
- A non-parametric density function
\> Each data point contributes towards the overall density according to some smoothing function, called a kernel
\> To form a density estimate at a point, simply sum the contributions from kernels placed at every data point
47
Bandwidth
- The width of the kernel gives a trade-off between the smoothness and accuracy of the result
\> Use a 'bandwidth' parameter to tune the technique
\> A good selection of bandwidth depends on the data
\> The choice of bandwidth is more important than the choice of kernel
48
Mean Shift
- A non-parametric algorithm which uses the kernel density technique to find local maxima
- Most common application is clustering
- Algorithm steps:
For each point:
1) Estimate the density at the point and at several points in a region nearby (using KDE)
2) If the nearby density is all lower, this is a local maximum
3) Otherwise, move to the highest point and repeat
49
Axioms of probability theory
1) All probabilities are non-negative,for all x: p(x) ≥ 0
2) Mutually exclusive events add
3) The probability that at least one of all the possible outcomes of a process will occur is 1
50
Probability functions
- Probabilities for all possible events as a function
1) Probability mass function
\> Discrete data
\> Must sum to 1
\> Can never exceed 1
\> Probability is given directly by the function
2) Probability density function
\> Continuous data
\> Must integrate to 1
\> Can exceed 1 locally
\> Probability is given by integrating over an interval
51
Optimisation
If the optimal values cannot be computed directly, then search for them while excluding all outliers
52
Expectation maximisation
- A meta-algorithm used in unsupervised GMM classifying
- Used for latent variables, when the model is in the exponential family (e.g. Gaussian)
- Two steps
\> Expectation: find the expected value of the log-likelihood
\> Maximisation: find parameters that maximise this
- Problems
\> If data isn't Gaussian distributed or clusters overlap
\> May not give global maximum
\> Number of clusters must be specified
- For the last point, can incorporate measure of complexity into algorithm to pick automatically
53
Deterministic optimisation
- The output is fully determined by the parameter values and initial conditions
54
Stochastic optimization
The output will be the result of an inherent randomness of the inputs (in other words, the same set of parameters will lead to different results most of the time)
55
Closed form optimisation
- Is deterministic and can be derived mathematically
- However, there is a set number of steps to do in closed form solutions while with deterministic solutions that is not the case
56
Population mean
- μ = (ΣX)/ N
- μ = mean
- ΣX = sum of all values in the group
- N = number of items in the group
57
Sample mean
58
Least squares objective function
A measure for how well a given line (m,c) fits the data D
59
Classification problem
- Data required:
\> Feature vectors
\> Labels corresponding to each item in the feature vector
- Processing data:
\> Splitting into two sets: training data (the data that will be used to build the model) and test data (the data that will be used to test said model)
- Model used:
\> Only depends on the number of features and the number of classes
\> Doesn't get larger as more training data is added
-- p(c|x) = p(c)p(x|c)
-- p(c) = probability of the class (the number of times the class occurs divided by the total number of training data items)
-- p(x|c) = the probability that the word x↓i appears in the sentiment c↓j (this can be computed by counting occurrences)
-- p(x) is dropped in order to maximise the values, as it's a MAP approach
- Testing the system:
\> Keep a portion of the labelled data separate
\> Plot the results as a 2D confusion matrix
\> Values in the diagonal indicate the prediction was correctly. Values elsewhere indicated a wrong prediction
60
Curse of dimensionality
- As the number of features grows, the amount of data needed to generalise accurately grows exponentially
- This is a problem for any method that requires statistical significance
61
K-Means
- Example of an algorithm that doesn't require a human supervisor to partition data into classes
62
Viterbi Algorithm
- A dynamic programming algorithm of complexity O(n \* |S|2) that calculates the most probable path through the hidden states given the observations
- pk(i,t) = ek(i) maxl(pl(j,t-1)\*plk)
63
Barum-Welch Algorithm
- Can find local minimum/ maximum
- maxvp(v|data)
Steps:
1) Choose a random HMM
2) Use the Viterbi algorithm to calculate α's and β's
3) Use Bayes theorem to update parameters
Problems:
\> There are lots of parameters, which can cause overfitting
-- This may result in the algorithm having to be run a few times, which would either need longer sequences or many short ones
\> Can't learn on long sequences
-- Multiplying many small numbers together results in 0s. Need to use log probabilities and not probabilities themselves or generate many short sequences
64
Hessian
A square matrix of second order partial derivatives
65
k Nearest Neighbours
- Requires a feature vector (objects to be classified)
- Requires a training set (A set of samples with known classification)
- For a given test object, compute the distance d between the test and each element of the training set
- Look at the k elements with smallest d, take the classification with the biggest vote
66
Covariance Matrix
- A matrix whose element in the i, j position is the covariance between the i-th and j-th elements of a random vector
- Determines the correlation between features
- It's ideal to use features that are not correlated and use as few features as possible, in order to avoid the curse of dimensionality
Year 2
flashcards
Decks in class (5)
# Cards
