#  Affective and Dynamic Beam Search for Story Generation

Tenghao Huang1 Ehsan Qasemi1 Bangzheng Li1
He Wang2 Faeze Brahman3 Muhao Chen1,4 Snigdha Chaturvedi5
1University of Southern California 2Columbia University
3Allen Institute for Artificial Intelligence 4University of California, Davis
5University of North Carolina
{tenghaoh, qasemi<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Storytelling’s captivating potential makes it a fascinating research area,
with implications for entertainment, education, therapy, and cognitive
studies. In this paper, we propose Affective Story Generator (AffGen) for
generating interesting narratives. AffGen introduces ‘intriguing twists’ in
narratives by employing two novel techniques—Dynamic Beam Sizing and Affective
Reranking. Dynamic Beam Sizing encourages less predictable, more captivating
word choices using a contextual multi-arm bandit model. Affective Reranking
prioritizes sentence candidates based on affect intensity. Our empirical
evaluations, both automatic and human, demonstrate AffGen’s superior
performance over existing baselines in generating affectively charged and
interesting narratives. Our ablation study and analysis provide insights into
the strengths and weaknesses of AffGen.

##  1 Introduction

Stories have been a central part of human cultures for millennia, shaping
societies, identities, and beliefs Kasunic and Kaufman (2018). However, the
question of why some stories captivate us while others leave us indifferent
remains intriguing. While humans can skillfully craft interesting narratives,
even the most recent AI models cannot compose stories that can engage the
reader for long enough. In this work, we address the task of automatically
generating interesting stories.

Automatically generating interesting stories could potentially help cognitive
studies by revealing patterns that make stories interesting. From an
application perspective, the capability to generate interesting stories could
revolutionize the fields like entertainment Akoury et al. (2020); Thue et al.
(2007), education Zhao et al. (2022), and even therapy Gabriel and Young
(2011).

While large language models (LLMs), such as GPT Radford et al. (2019), have
been de facto winners in generating coherent text, their prowess in creating
narratives that captivate human interest leaves much to be desired. LLMs’
coherence is mainly rooted in their training objective that incentivizes text
likelihood which is not necessarily correlated with human quality judgements
Holtzman et al. (2019); Zhang et al. (2021) or writing style Gehrmann et al.
(2019).

Figure 1: Two example stories. Story 1 is an interesting story with an
intriguing twist (highlighted in orange color) that was produced by AffGen
using dynamic beam sizing. Story 2 is a relatively less interesting story with
a straightforward and predictable plot.

The concept of “interesting stories” is also highly subjective and context-
dependent Roemmele (2021). Previous research in the field increases “interest”
in the story by structural planning to control specific aspects of the story,
e.g. modeling the emotional flow of the protagonist Luo et al. (2019); Brahman
and Chaturvedi (2020) or incorporating flashbacks Han et al. (2022). However,
such methods ignore that text complexity and quality also raise its
interestingness Schraw et al. (2001).

Bradley and Lang (1999) advocates for decorating the plot with affective terms
to increase the suspense and intensity of the story that results in control of
the audience’s emotions Delatorre et al. (2016). With this motivation, we
propose Affective Story Generator (AffGen)111Code is available at
https://github.com/tenghaohuang/AFFGEN.git that controls text coherence and
leverages words’ affective dimensions to promote text interestingness. Our
method is based on two key ideas. First, in beam-search-based decoding of
language models, occasionally exploring larger beams can help in generating
slightly lower probability but potentially more interesting words. Second,
switching between large and small beams can help in maintaining the balance
between coherence and interestingness. We use these ideas to generate stories
with an intriguing twist. Figure 1 shows an example of an interesting story,
Story 1, with an intriguing twist (highlighted in orange color) that was
produced by dynamically using different beam sizes. It also shows an
uninteresting story, Story 2, that used a comparable language model but with a
constant beam size.

To generate an interesting story, AffGen first identifies where to generate
the intriguing twist that would push the story to be more interesting. Then it
generates the intriguing twist using two novel techniques, i.e. Dynamic Beam
Sizing and Affective Reranking. In dynamic beam sizing, AffGen uses a
contextual bandit model Thompson (1933) to dynamically explore different beam
sizes thus encouraging the model to select words that are less predictable and
more intriguing without compromising coherence. In affective reranking, AffGen
reranks possible candidates for the sentence to be generated according to
their arousal and valence scores Mohammad (2018), thereby modulating the
emotional dynamics of the story.

Our automatic and human evaluations show that stories generated by AffGen are
more engaging than the baselines without sacrificing coherence. Our ablation
studies and analysis provide deeper insights into the functioning of AffGen

Our contributions are:

  * •

We propose the task of generating interesting stories.

  * •

We propose AffGen, a language model that uses a novel contextual bandit-based
decoding algorithm and explores dynamic beam sizes and affective reranking.

  * •

We conduct automatic and human evaluations to empirically demonstrate that
AffGen can produce interesting and coherent narratives.

  * •

We conduct ablation studies and analysis to further understand the working of
AffGen.

##  2 Related Works

We discuss two lines of related work that are closely relevant to this study.

Story Generation. Early research on story generation explored symbolic
planning methods PÉrez and Sharples (2001); Porteous and Cavazza (2009); Riedl
and Young (2010) that used predefined rules and structures to generate
stories. Later efforts used neural methods Jain et al. (2017); Peng et al.
(2018); Fan et al. (2018); Puduppully et al. (2019); Zhai et al. (2019); Yao
et al. (2019); Wang et al. (2021); Peng et al. (2022).

However, generating interesting stories has remained a challenge due to the
subjective nature of “interestingness” Roemmele (2021). Some previous work has
attempted to generate interesting stories by controlling specific aspects of
the generated content, such as modeling emotions Luo et al. (2019); Brahman
and Chaturvedi (2020), flashbacks Han et al. (2022), personas Zhang et al.
(2022), topics Lin and Riedl (2021), and social relationships Vijjini et al.
(2022). Alhussain and Azmi (2021) pointed out factors that could lead to
interesting narratives, such as suspense Tan and Fasting (1996), discourse
Genette (1980), and characters Liu et al. (2020). This work differs from these
approaches in the sense that it focuses on generating interesting content by
choosing more affective, and not necessarily high-likelihood, words.

Sampling strategies for decoding. One of the commonly used strategies in
neural text (and story) generation is Nucleus Sampling Holtzman et al. (2019).
This method involves selecting a subset of the vocabulary, called the nucleus,
from which the next word is sampled. Another strategy is Top-$k$ Sampling Fan
et al. (2018), which only considers the $k$ most probable words for the next
word. Meister et al. (2023) proposed an information-theoretic strategy,
Locally Typical Sampling, with the aim of making the model’s output more
human-like.

Our approach differs from these existing strategies in two key perspectives.
First, while previous works primarily aim to encourage generation fluency and
diversity we focus on including more affective terms during decoding. Second,
we use re-scoring, which involves adjusting the probabilities of the words
based on additional criteria, rather than solely relying on the logits
distribution generated by the model. This allows us to further enhance the
diversity and affective quality of the generated text.

##  3 Problem statement

Given a sentence, $\mathbf{s_{1}}$, as a prompt that represents the first
sentence of a story, our goal is to generate an interesting story represented
as a sequence of generated sentences
$\mathbf{s_{2}},\mathbf{s_{3}},\ldots,\mathbf{s_{N}}$. Each sentence is a
sequence of tokens. In this paper, one of these generated sentences serves as
the intriguing twist in the narrative.

##  4 Controlled Affective Story Generator

This section presents the Controlled Affective Story Generator (AffGen), a
narrative generation model designed to produce interesting stories. AffGen
operates in two key stages. First, it identifies the position of the sentence
that should contain the intriguing twist, $p_{IT}$ (Section 4.1). Then, it
generates the story in the left-to-right manner using a language model. For
generating sentences that do not contain the intriguing twist, it uses a
standard decoding algorithm since the focus is on maintaining narrative
coherence (Section 4.2). For generating the sentence that contains the
intriguing twist, it uses our proposed decoding algorithm based on Dynamic
Beam Sizing and Affective Reranking since the focus is on balancing emotional
arousal, interestingness, and coherence (Section 4.3).

###  4.1 Position of the intriguing twist

Narratives are highly structured texts. Freytag’s pyramid Freytag (1908), a
widely recognized model of narrative structure, delineates the story into five
key components: exposition, rising action, climax, falling action, and
resolution.

Given the prompt sentence, $\mathbf{s_{1}}$, our objective is to determine the
most suitable location for the climax or the intriguing twist,
$n_{IT}\in\\{2,3,\ldots N\\}$. There has been some work on identifying the
climax or turning point in a given story Ouyang and McKeown (2015); Wang et
al. (2022); Vijayaraghavan and Roy (2023). We employ a data-driven approach
inspired by the work of Wilmot and Keller (2020). Their methodology operates
on the premise that if the embedding of two sentences is sufficiently distant,
the latter sentence can be deemed unexpected or interesting with respect to
the former sentence. They use this idea to identify the sentence that presents
the turning point or intriguing twist in a narrative.

Our data-driven approach utilizes the WritingPrompts dataset Fan et al.
(2018), a collection of human-written stories. We use this dataset to form a
distribution, $D(n)$, which corresponds to the probability of observing the
intriguing twist at the $n^{th}$ sentence. During inference, AffGen samples a
relative position $n_{IT}$ from $D(n)$ to pinpoint the location of the
sentence that would be the intriguing twist in the story that will be
generated

$n_{IT}\sim D(n).$

Next, we discuss how AffGen generates the various sentences of the story.

###  4.2 Base Storyteller

For generating sentences that do not contain an intriguing twist
($\mathbf{s_{i}}$’s $\forall i\notin\\{1,n_{IT}\\}$), the focus is on
maintaining narrative coherence. We use a GPT-based language model Radford et
al. (2019); Brown et al. (2020) which has shown promising performance on story
generation Brahman and Chaturvedi (2020); Clark and Smith (2021). We fine-tune
the language model on a dataset of stories (section 5.1) by minimizing the
negative conditional log-likelihood:

$NLL=-\log\prod_{i=1}^{n}p(w_{i}|w_{1},...,w_{i-1}).$ (1)

where $w_{i}$’s represents the tokens of the story. We use beam search for
inference in this model.

###  4.3 Generating Intriguing Twist

To generate the sentence that contains the intriguing twist in the narrative,
$\mathbf{s}_{IT}$, we use the fine-tuned language model from Section 4.2 but
with a novel beam search-based decoding. Our decoding method uses Dynamic Beam
Sizing and Affective Reranking to produce interesting text.

Dynamic Beam Sizing. The motivation behind our beam search-based decoding
algorithm is that while a small beam size helps in producing coherent text, by
expanding the beam size of the PLM, we can explore slightly lower probability
but potentially more intriguing words. However, maintaining a large beam size
throughout is also not desirable because not all words in a sentence need to
be interesting. A large beam throughout can also slow down the inference
process and require more resources. So during inference, the model needs to
dynamically switch between large and small beam sizes to balance the tradeoff
between the coherence and interestingness of the generated text.

To address this, we introduce Dynamic Beam Sizing, where depending on the
context, the model decides the beam size before generating a token. For
practical purposes, we assume that the beam size can take one of $k$ values
$\\{b^{1},b^{2}...b^{k}\\}$, and the model has to choose one. We cast the
problem of choosing a beam size as a contextual $k$-arm bandit problem
Langford and Zhang (2007), where the arms of the bandit are the various beam
sizes. The bandit’s choice of beam size at time step or trial, $t$, depends on
the the context of the bandit. The context considers the tokens generated so
far for the intriguing twist sentence, $\mathbf{s}_{IT}$. We use
$\mathbf{s_{IT,t-1}}$ to refer to the sequence of tokens in this partial
sentence and represent the context using following features:
1\. Arousal score: The arousal score of the sentence generated so far,
$\mathbf{s_{IT,t-1}}$. The arousal score of a partial sentence, viewed as a
sequence of tokens, $\mathbf{s}$, of length $n$ is:

$A(\mathbf{s})=\sum_{i=1}^{n}a(w_{i})$ (2)

where $a(w_{i})$ is the arousal score of the $i^{th}$ token obtained from the
NRC Word-Emotion Association lexicon Mohammad (2018). Since longer sentences
can accumulate higher arousal scores, we divide the arousal score by a length
normalizing factor Wu et al. (2016). The length normalizing factor for a
sentence of length $n$ is:

$lp(n)=\frac{{(5+n)^{\lambda}}}{{(5+1)^{\lambda}}}$ (3)

where $\lambda$ is the normalization coefficient.
2\. Event trigger likelihood: Sims et al. (2019) points out that in narratives
there are certain words in a sentence that trigger interesting literary
events. E.g. In the sentence “… Stephen leaned his arms on …”. The word
“leaned” is an event trigger. Identifying such event triggers can help in
locating the interesting part of a sentence, which in turn will help in
deciding whether to choose a larger beam. With this motivation, we train a
RoBERTa Liu et al. (2019) based predictor that given a partial sentence
predicts whether the next token would be the trigger for an interesting
literary event. We provide the partial sentence generated so far,
$\mathbf{s_{IT,t-1}}$, as the input to this predictor and use the likelihood
assigned by it (for the next token to be an event trigger) as a feature.
3\. Sequence length: Length of the partial sentence generated so far,
$\mathbf{s_{IT,t-1}}$. Knowing where the model is, in terms of position, can
help it decide whether to generate an interesting token next.
4\. Perplexity: The model’s perplexity on the partial sentence generated so
far, $\mathbf{s_{IT,t-1}}$. This helps in maintaining coherence.

For choosing an arm $b\in\\{b^{1},b^{2}...b^{k}\\}$, the bandit also receives
a payoff. The payoff accounts for all the candidate sequences in the beam
$\\{\mathbf{c}^{1},\mathbf{c}^{2},...,\mathbf{c}^{b}\\}$. Each
$\mathbf{c}^{i}$ is basically a concatenation of the partial sentence
generated so far, $\mathbf{s}_{IT,t-1}$, and the $i^{th}$ token in the beam.
The payoff rewards beams that contain candidate sequences with high arousal
scores (to promote interestingness) and low perplexity (to promote coherence).
It also penalizes large beam sizes to encourage using fewer compute resources.
Mathematically, the payoff value $R(b_{t},t)$, for choosing a beam size,
$b_{t}$, at time step $t$, is defined as:

$R(b_{t},t)=\underset{i\in[1,b_{t}]}{\max}(\text{A}(\mathbf{c}^{i})-\alpha\cdot\text{ppl}(\mathbf{c}^{i})-\beta\cdot|b_{t}|),$
(4)

where $\alpha,\beta$ are coefficients for each component,
$\text{A}(\mathbf{c})$ and $\text{ppl}(\mathbf{c})$ represent the arousal
score (as defined in Eqn. 2) and the perplexity of the candidate sequence
$\mathbf{c}$ respectively, and $|b_{t}|$ represents the size of beam $b_{t}$.

Given the set of $k$ choices for beam sizes $\\{b^{1},b^{2},\ldots b^{k}\\}$,
the optimal beam size $b^{*}_{t}$ at timestep $t$ is given by

$b^{*}_{t}=\underset{i\in[1,k]}{\text{argmax}}\;R(b^{i}_{t},t)$ (5)

Correspondingly, the optimal payoff at time step, $t$ is $R(b^{*}_{t},t)$.

Using the LinUCB (Upper Confidence Bound) algorithm Li et al. (2010), we
optimize the bandit model by minimizing regret $L$ defined as:

$L=\mathbb{E}[\Sigma^{T}_{t=1}R(b^{*}_{t},t)]-\mathbb{E}[\Sigma^{T}_{t=1}R(b_{t},t)]$
(6)

where $T$ is the total number of time steps or the total number of tokens in
$\mathbf{s}_{IT}$.

Affective Reranking. While Dynamic Beam Sizing introduces more arousing
content, it does not consider the variation of emotions associated with the
content. Chung et al. (2022) highlighted that variation of emotional arc
Reagan et al. (2016) can make a story more engaging. We, therefore, introduce
Affective Reranking.

Let $\\{\mathbf{s_{IT}}^{1},\mathbf{s_{IT}}^{2}\ldots\mathbf{s_{IT}}^{b}\\}$
be the candidate sentences that are generated as potential intriguing twists
in the beam. The best candidate should have a high arousal score and should
also have high affective contrast. We quantify affective contrast as the
difference in the valence scores of the candidate sentence and the story
generated so far. Valence score of a sequence of tokens, $v$, is the length-
normalized cumulative valence score of its individual tokens. We use the NRC-
VAD lexicon Mohammad (2018) to obtain valence scores of tokens.

We select the best candidate for the intriguing twist sentence
$\mathbf{s}^{*}$ such that:

$\mathbf{s}^{*}=\underset{i\in[1,b]}{\text{argmax}}\;A(\mathbf{s_{IT}}^{i})+\lvert
v(\mathbf{s_{IT}}^{i})-v(\mathbf{s_{1:IT-1}})\rvert$ (7)

##  5 Empirical Evaluation

In this section, we describe our experiments.

###  5.1 Experimental Setup

Dataset. For our experiments, we use the ROCStories dataset Mostafazadeh et
al. (2016), a large collection of 100k five-sentence ‘commonsense’ stories
about everyday events. We held out 1k stories each for validation and testing
and use the first sentence of every story as the prompt. We chose this dataset
because it allows us to assess the performance of our model’s ability to learn
from a collection of everyday life stories and improvise them to be
interesting. The short nature of these stories also makes the manual
assessment of narrative quality feasible during human evaluation which
otherwise would have been difficult. This focus on short stories, however,
does not limit the potential application of our model to longer narratives.

Our base storyteller is trained on the ROCStories dataset. The contextual
bandit model is trained in an unsupervised manner, relying on the internal
regret function.

Implementation Details. All hyperparameters were set based on the performance
on the validation set. We used $\alpha$ = 0.00015, $\beta$ = 0.0003 in Eqn. 4
and $\lambda=1.5$ in Eqn. 3. We trained the bandit model on single A5000 for
10 epochs and it chose between three beam sizes of $10$, $30$ and $60$.

Baselines. Our primary baseline is GPT2 fine-tuned on the RocStories dataset
since it is widely recognized for its story generation capabilities Brahman
and Chaturvedi (2020). We use GPT3 as a baseline to compare with a large
language model. For GPT3, we use the following prompt 222Please refer to Table
7 for more pormpt details. (after experimentation): “Continue writing an
interesting story using the following context, <context>. The total length of
the story should be five sentences. The total words limit is 60 words.""

Model | PPL $\downarrow$ | Uni $\uparrow$ | RUB $\uparrow$ | Aro $\uparrow$
---|---|---|---|---
GPT2 | 26.77 | 0.021 | 0.1546 | 0.45
AffGen-2 | 40.27 | 0.019 | 0.1556 | 0.51
GPT3 | $\textbf{18.90}^{*}$ | 0.028 | 0.1541 | 0.46
AffGen-3 | 25.66 | 0.029 | $0.1547$ |  0.53*
Table 1: Automatic evaluation of AffGen using Perplexity (PPL), UNION score
(Uni) Guan and Huang (2020), (RUB) score Tao et al. (2018), and Arousal score
(Aro). $\uparrow$ and $\downarrow$ indicate if higher or lower scores are
desirable. Bold fonts indicate best scores and * indicates statistical
significance ($p<0.01$). The results indicate that both versions of AffGen can
generate interesting stories without compromising coherence.

###  5.2 Automatic Evaluation

Table 1 presents a comparison between AffGen and baseline methods. We use two
versions of our model, AffGen-2 and AffGen-3. They use fine-tuned GPT-2 and
GPT-3 as the base storytellers (Section 4.2). We observe that both versions of
AffGen have higher perplexity (PPL) scores than the baselines. This, however,
is expected and does not imply low coherence because AffGen encourages using
low-likelihood words during the decoding process to generate interesting
content.

For a better evaluation of coherence, we consider the UNION (UNI) Guan and
Huang (2020) and RUBER (RUB) scores Tao et al. (2018). UNION is a reference-
free score specially designed for evaluating open-ended story generation
models. RUBER is a hybrid of referenced and unreferenced metric used for
evaluating dialog systems. We only use its unreferenced part to evaluate the
quality of a piece of text (story) generated in response to a query (the story
prompt). A higher value for these scores is better. We observe that for these
scores versions of AffGen either perform better than or comparable to the
baselines. This indicates that AffGen is capable of generating coherent
narratives.

For evaluating how interesting the stories are, we measure their per-token
Arousal score (Aro) (Eqn. 2) which quantifies their affect level. A higher
value is better for this score. We observe that both versions of AffGen
outperform the baselines with AffGen-3 achieving the highest score. This
indicates that AffGen generates more interesting stories.

Evaluation Criteria | Win | Lose | Tie
---|---|---|---
Coherence |  50.5* | 40.7 | 8.8
Emotional Engagement |  53.0* | 40.3 | 6.7
Empathy |  53.8* | 40.2 | 6.0
Interestingness |  54.9* | 41.1 | 4.0
Overall Preference |  52.7* | 39.6 | 7.7
Table 2: Human evaluation of AffGen vs GPT-3. AffGen generates better stories
across all measures. * indicates statistical significance (p<0.1 for coherence
and p<0.05 for others).

###  5.3 Human Evaluation

In order to assess the performance of AffGen, a comprehensive human evaluation
was conducted on the Amazon Mechanical Turk (AMT) platform. A total of 100
instances were randomly selected from our test set. We feed their initial
sentences as prompts for generating stories using AffGen-3 and GPT-3, our
stronger baseline. To eliminate any potential bias, the presentation order of
the two stories was randomized. The Turkers then selected the better of the
stories according to 6 criteria: coherence, emotional engagement, empathy,
interestingness, and overall preference. These criteria were chosen based on
prior research conducted by Chhun et al. (2022). The Turkers could also select
an _"equally good"_ option. The Turkers were explicitly instructed to solely
consider the given criterion when evaluating, except when expressing an
overall preference. In the appendix, Figure 4 showcases a screenshot of our
AMT setup. We specifically utilized Master annotators predominantly from
English-speaking countries (US, UK, Canada, and Australia). We evaluated 200
stories in total, and each pair was assessed by three different annotators. We
discuss the results shown in Table 2 below. All differences in this table are
statistically significant (p<$0.1$ for coherence and p<$0.05$ for others) and
the inter-annotator agreement is $0.58$ (moderate agreement).

Evaluation Criteria | Win | Lose | Tie
---|---|---|---
Coherence | 14.5 |  38.8* | 46.7
Emotional Engagement |  55.5* | 24.8 | 19.7
Empathy |  40.8* | 28.6 | 30.6
Interestingness |  45.3* | 26.3 | 28.4
Overall Preference | 45.3 | 35.7 | 19.0
Table 3: Human evaluation of AffGen vs ChatGPT. AffGen generates not as
coherent but more interesting and empathetic stories. * indicates statistical
significance (p<0.05).

Coherence evaluated the logical flow and connection between the different
elements of the story. For this criterion, judges found stories generated by
AffGen-3 to be more coherent than those generated by GPT-3 in 50.5% of
instances, while AffGen-3’s stories were considered less coherent in 40.7% of
cases. The remaining 8.8% resulted in a tie. This indicates that AffGen does
not compromise on coherence while generating stories.

Emotional Engagement evaluated how effectively a story conveys a range and
intensity of emotions that capture and hold the reader’s attention and create
a sense of emotional depth and complexity. For this criterion, judges found
stories generated by AffGen-3 to be more emotionally engaging than GPT-3 in
$53.0\%$ and less emotionally engaging in $40.3\%$ of the cases. This
demonstrates AffGen’s stronger ability to evoke emotions in readers.

Empathy evaluated if the story arouses the readers’ empathy for the
characters. The conflicts and challenges described in stories can create
situations that make the readers project their own emotions and thoughts onto
the characters, keeping them invested and engaged. For this criterion,
AffGen-3 outperformed GPT-3 by a large gap of $13.6\%$ ($53.8\%$ wins and
$40.2\%$ losses). This demonstrates that AffGen can generate emotionally
resonant content.

Interestingness evaluates the story’s ability to be compelling and engaging.
For this criterion also, AffGen-3 outperformed GPT-3 by a large gap of
$13.8\%$ ($54.9\%$ wins and $41.1\%$ losses). This demonstrates AffGen’s its
superiority in keeping the reader’s interest while generating stories.

Overall Preference Finally, we observed that overall, the judges preferred
AffGen over the baseline in $52.7\%$ of the cases (as compared to preferring
baseline over AffGen in $39.6\%$ cases).

To conclude, the human evaluation results provide strong evidence of the
superiority of the AffGen in various critical aspects of open-ended story
generation underlying its ability to generate interesting and engaging stories
while maintaining coherence.

###  5.4 Comparison with ChatGPT

In this section we compare AffGen with a large language model, ChatGPT
333OpenAI. (2023). ChatGPT (May 24th version) [Large language model].
https://chat.openai.com. We used a human evaluation setup similar to that
described in Section 5.3. These annotations were performed by expert
annotators who were students of literature theories. For generating stories
with ChatGPT, we experimented with different prompts and the final prompt is
shown in Table 7. Table 3 shows the results. Annotators expectedly found
ChatGPT’s stories to be more coherent. Our initial analysis also revealed
ChatGPT text to have more sophisticated structure. However, annotators found
AffGen’s stories to be significantly more emphathy-evoking and interesting.
Because of this, the annotators preferred AffGen over ChatGPT in the overall
preference.

| UNION | RUBER | Arousal
---|---|---|---
$\mbox{{AffGen}}_{10}$ | -0.007 | -0.012 | -0.018
$\mbox{{AffGen}}_{30}$ | -0.002 | -0.007 | 0.024
$\mbox{{AffGen}}_{60}$ | -0.005 | -0.006 | 0.047
$\mbox{{AffGen}}-AR$ | 0.002 | -0.001 | -0.070
Table 4: Performance of ablated versions of AffGen with static beam sizes
relative to AffGen. Subscripts indicate the beam sizes. A negative score
indicates that the ablated version did not perform as well as AffGen. These
results indicate that it is important to explore large beam sizes in a dynamic
manner to generate interesting and coherent stories.

###  5.5 Ablation Study

We now describe our ablation study in which we investigate the importance of
exploring different beam sizes and affective reranking. In our experiments
reported so far, we made AffGen explore three different beam sizes during
decoding. In this study, we design ablated versions of AffGen that only uses
one of the three beam sizes. We call them $\mbox{{AffGen}}_{10}$,
$\mbox{{AffGen}}_{30}$, and $\mbox{{AffGen}}_{60}$, where the subscript
indicates the beam size being used. The first three rows of Table 4 reports
the relative performance of these versions with AffGen. All models use fine-
tuned GPT-2 as the base storyteller. For all scores, a negative score
indicates that the ablated version did not perform as well as AffGen (and vise
versa). We can see that for most of the ablated versions, the UNION and RUBER
scores are negative. This means that the stories generated by the ablated
versions are less coherent than the full model. In terms of Arousal scores,
$\mbox{{AffGen}}_{10}$ produces less arousing stories than AffGen but
$\mbox{{AffGen}}_{30}$, and $\mbox{{AffGen}}_{60}$ produce more arousing
stories than AffGen. This aligns with our initial intuition that a larger beam
size helps the model generate more interesting content. However, because of
large but static beam sizes, the stories generated by these two versions were
less coherent than those generated by AffGen.

Next, we also consider another version of AffGen but without Affective
Reranking. The relative performance of this model is shown in the last row of
Table 4. We can see that the performance of this version is quite close to the
baseline. Also, while its coherence is comparable to AffGen, the arousal score
is particularly worse indicating the importance of this component in
generating interesting content.

Overall, we can draw two conclusions from this ablation study. First,
exploring large beam sizes and affective reranking can help in generating more
interesting content. Second, it is important to dynamically switch between
larger and smaller beams to balance interestingness and coherence.

###  5.6 Expansion to Longer Narratives

Our experiments have used RocStories which are short in nature. This focus on
short stories does not limit the potential application of our model to longer
narratives. Jolles (2017) points out that stories could be condensed into
“simple forms”. Story composition could be viewed as a process of expanding
these simple forms into presentable longer narratives. Table 10 presents
expanded AffGen-generated stories and compared with vanilla ChatGPT generated
stories. With the help of the five-sentence interesting plots produced by
AffGen, ChatGPT expand them into better stories comparing to vanilla ChatGPT
generated stories.

###  5.7 Dynamic Beam Sizing

We now investigate how the beam size changes as AffGen generates an
interesting sentence. Figure 2 shows the average beam size used to generate at
different positions of a typical sentence. We observe that AffGen is using
larger beam sizes for the first few tokens. Our manual analysis revealed that
the interesting words indeed appear earlier in a sentence, in general.

Since the model is capable of transitioning between beam sizes, we plot a heat
map of the transitions shown in Figure 3. Each cell shows the probability of
transitioning from beam size on Y axis to a beam size on the X axis. Darker
color indicates higher probabilities. We observe that in general, while AffGen
has a tendency to stick to a chosen beam size ($\sim 70\%$), it does
transition to different beam sizes about $30\%$ of the times indicating the
importance of switching between beam sizes.

Figure 2: Average beam size used to generate at different positions of a sentence.  Figure 3: Transitional probability between beam sizes.  GPT-3 |  Grayson wanted to bake his brother a birthday cake, so he got out his mom’s recipe book and started searching for the perfect one. He decided to go all out and make a four layer chocolate cake with cream cheese frosting. His brother was so impressed that he wolfed down 2 pieces in a row.
---|---
AffGen |  Grayson wanted to bake his brother a birthday cake. The first attempt turned out terribly bad and ruined. Grayson was determined to make the perfect cake for his brother’s birthday. Undeterred, Grayson started again from scratch and was finally able to make a delicious cake that his brother loved.
Human Explanation |  The story by AffGen is more emotionally expressive
Table 5: Sample stories generated by GPT-3 and AffGen. As indicated by the
judge, AffGen’s story is more emotionally engaging.

###  5.8 Qualitative Analysis

During the human evaluation (Section 5.3), when asking for preferences for the
stories, we also asked the judges to provide explanations for their choices.
We then analyzed the explanations to further analyze the stories generated by
AffGen. Table 5 show an example of stories generated by GPT-3 and AffGen for
the same input prompt as well as the human-provided explanation. While both
stories have a happy ending, AffGen’s story introduces a plot complication,
where the protagonist, Grayson’s, initial attempt to bake a cake fails. He
resolves the situation through determined efforts, creating a narrative of
perseverance. Compared to the baseline, the plot in AffGen’s story becomes
more complicated and has more ups and downs, which enhances the emotional
engagement and interest of the reader. The AMT judges noted that the AffGen’s
story was more emotionally expressive.

Table 8 in the Appendix provides more comparative examples of stories
generated by the baseline and AffGen and corresponding explanations. Analyzing
explanations for story pairs we found that the judges preferred AffGen’s
stories because they presented a shift in mood enhancing the affect they had
on the reader. AffGen’s stories also presented unexpected twists which provide
a relief from the story’s prevalent theme and increases its interest. In
contract, the baseline stories were banal and conflict-less. Sometimes
AffGen’s stories introduced a melancholic theme, but the judges still found
them pleasant. This aligns with the narratological theory presented by Massumi
(2002) who argues that there is a gap between the content and the effect on
the receiver’s end. As a result, audience often rate “sad” scenes in the film
as the “most pleasant”. Overall, AffGen was found to be better at generating
more emotionally captivating and interesting stories leading to to better
storytelling experience.

###  5.9 Error Analysis

Using the judges’ explanations provided during the human evaluation, we also
conduct an error analysis to identify issues encountered during story
generation by AffGen. Table 9 in Appendix shows some examples of story pairs
in which the judges did not prefer AffGen’s stories over GPT-3’s stories and
their explanations. We observe that while AffGen introduces an intriguing
twist in the story, it sometimes suffers from typical language modeling
challenges like repetitive phrases and ideas (Story 2) and incoherence. Often
the incoherence is caused by a lack of commonsense knowledge like sunglasses
cannot change eye colors (Story 1), and if a toy breaks, it cannot function
(Story 3). This aligns with the proposition made by Alhussain and Azmi (2021)
that coherence (and also causality) are fundamental in storytelling. Without
them, the story may disintegrate into inconsistent fragments.

##  6 Conclusion

This paper addresses the task of generating interesting stories. For this, we
present, AffGen, a language model that uses a novel contextual bandit-based
decoding mechanism. This new decoding mechanism enables the AffGen to
dynamically explore different beam sizes and rerank based on affective quality
of the text. Our experiments indicate that AffGen can generate interesting but
coherent narratives. Our ablation studies underscore the importance of dynamic
beam sizing and affective reranking, and our qualitative and error analysis
point to the strengths and weaknesses of our model. We hope that this ability
to compose interesting narratives can open new dimensions of computational
creativity, driving the generation of unique and captivating content at an
unprecedented scale and speed.

## Acknowledgement

We appreciate the reviewers for their insightful comments and suggestions.
Tenghao Huang and Muhao Chen were supported by the NSF Grant IIS 2105329, an
Amazon Research Award and a Keston Exploratory Research Award. Ehsan Qasemi
was supported by the DARPA MCS program under Contract No.N660011924033 with
the United States Office Of Naval Research. Computing of this work was partly
supported by a subaward of NSF Cloudbank 1925001 through UCSD.

## Limitations

Our study has the following limitations.

We assume a single sentence containing an intriguing twist can enhance a
story’s interestingness. This paper focused on how to generate that intriguing
twist. However, a story can potentially benefit from multiple interesting
sentences and future works can investigate into how frequently and where to
generate interesting content.

We adopted a simple data-driven approach for deciding where to put the
sentence that contains the intriguing twist. It samples from a distribution
learned from a collection of stories. Future work could work on more
sophisticated methods that consider the preceding narrative context for
deciding when to describe an interesting twist so that it integrates better
with the story being generated.

For practical purposes, the bandit model discretized beam sizes. However, beam
size is a continuous variable, and discretizing it can restrict the model from
exploring all possible values.

Our experiments used GPT-2 and GPT-3 as the base storyteller for generating
the stories. However, we see AffGen as a framework that could incorporate
other language models and future work can investigate this aspect.

Our experiments explored short and fictional narratives. Future work could
investigate advanced planning and strategies for composing longer stories or
non-fictional content.

Our dataset and experiments use only one language - English. We did not
investigate the model’s capabilities to generate stories in other languages.

## Ethical considerations

Our experiments use a publicly available dataset. Previous work Huang et al.
(2021) has shown that it contains gender-related biases and storytelling
models that use this dataset can replicate and amplify these biases. Our model
also encourages low-perplexity text, which could unintentionally encourage
biased, violent, or sexually explicit content. Since we have not employed any
bias or toxicity removal methods, applications of our work should control for
inappropriate content.

## References

  * Akoury et al. (2020) Nader Akoury, Shufan Wang, Josh Whiting, Stephen Hood, Nanyun Peng, and Mohit Iyyer. 2020.  STORIUM: A Dataset and Evaluation Platform for Machine-in-the-Loop Story Generation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6470–6484, Online. Association for Computational Linguistics.
  * Alhussain and Azmi (2021) Arwa I. Alhussain and Aqil M. Azmi. 2021.  Automatic story generation: A survey of approaches.  _ACM Comput. Surv._ , 54(5).
  * Bradley and Lang (1999) Margaret M Bradley and Peter J Lang. 1999.  Affective norms for english words (anew): Instruction manual and affective ratings.  Technical report, Technical report C-1, the center for research in psychophysiology.
  * Brahman and Chaturvedi (2020) Faeze Brahman and Snigdha Chaturvedi. 2020.  Modeling protagonist emotions for emotion-aware storytelling.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5277–5294, Online. Association for Computational Linguistics.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in Neural Information Processing Systems_ , 33:1877–1901.
  * Chhun et al. (2022) Cyril Chhun, Pierre Colombo, Fabian M. Suchanek, and Chloé Clavel. 2022.  Of human criteria and automatic metrics: A benchmark of the evaluation of story generation.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 5794–5836, Gyeongju, Republic of Korea. International Committee on Computational Linguistics.
  * Chung et al. (2022) John Joon Young Chung, Wooseok Kim, Kang Min Yoo, Hwaran Lee, Eytan Adar, and Minsuk Chang. 2022.  Talebrush: Sketching stories with generative pretrained language models.  In _Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems_ , CHI ’22, New York, NY, USA. Association for Computing Machinery.
  * Clark and Smith (2021) Elizabeth Clark and Noah A Smith. 2021.  Choose your own adventure: Paired suggestions in collaborative writing for evaluating story generation models.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3566–3575.
  * Delatorre et al. (2016) Pablo Delatorre, Barbara Arfe, Pablo Gervás, and Manuel Palomo-Duarte. 2016.  A component-based architecture for suspense modelling.
  * Fan et al. (2018) Angela Fan, Mike Lewis, and Yann Dauphin. 2018.  Hierarchical neural story generation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 889–898, Melbourne, Australia. Association for Computational Linguistics.
  * Freytag (1908) Gustav Freytag. 1908.  _Freytag’s technique of the drama: an exposition of dramatic composition and art_.  Scott, Foresman and Company.
  * Gabriel and Young (2011) Shira Gabriel and Ariana F Young. 2011.  Becoming a vampire without being bitten: The narrative collective-assimilation hypothesis.  _Psychological science_ , 22(8):990–994.
  * Gehrmann et al. (2019) Sebastian Gehrmann, Hendrik Strobelt, and Alexander Rush. 2019.  GLTR: Statistical detection and visualization of generated text.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 111–116, Florence, Italy. Association for Computational Linguistics.
  * Genette (1980) Gerard Genette. 1980.  Narrative discourse.  In _Narrative Discourse_. Cornell University Press.
  * Guan and Huang (2020) Jian Guan and Minlie Huang. 2020.  UNION: An Unreferenced Metric for Evaluating Open-ended Story Generation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9157–9166, Online. Association for Computational Linguistics.
  * Han et al. (2022) Rujun Han, Hong Chen, Yufei Tian, and Nanyun Peng. 2022.  Go back in time: Generating flashbacks in stories with event temporal prompts.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1450–1470, Seattle, United States. Association for Computational Linguistics.
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2019.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_.
  * Huang et al. (2021) Tenghao Huang, Faeze Brahman, Vered Shwartz, and Snigdha Chaturvedi. 2021.  Uncovering implicit gender bias in narratives through commonsense inference.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 3866–3873, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Jain et al. (2017) Parag Jain, Priyanka Agrawal, Abhijit Mishra, Mohak Sukhwani, Anirban Laha, and Karthik Sankaranarayanan. 2017.  Story generation from sequence of independent short descriptions.  _arXiv preprint arXiv:1707.05501_.
  * Jolles (2017) André Jolles. 2017.  _Simple forms: Legend, saga, myth, riddle, saying, case, memorabile, fairytale, joke_.  Verso Books.
  * Kasunic and Kaufman (2018) Anna Kasunic and Geoff Kaufman. 2018.  Learning to listen: Critically considering the role of AI in human storytelling and character creation.  In _Proceedings of the First Workshop on Storytelling_ , pages 1–13, New Orleans, Louisiana. Association for Computational Linguistics.
  * Langford and Zhang (2007) John Langford and Tong Zhang. 2007.  The epoch-greedy algorithm for contextual multi-armed bandits.  _Advances in neural information processing systems_ , 20(1):96–1.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670.
  * Lin and Riedl (2021) Zhiyu Lin and Mark Riedl. 2021.  Plug-and-blend: A framework for controllable story generation with blended control codes.  In _Proceedings of the Third Workshop on Narrative Understanding_ , pages 62–71, Virtual. Association for Computational Linguistics.
  * Liu et al. (2020) Danyang Liu, Juntao Li, Meng-Hsuan Yu, Ziming Huang, Gongshen Liu, Dongyan Zhao, and Rui Yan. 2020.  A character-centric neural model for automated story generation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 1725–1732.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Luo et al. (2019) Fuli Luo, Damai Dai, Pengcheng Yang, Tianyu Liu, Baobao Chang, Zhifang Sui, and Xu Sun. 2019.  Learning to control the fine-grained sentiment for story ending generation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6020–6026, Florence, Italy. Association for Computational Linguistics.
  * Massumi (2002) Brian Massumi. 2002.  _Parables for the Virtual: Movement, Affect, Sensation_.  Duke University Press, Durham, NC.
  * Meister et al. (2023) Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. 2023.  Locally typical sampling.  _Transactions of the Association for Computational Linguistics_ , 11:102–121.
  * Mohammad (2018) Saif Mohammad. 2018.  Obtaining reliable human ratings of valence, arousal, and dominance for 20,000 English words.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 174–184, Melbourne, Australia. Association for Computational Linguistics.
  * Mostafazadeh et al. (2016) Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. 2016.  A corpus and cloze evaluation for deeper understanding of commonsense stories.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 839–849.
  * Ouyang and McKeown (2015) Jessica Ouyang and Kathleen McKeown. 2015.  Modeling reportable events as turning points in narrative.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 2149–2158.
  * Peng et al. (2018) Nanyun Peng, Marjan Ghazvininejad, Jonathan May, and Kevin Knight. 2018.  Towards controllable story generation.  In _Proceedings of the First Workshop on Storytelling_ , pages 43–49, New Orleans, Louisiana. Association for Computational Linguistics.
  * Peng et al. (2022) Xiangyu Peng, Siyan Li, Sarah Wiegreffe, and Mark Riedl. 2022.  Inferring the reader: Guiding automated story generation with commonsense reasoning.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 7008–7029, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * PÉrez and Sharples (2001) Rafael PÉrez Ý PÉrez and Mike Sharples. 2001.  Mexica: A computer model of a cognitive account of creative writing.  _Journal of Experimental & Theoretical Artificial Intelligence_, 13(2):119–139.
  * Porteous and Cavazza (2009) Julie Porteous and Marc Cavazza. 2009.  Controlling narrative generation with planning trajectories: the role of constraints.  In _Interactive Storytelling: Second Joint International Conference on Interactive Digital Storytelling, ICIDS 2009, Guimarães, Portugal, December 9-11, 2009. Proceedings 2_ , pages 234–245. Springer.
  * Puduppully et al. (2019) Ratish Puduppully, Li Dong, and Mirella Lapata. 2019.  Data-to-text generation with content selection and planning.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 6908–6915.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Reagan et al. (2016) Andrew J Reagan, Lewis Mitchell, Dilan Kiley, Christopher M Danforth, and Peter Sheridan Dodds. 2016.  The emotional arcs of stories are dominated by six basic shapes.  _EPJ Data Science_ , 5(1):1–12.
  * Riedl and Young (2010) Mark O Riedl and Robert Michael Young. 2010.  Narrative planning: Balancing plot and character.  _Journal of Artificial Intelligence Research_ , 39:217–268.
  * Roemmele (2021) Melissa Roemmele. 2021.  Inspiration through observation: Demonstrating the influence of automatically generated text on creative writing.
  * Schraw et al. (2001) Gregory Schraw, Terri Flowerday, and Stephen Lehman. 2001.  Increasing situational interest in the classroom.  _Educational Psychology Review_ , 13:211–224.
  * Sims et al. (2019) Matthew Sims, Jong Ho Park, and David Bamman. 2019.  Literary event detection.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3623–3634, Florence, Italy. Association for Computational Linguistics.
  * Tan and Fasting (1996) Ed S Tan and Barbara Trans Fasting. 1996.  Emotion and the structure of narrative film: Film as an emotion machine.
  * Tao et al. (2018) Chongyang Tao, Lili Mou, Dongyan Zhao, and Rui Yan. 2018.  Ruber: An unsupervised method for automatic evaluation of open-domain dialog systems.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32.
  * Thompson (1933) William R Thompson. 1933.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3-4):285–294.
  * Thue et al. (2007) David Thue, Vadim Bulitko, Marcia Spetch, and Eric Wasylishen. 2007.  Interactive storytelling: A player modelling approach.  In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , volume 3, pages 43–48.
  * Vijayaraghavan and Roy (2023) Prashanth Vijayaraghavan and Deb Roy. 2023.  M-sense: Modeling narrative structure in short personal narratives using protagonist’s mental representations.  _arXiv preprint arXiv:2302.09418_.
  * Vijjini et al. (2022) Anvesh Rao Vijjini, Faeze Brahman, and Snigdha Chaturvedi. 2022.  Towards inter-character relationship-driven story generation.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 8970–8987, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Wang et al. (2021) PeiFeng Wang, Jonathan Zamora, Junfeng Liu, Fangyu Liu, Muhao Chen, and Xiang Ren. 2021.  Contextualized scene imagination for generative commonsense reasoning.  In _International Conference on Learning Representations_.
  * Wang et al. (2022) Zhilin Wang, Anna Jafarpour, and Maarten Sap. 2022.  Uncovering surprising event boundaries in narratives.  In _Proceedings of the 4th Workshop of Narrative Understanding (WNU2022)_ , pages 1–12, Seattle, United States. Association for Computational Linguistics.
  * Wilmot and Keller (2020) David Wilmot and Frank Keller. 2020.  Modelling suspense in short stories as uncertainty reduction over neural representation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1763–1788, Online. Association for Computational Linguistics.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016.  Google’s neural machine translation system: Bridging the gap between human and machine translation.
  * Yao et al. (2019) Lili Yao, Nanyun Peng, Ralph Weischedel, Kevin Knight, Dongyan Zhao, and Rui Yan. 2019.  Plan-and-write: towards better automatic storytelling.  In _Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence_.
  * Zhai et al. (2019) Fangzhou Zhai, Vera Demberg, Pavel Shkadzko, Wei Shi, and Asad Sayeed. 2019.  A hybrid model for globally coherent story generation.  In _Proceedings of the Second Workshop on Storytelling_ , pages 34–45, Florence, Italy. Association for Computational Linguistics.
  * Zhang et al. (2021) Hugh Zhang, Daniel Duckworth, Daphne Ippolito, and Arvind Neelakantan. 2021.  Trading off diversity and quality in natural language generation.  In _Proceedings of the Workshop on Human Evaluation of NLP Systems (HumEval)_ , pages 25–33, Online. Association for Computational Linguistics.
  * Zhang et al. (2022) Zhexin Zhang, Jiaxin Wen, Jian Guan, and Minlie Huang. 2022.  Persona-guided planning for controlling the protagonist’s persona in story generation.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3346–3361, Seattle, United States. Association for Computational Linguistics.
  * Zhao et al. (2022) Zhenjie Zhao, Yufang Hou, Dakuo Wang, Mo Yu, Chengzhong Liu, and Xiaojuan Ma. 2022\.  Educational question generation of children storybooks via question type distribution learning and event-centric summarization.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5073–5085, Dublin, Ireland. Association for Computational Linguistics.

