Speech Recognition using Graphs

Team members: Adrian Löwenstein, Kiran Bacsa, Manuel Vonlanthen
Date: 22.01.2018

Important Prior Information

To be able to rerun this notebook the function files "cut_audio.py" and "main_pipeline.py" (provided in the uploaded .zip file)have to be located inside the working path. In addition, the entire used data set, as well as a pickle file containing all extracted features from it can be downloaded here. For recomputation purposes the pickle file has to be located in a folder called "Features Data", which in turn has to be located in the working path. The dataset containing all audio files (circa 2 GB) has to be located at ..\Data.

Problem Description

In this section we will describe in detail the problem we studied during the final project of the course "Network Tour of Data Science". We wanted to do speech recognition using the Graph/Network theory learned during the course. We were inspired by the kaggle competition "Tensor Flow Speech Recognition Challenge: Can you build an algorithm that understands simple speech commands" put up by google. In said competition the goal was to classify 20 distinct words. Words that do not belong to any of the 20 classes should be classified as "unknown". For the kaggle competition the TensorFlow library had to be used. For this purpose Google provided a large training data set (64'720 audio files) with known labels and an even larger test (150'000+ audio files) with unknown labels for them to evaluate the built algorithms. We, however, decided to only work with the provided training data, because the data set is large enough to perform statistically valid model evaluation and it this we we weren't dependant on the kaggle competition.

The provided data set consists of 64'720 .wave files of length 1s, sampled with a sampling rate of $16$ kHz. Each audio files contain one of 30 possible spoken words. The files were created using crowd-sourcing, which means that the conditioning of the audio signal is not equal for all audio files. This led to very different noise levels, amplitudes, etc. Also the same speaker might have recorded different audio files. The 20 core words which have to be classified correctly are:

- up, down
- zero, one, two, three, four, five ,six ,seven, eight, nine
- go, stop 
- left, rigth
- no, yes
- off, on

In addition to these 20 words, 10 other words were provided inside the training set to train the algorithm to classify words which it should not react to as "unknown". The following "unknown" words are contained in the training data:

- bed
- bird, cat, dog, mouse
- tree
- happy
- marvin, sheila
- wow

At this point we want to empphasize that we did not study the problem suggested for the kaggle competition, but a slightly simplified one. First of all we did not restrict ourselves to using TensorFlow, in fact we did not use it at all. However, we did restrict ourselves to use Graph theory as central part of our classification algorithm. Our goal was, using only the provided training set, to build a classifier which calssifies the above listed core words as accurate as possible. In addition, all other words (the 10 additional words) should be classified as "unknown". This means we wanted to build a "word"-classifier for 21 different classes using graph theory.

Mathematically, we can define the task as follows. We split up our training data set into a training set $S_t$ of some size N (we will later comment on its size) and a validation set $S_v$ of size $V \leq 64'720-N$, used to check how well the classifier works. Using $\mathbf{x_n} \in S_t$, which is some training audio file $\mathbf{x_n} \in \mathbb{R}^D$, where $D = 1s\cdot 16kHz = 16000$ is the number of samples per audio file, we can build our training data matrix $\mathbf{X}^{\mathbf{N\times D}}$. Using $\mathbf{X}$ we want to learn a function $f(\mathbf{v_v}, \mathbf{X}): \mathbb{R}^{N+1\times D} \to \{1,2,3,...,21\}$, where $\mathbf{v_v}\in S_v$ is a validation audio file $\mathbf{v_v}\in\mathbb{R}^D$, such that the resulting estimated label $\hat{y_v} = f(\mathbf{v_V}, \mathbf{X})$ is equal to the correct label $y_v \in \{1,2,3,...,21\}$ for as many validation samples as possible. Hence, we use the accuracy measure defined as $$acc = \frac{\sum_{i=1}^{K}\max[\min[(|y_k-\hat{y_k}|),1],0]}{K},$$ where $K$ is the number of tested samples $v_k$. We want to remark that the model could also work with a subset $\mathbb{v}\subseteq S_v$ (batch) instead of a single validation file $v_v$. In this case we define the cardinality of said subset $|\mathbb{v}|=K$ and the model would correspond to $f(\mathbb{v}, \mathbf{X}): \mathbb{R}^{(N+K)\times D} \to \{1,2,3,...,21\}^K$.

