Supervised Classification of Audio Streams: Part II

Overfitting

Overfitting is the key issue with machine learning algorithms. It is trivially easy to devise a supervised learning algorithm that takes in input features and exactly predicts the corresponding output classes in the training data. A simple lookup table will do this.

To make useful predictions, a learning algorithm must predict values with features it has never seen. The problem is we can only optimise the performance based on data we have seen. The generalisation performance of an algorithm is the ablility to make predictions outside of the training data.

This means that we cannot optimise an algorithm by adjusting parameters to fit the training data better; this will lead to overfitting, where the predictive power of the algorithm decreases as it is exposed to additional data.

Kernel density estimation example

We can see the overfitting effect if we try to learn the distribution of data using kernel density estimation (KDE). KDE is effectively a smoothed histogram, which is created by "placing" smooth distributions on each observed data point and summing them (i.e. convolving them with some window function). This can be used to estimate an underlying smooth distribution from point samples.

The key parameter in KDE is the kernel width $\sigma$, which determines how wide each distribution will be and thus how smooth the overall distribution will be.

As the function approximates the data better, the generalisation performance drops. If we split the data randomly into two portions $X_1$ and $X_2$, and learn the KDE using only $X_1$ (training set) and then compute how likely $X_2$ (test set) is given that learned distribution, we can see this loss of generalisation performance.

Training error can always be reduced -- but it makes things worse

This is why data hygiene is absolutely critical. If you let any part of the data you use to evaluate performance affect the train process your results are biased (potentially to the point they are meaningless).

Randomised selection vs block selection

One approach to splitting up data is to randomly assign some elements to the training set and some to the test set (e.g. in an image classification task, 70% of the images are assigned to the training class and 30% to the test class).

This seems like an unbiased way of separating the data, and it is for problems which are effectively uncorrelated. But imagine we have a time series $x_0, x_1, \dots, x_n$ and we build our input features $X_0, X_1, \dots$ by taking overlapping windows of the series. If we randomly choose elements of $X$, many of the elements in the test and training set may be almost identical ( because they appeared next to each other in the time series). This leads to wildly optimistic test results

Jellyfish classifier example

Imagine we want to train a classifer to detect jellyfish in an aquarium tank.

Random selection: training set nearly identical to test set

[Train] [Test]

Block selection: training set and test set distinct

[Train] [Test]