##  Appendix A HIT Example

Figure 4 illustrates a screenshot of the form presented to the annotators on
the AMT.

Figure 4: Screenshot of the AMT survey used for human evaluations in Section
5.3

##  Appendix B Prompts for LLM

In our exploration, we investigated multiple prompt optimization techniques.
Initially, we utilized demonstrations as a potential avenue. Yet, as
illustrated in Table Table 6, it became evident that the resultant narrative
exhibited a significant degree of repetitiveness with the given demonstration.
An attempt to introduce diversity by leveraging a varied ensemble of
demonstrations did not yield improvements in reducing narrative redundancy.
Subsequently, we explored the incorporation of specific keywords within
prompts to guide the generative process. For instance, by prompting LLM "Write
a five-sentence interesting story with mystery", we observed that while such
specificity could yield captivating narratives, they bore a recurring thematic
redundancy. To exemplify, from a sample of ten stories generated using the
“mystery-enhanced” prompt, it was observed that seven out of ten generated
stories converged around the theme of a hidden secret being revealed towards
the conclusion. Representative narratives included scenarios such as a
photographer unveiling a mystery within a haunted lighthouse, a young woman
unearthing a concealed garden, and an individual discerning a hidden cache of
treasure, etc. In consideration of these findings, and without loss of
generality, we opted for the current prompt for subsequent generations.