Imports

Recompute

WARNING If you set recompute to True this will reextract all featrues, which will take approiximately a days, so we do not recommend it. It is here for completeness so you can see how the step was done during th project. We've already computed it and saved the results into a pickle file. Our entire used data, as well as the pickle files can be found here.

Feature Extraction

The Dataset that was taken from the Kaggle competition was initally separated in 2 sets. A Training Set containing labeled test words from different speakers with various background noises. The test set contains unlabeled data, and will not be used with this project as it won't allow the calculation of the accuracy. In the following we will only use the original training set as our main dataset. The words are provided in the form of a .wav sound file of 1 second.

Feature Extraction Pipeline :

1. We first analyse the dataset and save into a dataframe for each word : the path, the label and the id of the speaker.
2. We then import the audio content using Librosa and store it into this dataframe.
3. Next we proceed to the cleaning of the data by cutting the silences before and after the words are pronounced.
4. Finally we compute the main features : the MFCCs that are then stored into a pickle.

As for the feature chosen, we have kept only the MFCCs of the audio file. Other features we considered as the MFCCs for the whole audio file (instead of the cut version), or the statistics on the MFCCs .

Recomputing the whole Feature Extraction and Computation :

Pipeline for a small number of audio files :

After selecting 2 words we normalize their values to their maximum.

Next we define two auxiliary function that allow us to select main lobes of the signal and to keep only those lobes.

For the selection of the lobes we use the RMSE transformation. We next display the shape of those signals after this transformation :

Next we apply the our auxiliary function cut_signal to the 2 audio samples. As we see it removes efficiently the silence surrounding the main lobes.

Of the cut audio file we want now to compute our features the Mel-Frequency Cepstral Coefficients, short mfccs. For this, no matter the length of the audio file, we compute 20 mfcc vectors of dimension 10. This means we compoute a short-time Fourier transform at 20 equidistant time points inside the cut audio files and keep the lower 10 mfccs of the spectrum. Since the audio files are of different length after the cutting, we adjust the hop-length (length between two short-time Fourier analyses) for every audio file accordingly. this makes the resulting feature vectors comparable and adds a "time warping" effect which should make the feature more robust to slower/faster spoken words.

As we have allready computed the Features for the whole dataset we load it directly from the following pickle file.

Classification Methods

Now that we have extracted some meaningful features from the raw data, we want to build a model that uses some training set $S_t$ of cardinality $|S_t|=N$, which can be used to classify the rest of the data (validation set). We've mainly analyzed two methods, "Spectral Clustering" and "Semi-Supervised Clustering", which we will describe in detail in this section.

We found that using a training set of cardinality $|S_t| = N = 4800$ and a validation batch size of $|\mathbb{v}|= K = 200$ to be both computationally reasonable and yielding good results. This means that we use the same $N$ datapoints (feature vectors of audio files), of which we know the labels, to classify all other audio files (validation set), of which we pretend not to know the labels. The classification of the validation set (size $V$) is done batch-wise, i.e. $K$ files are classified simultaniously and we iterate trough the entire validation set, i.e. $V/k$ iterations are performed. Which $N$ datapoints are chosen to form the training set is determined randomly with a restriction that every word (or class) is represented equally. Thus, for $N = 4800$ we choose $160$ audio samples of every one of the 30 clases/words at random.

In this section we will classify one batch of size $K = 200$ and while doing that explain both classification methods using graphs in detail.

Create training set, validation set and Data Matrix

