How does "BeamSearch" work?

Question

I'd like to see a more intuitive example of what this type of net decoder actually does (in the context of lstm's and text/caption generation).

This is the only example in the docs:

and I have no idea how to use this!

References:

• https://github.com/yunjey/show-attend-and-tell/issues/41

Answer 1

I found these articles useful for understanding.

https://distill.pub/2017/ctc/

https://machinelearningmastery.com/beam-search-decoder-natural-language-processing/

Answer 2

http://blog.wolfram.com/2018/05/24/learning-to-listen-neural-networks-application-for-recognizing-speech/

The Data

ro = ResourceObject["Spoken Digit Commands"]

trainingData = ResourceData[ro, "TrainingData"];
testingData = ResourceData[ro, "TestData"];
RandomSample[trainingData, 3] // Dataset

RNN Using CTC Loss

We can attempt something more adventurous on this dataset: up until now, we have simply done classification (a sequence goes in, a single class comes out). What if we tried transduction: a sequence (the MFCC features) goes in, and another sequence (the characters) comes out?

First of all, let’s add string labels to our data:

labels = <|0 -> "zero", 1 -> "one", 2 -> "two", 3 -> "three",
   4 -> "four", 5 -> "five", 6 -> "six", 7 -> "seven", 8 -> "eight",
   9 -> "nine"|>;
trainingDataString =
  Append[#, "Target" -> labels[#Output]] & /@ trainingData;
testingDataString =
  Append[#, "Target" -> labels[#Output]] & /@ testingData;

We need to remember that once trained, this will not be a general speech-recognition network: it will only have been exposed to one word at a time, only to a limited set of characters and only 10 words!

Union[Flatten@Characters@Values@labels]//Sort

{"e", "f", "g", "h", "i", "n", "o", "r", "s", "t", "u", "v", "w", "x", "z"}

A recurrent architecture would output a sequence of the same length as the input, which is not what we want. Luckily we can use the CTCBeamSearch NetDecoder to take care of this. Say that the input sequence is n steps long, and the decoding has m different classes: the NetDecoder will expect an input of dimensions {n,m+1} (there are m possible states, plus a special blank character). Given this information, the decoder will find the most likely sequence of states by collapsing all of the ones that are not separated by the blank symbol.

Another difference with the previous architecture will be the use of NetBidirectionalOperator. This operator applies a net to a sequence and its reverse, catenating both results into one single output sequence:

net = NetGraph[{NetBidirectionalOperator@
    GatedRecurrentLayer[64, "Dropout" -> {"VariationalInput" -> 0.4}],
   NetBidirectionalOperator@
    GatedRecurrentLayer[64, "Dropout" -> {"VariationalInput" -> 0.4}],
   NetMapOperator[{LinearLayer[128], Ramp, LinearLayer[], 
     SoftmaxLayer[]}]},
  {NetPort["Input"] -> 1 -> 2 -> 3 -> NetPort["Target"]},
  "Input" -> 
   NetEncoder[{"AudioMFCC", "TargetLength" -> All, 
     "NumberOfCoefficients" -> 28, "SampleRate" -> 16000, 
     "WindowSize" -> 1024, "Offset" -> 571, "Normalization" -> True}],
  "Target" -> NetDecoder[{"CTCBeamSearch", Alphabet[]}]]

To train the network, we need a way to compute the loss that takes the decoding into account. This is what the CTCLossLayer is for:

trainedCTC = 
  NetTrain[net, trainingDataString, 
   LossFunction -> 
    CTCLossLayer["Target" -> NetEncoder[{"Characters", Alphabet[]}]], 
   ValidationSet -> Scaled[.05], MaxTrainingRounds -> 20];

Let's pick a random example from the test set:

a = RandomChoice@testingDataString

Look at how the trained network behaves:

trainedCTC[a["Input"]]

{"s", "i", "x"}

We can also look at the output of the net just before the CTC decoding takes place. This represents the probability of each character per time step:

probabilities = 
  NetReplacePart[trainedCTC, "Target" -> None][a["Input"]];
ArrayPlot[Transpose@probabilities, DataReversed -> True, 
 FrameTicks -> {Thread[{Range[26], Alphabet[]}], None}]

We can also show these probabilities superimposed on the spectrogram of the signal:

Show[{ArrayPlot[Transpose@probabilities, DataReversed -> True, 
   FrameTicks -> {Thread[{Range[26], Alphabet[]}], None}], 
  Graphics@{Opacity[.5], 
    Spectrogram[a["Input"], 
      DataRange -> {{0, Length[probabilities]}, {0, 27}}, 
      PlotRange -> All][[1]]}}]

There is definitely the possibility that the network would make small spelling mistakes (e.g. "sixo" instead of "six"). We can visually inspect these spelling mistakes by applying the net to all classes and get a WordCloud of them:

WordCloud[StringJoin /@ trainedCTC[#[[All, "Input"]]]] & /@ 
 GroupBy[testingDataString, Last]

Most of these spelling mistakes are quite small, and a simple Nearest function might be enough to correct them:

nearest = First@*Nearest[Values@labels];
nearest["sixo"]

"six"

To measure the performance of the net and the Nearest function, first we need to define a function that, given an output for the net (a list of characters), computes the probability per each class:

probs = AssociationThread[Values[labels] -> 0];
getProbabilities[chars : {___String}] := 
 Append[probs, nearest[StringJoin[chars]] -> 1]

Let's check that it works:

getProbabilities[{"s", "i", "x", "o"}]
getProbabilities[{"f", "o", "u", "r"}]

<|"zero" -> 0, "one" -> 0, "two" -> 0, "three" -> 0, "four" -> 0, "five" -> 0, "seven" -> 0, "eight" -> 0, "nine" -> 0, "six" -> 1|>

<|"zero" -> 0, "one" -> 0, "two" -> 0, "three" -> 0, "five" -> 0, "six" -> 0, "seven" -> 0, "eight" -> 0, "nine" -> 0, "four" -> 1|>

Now we can use ClassifierMeasurements by giving an association of probabilities and the correct labels per each example as input:

cm = ClassifierMeasurements[
  getProbabilities /@ trainedCTC[testingDataString[[All, "Input"]]], 
  testingDataString[[All, "Target"]]]

The accuracy is quite high!

cm["Accuracy"]
cm["ConfusionMatrixPlot"]

0.949