Speaker |  Content
---|---
User |  Here is an interesting story. "Melissa invited Mark to the park for a picnic. The weather turned bad when thunder hit. Mark and Melissa decided to wait out the storm, and when the rain cleared, they had the most romantic picnic they’d ever experienced, watching the sun set over the park". Write an interesting story based on the context "Tom is going to fish on Saturday". The story should be five-sentence long and 60 words maximum.
ChatGPT |  Tom eagerly awaited Saturday, planning a day of fishing at his beloved lakeside spot. As dawn broke, he cast his line, lost in the tranquility. Suddenly, dark clouds loomed, and rain poured down. Seeking refuge under a tree, he met Sarah, another angler. The rain ceased, but Tom left with a newfound friend and a heartwarming memory.
Table 6: Attempt to optimize prompts through demonstration Task |  Prompts for LLM
---|---
GPT-3 infilling |  “Continue writing a story using the following context, <context>. The total length of the story should be <n> sentences. The total words limit is <n*12> words."
GPT-3 |  “Continue writing an interesting story using the following context, <context>. The total length of the story should be <n> sentences. The total words limit is 60 words."
ChatGPT |  “Write a five-sentence interesting short story using the following sentence as the first sentence: <context>."
Table 7: Prompts for Large Language Models

##  Appendix C Stories with Annotator Preferences