In a first step, we create the label vector $\mathbf{y}\in\{1,2,3,...,30\}^{64'720}$ for all datapoints. In addition we plot the labels and the distribution of the classes.

In the above histogram we can see that the classes are not balanced inside the test set. However, for our testing we will chose a balanced training, as well as a balanced validation step. This corresponds to having an equal prior probability of occurence between the different words we want to classify. Thus, in the next cell we choose at random $160$ datapoints per class to form our training set $S_t$ ($30*160=4800$) and $1553$ datapoints per class to form the validation set $S_v$ ($1553*30 = 46590$), which is the maximum amount of datapoints we can put into the vlidation set for it to still be balanced.

We will define the batch sizem which defines how many validation samples are classified simultaniously. Then we choose at random 200 datapoints of the validation set $S_v$ to build said batch. Remark: Although the training and the validation sets are both balanced, the batch itself is not necessarily, because this would be an unreasonable constraint for the task.

Now we build our feature matrix $\mathbf{X}^{(N+K)\times D}$ by concatenating the feature vectors of all datapoints inside the training set $S_t$ and the batch datapoints. The feature are then normalized by substracting their mean, as well as dividing by the standard deviation. The feature normalizing step was found to have a ver significant effect on the resulting classification accuracy.

Build Graph from Data Matrix

We now want to build a graph from the earlier obtained data matrix. Every node in our graph will correspond to one datapoint (feature vector of one audio file). We use a weighted, undirected graph. The weight is very important for our application, since it gives us a measure of how similair the feature vectors of the two datapoints are. The undirectedeness is a logical conclusion of our edges being similitarity measures, which are inherently undirected.

To build the weight matrix $W\in \mathbb{R}^{(N+K)\times (N+K)}$ we compute the cosine distance between each datapoint $\mathbf{x_n}$ in the datamatrix $\mathbf{X}$, which is defined as $$d(\mathbf{x_i},\mathbf{x_j}) = \frac{\mathbf{x_i}^T\mathbf{x_j}}{||\mathbf{x_i}||_2||\mathbf{x_j}||_2}$$ and then build a similarity graph using $$\mathbf{W_{i,j}} = exp(\frac{-d(\mathbf{x_i},\mathbf{x_j})^2}{\sigma^2}).$$ Other, distance functions were tested, but the cosine distance was found to be the most effective. We used the mean overall distance as $\sigma$.

We can already see that there is a distinct square pattern inside the weight matrix. This points to a clustering inside a graph, achieved by good feature extraction (rows and columns are sorted by labels, except last 200). At this point we are ready to present the first classification method that was analyzed: Spectral Clustering.

Spectral Clustering

Our first approach was to naively reuse the code from assignment 3 : spectral graph theory. By combining all our of samples into a single graph and extracting the resulting graph laplacian, we hope to identify clusters which would correspond to the different words that need to be classified.

Unfortunatly, increasing sparsity has the effect of reducing classification accuracy. We therefore decided to remove k-NN sparsification all together and keep the sample graph as it is.

We can now calculate the eigenvectors of the Laplacian matrix. These eigenvectors will be used as feature vectors for our classifier.

In a next step we split the eigenvectors of the graph into two parts, one containing the nodes representing the training datapoints, one containing the nodes representing the validation datapoints.

A wide range of classifiers were tested on our input features. Remarkably, a very simple classifier such as the Gaussian Naive Bayes classifier produced far better results than more advanced techniques. This is mainly because the graph datapoints were generated using a gaussian kernel, and is therefore sensible to assume that our feature distribution will be gaussian as well. However, the best results were obtained using a Quadratic Discriminant Analysis classifier.

Once our test set has been classified we can visualize the effectiveness of our classification using a confusion matrix.

Finally we can focus on the core words that need to be classified and label the rest as 'unknown'.

In conclusion, we can say that, using spectral clustering, we were able to leverage the properties of graph theory to find relevant features in speech recognition. However, the accuracy achieved with our model is too far low for any practical applications. Moreover, this model does not benefit from sparsity, meaning that it will not be able to scale with large datasets.

Semi-Supervised classification

Now that we have seen the spectral clustering method, we want to present the semi-supervised classification method. For this we start by using the same training set $S_t$, validation set $S_v$, batch and Laplaian, as we used to explain the spectral clustering method.

Unlike for spectral clustering, for this method sparsifying the graph is very important. We noticed a significant increase in classificatiion accuracy using quite sparse graphs. Thus we now sparsify the graph, to have a more significant clustering. We use k-nearest neighbors approach for this.For the purpose of explaining the method we will keep $120$ strongest neighbors of each node.

We can see that the sparsifyied weight matrix is very focused on its diagonal. We will now build the normalized Laplacian, since it is the core graph feature we will use for semi-supervised classification. The normalized Laplacian is defined as $$L = \mathbf{I}-\mathbf{D}^{-1/2}\mathbf{W}\mathbf{D}^{-1/2},$$ where $\mathbf{I}$ is the $(N+K)\times (N+K)$ identity matrix and $\mathbf{D}\in \mathbb{N}^{(N+K)\times (N+K)}$ is the degree matrix of the graph.

For the semi-supervised classification approach, we now want to transform the label vector of our training data $\mathbf{y_t} \in \{1,2,...,30\}^{N}$ into a matrix $\mathbf{Y_t}\in \{0,1\}^{30\times N}$. Each row $i$ of the matrix $\mathbf{Y_t}$ contains an indicator vector $\mathbf{y_{t,i}}\in\{0,1\}^N$ for class $i$, which means it contains a vector which specifyies for each training node in the graph if it belongs to node $i$ or not.

In the next cell we extend our label matrix $\mathbf{Y_t}$, such that there are labels (not known yet) for the validation datapoints we want to classify. Thus we extend the rows of $\mathbf{Y}$ by $K$ zeros, since the last $K$ nodes in the weight matrix of the used graph correspond to the validation points. We also create the masking matrix $\mathbf{M}\in\{0,1\}^{30\times (N+K)}$, which specifies which of the entries in $\mathbf{Y}$ are known (training) and which are unknown (validation).

Now comes the main part of semi-supervised classification. The method relies on the fact that we have a clustered graph, which gives us similarity measures between all the considered datapoints. The above mentioned class indicator vectors $\mathbf{y_i}$ (rows of $\mathbf{Y}$) are considered to be smooth signals on the graph, which is why achieving a clustered graph with good feature extraction was important.

We try to fill in the gaps left in the label vector $\mathbf{y}$, i.e. estimating a $\mathbf{\hat{y}}\in \{1,2,...,30\}$, which should ideally be equal to the original label vector, i.e. containing the correctly classified labels for the validation datapoints. To achieve this we try to learn indicator vectors $\mathbf{\hat{y_i}} \in \mathbb{R}^{N+K}$ for each class $i$, which also contain labels for the validation points (unlike the afore mentioned $\mathbf{y_i}$). The higher the value $\mathbf{\hat{y_{i,j}}}$, the higher the probability that node $j$ belongs to class $i$. For this purpose, we solve the following optimization problem for each of the 30 classes, specified by $i\in \{1,2,...,30\}$.

$$ \underset{\mathbf{\hat{y_i}} \in \mathbb{R}^{N}}{argmin} \quad \frac{1}{2}||\mathbf{M_i}(\mathbf{y_i}-\mathbf{\hat{y_i}})||^2_2 + \frac{\alpha}{2} \mathbf{\hat{y_i}}^T\mathbf{L}\mathbf{\hat{y_i}} + \frac{\beta}{2}||\mathbf{\hat{y_i}}||_2^2$$

The matrix $\mathbf{M_i}$ is defined as the diagonal matrix containing the $i^{th}$ row of $\mathbf{M}$ on its diagonal. The first term of the above depicted cost function is the fidelity term, which makes sure that the estimated vector $\mathbf{\hat{y_i}}$ is sufficiently close to the known entries of $\mathbf{y_i}$ (i.e. the labels of the training data points). The second term makes sure that the learned vector $\mathbf{\hat{y_i}}$ is smooth on the graph. The last term is there to make sure that we solve for a low energy verctor and avoid that the optimization problem is ill-posed. The two factors $\alpha, \beta >0$ are hyperparameters which give weight to their respective term or criterion.

For the above described optimization problem we can find an explicit solution. For this, we first compute the gradient of the cost function with respect to $\mathbf{\hat{y_i}}$.

$$\nabla f(\mathbf{\hat{y_i}}) = -\mathbf{M_i}^T\mathbf{M_i}(\mathbf{y_i}-\mathbf{\hat{y_i}}) + \frac{\alpha}{2} (\mathbf{L}^T +\mathbf{L})\mathbf{\hat{y_i}} + \beta \mathbf{\hat{y_i}}$$

Using the fact that $\mathbf{M_i}$ is a diagonal, symmetric matrix containing only '1' and '0', as well as the fact that $\mathbf{L}$ is symmetric, we can simplify $\nabla \mathbf{f}$ to

$$\nabla f(\mathbf{\hat{y_i}}) = -\mathbf{M_i}(\mathbf{y_i}-\mathbf{\hat{y_i}}) + \alpha \mathbf{L} \mathbf{\hat{y_i}} + \beta \mathbf{\hat{y_i}}.$$

To find the solution $\mathbf{\hat{y_i}^*}$ to the optimization problem we set the gradient to 0 to obtain

$$\nabla f(\mathbf{\hat{y_i}^*}) = 0 = \mathbf{M_i}(\mathbf{y_i}-\mathbf{\hat{y_i}^*}) - \alpha \mathbf{L} \mathbf{\hat{y_i}^*} - \beta \mathbf{\hat{y_i}^*},$$

and thus

$$\mathbf{M_i y_i} = (\mathbf{M_i}+\alpha \mathbf{L} + \beta \mathbf{I}_{(N+K)(N+K)}) \mathbf{\hat{y_i}^*}.$$

$\mathbf{I}_{(N+K)(N+K)}$ is the identity matrix of size $(N+K) \times (N+K)$. Introducing $\mathbf{y_{i,compr}} = \mathbf{M_i y_i}$ we can write

$$\mathbf{y_{i,compr}} = (\mathbf{M_i}+\alpha \mathbf{L} + \beta \mathbf{I}_{(N+K)(N+K)}) \mathbf{\hat{y_i}^*}.$$

We define the matrix $\mathbf{A} = (\mathbf{M_i}+\alpha \mathbf{L} + \beta \mathbf{I}_{(N+K)(N+K)})$ and now want to analyse its invertibility.

We know that the Laplacian $\mathbf{L}$ is positive semi-definite (PSD), which means that all its eigenvlues are $\geq 0$. $M_i$ simply adds '1' to some of that eigenvalues, unfortunately not to all of them and thus it is not a sufficient criteria to render $\mathbf{A}$ full-ranlk an thus invertible. For this prupose we introduce the $l_2$-prior which adds $\beta >0$ to each eigenvalue, which makes $\mathbf{A}$ psoitive definite and thus invertible. I.e. by controlling $\beta$ our problem is well-posed and a unique solution $\mathbf{\hat{y_i}^*}$ can be found.

$$\mathbf{\hat{y_i}^*} = \mathbf{A^{-1}}\mathbf{y_{i,compr}}$$

Having found an $\mathbf{\hat{y_i}}$ for every class $i$, we then build a matrix $\mathbf{\hat{Y}}\in \mathbb{R}^{30\times N}$, containing learned vectors $\mathbf{\hat{y_i}}$ as its rows. The final labelling vector $\mathbf{\hat{y_i}_{fin}}\in \{1,2,...,30\}$ is obtained by finding the row $i$ for each column $j$ of $\mathbf{\hat{Y}}$ in which the value is maximal and the index $i$ of the corresponding row will be the class $i$ of the datapoint (node) corresponding to the column $j$.

$$\mathbf{M_i y_i} = (\mathbf{M_i}+\alpha \mathbf{L} + \beta \mathbf{I}_{NN}) \mathbf{\hat{y_i}^*}.$$

$\mathbf{I}_{NN}$ is the identity matrix of size $N \times N$. Introducing $\mathbf{y_{i,compr}} = \mathbf{M_i y_i}$ we can write

$$\mathbf{y_{i,compr}} = (\mathbf{M_i}+\alpha \mathbf{L} + \beta \mathbf{I}_{NN}) \mathbf{\hat{y_i}*}.$$

We define the matrix $\mathbf{A} = (\mathbf{M_i}+\alpha \mathbf{L} + \beta \mathbf{I}_{NN})$ and analyse its invertibility. We know that the Laplacian $\mathbf{L}$ is positive semi-definite (PSD), which means that all its eigenvlues are $\geq 0$. $M_i$ simply adds '1' to some of that eigenvalues, unfortunately not to all of them and thus it is not a sufficient criteria to render $\mathbf{A}$ full-ranlk an thus invertible. For this prupose we introduce the $l_2$-prior which adds $\beta >0$ to each eigenvalue, which makes $\mathbf{A}$ psoitive definite and thus invertible. I.e. by controlling $\beta$ our problem is well-posed and a unique solution $\mathbf{\hat{y_i}^*}$ can be found.

$$\mathbf{\hat{y_i}^*} = \mathbf{A^{-1}}\mathbf{y_{i,compr}}$$

Having found a $\mathbf{\hat{y_i}}$ for every class $i$, we then build a matrix $\mathbf{\hat{Y}}\in \mathbb{R}^{30\times N}$, containing the learned vectors $\mathbf{\hat{y_i}}$ as its rows. The final labelling vector $\mathbf{y_{pred}}\in \{1,2,...,30\}$ is obtained by finding the row $i$ for each column $j$ of $\mathbf{\hat{Y}}$ in which the value is maximal and the index $i$ of the corresponding row will be the class $i$ of the datapoint (node) corresponding to the column $j$.

Method Validation

In the previous section we introduced two ways of doing speech classification using graphs. For this purpose one single validation batch of size 200 was classified. To have a better idea on how well the two methods classify data, we will now perform 100 iterations of the above explained code (from feature extraction to prediction). The used code can be found in its entirity in main_pipeline.py. This means that for every iteration an entirely new training set and validation set is created, such that the variance due to good or bad training sets is included in the obtained results.

In the boxplot shown below we can see the resulting mean accuracy, as well as the variance for both classification methods.

Conclusion

We introduced two methods to classify word using graph theory. We saw that spectral clustering with an average accuracy of 78% performs better than semi-supervised learning with an average accuracy of 70%. However, eve though the methods currently have similar computation time, in theory semi-superised learning could be implemented to be significantly faster, since it works with sparse representations of the graph, where spectral clustering works best usin a dense graph.

Even though, we could achieve respectable classification results, we could not come close to state of the art accuracies for the same task (ca. 90%). Still, if we take our mean accuracy score of 78% and assume that it would have performed similairly on the testing set of the kaggle competition a rank amongst the top 50 teams would have been achieved.

Several steps were integral in improving the performance of our classification. We started out with applying spectral clustering directly on the mfcc statistics (assignment 3) of the raw audio data. With this we achieved roughly 30% - 40% accuracy. Two large steps forward could be achieved by extracting the words from the audio files (circa 10%), as well as using the raw mfccs, dynamically adapted to the length of the spoken word, as defined above (circa 15%). Playing with the sparsity of the Laplacian was critical to achieve good results for both methods. Finally, finding the optimal training size to batch size ratio of 4 to 5% was imperative for the achieved results.

For spectral clustering, using a dense graph, reducing the size of the eigenvectors and using a good classifier (QDA was found to be optimal) were the main points for achieving our current results. For the semi-supervised classification to work at all it was imperative to add l2 regularization to the optimization, otherwise the problem was often ill-posed.

Further research on this topic would include a more thorough benchmarking of the different hyperparameters (especially for semi-supervised clustering). Furthermore it would have been interesting to try out other methods, such as the graph inference techniques mentioned in the last lecture.