Hello everyone,
I’m Nora Castner from the Human-Computer Interaction group at the University of Tuebingen
and I will talk you about MinHash, a fast approach for scanpath classification.
Scanpath approaches that consider the whole scanpath often suffer when it comes to real world tasks.
For many tasks, such as driving, performing surgery, or even grocery shopping,
there can be numerous Areas of Interest.
This becomes more problematic with the longer the time on task,
which contributes to larger the data stream, for instance the sequence of AOI transitions.
We present a method, MinHash, that uses the same-named technique
to extract scanpath similarity from subsequence frequencies.
This method improves on the runtime performance compared to traditional sequence alignment approaches
and is highly generalizable due to the model's built using data mining.
We have also made the algorithm publicly available on gitlab.
First, we construct Areas of Interest (AOIs), this can be done as the researcher pleases.
We then encode the fixation sequence based on the AOI hits.
This gives us a normalization of the scanpath to spatial and/or semantic information,
but maintains the temporal aspect of the scanpath.
And though we did not test it, you could also include the fixation duration
with, for instance, temporal binning
We continue on to get the sequence for the whole scanpath.
And up to this point, our approach does not differ from many SOTA sequence alignment approaches.
The next step is to extract and compare subsequences of scanpaths.
For this, we use N-Gram scanning to extract words of a fixed length
using a sliding window over the scanpath.
For instance we can look at words that are 4 letters long.
We deliberately insert gaps to compensate for signal noise,
this way we can map similar patterns to each other
Even if there's a slight offset in the signal.
The words then get tallied into a dictionary,
where matches affect the frequency of the word in the dictionary.
Now we have a dictionary for each scanpath.
The traditional approach is to consider the dictionary as a high-dimensional vector
and generally for comparing two scanpath dictionaries,
you would calculate the similarity, for example by the Euclidean distance.
However, as previously mentioned,
large and AOI-complex scanpaths can create excessively large dictionaries.
Our solution is to compare the minimal response
of a set of hash functions over the dictionary -> MinHash.
This corresponds to a repeated comparison of randomly selected subsequences of two scanpaths.
And the likelihood of equality corresponds to the Jaccard index.
Now for the all the scanpaths, the straightforward MinHash approach is
to count the matches between the words or hash functions.
If you use m distinct hash functions it takes m operations to compare 2 scanpaths.
But how do we handle the different frequencies within the scanpaths?
To solve this, we use Local Sensitive Hashing.
For scanpaths that have min-matches for 2 substrings
we can visualize the substring frequencies along 2 axes.
We apply some random thresholds,
this creates a signature,
Scanpaths with similar frequencies will appear more often on the same side of the threshold
The similar frequencies found through the thresholding
are then used to estimate the Jaccard Index of 2 scanpaths.
Then using the Jaccard Index, we can take unseen scanpaths.
and classify them using a k-nearest-neighbor classifier
To Evaluate MinHash, we used the dataset provided by the 2019 ETRA challenge.
Subjects were given 3 tasks: free viewing, puzzle, and 'Where is Waldo?',
which provide distinct task based scanpaths for classification.
We evaluated minhash with 4 different minimum hash functions: 64, 128, 256, and 512
and compared the classification performance to SubsMatch,
another state of the art by Kubler and colleagures in 2017
This method also employs subsequence frequencies for classification.
From this plot we can see the accuracy of MinHash and SubsMatch
MinHash in green is in the 80% accuracy range
with the best performance at 88% accuracy
and that's using 256 hash functions, or 512 hash functions
And this is comparable to the performance of SubsMatch, here in red,
which reaches about 90% accuracy
But what stands for MinHash is the time it takes to accurately classify the different tasks
As you can see here on the x-axis, MinHash is much quicker than SubsMatch,
at classifying.
SubsMatch clocks in at around 29 seconds to classify all the tasks
Whereas MinHash with 64 hash functions takes about 5 seconds.
But if we want that good accuracy, that 88% accuracy,
It'll take us about 15 seconds.
Additionally, MinHash has a constant runtime for long scanpaths.
Which is not the case for SubsMatch
And definitely not the case for sequence alignment algorithms such as Needleman-Wunsch.
Thus we can conclude that we have fast subsequence similarity-extraction and classification
because the number of hash functions affect the runtime.
And this is applicable for long and complex scanpaths.
And it's also highly generalizable since it uses data-mining techiques.
Thank you for your attention! :-)