ID |  Baseline |  AffGen story |  Explanation
---|---|---|---
1 |  Melissa invited Mark to the park for a picnic. They had a great time, playing games and eating the delicious food she had prepared. They laughed, talked and made plans for their future. It was a perfect day that they would remember forever. |  Melissa invited Mark to the park for a picnic. The weather turned bad when thunder hit. Mark and Melissa decided to wait out the storm, and when the rain cleared, they had the most romantic picnic they’d ever experienced, watching the sun set over the park. |  <AffGen’s> story is more romantic.
2 |  Ella wrote her grandma a letter, filled with stories about her first day at school. She told her about the new friends she made, the lunch she had, and the fun she had learning. Grandma was so proud of her, and Ella couldn’t wait to get a letter back. |  Ella wrote her grandma a letter. Ella’s grandma wrote back with an unexpected news. Her favorite aunt died unexpectedly of cancer! Ella was saddened to hear the news, but was also comforted in knowing that her aunt had lived a full and happy life. |  Emotional condolences gives <AffGen’s> story an interesting and sad theme
3 |  Jen has a big test tomorrow and she’s determined to ace it. She spends hours studying, memorizing facts and theories, and rehearsing for the exam. She knows she’s ready and is confident that she’ll get the grade she desires. |  Jen has a big test tomorrow. Jen stayed up all night studying, but still felt unprepared. Her roommate surprised and excited with good news! She had found out that the professor had decided to give everyone an extra day to study for the test. |  The <Baseline> story has no bumps, it’s so banal
Table 8: More sample stories generated by GPT-3 and AFFGEN. As indicated by
the judge, AFFGEN’s story is more preferred by annotators in various aspects.

