mO Heng[#1] mO Mohit[#1] mO Manling[#1] mO Zoey[#1] mO Yu[#1] mO Xudong[#1] mO
Zhenhailong[#1]

# Non-Sequential Graph Script Induction via Multimedia Grounding

Yu Zhou1, Sha Li2, Manling Li2, Xudong Lin3, Shih-Fu Chang3, Mohit Bansal4,
Heng Ji2
1 University of California, Los Angeles 2 University of Illinois Urbana-
Champaign
3 Columbia University 4 University of North Carolina at Chapel Hill
<EMAIL_ADDRESS>{shal2, manling2<EMAIL_ADDRESS>
<EMAIL_ADDRESS>{xudong.lin<EMAIL_ADDRESS>
###### Abstract

Online resources such as wikiHow compile a wide range of scripts for
performing everyday tasks, which can assist models in learning to reason about
procedures. 111Our data and code are publicly available for research purposes
at https://github.com/bryanzhou008/Multimodal-Graph-Script-Learning/ However,
the scripts are always presented in a linear manner, which does not reflect
the flexibility displayed by people executing tasks in real life. For example,
in the CrossTask Dataset, 64.5% of consecutive step pairs are also observed in
the reverse order, suggesting their ordering is not fixed. In addition, each
step has an average of 2.56 frequent222Occurred in more than 10 videos. next
steps, demonstrating "branching". In this paper, we propose a new challenging
task of non-sequential graph script induction, aiming to capture optional and
interchangeable steps in procedural planning. To automate the induction of
such graph scripts for given tasks, we propose to take advantage of loosely
aligned videos of people performing the tasks. In particular, we design a
multimodal framework to ground procedural videos to wikiHow textual steps and
thus transform each video into an observed step path on the latent ground
truth graph script. This key transformation enables us to train a script
knowledge model capable of both generating explicit graph scripts for learnt
tasks and predicting future steps given a partial step sequence. Our best
model outperforms the strongest pure text/vision baselines by 17.52% absolute
gains on F1@3 for next step prediction and 13.8% absolute gains on Acc@1 for
partial sequence completion. Human evaluation shows our model outperforming
the wikiHow linear baseline by 48.76% absolute gains in capturing sequential
and non-sequential step relations.

##  1 Introduction

A script consists of typical actions that are performed to complete a given
task. Online resources such as wikiHow333www.wikiHow.com provide a wide
variety of community-edited scripts for everyday tasks (Fig.1). Such a large
library of linear scripts can serve as a starting point for learning goal-step
knowledge Zhang et al. (2020); Yang et al. (2021b). However, as the saying
goes, “all roads lead to Rome”. There is usually more than one way to achieve
any given goal. Practically speaking, users should be presented with multiple
alternative step sequences so that they can pick the most suitable route
according to their unique situations and preferences. Robots and virtual
assistants also stand to gain the crucial abilities of global planning
optimization and on-the-spot improvisation from alternative step paths.

Figure 1: Example of wikiHow linear script of the procedural task make egg
fried rice compared to an ideal example of our non-sequential graph script
consisting of  optional and  interchangeable steps.

In particular, we observe that two types of steps are overlooked by linear
scripts: optional steps and interchangeable steps. Optional steps such as Add
some chili peppers can be skipped based on the users’ preference or item
availability. Interchangeable steps such as Pre-cook some eggs and Cut some
green onions can be performed in either order without affecting the overall
task completion. After accounting for these two step types, the original
linear script is converted into a ‘non-sequential graph script’, as shown in
Fig.1 (right).

Previous efforts like Proscript Sakaguchi et al. (2021) obtained non-linear
graph scripts via crowdsourcing, which is not scalable. In this work, we
automate the process of transforming a linear text script into a non-linear
graph script by grounding into visual observations (videos) of people
executing the task. If we observe that people often skip a certain step, then
it is natural to denote that step as optional. Similarly, if people tend to
swap the ordering of a group of steps, these steps are likely interchangeable.
Since wikiHow does not contain such emperical observations, we align wikiHow
scripts with procedural video datasets such as Crosstask Zhukov et al. (2019)
and Howto100M Miech et al. (2019) (see Fig.2).

To map a video to a sequence of wikiHow steps, we perform alignment on both
task-level and step-level. On the task level, we use a title matching
algorithm based on Sentence-BERT similarity to select videos and wikiHow
documents for the task. Then, we propose an effective pre-possessing strategy
(simplification + deduplication) to create the wikiHow step libarary. At the
step level, we consider two situations based on whether the video has been
segmented into steps. When manual segmentation is provided, we directly map
video annotations to the wikiHow step library. Otherwise, we first segment the
video into clips based on ASR sentence groups (Fig.2), and then map them to
wikiHow steps using a fault tolerant grounding strategy (§3.1) that is robust
to inaccurate ASR sentence boundaries. When grounding is complete, we obtain
the set of observed step sequences for each task.

Next, to obtain the desired graph script from the observed step sequences, we
use auto-regressive seq2seq models Sutskever et al. (2014) to learn the
distribution of valid paths (step sequences) along the graph (§3.2). As
opposed to directly training a graph generation model, our path generation
learning format is better aligned with existing procedural video data and also
takes advantage of pretrained seq2seq models to improve generalization across
tasks. Since the cross-entropy loss used for training auto-regressive models
focuses on penalizing local “one-step” errors (the errors in predicting each
single step), we further introduce a Path-level Constraint Loss to reduce
global inconsistencies of the entire path. To generate hard negative
contrastive-paths that fail to complete the task, we manipulate the video-
grounded positive paths through global reordering, shuffling, and re-sampling
(§3.2).

After training, our model is able to produce complete paths given input step
libraries from various domains, including but not limited to: cooking, car
maintenance, and handcrafting, etc. To automatically generate explicit graph
scripts, we implement step-level constraint beam-decoding to sample multiple
generated step sequences and record a step-adjacency matrix for constructing
the final graph script.

For downstream evaluation, we adapt the existing CrossTask dataset Zhukov et
al. (2019) to set up two new evaluation sub-tasks: Next Step Prediction and
Partial Sequence Completion. Compared against top-performing test/video only
baselines, our best model achieves 17.52% absolute gains in overall F1@3 for
next step prediction and 13.8% absolute gains on Accuracy@1 for partial
sequence completion. Moreover, we use MTurk to perform Human Evaluation on the
correctness and expressiveness of our auto-generated graph scripts. Results
show our model can correctly capture optional, interchangeable and sequential
step relationships with up to 82.69% overall accuracy.

Figure 2: Example of grounding procedural videos of the Making BLT Sandwich
task to wikiHow steps. We create a wikiHow step library through task-level
matching and step pre-processing, and then ground video step annotations/asr-
narrations to textual steps from the wikiHow step library.

Key contributions of this paper include:

  * •

We introduce an automatic method for converting sequential text scripts into
non-sequential graph scripts by aligning / grounding textual scripts to video
datasets.

  * •

We propose a path generation model capable of learning from video-grounded
step sequences with Path-Level Constraint Loss.

  * •

Experiments show our non-sequential path generation model to be more effective
than existing text/vision baselines in next step prediction and partial
sequence completion.

  * •

Human evaluation of generated graph scripts demonstrates our non-sequential
graph scripts to be more accurate and expressive in capturing step-
relationships.

##  2 Task Formulation

In this paper, we propose a new challenge of graph script induction for
procedural tasks: Given a procedural task $\mathcal{T}$ represented by a task
name, our goal is to induce a graph script for the task using the steps in the
linear script. In particular, the graph script should capture the following
relations between steps: (1) sequential $\langle s_{i}\rightarrow
s_{j}\rangle$ where two steps should be completed sequentially; (2)
interchangeable $\langle s_{i}\leftrightarrow s_{j}\rangle$ where two steps
can be completed in either order or at the same time; (3) optional $\langle
s_{i}\rightarrow s_{k},s_{i}\rightarrow s_{j}\rightarrow s_{k}\rangle$ where a
step can be optionally added between other steps.

To achieve this goal, we assume that we have access to a large repository of
textual scripts (wikiHow) and a set of videos that record people carrying out
the tasks.444Or a large repository of videos from which we can find matching
videos using retrieval. The videos might have step-level annotations or
accompanying narration which we can convert into text using ASR tools.

##  3 Methodology

To learn a graph script induction model, we first ground the video dataset to
textual steps on both task-level and step-level (Fig. 2). After grounding,
each video can be seen as a valid step sequence sampled from the ground truth
graph script. Then, we use such grounded step sequences to train our graph
script model and enhance model learning by introducing a Path-Level Constraint
Loss over carefully designed contrastive step sequences.

###  3.1 Video to Script Grounding

For each video, we first perform task-level alignment to find the top-$m$ most
relevant wikiHow documents and then step-level alignment to ground the video
to specific wikiHow steps. We consider the following two cases based on
whether the video dataset includes step-level annotation:

#### Labelled Video Datasets:

Labelled video datasets like Crosstask Zhukov et al. (2019) contain procedural
videos grouped by human-annotated task names. In addition, the videos are
labelled with temporal step segmentation and relatively accurate step
annotations in the form of short imperative English sentences. The example
video in Fig.2 for task: "Make BLT Sandwich" is annotated with steps: "cook
the bacon in a pan", "put mayo on bread", etc.

At the task level, we first use keyword matching to quickly find all relevant
wikiHow documents whose title contains $\geq$ 85% of keywords in the task
name. For example in Fig. 2, the task name: "Make BLT Sandwich" is matched to
wikiHow documents: "Make a BLT Sandwich1", "Make a Breakfast Sandwich", etc.
After we retrieve a list of relevant wikiHow documents, they are further
ranked by cosine similarity between Sentence-BERT embeddings of document title
and the task name. Finally, the steps of the top $m$ wikiHow documents are
selected to form the initial wikiHow step candidate pool.

In step-level grounding, we first record Sentence-BERT Similarity scores
between each video step annotation and all processed steps in the wikiHow step
library. Then, we do greedy matching between video step annotations and
wikiHow steps with priority given to higher scoring pairs. Here we keep video
steps with best score $\geq k_{1}$555Hyperparameters in the grounding section
are empirically selected based on qualitative evaluation over a small subset.,
while lower scoring video steps are considered ungroundable. When all videos
have been grounded, unused steps from the wikiHow step library are removed.

#### Unlabelled Video Datasets:

Although we achieve high grounding quality for annotated video datasets, step-
level annotation is quite costly and often not available for a wide range of
tasks that we are interested in. A more practical scenario is when we have a
large repository of videos like Howto100M from which we can retrieve videos
corresponding to the target task. Task-level alignment for Howto100M is
different from that of annotated video datasets due to questionable video
grouping. In Howto100M, videos for each task are selected purely based on
Youtube search ranking. This ranking often prioritizes popular videos that
have low correlation to the task at hand. To ensure high video-task
correlation, we re-select Howto100M videos for each task based on BERT-
Similarity between video title and the task name (only videos with similarity
score $\geq k_{2}$ are selected).

Step-level alignment also becomes much more challenging as we must rely on
video ASR transcriptions without human step-level annotations. ASR narrations
usually comprise of short partial sentence pieces without strict temporal step
boundary labels (Fig.2). In addition, since Howto100M videos are collected
from Youtube, some ASR narrations contain task-irrelevant information such as
subscription requests (Fig.2). To address these challenges, we use a more
fault tolerant grounding strategy shown in Fig.2: First, we remove all
sentence pieces containing Youtube stop words including “subscribe”,
“channel”, “sponsor”, etc. Then, we expand each ASR sentence piece by
concatenating it with surrounding pieces until the length of the resulting
piece exceeds 10 words666This parameter is borrowed from Lin et al. (2022)
which uses the same length threshold. Finally, we ground each resulting ASR
step to wikiHow steps with a higher match threshold $k_{3}$.

Figure 3:  Example input/output sequence in model training. We create the
input sequence by shuffling and concatenating the wikiHow step library. We use
the concatenated grounded sequence as the target output (positive example) and
its permuted/resampled versions as the contrastive output (negative example).

#### Processing the wikiHow Step Library:

High quality step-level alignment demands the wikiHow Step Library used for
grounding to contain clean, non-overlapping steps that are homogeneous in
format and granularity to the video step annotations. Since the vanilla
wikiHow dataset Koupaee and Wang (2018) does not meet these criteria, we
perform a series of pre-processing before step-level alignment:

  1. 1.

First, we put the steps in the initial wikiHow step library through a series
of regex-based parsing to standardise stylistic elements like capitalization,
punctuation and bracket/parentheses usage.

  2. 2.

Then, we use a seq2seq text simplification model Maddela et al. (2021) to
reduce granularity in wikiHow steps which are often more fine-grained than
video step annotations.

  3. 3.

Finally, we deduplicate the wikiHow Step Library by enforcing a minimum
weighted Levenshtein distance of 0.1 between any two steps and removing overly
similar duplicate steps.

###  3.2 Model Training

#### Graph Script Learning

Inspired by Bojchevski et al. (2018), we transform the graph script learning
problem into a path learning problem by treating steps as nodes and temporal
relationships between the steps as directed edges (edges point to future
step). For each procedural task $\mathcal{T}$, the wikiHow step library of
task-relevant steps $\mathcal{W_{\mathcal{T}}}$ generated in §3.1 represents
the set of nodes used to construct the latent ground-truth graph script. In
§3.1, we grounded each procedural video to a wikiHow step sequence. These step
sequences can be regarded as observed step node paths that lead to successful
completion of $\mathcal{T}$. In this formulation, learning the latent graph
script for a task can be regarded as learning the weights of valid paths
through $\mathcal{W_{\mathcal{T}}}$.

For our basic architecture, we train a BART-base model Lewis et al. (2019) to
generate complete step sequences given a wikiHow step library. As illustrated
in Fig.3, for each task $\mathcal{T}$, we first shuffle the corresponding
wikiHow step library to remove any pre-existing step ordering. Then, we
concatenate the shuffled step library with a special separator token777We
define the separator token as ¡-¿. appended to the end of every step to
indicate step boundary. The resulting sequence is used as the input sequence
for all training data regarding $\mathcal{T}$. For each target output, we
first collect all grounded step sequences of videos completing $\mathcal{T}$.
Similar to input sequences, steps in the output are also appended with the
same separator token and concatenated. Finally, each processed video-grounded
step sequence is used individually as a target output sequence for our model.

#### Path-Level Constraint

Besides being able to generate valid step sequences that lead to successful
task completion, we also enable our model to differentiate valid step
sequences from invalid ones that fail to complete the task. We accomplish this
by introducing a Path-Level Constraint in the form of a contrastive loss. For
each positive step sequence, we generate $n$ negative contrastive sequences
using the following 3 methods (Fig.3):

  1. 1.

Re-sample: randomly re-sample a step sequence of the same length from the
wikiHow step library. Both step selection and step ordering are wrong.

  2. 2.

Shuffle: shuffle the sequence until no longer valid. Step selection is
preserved, but local/global step ordering are wrong.

  3. 3.

Cut & Swap: cut the sequence at a random position and swap the latter part to
the front. Step selection and local step ordering are preserved, but global
step ordering is wrong.

To maximize the model’s learning potential, we follow the paradigm of
curriculum learning Bengio et al. (2009) when introducing contrastive
examples: we start with contrastive sequences generated via Re-sample because
they are most dissimilar from valid sequences. As training progresses, we
shift toward Shuffled and Cut & Swap by gradually increasing the probability
of sampling from those contrastive sequence groups.

Figure 4: Example of Graph Script Generation. To decode a graph from our
generator, we first ask the model to generate alternative step sequences via
beam-decoding and record them in an step-adjacency matrix, which is then be
used to reconstruct the non-sequential graph script (with low-frequency edges
removed).

Inspired by Saha et al. (2022) , we use the last layer of the decoder in BART
as the representation of each token in the sequence and obtain the sequence
representation by averaging over the constituent token representations. Let
the hidden representations of our generated sequence $\mathbf{s}^{(g)}$, true
grounded sequence $\mathbf{s}^{(p)}$ and negative contrastive sequence
$\mathbf{s}^{(n)}$ be denoted by $\mathbf{z}^{(g)}$, $\mathbf{z}^{(p)}$ and
$\mathbf{z}^{(n)}$, respectively. Let
$\mathcal{Z}=\left\\{\mathbf{z}^{(p)}\right\\}\bigcup\left\\{\mathbf{z}_{i}^{(n)}\right\\}_{i=1}^{M}$,
with $M$ as the number of negative contrastive sequences. Hence, we define our
Path-level Contrastive Loss: 888Based on the InfoNCE Contrastive Lossvan den
Oord et al. (2018):

$\leavevmode\resizebox{418.55473pt}{}{$\mathcal{L}_{PC}=-\log\frac{\exp\left[\operatorname{sim}\left(\mathbf{z}^{\mathbf{(g)}},\mathbf{z}^{(p)}\right)/\tau\right]}{\sum_{\mathbf{z}^{(i)}\in\mathcal{Z}}\exp\left[\operatorname{sim}\left(\mathbf{z}^{\mathbf{(g)}},\mathbf{z}^{(i)}\right)/\tau\right]}$},$
(1)

where the temperature $\tau$ is a hyperparameter and $\operatorname{sim}$
denotes cosine similarity. Finally, our overall loss combines the Path-level
Contrastive Loss with the Cross-Entropy Loss of seq2seq models:

$\mathcal{L}_{CE}=\sum_{i}-\log
P\left(\mathbf{s}_{i}^{(p)}\mid\mathbf{s}_{<i}^{(p)},\mathcal{W_{\mathcal{T}}}\right),$
(2)

$\mathcal{L}_{\text{total}}=\mathcal{L}_{\text{CE}}+\alpha\mathcal{L}_{\text{PC}},$
(3)

where $\alpha$ is a hyperparameter and $\mathcal{W_{\mathcal{T}}}$ denotes the
task-specific wikiHow step library.

###  3.3 Graph Script Generation

In §3.2, we transformed the graph script learning problem into a path learning
problem by treating procedural step relationships as edges between nodes and
abstracting the latent ground truth graph as the collection of paths through
node-set $\mathcal{W_{\mathcal{T}}}$ that lead to successful task completion.
After our model has learnt the latent ground truth graph scripts for a set of
tasks, we use it to reconstruct explicit graph scripts through the following
procedure:

For each task $\mathcal{T}$, we use $\mathcal{W_{\mathcal{T}}}$ as model input
and have the model generate output step sequences consisting only of steps
within $\mathcal{W_{\mathcal{T}}}$. We enforce this by implementing Step-
constrained Beam Search, an extension of Constrained Beam Search De Cao et al.
(2021), where the model is only allowed to generate valid next words that lead
to entities stemming from a fixed prefix trie $\mathcal{P}$. Here, we
construct $\mathcal{P_{\mathcal{T}}}$ containing all steps in
$\mathcal{W_{\mathcal{T}}}$ and ask the model to repeatedly decode from
$\mathcal{P_{\mathcal{T}}}$ to generate step sequences. After each step is
fully generated, the model is given the choice to end generation by producing
the end-of-sentence (eos) token or continue decoding the next step by
producing a token from the root of $\mathcal{P_{\mathcal{T}}}$. After
generating the predicted step sequences, we break them down and record the
edges in an graph adjacency matrix between all generated step nodes. The low-
frequency edges representing unlikely paths are removed to improve graph
script confidence. Finally, we reconstruct the output graph script from the
graph adjacency matrix. An example of this process on the task "Make Lemonade"
is detailed in Fig.4.

Model | HT100M | Next Step Prediction | Partial Sequence Completion
---|---|---|---
Acc@1 | Acc@3 | Rec@3 | F1@3 | Acc@1 | Edit | Normalized
$\uparrow$ | $\uparrow$ | $\uparrow$ | $\uparrow$ | $\uparrow$ | Dist. $\downarrow$ | Edit Dist. $\downarrow$
TimeSformer+DS | ✗ | 59.91 | 60.82 | 52.98 | 43.83 | - | - | -
Random | ✗ | 31.34 | 50.32 | 28.84 | 38.04 | 1.20 | 2.398 | .6935
wikiHow Linear | ✗ | 44.05 | 59.51 | 54.02 | 42.14 | 11.74 | 1.872 | .6061
ReBART | ✗ | 49.07 | 58.00 | 61.39 | 44.38 | 18.28 | 1.802 | .4411
Direct NSP (Grounding) | ✗ | 68.89 | 63.02 | 79.01 | 53.85 | - | - | -
Direct PSC (Grounding) | ✗ | - | - | - | - | 29.17 | 1.214 | .4118
Ours (Grounding) | ✗ | 75.59 | 67.50 | 83.17 | 58.29 | 20.12 | 1.639 | .4296
Ours (Grounding) | ✓ | 70.97 | 74.68 | 74.14 | 61.52 | 29.34 | 1.193 | .4093
Ours (Grounding + PLC) | ✗ | 75.49 | 71.89 | 72.51 | 58.48 | 26.70 | 1.228 | .4267
Ours (Grounding + PLC) | ✓ | 76.09 | 73.72 | 78.22 | 61.90 | 32.08 | 1.123 | .3849
|  |  |  |  |  |  |  |
Table 1:  Automatic Evaluation Results on Next Step Prediction and Partial
Sequence Completion. Here “HT100M” denotes whether the model is pre-trained on
the Howto100M dataset with temporal order information. “Normalized Edit Dist.”
represents the average Levenstein distance normalized by sequence length.
“Grounding” denotes whether the model used our grounded video sequences for
training. “PLC” represents Path-Level Constraint.

##  4 Experiments

To evaluate our non-sequential graph script induction model, we propose 3 new
downstream tasks:

  1. 1.

Graph Script Generation: for each task $\mathcal{T}$, the system is asked to
produce a 2-dimensional probabilistic graph script similar to Fig.1 that
captures the step relationships introduced in section 1). The model is scored
based on human evaluation of its generated graph scripts.

  2. 2.

Next Step Prediction: given a partial step sequence
$S_{p}=(s_{1}\rightarrow...\rightarrow s_{t-1})$, the model is asked to
predict the top-k most likely choices for the next step $s_{t}$ from
$\mathcal{W}_{\mathcal{T}}$. For each partial step sequence, there can be a
variable number of correct next steps.

  3. 3.

Partial Sequence Completion: given a partial step sequence
$S_{p}=(s_{1}\rightarrow...\rightarrow s_{t-1})$, the model is asked to
produce a sequence $S=(s_{1}\rightarrow...\rightarrow s_{n})$ using steps from
$\mathcal{W}_{\mathcal{T}}$ that completes the task $\mathcal{T}$. This task
is particularly challenging because the model is asked to predict a variable-
length step sequence that best completes the task at hand.

###  4.1 Baselines

Baseline: TimeSformer+DS. TimeSformer Bertasius et al. (2021) trained with
unsupervised distant supervision Lin et al. (2022) provides the state-of-the-
art step-level video representation for pure-video-based step forecasting. We
fine-tuned the model on CrossTask videos before testing.

Baseline: wikiHow Linear. This model is trained on all wikiHow linear step
sequences selected during title-matching (§3.1). To ensure fairness in
comparison, the training sequences undergo the same step processing as that of
the non-sequential model. For each training sequence, the model takes the
complete wikiHow step library as input and one linear sequence from the
selected wikiHow documents as target output.

Baseline: ReBART. ReBART Chowdhury et al. (2021) is the state-of-the-art
sentence re-ordering method that uses a text-to-marker generation format.
Numbered markers are inserted before each step in the training data, and the
target output step sequence is translated into corresponding marker sequences.

Ablation Study: Direct Next Step Prediction & Direct Partial Sequence
Completion. These two task-specific models are included as variants of our
model (§3.2) where the input training sequence is a partial start sequence and
the target output sequence is just the next step (for next step prediction) or
the remaining sequence (for partial sequence completion). The training data
for these two models are also constructed from our grounded video step
sequences (§3.1).

###  4.2 Automatic Evaluation

#### Evaluation Dataset

Inspired by Chen et al. (2022), we build our evaluation dataset on top of the
existing CrossTask Dataset Zhukov et al. (2019) and reuse their manual
temporal step annotations. Using procedures in §3.1, we ground annotated
CrossTask videos (Fig.2) to sentence-simplified wikiHow Steps. Afterwards, we
randomly select 40% of grounded step sequences to form the training set.
Remaining sequences form the test set.

For each grounded step sequence $S=(s_{1}\rightarrow...\rightarrow s_{n})$ in
the test set, we split after all steps $(s_{t}|t\in[1,n-1])$ to produce
partial start sequences $S_{p}=(s_{1}\rightarrow...\rightarrow s_{t})$. For
next step prediction, the correct output corresponding to $S_{p}$ is the next
step $s_{t+1}$; while for partial sequence completion, the correct output
corresponding to $S_{p}$ is the remaining sequence
$(s_{t+1}\rightarrow...\rightarrow s_{n})$. In the case where multiple
grounded step sequences share the same partial start sequence $S_{p}$ but have
different next step / remaining steps, the input sequence $S_{p}$ would have
multiple correct answers for next step prediction / partial sequence
completion.

#### Next Step Prediction

As shown in Table 1, our models trained using video-to-text grounded step
sequences outperform other baselines trained with wikiHow linear step
sequences by 15% $\sim$ 20% absolute gains in all next step prediction
metrics. This shows the advantage of our video-grounded step sequences over
wikiHow linear sequences in improving the model’s ability to predict next
steps. Comparing our models trained on complete step sequences against models
trained directly on next step prediction without whole script knowledge, we
see a large performance gap. This shows the importance of learning whole-
script knowledge for next step prediction. When predicting top-3 most likely
next steps, models pretrained on Howto100M significantly outperform models w/o
pretraining. This can be attributed to the pretrained models having better
knowledge of sequence "branching" from observing more diverse task executions.

#### Partial Sequence Completion

Our best performing models trained using video-to-text grounded step sequences
typically achieves over 13% absolute gains on Accuracy@1 and over 14% relative
gains on normalized edit distance against other baselines trained using
wikiHow linear step sequences, showing grounded videos step sequences can
boost models’ ability in partial sequence completion. When comparing models
trained with the Path-Level Constraint (Sec.3.2) to otherwise identical models
trained without such constraint, we see significant gains across all metrics.
This demonstrates the effectiveness of our Path-Level Constraint in teaching
the model to produce valid step sequences while avoiding their invalid
counterparts. We also observe a performance gain for models pretrained on
Howto100M vs the same models w/o such pretraining. This result combined with
similar results in next step prediction shows that pretraining on a large
unlabelled procedural video dataset can improve the model’s ability to learn
scripts for other tasks.

Relation Type | Linear | Ours
---|---|---
#/task | Acc | #/task | Acc
Sequential | 10.56 | 35.79 | 12.50 | 88.02
Optional | 1.40 | 19.23 | 2.44 | 65.91
Interchangeable | 0.44 | 37.50 | 1.44 | 88.46
Overall | 12.40 | 33.93 | 16.38 | 82.69
|  |  |  |
Table 2: Human Evaluation results by step-relation type. Task Category | Linear | Ours
---|---|---
#/task | Acc | #/task | Acc
Cooking | 12.1 | 35.16 | 16.2 | 81.07
Household | 12.5 | 28.33 | 16.0 | 75.00
Car Maintenance | 15.0 | 36.67 | 17.5 | 88.89
|  |  |  |
Table 3: Human Evaluation results by task category. #/task denotes average
number of relations per task.

###  4.3 Human Evaluation

Using the graph construction method in §3.3, we generate two graph scripts for
each procedural task in CrossTask using the wikiHow Linear baseline (§4.1) and
our non-sequential graph script induction model. To evaluate the correctness
and expressiveness of generated graph scripts, we design T/F questions
regarding sequential, optional, and interchangeable relations. For optional
and interchangeable step relationships indicated by the graph script, we ask
annotators whether the relationship is appropriate. For other steps in the
connected graph script, we ask annotators whether their previous and
subsequent steps are sequentially appropriate.

Table 2 and table 3 show our model achieves 46.68% $\sim$ 52.23% absolute
gains in Accuracy across all relation types and task categories. In addition,
our model is able to accurately capture 74% more optional steps and 227% more
interchangeable step pairs in generated graph scripts.

##  5 Related Work

#### Text-based Script Induction

Temporal relations have always been the core of script (schema) related tasks,
which can either be learned from data or human annotation. When human-written
scripts are available, previous works have typically assumed that the human-
provided ordering of steps is the only correct order Jung et al. (2010);
Ostermann et al. (2017); Nguyen et al. (2017); Lyu et al. (2021); Sakaguchi et
al. (2021). Another line of work has attempted to learn event ordering from
data alone, either by assuming that the events follow narrative order Chambers
and Jurafsky (2008, 2009); Jans et al. (2012); Rudinger et al. (2015); Ahrendt
and Demberg (2016); Wang et al. (2017) or by using an event-event temporal
relation classifier to predict the true ordering of events Li et al. (2020,
2021). Our work is distinct from both paradigms as we use human-written
scripts as a basis and learn the event ordering from observed sequences in
videos.

#### Video-based Script Induction

Existing efforts that utilize visual information in script induction can be
mainly classified into implicit script knowledge models and explicit
sequential script induction models. Some previous efforts have focused on
training models with implicit script knowledge that can make step-level
predictions based on textual Yang et al. (2021c), visual Sener and Yao (2018);
Lin et al. (2022); Zhou et al. (2023), or multimedia Zellers et al. (2021)
input. Other models aim to produce explicit sequential graph scripts that only
capture procedural relations between steps Salvador et al. (2018); Yang et al.
(2021a). Another line of works use multimedia information to generate explicit
graph scripts that model only pre-conditional/dependency relationships between
events Logeswaran et al. (2023) and sub-events Jang et al. (2023). Ours is the
first work to generate explicit non-sequential graph scripts that capture rich
procedural, optional, and interchangeable relations through multimedia
learning.

##  6 Conclusions and Future Work

We propose the new task of Non-sequential Graph Script Induction to capture
optional and interchangeable steps in procedural tasks. Instead of relying on
the script annotation, we automatically induce graph scripts by grounding
procedural videos to a wikiHow textual step library. We transform the graph
generation problem to a path generation problem that can better aligned with
video observations, and train a seq2seq model using our grounded step
sequences while imposing path-level constraints via a contrastive loss.
Experiments demonstrate our model’s superiority on downstream tasks including
next step prediction and partial sequence completion. Human evaluation
confirms our model’s ability to generate graph scripts that correctly capture
optional and interchangeable steps. Future work will focus on incorporating
more video supervision signals such as enriching steps from videos and adding
the repeatable steps.

##  7 Limitations

###  7.1 Representation of Repeatable Steps

Our current approach is not able to capture repeatable steps due to data
source constraints from our video datasets. The video datasets we use in this
work, namely Howto100M and CrossTask, are both constructed from Youtube
videos. At the end of many Youtube instructional videos, there is a brief
recap of the whole task, where many steps are displayed for a second time.
Since CrossTask was originally proposed for step segmentation, the step
annotations capture all video references to task-related steps, including the
brief mentions at the end of the videos that are not actually part of task
execution. Similarly, Howto100M videos ASR pieces near the end of the video
would also capture the vioceover going through such step references.

Therefore, to ensure the grounded video step sequence only contains steps
included in the execution of the task, we simply removed all repeated steps in
the grounded step sequence and only kept the first occurrence. However in this
process, we also removed valid repeats of the same step. For example, if the
step Add some salt was executed twice at different stages of the task. We
leave this area of improvement for future works.

###  7.2 Enrichment of Steps from Video

In our current model, all the steps in the wikiHow step library are processed
steps from related wikiHow documents. However, it has been shown that textual
sources can be prone to reporting bias, occasionally ignore task-relevant
information that is present only in the vision modality Chen et al. (2021).

Continuous frames from video data can capture details that text descriptions
do not explicitly mention. If the model is able to make use of such vision-
exclusive details and learn patterns from them, its overall ability can be
improved. The challenge in utilizing such underlying visual information is to
differentiate task-relevant video steps from their task-irrelevant
counterparts. This area has not been covered by our current graph script
induction pipeline, we hope to provide comprehensive solutions in future work.

##  8 Ethics and Broader Impact

###  8.1 Datasets

In this work, we used publicly available text data from the wikiHow Dataset
(https://github.com/mahnazkoupaee/wikiHow-Dataset) Creative Commons License
(CC-BY-NC-SA), which is under the Attribution-Noncommercial-Share Alike 3.0
Creative Commons License which allows us to use the dataset for non-commercial
purposes. For video data, we used the publicly available CrossTask Dataset
(https://github.com/DmZhukov/CrossTask) under the BSD 3-Clause "New" or
"Revised" License and the Howto100M Dataset
(https://www.di.ens.fr/willow/research/howto100m/) under the Apache License
2.0. Both licenses allows us to use the datasets for non-commercial purposes.

The datasets we use consist of non-offensive instructional and procedural
videos / text scripts about everyday tasks. Our usage of the datasets only
concerns the task related information and does not violate privacy.

###  8.2 Human Evaluation

As detailed in §4.3, we conduct human evaluation for our generated graph
scripts in this paper via Amazon Mechanical Turk(https://www.mturk.com/). All
annotators involved in the human evaluation are voluntary participants and
receive a fair wage. All annotators were instructed of the task nature and
consent to complete the annotation via a online consent form. We have applied
for IRB exemption and the request was approved.

###  8.3 Model Usage

Our graph script induction framework is not intended to be used for any
activity related to any human subjects. Instead, it should only be used for
generating graph scripts regarding everyday tasks that benefit people’s
learning and understanding. It may also be used for predicting/instructing
future step/steps to facilitate completion of relevant tasks. Note that our
graph script induction framework is intended for wikiHow visual tasks and
might not be applicable for other scenarios.

## Acknowledgement

We thank the anonymous reviewers for their helpful suggestions. This research
is based upon work supported by U.S. DARPA KAIROS Program No.
FA8750-19-2-1004. The views and conclusions contained herein are those of the
authors and should not be interpreted as necessarily representing the official
policies, either expressed or implied, of DARPA, or the U.S. Government. The
U.S. Government is authorized to reproduce and distribute reprints for
governmental purposes notwithstanding any copyright annotation therein.

## References

  * Ahrendt and Demberg (2016) Simon Ahrendt and Vera Demberg. 2016.  Improving event prediction by representing script participants.  In _North American Chapter of the Association for Computational Linguistics_.
  * Bengio et al. (2009) Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. 2009\.  Curriculum learning.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , ICML ’09, page 41–48, New York, NY, USA. Association for Computing Machinery.
  * Bertasius et al. (2021) Gedas Bertasius, Heng Wang, and Lorenzo Torresani. 2021.  Is space-time attention all you need for video understanding?  In _Proceedings of the International Conference on Machine Learning (ICML)_.
  * Bojchevski et al. (2018) Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. 2018.  Netgan: Generating graphs via random walks.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pages 609–618.
  * Chambers and Jurafsky (2008) Nathanael Chambers and Dan Jurafsky. 2008.  Unsupervised learning of narrative event chains.  In _Proceedings of ACL-08: HLT_ , pages 789–797, Columbus, Ohio. Association for Computational Linguistics.
  * Chambers and Jurafsky (2009) Nathanael Chambers and Dan Jurafsky. 2009.  Unsupervised learning of narrative schemas and their participants.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Chen et al. (2021) Brian Chen, Xudong Lin, Christopher Thomas, Manling Li, Shoya Yoshida, Lovish Chum, Heng Ji, and Shih-Fu Chang. 2021.  Joint multimedia event extraction from video and article.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Chen et al. (2022) Long Chen, Yulei Niu, Brian Chen, Xudong Lin, Guangxing Han, Christopher Thomas, Hammad Ayyubi, Heng Ji, and Shih-Fu Chang. 2022.  Weakly-supervised temporal article grounding.  In _Empirical Methods in Natural Language Processing (EMNLP), 2022_.
  * Chowdhury et al. (2021) Somnath Basu Roy Chowdhury, Faeze Brahman, and Snigdha Chaturvedi. 2021.  Reformulating sentence ordering as conditional text generation.  _CoRR_ , abs/2104.07064.
  * De Cao et al. (2021) Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. 2021.  Autoregressive entity retrieval.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.
  * Jang et al. (2023) Y. Jang, Sungryull Sohn, Lajanugen Logeswaran, Tiange Luo, Moontae Lee, and Ho Hin Lee. 2023.  Multimodal subtask graph generation from instructional videos.  _ArXiv_ , abs/2302.08672.
  * Jans et al. (2012) Bram Jans, Steven Bethard, Ivan Vulic, and Marie-Francine Moens. 2012.  Skip n-grams and ranking functions for predicting script events.  In _Conference of the European Chapter of the Association for Computational Linguistics_.
  * Jung et al. (2010) Yuchul Jung, Jihee Ryu, Kyung min Kim, and Sung-Hyon Myaeng. 2010.  Automatic construction of a large-scale situation ontology by mining how-to instructions from the web.  _J. Web Semant._ , 8:110–124.
  * Koupaee and Wang (2018) Mahnaz Koupaee and William Yang Wang. 2018.  Wikihow: A large scale text summarization dataset.  _CoRR_ , abs/1810.09305.
  * Lewis et al. (2019) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2019.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Li et al. (2021) Manling Li, Sha Li, Zhenhailong Wang, Lifu Huang, Kyunghyun Cho, Heng Ji, Jiawei Han, and Clare R. Voss. 2021.  The future is not one-dimensional: Complex event schema induction by graph modeling for event prediction.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Li et al. (2020) Manling Li, Qi Zeng, Ying Lin, Kyunghyun Cho, Heng Ji, Jonathan May, Nathanael Chambers, and Clare R. Voss. 2020.  Connecting the dots: Event graph schema induction with path language modeling.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Lin et al. (2022) Xudong Lin, Fabio Petroni, Gedas Bertasius, Marcus Rohrbach, Shih-Fu Chang, and Lorenzo Torresani. 2022.  Learning to recognize procedural activities with distant supervision.  _arXiv preprint arXiv:2201.10990_.
  * Logeswaran et al. (2023) Lajanugen Logeswaran, Sungryull Sohn, Y. Jang, Moontae Lee, and Ho Hin Lee. 2023\.  Unsupervised task graph generation from instructional video transcripts.  _ArXiv_ , abs/2302.09173.
  * Loshchilov and Hutter (2017) Ilya Loshchilov and Frank Hutter. 2017.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_.
  * Lyu et al. (2021) Qing Lyu, Li Zhang, and Chris Callison-Burch. 2021.  Goal-oriented script construction.  _ArXiv_ , abs/2107.13189.
  * Maddela et al. (2021) Mounica Maddela, Fernando Alva-Manchego, and Wei Xu. 2021.  Controllable text simplification with explicit paraphrasing.  In _Proceedings of the North American Association for Computational Linguistics (NAACL)_.
  * Miech et al. (2019) Antoine Miech, Dimitri Zhukov, Jean-Baptiste Alayrac, Makarand Tapaswi, Ivan Laptev, and Josef Sivic. 2019.  Howto100m: Learning a text-video embedding by watching hundred million narrated video clips.  _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 2630–2640.
  * Nguyen et al. (2017) Dai Quoc Nguyen, Dat Quoc Nguyen, Cuong Xuan Chu, Stefan Thater, and Manfred Pinkal. 2017.  Sequence to sequence learning for event prediction.  In _IJCNLP_.
  * Ostermann et al. (2017) Simon Ostermann, Michael Roth, Stefan Thater, and Manfred Pinkal. 2017.  Aligning script events with narrative texts.  _ArXiv_ , abs/1710.05709.
  * Rudinger et al. (2015) Rachel Rudinger, Pushpendre Rastogi, Francis Ferraro, and Benjamin Van Durme. 2015\.  Script induction as language modeling.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Saha et al. (2022) Swarnadeep Saha, Prateek Yadav, and Mohit Bansal. 2022.  Explanation graph generation via pre-trained language models: An empirical study with contrastive learning.  In _ACL_.
  * Sakaguchi et al. (2021) Keisuke Sakaguchi, Chandra Bhagavatula, Ronan Le Bras, Niket Tandon, Peter Clark, and Yejin Choi. 2021.  proScript: Partially ordered scripts generation.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 2138–2149, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Salvador et al. (2018) Amaia Salvador, Michal Drozdzal, Xavier Giró i Nieto, and Adriana Romero. 2018\.  Inverse cooking: Recipe generation from food images.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 10445–10454.
  * Sener and Yao (2018) Fadime Sener and Angela Yao. 2018.  Zero-shot anticipation for instructional activities.  _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 862–871.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014.  Sequence to sequence learning with neural networks.  _CoRR_ , abs/1409.3215.
  * van den Oord et al. (2018) Aäron van den Oord, Yazhe Li, and Oriol Vinyals. 2018.  Representation learning with contrastive predictive coding.  _CoRR_ , abs/1807.03748.
  * Wang et al. (2017) Zhongqing Wang, Yue Zhang, and Ching-Yun Chang. 2017.  Integrating order information and event relation for script event prediction.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _ArXiv_ , abs/1910.03771.
  * Yang et al. (2021a) Yue Yang, Joongwon Kim, Artemis Panagopoulou, Mark Yatskar, and Chris Callison-Burch. 2021a.  Induce, edit, retrieve: Language grounded multimodal schema for instructional video retrieval.  _ArXiv_ , abs/2111.09276.
  * Yang et al. (2021b) Yue Yang, Artemis Panagopoulou, Qing Lyu, Li Zhang, Mark Yatskar, and Chris Callison-Burch. 2021b.  Visual goal-step inference using wikiHow.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2167–2179, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Yang et al. (2021c) Yue Yang, Artemis Panagopoulou, QING LYU, Li Zhang, Mark Yatskar, and Chris Callison-Burch. 2021c.  Visual goal-step inference using wikihow.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Zellers et al. (2021) Rowan Zellers, Ximing Lu, Jack Hessel, Youngjae Yu, Jae Sung Park, Jize Cao, Ali Farhadi, and Yejin Choi. 2021.  Merlot: Multimodal neural script knowledge models.  In _Neural Information Processing Systems_.
  * Zhang et al. (2020) Li Zhang, Qing Lyu, and Chris Callison-Burch. 2020.  Reasoning about goals, steps, and temporal ordering with WikiHow.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 4630–4639, Online. Association for Computational Linguistics.
  * Zhou et al. (2023) Honglu Zhou, Roberto Mart’in-Mart’in, Mubbasir Kapadia, Silvio Savarese, and Juan Carlos Niebles. 2023.  Procedure-aware pretraining for instructional video understanding.  _ArXiv_ , abs/2303.18230.
  * Zhukov et al. (2019) Dimitri Zhukov, Jean-Baptiste Alayrac, Ramazan Gokberk Cinbis, David F. Fouhey, Ivan Laptev, and Josef Sivic. 2019.  Cross-task weakly supervised learning from instructional videos.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3532–3540.

##  Appendix A Appendix

###  A.1 Grounding Details

The following hyper-parameters used in the grounding section are determined
empirically. In video to text grounding, for each video, we find the top-10
most relevant wikiHow documents. For keyword matching at the task level, we
first select wikiHow documents whose title contains $\geq$ 85% of keywords in
the task name. This is to avoid calculating Sentence-BERT similarity between
the task name and all wikiHow document titles. If this does not yield $\geq$
10 documents, we relax the threshold to 75%. For title matching and step
matching, the Sentence-BERT similarity thresholds are determined empirically
by qualitative evaluation over a small subset of 150 examples. For labelled
videos, the step-level grounding similarity threshold $k_{1}$ is 0.35. For
unlabelled videos, the task-level grounding similarity threshold $k_{2}$ is
0.75 and the step-level grounding similarity threshold $k_{3}$ is 0.40.

###  A.2 Training Details

For our models and baselines, we mainly use the BART-base model (140M
Parameters) from the Huggingface Framework Wolf et al.
(2019)999https://huggingface.co/docs/transformers/index. We normalize all
input and target output sentences into lower case and remove special non-
English characters. For training, we use the AdamW optimizer Loshchilov and
Hutter (2017) with a learning rate of $2\times 10^{-5}$ and 1000 warm-up
steps. We use max input and output sequence length of 1024 for training and
testing.

For the InfoNCE contrastive loss, we set the temperature $\tau=0.1$. To
implement curriculum learning. We reset the probability of sampling from
different contrastive sequence groups every 5 epochs. At first we only use
’re-sampled’ contrastive sequence, then in every 5 epochs we transfer 20%
probability to sampling from the ’shuffled’ contrastive sequences. After 25
epochs, we starting the same shift from ’shuffled’ contrastive sequences to
’cut & swapped’ contrastive sequences.

We use NVIDIA V-100 GPUs with 16GB RAM and full precision. Due to GPU RAM
limitation, we use gradient accumulation with equivalent batch size of 32.
Training our basic model on the CrossTask training set takes approximately 5
hours while training our contrastive model with Path-Level Constraint will
take 20 hours. Pre-training our model on Howto100M grounded sequence takes
approximately 3 days.

###  A.3 Inference Details

During graph generation, for Step-constrained Beam Search, we use a beam
number of 40 to sample steps sequences for producing the graph script.
Afterwards, we filter out low-frequency edges in the adjacency graph with edge
weight $\leq 0.175$ (or in this case occurrence $\leq 7$). The remaining edges
are used to construct the final graph script.

###  A.4 Human Evaluation Details

In our human evaluation of model-generated graph scripts, three types of
questions are asked regarding corresponding types of step relationships as
displayed in the generated graph script:

  1. 1.

Optional: Do you think step (a) is optional when completing this task?

  2. 2.

Interchangeable: Do you think the steps (b) and (c) are interchangeable (can
be executed in either order) when completing this task?

  3. 3.

Sequential: Do you think the previous and/or subsequent steps for step (d) are
reasonable when completing this task?

To make questions more direct and objective for the annotators, each question
only focuses on a small portion of steps in the generated graph script. For
example, given the output graph script for the task "Make Strawberry Cake" as
shown in Fig.5, the annotator would be asked the following questions
(partial):

  1. 1.

Optional: Make Strawberry Cake: Do you think the step "cut the strawberries"
is optional when completing this task?

  2. 2.

Interchangeable: Make Strawberry Cake: Do you think the steps "add sugar to
the mixture" and "whisk the mixture" are interchangeable (can be executed in
either order) when completing this task?

  3. 3.

Sequential: Make Strawberry Cake: Do you think the previous and/or subsequent
steps for step "add flour to the mixing bowl" are reasonable when completing
this task?

We used 8 human annotators while each annotator answered (on average) 65
questions. Each question is assigned to $\geq$ 2 annotators with 72.31% inter-
annotator agreement. An example screenshot of the annotation interface is
shown in Fig.6.

Figure 5: Example outputs of our non-sequential graph script induction model
used in Human Evaluation Figure 6: A screenshot from our annotation task on
Mechanical Turk.


# Jazz Contrafact Detection

###### Abstract

In jazz, a contrafact is a new melody composed over an existing, but often
reharmonized chord progression. Because reharmonization can introduce a wide
range of variations, detecting contrafacts is a challenging task. This paper
develops a novel vector-space model to represent chord progressions, and uses
it for contrafact detection. The process applies principles from music theory
to reduce the dimensionality of chord space, determine a common key signature
representation, and compute a chordal co-occurrence matrix. The rows of the
matrix form a basis for the vector space in which chord progressions are
represented as piecewise linear functions, and harmonic similarity is
evaluated by computing the _membrane area_ , a novel distance metric. To
illustrate our method’s effectiveness, we apply it to the Impro-Visor corpus
of 2,612 chord progressions, and present examples demonstrating its ability to
account for reharmonizations and find contrafacts.

##  1 Introduction

In jazz, a contrafact is a song whose harmony is similar to that of another
song, but has a different melody [1]. The tune _Rhythm Changes_ , by George
Gershwin (1930), is a well-known source of many contrafacts [2], and there are
numerous examples of other jazz standards that also have them [3].

In addition to the difference in melody, contrafact chord progressions often
have reharmonizations, a common practice in jazz that makes chord
substitutions in a song while maintaining its harmonic identity [4].
Reharmonization is a core characteristic of jazz – so much so that it is not
unusual for different published versions of the same song to exhibit
significant variations. Furthermore, jazz musicians regularly employ
reharmonization as an improvisational technique in both live and studio-
recorded performances.

These observations suggest that the harmonic similarity challenge encountered
in contrafact detection will also play an important role in music information
retrieval tasks such as cover song identification [5]. The analysis of
harmonic similarity has been studied by others, for example, using parse trees
and hierarchical models [6, 7]. The approach taken in this paper, however, is
a novel method that accounts for reharmonizations using distributional
semantics [8]. The implementation generates a vector space embedding for
chords based on a co-occurrence matrix [9], computed from a corpus of symbolic
jazz chord progressions.

As many chords in our corpus occur only rarely, the dimensionality of chord
space must be reduced [10]. Typically this would be accomplished after
vectorization, using truncated SVD or principal component analysis [11]. In
this paper, however, we propose a new approach: we use principles of music
theory to reduce the dimensionality of chord space before vector embedding.

The ensuing sections provide a comprehensive review of the source data,
followed by an in-depth description of how we apply music theory to achieve a
reduction in the dimensionality of chord space. The characteristics of the
resulting co-occurrence matrix are discussed, and a novel distance metric, the
_membrane area_ , is used for evaluating harmonic similarity and detecting
contrafacts.

##  2 The Data

The data used in this paper is a corpus of symbolic chord progressions similar
to those found in jazz fake books, such as the Real Book [12]. The
progressions are mainly jazz standards, but also include some blues, jazz-
blues, modal jazz, and pop tunes. The corpus is derived from a collection
distributed with _Impro-Visor_ , an open-source music notation program
intended to help musicians learn improvisation [13]. Our modifications remove
control information used by the Impro-Visor application, retaining the musical
content.

The Impro-Visor corpus provides chord progressions for 2,612 songs, and is the
largest digital collection of its type that we know of. The applications
iRealPro111https://www.irealb.com/forums/showthread.php?12753-Jazz-1350-Standards
and Band-in-a-Box222https://members.learnjazzstandards.com/sp/biab-
jazzstandards/ contain chord progressions for roughly 1400 and 226 jazz
standards, respectively. The Weimer Jazz Database contains chords for 456 jazz
songs (along with transcribed solos and extensive
annotations).333https://jazzomat.hfm-weimar.de/dbformat/dbcontent.html

The Impro-Visor corpus contains 134,182 chord symbols, and it is a rich
collection, consisting of 1,542 unique types. If the frequency of chord
symbols were uniform, there would be 87 instances of each one in the corpus.
In fact, 20% of the chord symbols occur just a single time, and 50% fewer than
six times.

As the corpus consists mainly of jazz standards, it contains a preponderance
of $7^{th}$ chords, comprising of at least a root, $3^{rd}$, $5^{th}$, and
$7^{th}$ notes. These types of chords often have additional extensions
($9^{th}$, $11^{th}$, $13^{th}$) and chromatic alterations ($\flat$9,
$\sharp$9, $\flat$5, $\sharp$5). A common variation of jazz chords replaces
the $7^{th}$ with a $6^{th}$. As $7^{th}$ chords are the basic harmonic unit
in jazz [14], and make up 77% of our corpus, they are the focus of our
approach to dimensionality reduction described in the next section.

Of the remaining chords, 16% (21,860) are three-note chords (triads), and 7%
are drawn from a variety of special types. These latter include _slash_
chords, _sus_ chords, _power_ chords, _polychords_ , major triads with an
added 9th, and the _no-chord_ symbol. Every chord in our corpus belongs to one
of these categories, as listed in Table 1, along with their frequencies.

Type | Number | Percentage
---|---|---
major7 | 19448 | 14.494%
dominant7 | 46944 | 34.985%
minor7 | 30471 | 22.709%
minor7$\flat$5 | 3568 | 2.659%
diminished7 | 2807 | 2.092%
major triad | 15410 | 11.484%
major triad add9 | 170 | 0.127%
minor triad | 5796 | 4.320%
diminished triad | 128 | 0.095%
augmented triad | 526 | 0.392%
slash chord | 6415 | 4.781%
sus chord | 1830 | 1.364%
no chord | 615 | 0.458%
power chord | 42 | 0.031%
polychord | 12 | 0.009%
Totals | 134182 | 100%
Table 1: Corpus chord types and their frequencies

##  3 Dimensionality Reduction

As discussed in the previous section, 20% of the chord symbols in the corpus
occur only a single time and 50% fewer than six times. A co-occurrence matrix
based on one-hot chord vectors of dimension 1,542 would be sparse and ill-
conditioned, suggesting the need for dimensionality reduction. The issue of
infrequent symbol types is well known in natural language processing (NLP).
NLP handles dimensionality reduction with techniques such as principal
component analysis, truncated singular value decomposition, and gradient
descent, applied after having mapped words to vector embeddings [11].

This paper takes a different approach. We apply principles of music theory to
reduce the dimensionality of chord space prior to vector embedding.
Specifically, we draw on chord-scale theory as described in [15] to select a
set of 60 chord classes, based on 5 chord types and 12 scale positions to
represent the core characteristics of jazz harmony. In the following sections,
we specify a method for mapping each chord in the corpus to one of these
classes, accounting for all 1,542 types. There are many ways that music theory
can be used to describe chord relationships. In the following, we describe the
details and rationale of our specific approach.

###  3.1 $7^{th}$ Chord Types

Our choice of chord types focuses on the four-note $7^{th}$ chords
diatonically generated from the 12 major scales. Figure 1 shows the chords
obtained from the C major scale, illustrating that there are four chord types:
major7 (M), minor7 (m), dominant7 (7), and minor7$\flat$5 (h), where the
symbols shown in parentheses are abbreviations we use in this paper.

Figure 1: Diatonic $7^{th}$ chords of the C major scale

Each chord type can be represented by its defining chord, as well as versions
of this chord with any extensions or alterations. For example, we map chords
such as Cm9 and Cm11 to the Cm7 class; C7$\flat$9, C7$\sharp$5, and C13 map to
the C7 class; and CM7$\sharp$11 maps to the CM7 class. In addition, in
accordance with reharmonization practices, we assign chords such as CmM7 to
the Cm7 class and C6 to the CM7 class.

In addition to chords diatonic to major scales, we add one additional type:
the diminished7 (o) chord. Although not generated by major scales, the
diminished7 plays an important and unique role in jazz [14, 16].

Finally, we include an additional class to account for the _no-chord_ symbol.
This symbol is used in the corpus to designate a momentary absence of harmony,
and is important to include as a metric spacer when comparing the harmonic
similarity of two songs.

###  3.2 Chord Type Mapping

The first five rows of Table 1 show the frequencies of the chord types defined
so far, accounting for 77% of the chords in the corpus. The no-chord type
accounts for an additional 0.5%, and in the following discussion, we detail
how we map the remaining 22.5% to the five types defined above.

####  3.2.1 Triads

Triads represent 16% of the chords in the corpus, and as they do not contain a
$7^{th}$ note, mapping them into the chord class types defined in the previous
section can be indeterminate. For example, a C major triad, consisting of the
notes C, E, and G, shares all of its notes with both the C major7 and C
dominant7 chords. We resolve triad ambiguities using principles from tonal
harmony to identify whether they have a subdominant, dominant, or tonic
function [15].

For a major triad, we look at the chord following it in the progression. If it
has a root a fifth down and is a member of the major7 or minor7 classes we
designate the triad as having a dominant function, and assign it to a
dominant7 type with the same root. Otherwise, it is assigned to a major7 class
type. We handle major triads with an added $9^{th}$ in the same way.

Augmented triads share their notes with dominant7$\sharp$5 chords, an
alteration of the dominant. We opted to map these to the dominant7 type class
with the same root. Finally, we map all the minor and diminished triads to
their corresponding minor7 and diminished7 types, respectively.

####  3.2.2 Sus Chords

Sus chords also have a harmonic function that depends on context [16]. When
followed by a dominant7 chord with the same root, they act like a subdominant
and we opt to map them to a minor7 class with a root a fifth above. For
example, a G7sus4 would map to a Dm7. Otherwise, they act like a dominant and
we map it to a dominant7 class with the same root.

####  3.2.3 Slash Chords

Slash chords are chords played over a specific bass note, for example C/G or
Dm7/G, where the symbol above (to the left of) the slash is a chord and below
it a note. If the bass note belongs to the chord above the slash (for example,
C/G), it is an inversion. For such case, we map it according to the chord
above the slash.

Slash chords are also commonly used to represent sus chords. For example,
Dm7/G is harmonically equivalent to G9sus4. We map these according to the
process for sus chords described in the previous section. For all other slash
chords, we map the chord as if the bass note were an extension or alteration
of the chord above the slash.

####  3.2.4 Power Chords and Polychords

Power chords consist of just two notes, a root and a fifth. As they have no
3rd or 7th, they are harmonically ambiguous. With only 42 instances in our
corpus, we have opted to map these chords to the _no-chord_ class.

With only 12 instances, polychords are rare. These chords consist of either an
upper and lower triad or triad and a $7^{th}$ chord. We map polychords
according to their lower structure, interpreting the upper structure as
extensions or alterations.

##  4 Key Signature Based Representation

To make distributional semantics more effective, we are interested in a
transposition invariant chord representation. Practices in music information
retrieval have made use of both transposition to the same key (for example,
[17]) or to the same key signature (for example, [18]). As knowing the key
signature of a song is sufficient to transpose it, we opt for the latter, and
transpose all songs to the key signature without sharps or flats
(corresponding to C major/A minor).

Transposing a song from one key signature to another presumes the former is
known. The key signature listed in the database should be a credible source
for this information. However, lead sheets and databases do not always
accurately provide it. Moreover, from extensive manual checking, we know that
our own database contains several hundred songs for which the stated key
signature is clearly in error (or for which we have doubts). For this reason,
we introduce a key signature estimation algorithm, which we describe in the
following section.

###  4.1 Key Signature Estimation Algorithm

Several authors have proposed key estimation algorithms for various music
information retrieval tasks [19, 20, 21, 22, 23]. However, as discussed, our
objective is not to estimate a song’s key, but rather it’s key signature. Some
prior work also exists for key signature estimation [24], however, it is based
on machine learning models applied to MIDI data for classical music. Here, we
introduce a simple algorithm that requires very little computation, and
estimates key signatures from symbolic jazz chord progressions.

Our algorithm estimates a song’s key signature by selecting the one most
consistent with its chords. Figure 1 is useful for illustrating our approach.
The key signature in the figure has no sharps or flats, and so corresponds to
the scale of C major. This scale generates the set of seven diatonic $7^{th}$
chords shown in the figure, and results in major7, minor7, dominant7 and
minor7$\flat$5 chord types. These correspond to four of the five types
discussed in Section 3. The fifth type, diminished7 chords, is not associated
to any major scale, and is not used in our estimation algorithm.

For each chord in a progression, we map it to one of the 61 classes, as
described in Section3. Except for chords from the diminished7 and no-chord
classes, each chord is diatonically related to one or more key signatures and
their related major scales. The number of beats a chord is active is
attributed to each one of the key-signatures to which it can belong. After
processing all the chords, the key signature accumulating the most beats is
the resulting estimate for that song.

Figure 2: Example application of the key signature estimation algorithm

Figure 2 provides a concrete illustration of how the key estimation algorithm
works for the case of a short chord progression: A7-Dm7-G7-CM7-CM7. Each
column of the table represents one measure, and in this example, there is one
chord per measure. The column labels correspond to the chords, and each row
label is a key signature whose major scale diatonically contains one or more
of the chords in the progression. As shown, the A7 chord belongs to D major;
the Dm7 chord belongs to Bb, C, and F major; G7 belongs to C major; and CM7
belongs to both C and G major. Presuming four beats per measure, C accumulates
the most beats (16), and is the resulting key signature estimate for this
short chord progression.

###  4.2 Algorithm Evaluation

As already mentioned, there are quite a few songs in our corpus where the key
signature is incorrect or in doubt. Nevertheless, it is worthwhile comparing
the results of our key estimation algorithm with the ones recorded in the
corpus. Of the 2,612 songs, the algorithm concurs with the database for 1,763
(67.5%) of them.

For the 849 songs with database keys signatures that don’t agree with our
estimates, we use the Circle of Fifths as a distance metric to evaluate the
magnitude of differences between the two. Key signatures next to each other on
the circle of fifths correspond to major scales that differ in a single note.
For example, as seen in Figure 3, the key of F has the same notes as the
adjacent key of C except for a B$\flat$, and G has the same notes as C except
for an F$\sharp$.

Figure 3: Distances around the circle of fifths

Table 2 recaps the statistics of applying the circle-of-fifths metric to
estimated and database key signatures when evaluated for all of the songs in
the corpus. The left-most column in the figure indicates the distance in
number of sharps or flats between the estimated and database key. The row with
the distance of $0$ corresponds to agreement. As already observed, a total of
1,763 cases fall into that category. There are 304 cases of songs where the
estimate is 1$\flat$ away from the database key signature, and 183 that are
1$\sharp$ away. The number of remaining cases for larger circle-of-fifths
distances tail off rapidly.

Distance | Number | Percent
---|---|---
6$\flat$ | 10 | 0.4%
5$\flat$ | 22 | 0.8%
4$\flat$ | 33 | 1.3%
3$\flat$ | 55 | 2.1%
2$\flat$ | 99 | 3.8%
1$\flat$ | 304 | 11.6%
0 | 1763 | 67.5%
1$\sharp$ | 183 | 7.0%
2$\sharp$ | 22 | 0.8%
3$\sharp$ | 25 | 1.0%
4$\sharp$ | 12 | 0.5%
5$\sharp$ | 1 | 0.0%
Ambig. | 123 | 4.7%
Table 2: Key signature estimation statistics

The last row of Table 2 is labelled "Ambig.". There are 123 songs in the
database for which the key estimation algorithm returns a non-unique result,
and finds two or more major scales that accumulate the most beats. This
represents 4.7% of the songs in the corpus, and when this occurs our
estimation algorithm defaults to the database key.

###  4.3 Mapping to Scale Position and Chord Classes

Once all the chords in the corpus have been attributed to their respective
classes, and the key estimation algorithm applied to each song, all songs can
be transposed to a common key signature. We selected the key signature of C
major / A minor, but that choice has no influence on the calculation of the
co-occurrence matrix or the similarity metric. The combination of a scale
position and chord type defines a chord class. The combination of our 5 chord
types with 12 scale positions plus the _no-chord_ symbol leads to 61 chord
classes.

The chord classes can be mapped to Roman numeral notation, which is commonly
used in harmonic theory. The choice of numerals depends on the assumed root
note (which determines the mode). Table 3 shows the mapping for C major. As an
example for this key signature, a sequence of chords such as A7-Dm-G7-CM maps
to vi7-iim-v7-iM. Under our schema, the relative minor cadence Bh-E7-Am maps
to viih-iii7-vim.

Root | Roman Numerals (C major)
---|---
C | i
D$\flat$ |  $\flat$ii
D | ii
E$\flat$ |  $\flat$iii
E | iii
F | iv
G$\flat$ |  $\flat$v
G | v
A$\flat$ |  $\flat$vi
A | vi
B$\flat$ |  $\flat$vii
B | vii
Table 3: Roman numeral notation for C major

##  5 Co-Occurrence Matrix

The model-reduced, transposed versions of songs in our corpus can be used to
compute a co-occurrence matrix [25, 26, 27, 9]. Prior to the computation, we
introduce a _< START>_ and _< END>_ symbol at the beginning and end of each
song’s chord progression. This increases the total number of classes to 63.
Using a symmetric context window of size 1, the $ij^{th}$ element of the co-
occurrence matrix represents the number of times the $j^{th}$ chord class
occurs in the context of the $i^{th}$ chord class. The elements of the co-
occurrence matrix, $\mathbf{C}_{ij}$, are obtained by tabulating the number of
times the $j^{th}$ chord class occurs next to the $i^{th}$ class when scanning
through all the chord progressions in the corpus. Given a corpus of size $D$,
this can be expressed as

$\mathbf{C}_{ij}=\sum_{k=1}^{D}\sum_{i=1}^{N_{k}}\begin{cases}1,&\text{if
$s_{k_{(i-1)}}=j$ and $(i-1)>0$}\\\ 1,&\text{if $s_{k_{(i+1)}}=j$ and
$(i+1)\leq N_{k}$}\\\ 0,&\text{otherwise}\end{cases}$ (1)

where $s_{k_{1}},\ldots,s_{k_{N_{k}}}$ is the chord class sequence for song
$k$, and $i,j\in\\{1,\ldots,63\\}$ are the corresponding chord class indices.
The rows $\mathbf{C}_{i}$ of the matrix can be used as a vector embedding for
the chord classes. Because co-occurrence matrices capture contextual
information, the vectors of chord classes that have similar harmonic function
are expected to be close to each with respect to the cosine similarity
measure.

Table 4 illustrates two examples of how the co-occurrence matrix in Equation 1
captures semantic structure in the chord progressions from our corpus. The
left-hand table shows the five closest chord classes to $\flat$ii7. The lowest
row of the table is the cosine similarity of this chord with itself and, as
expected, has a value of 1. Of the 62 remaining chord classes, the next
closest in cosine similarity is the v7 chord class with a value of 0.821. From
a music theory perspective, this result seems reasonable because the
$\flat$ii7 and v7 are tritone substitutes that are often used as
reharmonizations for each other.

Class | bii7
---|---
iio | 0.751
<START> | 0.781
io | 0.811
$\flat$iio | 0.813
v7 | 0.821
$\flat$ii7 | 1.000

Class | iim
---|---
v7 | 0.786
<END> | 0.829
vo | 0.850
$\flat$vi7 | 0.914
iih | 0.924
iim | 1.000

Table 4: Cosine distance and harmonic similarity for the $\flat$ii7 and the
iim chord classes

The table on the right-hand side of Table 4 shows the top five chord classes
nearest to iim. The closest, iih, seems satisfactory from a music theory
perspective. The iim is the most common subdominant chord, and is the first
chord in the major cadence, iim-v7-iM. The iih is a common reharmonization for
the iim, and is also the first chord in the minor cadence for the parallel
minor.

##  6 Membrane-Area Distance Metric

The normalized chord vectors derived from the co-occurrence matrix can be used
to plot the path of a song’s progression through 63-dimensional space.
Starting from the origin, the sequence of chord vectors can be concatenated
from head to tail, beginning with the <START>, and terminating with the <END>
vector. Each unit vector is scaled by the number of beats of the chord it
represents, and the result is a piecewise linear function through
$\mathbf{R}^{63}$.

The piecewise linear functions for two identical chord progressions would,
naturally, overlay each other, and two harmonically similar songs should trace
similar paths through $\mathbf{R}^{63}$.

Expressed formally, we represent song vector paths by piecewise linear
functions of the form $\mbox{\boldmath{$f$}}(t)\in\mathbf{R}^{63}$, where
$t\in[0,1]$ is a parametric variable representing the number of normalized
beats traversed in the song. We can move along the entire length of $f$ in
discrete, equal increments, $dt$, where the starting point of the function,
$\mbox{\boldmath{$f$}}(0)$ at $t=0$ is the origin, and the end point of the
function is at $t=1$.

Given two songs and their corresponding piecewise linear functions,
$\mbox{\boldmath{$f$}}(t)$ and $\mbox{\boldmath{$g$}}(t)$, and letting
$N=1/dt$, we can define a distance metric between them as the area of a 2D
membrane, $M$, stretched between the two paths. $M$ is calculated as the
integral obtained in the limit of

$M(\mbox{\boldmath{$f$}},\mbox{\boldmath{$g$}})=\lim_{dt\rightarrow
0}\sum_{n=0}^{N}\|\mbox{\boldmath{$f$}}(ndt)-\mbox{\boldmath{$g$}}(ndt)\|dt$
(2)

where $\|\cdot\|$ is the Euclidean norm.

Figure 4 is a graphical illustration of how the measure in Equation2 is
evaluated. The red and blue lines represent two different songs, each having
two chords (excluding the terminal symbols). The songs begin at the origin,
and the chord vectors are added head-to-tail. The metric is approximated by
summing the lengths of the $N$ equally spaced black line segments drawn
between the two songs.

Figure 4: Conceptual illustration of the membrane-area distance metric

##  7 Experiment

We have found no scholarly reference data sets for contrafacts that can be
used as ground truth for a comprehensive evaluation of our method. Although
there is a list of 252 jazz contrafacts assembled in a Wikipedia article [3],
only 91 of those songs are found in our corpus. Moreover, quite a few of the
examples cited in the article are not full contrafacts, meaning that the song
only borrows a portion of the harmony from another song. The eight bars of the
_Rhythm Changes_ bridge is an example of this.

Despite the lack of comprehensive ground truth, we can illustrate the
performance and characteristics of our method with an example. As the
membrane-area metric can be computed for any pair of songs, it can be used to
search for contrafacts. If $f^{*}$ is the vector path of a reference song and
$S$ is the set of all songs in the corpus excluding $f^{*}$ the song,
$\hat{f}$, harmonically closest to $f^{*}$ is

$\hat{f}=\arg\min_{f\in S}M(f^{*},f)$ (3)

As an example, Figure 5(a) illustrates the chord progression for the jazz
standard _On Green Dolphin Street_. Evaluating the distance between this song
and every other one in the corpus, the closest is the well-known contrafact,
_Green St. Caper_ [3], shown in Figure 5(b).

Figure 5: Chord progressions for (a) _On Green Dolphin Street_ , and (b)
_Green St. Caper_

Although contrafacts, these two songs have numerous differences. _On Green
Dolphin Street_ is in the key of C, and _Green St. Caper_ is in E$\flat$. The
former has 32 bars, and the latter has 36. There are also numerous differences
in harmonization. To more clearly see this last point, it is easier to examine
the two songs in Roman numeral notation, as shown in Figure 6.

Figure 6: Roman numeral notation for (a) _On Green Dolphin Street_ , and (b)
_Green St. Caper_. Measures with blue backgrounds are variations in
harmonization.

There are 10 measures in the two songs that have different chords (highlighted
with pale blue backgrounds). For example, measure 12 contains a vm-i7 in the
reference song and iM-$\flat$v7 in the contrafact. Here the contrafact has
replaced the vm by extending the duration of the iM from the previous bar, and
has replaced the i7 with its tritone substitute, the $\flat$v7. This is a
concrete instance of the example discussed in Table 4. The differences seen in
each of the other highlighted measures correspond to well-known
reharmonizations as discussed in [4].

##  8 Conclusions and Future Work

This paper makes several contributions. The first is the use of music theory
to reduce the dimensionality of chord space. Our method is comprehensive,
detailing how to map every one of the 1,542 chord types found in our corpus to
61 classes.

The resulting chord class progressions are used to compute a dense co-
occurrence matrix without needing to resort to non-parametric approximations
such as truncated SVD or gradient descent. Furthermore, we show that our
corpus generates a co-occurrence matrix that is able to capture semantic
information about harmony. Using the cosine similarity measure, we present
examples illustrating that rows of the co-occurrence matrix embody
characteristics of common reharmonizations.

Using the normalized rows of the matrix as vector embeddings of chord classes,
we modeled songs as piecewise linear paths in $\mathbf{R}^{63}$. A novel
distance metric, the membrane-area, was introduced, and used as a measure of
harmonic similarity between songs. An example of its application was
presented, successfully finding a song’s known contrafact even though the two
songs have numerous differences in harmonization.

This paper examines one type of vector embedding for chords, but other
approaches such as TF-IDF [28] or Word2Vec [29] are worthwhile exploring. The
latter is particularly interesting because it has been shown to capture
additional semantic characteristics (for example, analogy) when used in
natural language processing.

The vector embeddings discussed in this paper could be used as inputs to
machine learning architectures such as RNNs [30] and Transformers [31]. This
could be a promising avenue of application for MIR tasks such as automatic
chord recognition [32], automatic music transcription [33], genre detection
[34], and cover song identification [35, 36, 37, 38].

## References

  * [1] B. D. Kernfeld, _The New Grove Dictionary of Jazz: Gabler-Niewood_. Grove’s Dictionaries Incorporated, 2002, vol. 2.
  * [2] “Rhythm changes,” https://en.wikipedia.org/wiki/Rhythm_changes, 2022.
  * [3] “List of jazz contrafacts,” https://en.wikipedia.org/wiki/Listof-jazzcontrafacts, 2018.
  * [4] D. Berkman, _The Jazz harmony book: a course in adding chords to melodies_. Petaluma, CA, 2013.
  * [5] M. Schedl, E. Gómez Gutiérrez, and J. Urbano, “Music information retrieval: Recent developments and applications,” _Foundations and Trends in Information Retrieval. 2014 Sept 12; 8 (2-3): 127-261._ , 2014.
  * [6] W. B. De Haas _et al._ , “Music information retrieval based on tonal harmony,” Ph.D. dissertation, Utrecht University, 2012.
  * [7] M. Rohrmeier, “The syntax of jazz harmony: Diatonic tonality, phrase structure, and form,” _Music Theory and Analysis (MTA)_ , vol. 7, no. 1, pp. 1–63, 2020.
  * [8] G. Boleda, “Distributional semantics and linguistic theory,” _Annual Review of Linguistics_ , vol. 6, pp. 213–234, 2020.
  * [9] K. Lund and C. Burgess, “Producing high-dimensional semantic spaces from lexical co-occurrence,” _Behavior research methods, instruments, & computers_, vol. 28, no. 2, pp. 203–208, 1996.
  * [10] E. Bruni, N.-K. Tran, and M. Baroni, “Multimodal distributional semantics,” _Journal of artificial intelligence research_ , vol. 49, pp. 1–47, 2014.
  * [11] C. O. S. Sorzano, J. Vargas, and A. P. Montano, “A survey of dimensionality reduction techniques,” _arXiv preprint arXiv:1403.2877_ , 2014.
  * [12] H. Leonard, _The Real Book_. Hal Leonard Publishing Corporation, 2016.
  * [13] B. Keller, “Impro-visor,” https://www.cs.hmc.edu/~keller/jazz/improvisor/, 2008.
  * [14] R. Rawlins and N. E. Bahha, _Jazzology: the encyclopedia of jazz theory for all musicians_. Hal Leonard Corporation, 2005.
  * [15] J. Mulholland and T. Hojnacki, _The Berklee Book of jazz harmony_. Hal Leonard Corporation, 2013.
  * [16] M. Levine, _The jazz theory book_. " O’Reilly Media, Inc.", 2011.
  * [17] H. Tsushima, E. Nakamura, K. Itoyama, and K. Yoshii, “Function-and rhythm-aware melody harmonization based on tree-structured parsing and split-merge sampling of chord sequences.” in _ISMIR_ , 2017, pp. 502–508.
  * [18] M. C. Mozer, “Neural network music composition by prediction: Exploring the benefits of psychoacoustic constraints and multi-scale processing,” _Connection Science_ , vol. 6, no. 2-3, pp. 247–280, 1994.
  * [19] M. Mauch and S. Dixon, “Simultaneous estimation of chords and musical context from audio,” _IEEE Transactions on Audio, Speech, and Language Processing_ , vol. 18, no. 6, pp. 1280–1289, 2009.
  * [20] J. Pauwels and J.-P. Martens, “Combining musicological knowledge about chords and keys in a simultaneous chord and local key estimation system,” _Journal of New Music Research_ , vol. 43, no. 3, pp. 318–330, 2014.
  * [21] T. Rocher, M. Robine, P. Hanna, L. Oudre, Y. Grenier, and C. Févotte, “Concurrent estimation of chords and keys from audio.” in _ISMIR_. Citeseer, 2010, pp. 141–146.
  * [22] K. C. Noland and M. B. Sandler, “Key estimation using a hidden markov model.” in _ISMIR_. Citeseer, 2006, pp. 121–126.
  * [23] E. Benetos, A. Jansson, and T. Weyde, “Improving automatic music transcription through key detection,” in _Audio Engineering Society Conference: 53rd International Conference: Semantic Audio_. Audio Engineering Society, 2014.
  * [24] F. Foscarin, N. Audebert, and R. Fournier-S’Niehotta, “Pkspell: Data-driven pitch spelling and key signature estimation,” _arXiv preprint arXiv:2107.14009_ , 2021.
  * [25] S. Bordag, “A comparison of co-occurrence and similarity measures as simulations of context,” in _International Conference on Intelligent Text Processing and Computational Linguistics_. Springer, 2008, pp. 52–63.
  * [26] A. Globerson, G. Chechik, F. Pereira, and N. Tishby, “Euclidean embedding of co-occurrence data,” _Advances in neural information processing systems_ , vol. 17, 2004.
  * [27] L. Leydesdorff and L. Vaughan, “Co-occurrence matrices and their applications in information science: Extending aca to the web environment,” _Journal of the American Society for Information Science and technology_ , vol. 57, no. 12, pp. 1616–1628, 2006.
  * [28] J. Ramos _et al._ , “Using tf-idf to determine word relevance in document queries,” in _Proceedings of the first instructional conference on machine learning_ , vol. 242, no. 1. Citeseer, 2003, pp. 29–48.
  * [29] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” _arXiv preprint arXiv:1301.3781_ , 2013\.
  * [30] J. Chung, K. Kastner, L. Dinh, K. Goel, A. C. Courville, and Y. Bengio, “A recurrent latent variable model for sequential data,” _Advances in neural information processing systems_ , vol. 28, 2015.
  * [31] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [32] J. Pauwels, K. O’Hanlon, E. Gómez, M. Sandler _et al._ , “20 years of automatic chord recognition from audio,” in _Proceedings of the 20th ISMIR Conference_ , 2019.
  * [33] E. Benetos, S. Dixon, Z. Duan, and S. Ewert, “Automatic music transcription: An overview,” _IEEE Signal Processing Magazine_ , vol. 36, no. 1, pp. 20–30, 2018.
  * [34] N. Scaringella, G. Zoia, and D. Mlynek, “Automatic genre classification of music content: a survey,” _IEEE Signal Processing Magazine_ , vol. 23, no. 2, pp. 133–141, 2006.
  * [35] F. Yesiler, J. Serrà, and E. Gómez, “Accurate and scalable version identification using musically-motivated embeddings,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 21–25.
  * [36] X. Xu, X. Chen, and D. Yang, “Key-invariant convolutional neural network toward efficient cover song identification,” in _2018 IEEE International Conference on Multimedia and Expo (ICME)_. IEEE, 2018, pp. 1–6.
  * [37] M. Khadkevich and M. Omologo, “Large-scale cover song identification using chord profiles.” in _ISMIR_ , vol. 13, 2013, pp. 233–238.
  * [38] T. Bertin-Mahieux and D. P. Ellis, “Large-scale cover song recognition using hashed chroma landmarks,” in _2011 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA)_. IEEE, 2011, pp. 117–120.