[images from https://archive.org/details/Davidleeking-Jellyfish854 CC-NC-SA-2.0]

A much better approach here is to split the data into a large chunks. Say the data was a series of photographs from the jellyfish tank taken on 10 different days; the first 6 days might be assigned as training and the last 4 as test. This is more likely to be a reliable estimator of future performance, because the key idea is to predict future behaviour -- to learn what we have not seen.

Meta-algorithms: Ensembling

Meta-algortihms are ways of combining multiple learning models to improve performance. These generally involve ensembles of classifiers. They can be applied to a very wide range of strategies, and they generally always improve performance (even if the improvement is marginal). In major machine learning competitions (e.g. Kaggle, the Netflix challenge) ensemble algorithms are almost always the top performers.

The idea of a ensemble method is that if you train multiple classifiers/regressors of different types or on different datasets, they will learn different things well; and combining them together increases the robustness and generalisation performance.

Voting hybrid models

One simple model is to train a number of different types of classifiers on a dataset and have them vote on the class label. For regression, the median or mean can be used as the combination function.

Bagging

Rather than combining different models, we can use a single model but different datasets. Bagging applies the statistical process called the bootstrap to generate multiple classifiers/regressors.

Bootstrap generates synthetic datasets by randomly resampling the original dataset with replacement. From a dataset $X$ with $n$ elements, it generates $k$ new datasets each of which have $n$ elements consisting of random draws from the rows of $X$. Bagging then trains one independent classifier for each of these $k$ datasets then combines the output by voting or averaging. This increases the robustness of the model.

This has the advantage of working for any supervised learning task (but there may be significant computational issues if the datasets are very large). However, bagging may not improve (or may even make worse) classifiers that are not already overfitting.

Variations of this approach include randomly sampling the features (columns of $X$); random feature selection is called random subspaces and randomly sampling both features and samples is known as random patches.

Boosting

Boosting is an alternative ensemble method which trains a weak classifier on a dataset, identifies samples it is performing poorly on, and trains another classifier to learn the poor samples, identifies samples the ensemble is still performing poorly on, and trains a classifer to learn those and so on.

The selection of the weak samples is usually done by weighting the samples rather than a binary inclusion/exclusion. The AdaBoost algorithm is a well-known example of this class, and can combine weak learners into effective classifiers.

Stacking

More complex ensembles include stacking where a set of weak learners learn a function, and another "selection" learner learns from a combination of these classifier outputs and the original data. So each weak learner learns a function $f_1(x), f_2(x), \dots f_n(x)$, and the feature vector for the final classifier is extended to $[x_1, x_2, \dots x_d, f_1(x), f_2(x), \dots, f_n(x)]$.

Ensemble models can be as complicated as you like, but the improvements in performance are often small, and more complex algorithms are only worth it if marginal gains are important (as they are in competitive machine learning).

Multi-class approaches

There are many classifiers (such as the perceptron) which only produce binary labels (is the data point one side of the datapoint or the other?). If there are multiple output classes, we need a way of building a multi-class classifier from a set of binary ones. In the touch example, we need to distinguish multiple touch regions (maybe four or five). If we only have binary classifiers, we need to somehow adapt them to work for these classes.

There are two popular approaches: one-vs-all and one-vs-one.

One-vs-all

One-vs-all classifiers classify $k$ different target labels by training $k$ distinct binary classifiers, each of which predicts whether or not the output class $y$ is $y=i$ for the $i$th classifier. In other words, it classifies whether each point is either a member of the specific class or of the "whole world". A simple maximum is used to select the classifier with the largest output, and the index of this classifier becomes the class label.

One-vs-one

An alternative approach is to train classifiers for each pair of classes. This needs $k(k-1)$ classifiers for $k$ distinct target labels. This generally requires more training data (as the data is spread more thinly over the classifiers) and doesn't scale well to large values of $k$.

Different audio features

In the first exercise you used the Fourier transform; but you might find better results with different transforms. Here are some options you could explore to project the time series into different spaces.

Fourier variants

There are slighly variants of the FT, like the discrete cosine transform, which also decomposes into periodic components, but can sometimes offer better classification performance, because it has better spectral compactness. This means it concentrates more energy onto fewer frequency bands and "compresses" the audio data better.

Cepstral coefficients

There are other transforms like the cepstral transform and the mel-frequency cepstrum (mfcc) which essentially compute ifft(log(fft(x)) and are good at recovering structure from modulated periodic signals (like vocal tract pulses).

Filterbank approaches

Filterbank approaches are spectral transforms, but allow for arbitrary distribution over the spectrum, and recover only magnitude information (usually). Effectively these apply lots of parallel bandpass filters, which select specfic frequencies. The filters can be distributed in various ways, usually logarithmically, in a similar manner to human hearing.

Where to find these transforms

• DCT: scipy.fftpack.dct()
• Cepstrum: import cepstrum (the module is provided for you)
• mfcc: from python_speech_features import logfbank (see below to install python_speech_features if you want to)

• logfilterbanks: from python_speech_features import logfbank

• If you are more ambitious, you can use the Discrete Wavelet Transform dwt from the pywavelets package.

The challenge

You have to build a classifier that classifies the region of a device that is being touched based on the sound recorded from a piezo contact microphone. There are four possible touch regions and also a silence/handling noise class:

The data are all in the data/ folder.

You have training data for these regions, challenge_train_0.wav, challenge_train_1.wav, challenge_train_2.wav, challenge_train_3.wav, challenge_train_4.wav

There is a set of test wave files called challenge_test_0.wav, challenge_test_1.wav, challenge_test_3.wav, and corresponding test labels challenge_test_0.labels, etc. See the code below which plots these datasets alongside your predicted labels.

The wave files are 4Khz, 16 bit, mono.

Final test function

There is a test function challenge_evaluate_performance(classifier_fn). This gives you your current score!

Note that class 0 is the silence class; you might want to have one classifier classify silence/active and then a further classification strategy to identify which part has been touched.

Your classifier function must take a wave filename as an input, and return a sequence of classes:

# the simplest possible valid classifier:
# just returns one single zero for the entire sequence.
def classify(wave_file):
    return [0]               

You can return any number of classes in that vector, but each class value must be equispaced in time. For example, you could classify once a second, or 20 times a second, but not with variable timing. The test function will automatically interpolate your class vector as needed.

secret_test.challenge_evaluate_performance() returns a score which represents how usable the resulting interface is likely to be; higher is better. You don't have access to the internals of this function; just like a real human study, the usability metric is not directly accessible :).

Be aware that both accuracy and responsiveness are measured. The test takes some time to run; so you must be parsimonious with your calls to it.

Strategies

• Feature engineering You can devise alternative feature vectors, e.g. by changing windowing strategy or using different transformations like the DCT or MFCC.

• Evaluation strategy. You can adjust the way you validate performance to better match the generalisation performance; e.g. by changing the cross-validation fold size, or structuring the sampling of the folds differently.

• Hyperparameter optimisation. You can adjust the parameters that control the learning of the algorithms you have chosen.

• Learning algorithm you can choose different algorithms from sklearn (e.g. LDA versus SVM or Random Forest).

• Multi-class approach You can use either a one-vs-all or a one-vs-one approach to classification, or use a natively multiclass classifier.

• Dataset augmentation. You can try and synthesise new data entries, e.g. by offseting windows or adding noise. Note that you could add noise before or after any feature transform.

• Ensemble techniques. You can try and combine many classifiers, using techniques like bagging, boosting or stacking.

• Sequential structure. Sequential time windows are obviously not independent. You can use this to improve overall performance by applying some form of temporal smooth (e.g. a majority vote).

You should consider subsampling the data when you are adjusting parameters and strategies, and only training on the full set when needed, to optimise the available time.