Table 8 shows more sample stories generated by GPT-3 and AFFGEN. We present
detailed qualitative analysis in Section 5.8.

##  Appendix D Error Analysis

Table 9 shows some examples of story pairs in which the judges did not prefer
AffGen’s stories over GPT-3’s stories and their explanations. We present
detailed qualitative analysis in Section 5.9.

ID |  Baseline |  AffGen story |  Explanation
---|---|---|---
1 |  Hazel wished for blue eyes every night, but her green gaze never changed. She felt like a different person with blue eyes; she was sure they’d bring her the confidence she craved. One day, she found a mysterious pair of blue contacts. She put them on, and it was like a whole new world opened up for her. |  Hazel’s eyes were green, but she really wanted blue eyes. The school offered special free sunglasses! Hazel was always envious of her friends’ blue eyes. With the school’s offer of free sunglasses, she was determined to make her dream come true. She put on the sunglasses and instantly felt like she had the most beautiful blue eyes in the world. |  The <Baseline> story is interesting
2 |  We went out last night, dancing and laughing the night away. I had the time of my life, and I felt like nothing could stop us. I never wanted the night to end, and I will never forget it. |  We went out last night. My girlfriend was excited to meet new friends! We had a great time, and my girlfriend made a few new friends. We stayed out late, and although I was tired, I was happy to see her having a good time. We both agreed it was a great night out and we can’t wait to do it again. |  The <AffGen > story has too much repetitions and is basically dull, the first one sounds very authentic
3 |  Joan chased Janet around the playground, yelling for her to give back his gum. Janet laughed and kept running, eventually out of sight. Joan stomped back to his friends, still mad but with a plan. He would get his gum back, no matter what. |  Joan got mad when Janet stole his gum. Not wanting to be outdone, Joan decided to steal something back. Her favorite toy car broke loose. Joan snatched Janet’s favorite stuffed animal and ran away with it. Janet chased after Joan, but she was too late, as the toy car had already reached its destination. |  <AffGen > story does not make sense.
Table 9: Error analysis ID |  Vanilla ChatGPT |  Expanded AffGen story
---|---|---
1 |  Melissa invited Mark to the park for a picnic. It was a sunny Saturday, perfect for their long-awaited rendezvous. Melissa had spent hours preparing sandwiches, fruit salads, and homemade lemonade. As they spread out the checkered blanket, Mark noticed a curious twinkle in Melissa’s eye. "What’s the surprise?" he asked. With a mischievous grin, she pulled out a vintage camera. "I thought we could capture memories today." They laughed, took goofy selfies, and snapped candid shots of each other. The sun cast a warm glow, creating a picturesque backdrop. Later, Melissa reached into her bag, revealing a small book. It was a scrapbook, filled with their past adventures together. Tears welled in Mark’s eyes as he flipped through the pages, reminiscing about their journey as friends turned soulmates. As the sun set, they stargazed, cherishing the memories they had created that day and adding another chapter to their beautiful story. |  Melissa had planned the perfect picnic for Mark at their favorite park. The day started off sunny, but as they laid out their blanket and unpacked their delicious spread, ominous clouds gathered overhead. Suddenly, a deafening clap of thunder echoed through the park, sending them scrambling for cover. Huddled under a nearby tree, Mark and Melissa exchanged nervous laughter. As the rain poured down around them, they found themselves sharing stories, dreams, and even a few stolen kisses. Time seemed to stand still as the storm raged on. When the last raindrop fell and the sun emerged from behind the clouds, Mark and Melissa emerged from their shelter, hand in hand. The park glistened with fresh rain, and the sky painted itself in shades of pink and orange as the sun began its descent. They sat down on their damp blanket, feeling closer than ever, and savored their makeshift romantic picnic as they watched the sun set over the park. It turned out to be an unforgettable day, filled with unexpected magic.
2 |  Ella wrote her grandma a letter, her small hand gripping the pencil tightly. She missed her visits to Grandma’s cozy cottage in the woods, where they would bake cookies and read stories by the crackling fireplace. In her letter, Ella poured her heart out. She shared her adventures, like the time she found a rainbow-colored caterpillar or built a secret fort in the backyard. She also drew pictures of her favorite memories, hoping Grandma could see them through the words. Days turned into weeks, and Ella anxiously checked the mailbox. Then, one sunny morning, a letter arrived. Excitement danced in her eyes as she tore it open. Inside was a heartfelt response, filled with love and wisdom, reminding Ella of the magical moments they had shared. With Grandma’s letter in her hand, Ella felt like she was holding a piece of their cherished cottage. She knew that no distance could break the bond they shared, and that their love would continue to grow through letters, just like the flowers in Grandma’s garden. |  Ella, with tears in her eyes, carefully penned a heartfelt letter to her beloved grandma, sharing her recent adventures and school triumphs. Weeks passed, and to her surprise, a letter from her grandma arrived, the envelope trembling in her hands. Ella eagerly unfolded the letter, only to be met with heart-wrenching news: her favorite aunt had succumbed to an unexpected battle with cancer. Tears streamed down Ella’s cheeks as she absorbed the painful words. Memories of her aunt’s infectious laughter and warm hugs flooded her mind. Despite the sorrow, she found solace in her grandma’s words. Her aunt had lived a life filled with boundless love, adventures, and cherished moments. She had been a beacon of positivity, spreading happiness wherever she went. Ella vowed to honor her aunt’s legacy by embracing life with the same zest and determination. Though her heart ached, she knew her aunt’s spirit would continue to inspire and guide her through the ups and downs of life.
3 |  Jen had a big test tomorrow, and her nerves were getting the best of her. She had spent countless hours studying, poring over textbooks, and reviewing notes, but anxiety still gnawed at her. The weight of the impending test loomed over her like a dark cloud. She tried to calm herself with deep breaths and a reassuring pep talk. "You’ve prepared as best as you can, Jen," she whispered to herself. "You know the material. You’ve got this." Jen’s friends, knowing the stress she was under, decided to surprise her. They showed up at her doorstep with a homemade dinner, colorful sticky notes of encouragement, and their unwavering support. Together, they created a cozy study space filled with laughter and motivation. As the night wore on, Jen’s anxiety began to subside. With her friends by her side, she felt a renewed sense of confidence and determination. She knew that no matter what the test held, she had the support of some incredible friends who believed in her. |  Jen had a big test tomorrow, and anxiety gnawed at her as she burned the midnight oil, pouring over textbooks and notes. Hours passed, her eyelids heavy, but she still felt unprepared. Doubt clung to her like a stubborn shadow. Just as the clock struck midnight, her roommate, Sarah, burst into the room with a grin that could light up a stadium. Breathless and excited, she shared the unexpected news: the professor had decided to give everyone an extra day to study for the test. Jen’s heart swelled with relief and gratitude. It was like a lifeline thrown to a drowning swimmer. Tears of joy welled up in her eyes as she hugged Sarah tightly. The universe had given her a second chance, and she wasn’t going to waste it. She spent the next day revising her notes and feeling more confident with every passing hour. When she finally walked into the exam hall, she was armed not only with knowledge but also with the indomitable spirit of resilience that had seen her through the long night.
Table 10: Comparison betwen vanilla ChatGPT stories and expanded AFFGEN’s
stories. We used ChatGPT for story expansion. we instructed the model with the
following prompt “Expand the story to 150 words. The story should be
interesting. <AffGen-generated plots>.”. While narratives generated by the
vanilla ChatGPT model tend to be straightforward and lack of dramatic flair,
the narratives produced by the expanded AffGen-generated approach exhibit
dramatic undertones, contributing to a more captivating reading experience.


