Encoder Challenge

Given the input text $W = \{w_1, \ldots, w_n\}$ where $w_i$ is the $i$'th token in ​$W$, a contextualized encoder (e.g., BERT) takes $W$ and generates an embedding $e_i \in \mathbb{R}^{1 \times d}$ for every token $w_i \in W$using $w_i$ as well as its context. The challenge is that this encoder can take only up the $m$-number of tokens such that it cannot handle any input where $n > m$.

Baseline

One popular method is called the "Sliding Window", which splits the input into multiple blocks of text, generates embeddings for each block separately, and merges them at the end.

Let W = W_1 \cup \cdots \cup W_k \where $W_h = \{w_{(h-1)m+1}, \ldots, w_{hm}\}$ if $hm < n$; otherwise, $W_h = \{w_{(h-1)m+1}, \ldots, w_{n}\}$ such that $km \leq n$. Then, the encoder takes each $W_h$​ and generates $E_h = \{e_{(h-1)m+1}, \ldots, e_{hm}\}$ for every token in $W_h$. Finally, the embedding matrix $E \in \mathbb{R}^{n \times d}$ is created by sequentially stacking all embeddings in $W_{\forall h}$.

Advanced (Exercise)

Modify the baseline method such that a block has overlapped tokens with its surrounding blocks (both front and back). Once all blocks are encoded, each overlapped token should have two embeddings. Create an average embedding of those two embeddings and make it the final embedding for the overlapped token.

Decoder Challenge

In a sequence-to-sequence model (aka, an encoder-decoder model), a decoder takes an embedding matrix $E \in \mathbb{R}^{m \times d}$ and predicts what token should come next. It is often the case that this embedding matrix is also bounded by a certain size, which becomes an issue when the size of the matrix becomes larger than $m$ (for the case above, $E \in \mathbb{R}^{n \times d}$ where $n > m$). One common method to handle this issue is to use an attention matrix for dimensionality reduction as follows:

The embedding matrix $E \in \mathbb{R}^{n \times d}$ is first transposed to $E^T \in \mathbb{R}^{d \times n}$ then multiplied by an attention matrix $A \in \mathbb{R}^{n \times m}$ such that $E^T \cdot A \rightarrow D \in \mathbb{R}^{d \times m}$. Finally, the transpose of $D$, that is $D^T \in \mathbb{R}^{m \times d}$ gets fed into the decoder.

When you create a dataset, the followings need to be clearly described:

• Data collection (e.g., sources of the data).

• Preprocessing if performed (e.g., scripts that you write, existing tools used).

• Annotation scheme and guidelines if conducted with justification.

• People involved in this process (e.g., annotators, survey subjects).

• Quality of the created data (e.g., inter-annotator agreement).

• Statistics and analysis of the original, preprocessed, annotated data.

Here are a few papers presenting new datasets:

• , Li et al., EMNLP 2020 (see Section 3).

• , Yang and Choi, SIGDIAL, 2019 (see Section 3).

Content

Task

Your task is to design an algorithm that takes a post with the title and its comments with replies from a discussion forum (e.g., Reddit) and converts them into a multi-turn one-to-one dialogue.

Input

A post with the title ():

How do you focus when you’re depressed?

I have so many assignments due, with exams coming up too. Life's just keeps hitting me recently and I'm finding it really hard to sit down and take information in. Writing is hard, listening and paying attention is hard. Even if I manage to listen or read none of the information stays in my head. Any help is very appreciated!!

Comments and replies:

Get up early everyday and use the library to study if you have one, idk if you're like me but as soon as I get home I'm kinda done for the day so it helps to stay somewhere where you can't really relax.

• Thank you, I’ll give this a try tomorrow

What helps me is embracing when I'm feeling down and allowing myself to take a deserved break. Sometimes I confuse my depressive episodes with burnout and it's important to know your limits. The biggest pro tip to not be overwhelmed with so much to do all at once is doing something every day. Dedicating simply 30 minutes to an hour a day of intense studying goes a long way over time vs cramming at the end. If you're able to do more than 1 hour then great! But know that you don't have to do 6-7 intense studying hours a day to be successful. Be intentional with your time and work smarter vs harder. Your future self will thank you.

• This is so nice to hear, and very helpful, thank you!

Hardest part is starting to study, once I have like 15 minutes into my study session that’s my only focus and just forget everything else.

Overview

Give a comparison overview of your algorithms with key features:

We introduce two algorithms for the reddit-to-dialogue generation: the baseline algorithm considers every sentence in the post an utterance of Speaker 1 and each comment an utterance of Speaker 2 (Section 3.1), whereas the advanced algorithm finds an appropriate span of sentences from the post to form an utterance for Speaker 1 and an appropriate span of any comment to form an utterance for Speaker 2 (Section 3.2).

Indicate the objective of your algorithm(s):

The main objective is to generate a multi-turn dialogue using a post, its comments, and replies that flows naturally in context.

Describe what the input and output data should be (possible with a figure) that are commonly applied to all algorithms:

All algorithms assume that the number of sentences in the input post is less than or equal to the number of comments. The generated dialogues involve two speakers where utterances of Speakers 1 and 2 are extracted from the post and comments, respectively.

Baseline

Objective

• The title or each sentence in the post is considered an utterance of Speaker 1 (S1).

Output

S1 : How do you focus when you’re depressed?

S2 : What helps me is embracing when I'm feeling down and allowing myself to take ...

S1 : I have so many assignments due, with exams coming up too.

S2 : Get up early everyday and use the library to study if you have one, ...

S1 : Life's just keeps hitting me recently and I'm finding it really hard to sit down and take information in.

S2 : Hardest part is starting to study, once I have like 15 minutes into my study session that’s my only focus and just forget everything else.

Algorithm

1. Illustrate the baseline algorithm in pseudocode. Create helper methods if they help the readability and/or generalizability of your algorithm.

2. Give a brief overview of the algorithm by explaining what each line of the code does.

3. Describe helper methods (if any) in detail.

Overview

Define the input:

Initialize the output and auxiliary data structures:

Describe the loop:

Return the output:

Helper Methods

Advanced (Exercise)

Objective

• Any span of consecutive sentences is considered an utterance of S1.

Output

S1 : How do you focus when you’re depressed? I have so many assignments due, with exams coming up too.

S2 : What helps me is embracing when I'm feeling down and allowing myself to take a deserved break.

S1 : Life's just keeps hitting me recently and I'm finding it really hard to sit down and take information in.

S2 : Get up early everyday and use the library to study if you have one, idk if you're like me but as soon as I get home I'm kinda done for the day so it helps to stay somewhere where you can't really relax.

S1 : Writing is hard, listening and paying attention is hard.

S2 : Hardest part is starting to study, once I have like 15 minutes into my study session that’s my only focus and just forget everything else.

S1: Even if I manage to listen or read none of the information stays in my head. Any help is very appreciated!!

S2: Sometimes I confuse my depressive episodes with burnout and it's important to know your limits. The biggest pro tip to not be overwhelmed with so much to do all at once is doing something every day.