# Color Counting for Fashion, Art, and Design

Mohammed Al-Rawi
ADAPT Centre  Trinity College Dublin
Dublin  Ireland
<EMAIL_ADDRESS>
###### Abstract

Color modelling and extraction is an important topic in fashion, art, and
design. Recommender systems, color-based retrieval, decorating, and fashion
design can benefit from color extraction tools. Research has shown that
modeling color so that it can be automatically analyzed and / or extracted is
a difficult task. Unlike machines, color perception, although very subjective,
is much simpler for humans. That being said, the first step in color modeling
is to estimate the number of colors in the item / object. This is because
color models can take advantage of the number of colors as the seed for better
modelling, to make color extraction further deterministic. We aim in this work
to develop and test models that can count the number of colors of clothing and
other items. We propose a novel color counting method based on cumulative
color histogram, which stands out among other methods. We compare the method
we propose with other methods that utilize exhaustive color search that uses
Gaussian Mixture Models (GMMs) and K-Means as bases for scoring the optimal
number of colors, in addition to another method that relies on deep learning
models. Unfortunately, the GMM, K-Means, and Deep Learning models all fail to
accurately capture the number of colors. Our proposed method can provide the
color baseline that can be used in AI-based fashion applications, and can also
find applications in other areas, for example, interior design. To the best of
our knowledge, this work is the first of its kind that addresses the problem
of color-counting machine.

Figure 1: Color count is subjective. The dress has 9 distinct colors, but
people have different opinions.

##  1 Introduction

Automated color extraction is getting more attention in digital art work and
design. This includes, but is not limited to, fashion and decoration and vast
number of applications, like recommender systems. Digital images are the media
that are normally used to mimic real world objects. However, problems of color
degradation and the vast number of colors available makes automated color
estimation a difficult problem [7, 3]. The first step to assist models
accurately extract colors is knowing the how many colors are there in a scene
or object. While this might initially appear to be quite simple, in reality,
it is a challenging problem to overcome. In fact, estimating the number of
colors in a scene is highly subjective even for humans (even after excluding
protans and deutans; people with some form of color blindness).

Color counting is a highly intelligent task as it requires dual cognitive
modes; recognizing colors while discarding spatial information, and counting
intelligence. While color counting has long been used to teach toddlers, there
are still not enough resources nor models to keep machines on par with
toddlers color counting and matching skills. Hence, the computer vision
research community has devoted their efforts to extracting colors directly
from the images, by skipping the color counting step. In this direction,
clustering algorithms have widely been used, [4, 5, 2, 10, 15, 7], such that
the number of colors must be known / given a prior. A more recent work
proposed a multistage approach to automatically extract the color values;
clustering with large number of colors in the first stage followed by merging
the clustered colors, based on the hue values, in the second stage [1].

Classification techniques have also been used to categorize colors as in [11,
14, 13]. Classification techniques have the disadvantage that they are limited
to a predefined number of tagged colors, and worse, the problem of memorizing
the colors and shapes they see at training (the generalization dilemma).
Moreover, treating color modeling as a classification will lead to failure of
keeping pace with the millions of colors used in images [6].

This work addresses the ”color counting” problem and thus differs from
previous methods that jump straight into color extraction. By knowing the
exact number of colors, one can easily extract colors from images, as this
will make color extraction deterministic.

##  2 Methods

##  3 Color Distribution

Color images usually suffer from severe distortions distortions. Color
printing quality, color interlacing, photographic geometry, amount of light,
image compression, and even imaging devices affect how colors appear in images
and the amount of noise they may contain. Al-Rawi and Joeran showed in [1]
that the colors of a multichnnel (i.e., RGB) image can be modeled as a
Gaussian Mixture Model (GMM) prior distribution, which is given by:

$p(\mathbf{x})=\sum_{i=1}^{K}\phi_{i}\mathcal{N}(\mathbf{x}|\text{\boldmath$\mu$}_{i},\mathbf{\Sigma_{i}}),$
(1)

where

$\mathcal{N}(\mathbf{x}|\text{\boldmath$\mu$}_{i},\mathbf{\Sigma_{i}})=\\\
\frac{1}{\sqrt{(2\pi)^{K}|\mathbf{\Sigma_{i}}|}}\exp{\Big{(}-(\mathbf{x}-\text{\boldmath$\mu$}_{i})^{\text{T}}\mathbf{\Sigma_{i}}^{-1}(\mathbf{x}-\text{\boldmath$\mu$}_{i})\Big{)}},$

and $K$ denotes the number of colors, and the $i_{\text{th}}$ vector component
is characterized by normal distributions with weight
${\displaystyle\phi_{i}}$, mean ${\boldsymbol{\mu_{i}}}$ and covariance matrix
${\boldsymbol{\Sigma_{i}}}$. The color distribution becomes extremely
complicated when the clothing item has more than one color and because of the
possibility of frequency deviation of colors during the imaging process. In
this case, the GMM prior distribution will be given by:

$p(\mathbf{x})=\sum_{i=1}^{K^{\prime}}\phi_{i}\mathcal{N}(\mathbf{x}|\text{\boldmath$\mu$}_{i},\mathbf{\Sigma_{i}})),$
(2)

where $K^{\prime}$ denotes the total number of colors, or model components,
such that $K^{\prime}=K+K_{f}$, and $K_{f}$ denotes the number of new (but
fake) colors generated during image acquisition. To simplify notations and
without loosing generality, we deffer in what comes below from using the
$K^{\prime}$ notation and use $K$ instead. The GMM is also disrupted due to
the use of 8 bits for each pixel in the image, as it leads to truncating the
pixel values close to the lower-bound and / or upper-bound, i.e. values close
to 0 or 255 for an 8-bit per pixel image. Therefore, there will always be some
form of incorrectness in color distributions in real-world images containing
values close to these extreme values; the so we call truncated tail effect.

###  3.1 Color counting via GMMs

As aforementioned, GMMs denote the mathematical, and natural, distribution of
colors in images. This suggests that one can model colors as a GMM to estimate
the correct number of colors. The hypothesis is that the optimal number of
colors, $K$, yields to the optimal 1) score value computed as the per-sample
average log-likelihood of the given color values; 2) Akaike’s information
criterion (AIC); 3) the Bayesian information criterion (BIC), and 4) the
Jensen-Shannon distance (JS-distance) between two GMMs randomly sampled from
the given data. Testing these hypotheses requires running exhaustive search
processes up to a pre-defined maximum number of colors in the image; by
varying $K$ from 1 to $K_{max}$. The optimal number of components will
correspond to some extreme values of AIC or BIC [12], or JS distance. This is
widely known in the multivariate literature as estimating the number of
components [8]. However, while the literature shows some success in using
these scores to estimate the number of components, these studies mostly rely
on simulated data [12]; opposed to real data that has some form of distortion
and non-trivial noise, as in the color distribution case. Although the GMMs
computational burden is very high, obtaining a correct color count via GMMs
would be highly beneficial. We shall refer to this method as CC-GMM.

(a) multi bar, #colors=16(24) (b) 8 bars, #colors=4(8)

(c) chair, #colors=9(4) (d) waves, #colors=15(24)

(e) jacket, #colors=5(1) (f) dress, #colors=9(9)

(g) white-shirt, #colors=19(1) (h) sweatshirt, #colors=18(4)

Figure 2: Color counting using Gaussian Mixture Model, CC-GMM. Score shown on
the y-axis denotes the AIC (Akaike’s information criterion). We estimated the
GMM score over K=1, 2,…, 25. The sub-caption #colors=$x$($T$) denotes the
number of colors, where $x$ is estimated and ($T$) is the ground-truth. As
GMMs are stochastic, running the experiments again will lead to different
results each time.

(a) multi bar (b) #colors=19(24)

(c) 8 bars (d) #colors=6(8)

(e) chair (f) #colors=4(4)

(g) waves (h) #colors=19(24)

(i) jacket (j) #colors=1(1)

(k) shirt (l) #colors=4(4)

(m) pants (n) #colors=1(1)

(o) dress (p) #colors=8(9)

(q) sweatshirt (r) #colors=5(4)

(s) white-shirt (t) #colors=2(1)

Figure 3: Color counting using our proposed method, CC-CH. For each
consecutive pair (, a and b), we have the image in (a) and its distribution in
(b). The sub-caption #colors=$x$($T$) denotes the number of colors, where $x$
is estimated and ($T$) is the ground-truth. We scaled the images to fit in the
figure; that is, they are of different resolutions. Best viewed in color.

###  3.2 Color counting via K-Menas

It has been shown in [9] that K-Means clustering can be used to approximate a
GMM. Although K-Means clustering is computationally problematic (it is in fact
NP-hard), efficient heuristic algorithms quickly converge to a local minima.
We will use K-Means clustering as another method to estimate the number of
colors in images. We use the opposite of the value of the data (image) on the
K-means objective function. We shall refer to this method as CC-KM.

###  3.3 Color counting via deep convolutional neural networks

We use self-supervised learning to train a deep convolutional neural network
(DCNN) for it to work as a color counting model. The DCNN is a classifier, and
the self learning is done by randomly generating shapes of clothing and other
items that have different colors and shapes. The generator passes the image
and the number of colors to the DCNN. We use EfficientNet in PyTorch to model
the DCNN. We shall refer to this method as CC-DCNN.

###  3.4 Color counting via cumulative histogram

In this method, we calculate the histogram of each band of the RGB image.
Then, we arrange the histogram as a triplet vector that depends on the extreme
values in each channel. We further compress the histogram by removing the
outliers, which we define by the use of Principle Component Analysis (PCA).
Our hypothesis in this method is that colored pixels in the image will produce
peaks in the cumulative triplet vector which we compute as mentioned above.
Removal of outliers is an important step that controls the color count, aimed
at removing a few peaks resulting from noise and distortion. The number of
peaks will therefore give an estimate of the number of colors in the image. We
shall refer to this method as CC-CH

Figure 4: Score denotes the JS-distance between two GMMs calculated for the
sweatshirt image.

##  4 Results

We collected a benchmark of 100 different color images of fashion and art
articles that have a distinctive number of colors. We use sklearn to model
GMMs, and PyTorch for DCNNs. Due to lack of space, we visually demonstrate
experiments selected from the results that conform with whole dataset. We firs
use the K-Means algorithm from the sklearn package. The values of K ranges
from 1 to 25. The K-Means algorithm, although faster than the GMM, is
unsuccessful in estimating the number of colors. This is because the score
curve lacks distinctive extreme values that identify the number of colors. In
addition, the DCNN has also been unsuccessful in counting the colors. While
the DCNN converged well on the training set, it failed on the testing set;
which means it has serious overfitting issues due to memorizing color features
and focusing on the spatial information (shape) and not the targeted
objective, which is color count. The GMM approach results in slightly better
performance than the two aforementioned methods, yet, it is still far from
being accurate as shown in Fig. 2. Moreover, GMMs are also stochastic by
nature; for example, over 10 runs on the multi-bar image shown in Fig. 3,
estimated color counts are {15, 11, 6, 16, 24, 4, 7, 10, 14, 5}. We present in
Fig. 4 the JS-distance between two GMMs for the sweatshirt image, which has
four colors. We randomly split the image data into two halves, each used to
estimate one GMM, then we sample 100000 samples from each GMM to calculate the
distance. The curve has no distinctive behaviour, and the minimum distance is
found at K=24. Further experiments with other images are consistent with this
conclusion. This indicates that the JS-distance is not effective to estimate
the number of colors. There are some other methods that we have tested that
also were unsuccessful, and the discussion goes beyond the limit of this work;
such as Bayesian Gaussian Mixture Models, Siamese DCNNs, mean of GMMs /
K-Menas distributions over several iterations, and probing changes in
clusters’ sizes. Our proposed method, CC-CH, emerged after exploring all these
aforementioned approaches. Results depicted in Fig. 3 show CC-CH is very
promising . We can see that it can result in a correct number of colors, or a
number close to the correct number of colors in the image.

##  5 Conclusion

We proposed a novel method to count the number of colors in RGB images. Our
cumulative histogram method is not only more accurate than the GMM, but also
100 folds faster. Over the benchmark we used, the average execution time of
the GMM is 100 seconds, while the method we propose needed less than 1 second.
We implemented the experiments on the CPU and we can still have more reduction
in execution time if we are to use the GPU. Furthermore, our proposed method
is deterministic and does not depend on some random initialization parameters.
That being said, one gets exactly the same answer at every run. The GMMs, on
the other hand, need to randomly initialize the parameters of their
components. Therefore, GMMs are highly stochastic and one might not be able to
replicate the results or even ensure the correct ones. Moreover, our
experiences show that color counting via GMMs, although slightly better than
K-Means and DCNNs, is incorrect and unreliable.

## Acknowledgement

This research was conducted with the financial support of European Union’s
Horizon 2020 programme under the Marie Skłodowska-Curie Gran Grant Agreement #
801522 at the ADAPT SFI Research Centre at Trinity College Dublin. The ADAPT
SFI Centre for Digital Content Technology is funded by Science Foundation
Ireland through the SFI Research Centres Programme and is co-funded under the
European Regional Development Fund (ERDF) through Grant # 13/RC/2106_P2. This
work was also supported by TCHPC (Research IT, Trinity College Dublin).

## References

  * [1] Mohammed Al-Rawi and Joeran Beel.  Probabilistic color modelling of clothing items.  In Nima Dokoohaki, Shatha Jaradat, Humberto Jesús Corona Pampín, and Reza Shirvany, editors, Recommender Systems in Fashion and Retail, Lecture Notes in Electrical Engineering, chapter 2, pages 21–40. Springer Nature, Springer Nature Switzerland AG Gewerbestrasse 11, 6330 Cham, Switzerland, 2021.
  * [2] Hoel Le Capitaine and Carl Frélicot.  A fast fuzzy c-means algorithm for color image segmentation.  In Proceedings of the 7th conference of the European Society for Fuzzy Logic and Technology (EUSFLAT-11), pages 1074–1081, Aix-les-Bains, France, 2011. Atlantis Press.
  * [3] Wen-Huang Cheng, Sijie Song, Chieh-Yun Chen, Shintami Chusnul Hidayati, and Jiaying Liu.  Fashion meets computer vision: A survey, 2020.
  * [4] Julie Delon, Agnès Desolneux, Jose Luis Lisani, and Ana Belén Petro.  Automatic color palette.  In IEEE International Conference on Image Processing 2005, volume 2, pages II–706, Genova, Italy, 2005. IEEE.
  * [5] Julie Delon, Agnès Desolneux, Jose Luis Lisani, and Ana Belén Petro.  Automatic color palette.  Inverse Problems and Imaging, 1(2):265–287, 2007.
  * [6] Deane B Judd and Günter Wyszecki.  Color in Business, Science and Industry.  Wiley Series in Pure and Applied Optics (third ed.). New York: Wiley-Interscience, New York, NY, 1975.
  * [7] Ju-Mi Kang and Youngbae Hwang.  Hierarchical palette extraction based on local distinctiveness and cluster validation for image recoloring.  In Proceedings of 2018 ICIP, volume I, pages 2252–2256, 2018.
  * [8] Daeyoung Kim and Byungtae Seo.  Assessment of the number of components in gaussian mixture models in the presence of multiple local maximizers.  Journal of Multivariate Analysis, 125:100–120, 2014.
  * [9] Jörg Lücke and Dennis Forster.  k-means as a variational em approximation of gaussian mixture models.  Pattern Recognition Letters, 125:349 – 356, 2019.
  * [10] Sharon Lin and Pat Hanrahan.  Modeling how people extract color themes from images.  In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI ’13, page 3101–3110, New York, NY, USA, 2013. Association for Computing Machinery.
  * [11] Marco Manfredi, Costantino Grana, Simone Calderara, and Rita Cucchiara.  A complete system for garment segmentation and color classification.  Machine Vision and Applications, 25:955–969, 2013.
  * [12] Geoffrey J. McLachlan and Suren Rathnayake.  On the number of components in a gaussian mixture model.  In Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, volume 4, page 341–355. John Wiley & Sons, Inc., USA, Sept. 2014.
  * [13] Vacit Oguz Yazici, Joost van de Weijer, and Arnau Ramisa.  Color naming for multi-color fashion items.  In Álvaro Rocha, Hojjat Adeli, Luís Paulo Reis, and Sandra Costanzo, editors, Trends and Advances in Information Systems and Technologies, pages 64–73, Cham, 2018. Springer International Publishing.
  * [14] Lu Yu, Lichao Zhang, Joost van de Weijer, Fahad Shahbaz Khan, Yongmei Cheng, and C. Alejandro Párraga.  Beyond eleven color names for image understanding.  Machine Vision and Applications, 29:361–373, 2017.
  * [15] Qing Zhang, Chunxia Xiao, Hanqiu Sun, and Feng Tang.  Palette-based image recoloring using color decomposition optimization.  IEEE Transactions on Image Processing, 26:1952–1964, 2017.