\section{Introduction}

Games are often complex systems with a myriad of moving parts. In such games, designers provide a large selection of game objects, such as cards, skills or equipment, allowing players to play the game in many different ways with varying combinations of these game objects. However in competitive games where players are motivated to win, players often focus on gathering particular combinations of objects that maximize their perceived chances of winning. Balancing these game objects is one of the most important tasks for game designers. In an unbalanced game, there may be a single degenerate strategy that is unbeatable or it may be impossible to play a particular character class well. Such a game is essentially broken and experienced players tend to quickly lose interest.

Published by Blizzard, \emph{Hearthstone} is a popular collectible card game released in 2014 that contains over 2000 collectible cards. During a game, two players take turns trying to reduce the health of the opposing hero to zero. For any given game, a player chooses 30 cards to build a deck, and only these cards are accessible during gameplay. Cards from the deck are randomly drawn at each turn. Naturally, players try to pick combinations of cards that they think have the best chance of beating an opponent. While Blizzard sometimes edits existing cards (i.e.\ through \emph{nerfs} and \emph{buffs}), the longevity and popularity of the game indicates that the company is invested in keeping it well-tuned.

In part because there are millions of subscribed players for Hearthstone, when new cards are released or existing cards edited, these parts of the strategy space are quickly explored by the players. Even a single misbalanced card could result in large disruptions to the \emph{metagame} (i.e.\ popular decks and their win rates against each other). A balanced metagame promotes a variety of competitive decks. While Blizzard balances the game through a combination of deep domain knowledge, in-house playtesting, and by examining the metagame as it develops through data visualization, in a game with over 2000 cards, there is still a need for computational tools to help. The question this paper addresses is how AI methods can facilitate game balancing in a game as complex as Hearthstone.

This paper explores several methods for computationally balancing a collectible card game. While the focus here is on Hearthstone, the idea is that it is an exemplar for collectible card games. Methods in this paper could potentially apply to other games where players must choose from a wide collection of game objects to customize their characters.

The approach to game balancing in this paper is three-pronged. The first approach is based on the simplified assumption that decks should perform approximately equally against each other.  For this first experiment, we encode a set of card changes as an individual in an evolutionary algorithm, where good changes are those that equalize win rates between decks. This is a single objective optimization problem, where the fitness of individuals depends on how close the win rates for each deck matchup deviate from 50\%.

While after launch, some changes to a complex game are necessary to achieve balance, even small changes to cards can have a big effect on the metagame. Furthermore, such changes often require players to rethink their previous strategies, and in the case of Hearthstone they may need access to cards that they have yet to collect. Experiment 2 is a multi-objective optimization problem based on the same idea of balance as the first (i.e.\ decks achieve balance when they reach a 50\% win rate). However, one additional objective is to minimize changes.

While Experiment 1 and Experiment 2 holistically evolve changes for the entire set of cards, Experiment 3 explores the impact of targeting specific cards to balance. Focusing on a single deck, we first rank cards by how often the deck won if the player drew or played that card. Then we examine the impact of nerfing each card individually on the deck's win rates. We observe that nerfing cards that originally had a higher win rate when drawn (and to a lesser extent, win rate when played) tends to impact the deck's win rate more, suggesting that this could be a reasonable metric to guide  the search for effective balance changes in future experiments.

\section{Related Work}

Relevant background is described in this section including the game Hearthstone, previous approaches using AI in Hearthstone, and previous approaches of AI-techniques to balance games.

\subsection{Hearthstone}

Hearthstone is a Collectible Card Game (CCG) by Blizzard where players play as a hero from one of nine classes battling against each other to reduce their opponent's health points (HP) from a starting HP of 30 to 0. Before joining a match, players select a class and  build a deck of exactly 30 cards from a pool of class-specific cards plus a pool of neutral cards, which are available to any class.  Most cards cost a certain amount of mana, the game's main resource, to play. The amount of mana available on a player's turn starts at 1, and automatically increases by 1 per turn, to a maximum of 10.

Each card can be of one of four types. \emph{Minion} cards are player-controlled characters that can attack other minions or the enemy hero, dealing damage equal to their attack attribute. They are destroyed when dealt damage equal to or greater than their health attribute. \emph{Spell} cards are single-use effects applied when played, such as drawing cards, increasing health, summoning minions, dealing damage. \emph{Weapons} are a card type that a hero can equip to attack other minions or the opposing hero directly with, rather than through minion or spells. The last card type is a \emph{Hero} card, introduced in the sixth expansion. The hero cards replace a player's hero, sometimes changing the hero's properties.

Additionally, choosing a class grants the player the ability to use that Hero's power, which is a small effect (such as dealing 2 damage to the enemy hero or losing 2 life in order to draw a card) that can be used once per turn by paying 2 mana, but without requiring a card in hand.

Decks can be loosely characterized by their favored strategy. The first common strategy this paper is concerned with is  ``Aggro", which attempts to win the game quickly, typically with a combination of cheap Minions and direct damage Spells, without trying to kill many opposing Minions. ``Control" attempts to win the game later, after controlling the board by using removal Spells and defensive Minions. Other strategies exist, such as ``Combo", which attempt to assemble a combination of highly synergistic cards which provide a large advantage or even win the game when played together. This paper focuses on the Aggro and Control strategies.

\subsection{AI and Hearthstone}

Being a popular and complex game, Hearthstone has been the subject of study by multiple researchers. While many efforts are focused on building gameplaying AIs~\cite{da2018hearthbot, dockhorn2018predicting,grad2017helping, santos2017monte,stiegler2017symbolic,swiechowski2018improving,zhang2017improving}, this subject is tangential to our work. To play the game, we use a breadth-first search together with a gamestate evaluating heuristic to approximate common player strategies such as Aggro or Control playstyles. This agent is part of the SabberStone~\footnote{SabberStone - https://github.com/HearthSim/SabberStone} engine we use to emulate the game. While sub optimal, the agent performance is sufficient in terms of quality and time for our experiments.

Evolutionary algorithms have been employed in Hearthstone primarily to search the deck space~\cite{bhatt2018exploring, fontaine:gecco19,garcia2016evolutionary,garcia2018automated}. The problem of creating a deck is parallel to that of playing the game. Finding a high performance card set is a non-trivial task that is beyond the scope of this work. Rather, we utilize the decks found by the quality diversity algorithm Map-Elites~\cite{mouret2015illuminating} when searching the space of cards from the Basic and Classic sets of Hearthstone~\cite{fontaine:gecco19}. Furthermore, deck building in Hearthstone has been investigated outside the scope of evolutionary algorithms~\cite{chen2018q,stiegler2016hearthstone}, and evolutionary algorithms have been used to create decks for other games, such as Magic: The Gathering~\cite{bjorke2017deckbuilding}.

Win rate prediction for Hearthstone decks has been explored~\cite{jakubik2017evaluation}, specially with the introduction of the AAAI Data Mining Competition~\cite{janusz2018toward}. Most approaches are not applicable to the problem we are introducing, considering they rely on being trained in games played with the unchanged card stats.

Other works have targeted understanding the intricacies of the design by learning from replays~\cite{bursztein2016legend} or at evaluating card uniqueness~\cite{janusz2018investigating}. An utility measurement to analyze card and deck usefulness in an effort to create a balance model has been proposed~\cite{jin2018proposed}. While this work treats cards individually, we are interested in the impact that changing the cards can have on prebuilt decks with preset strategies.

Cards have been procedurally generated for Magic the Gathering from partial information~\cite{summerville2016mystical}. There is relation between card generation and card tuning and balancing, but our approach is not aimed at generating new content, but rather evaluating and changing the pre-existing cards.

\subsection{AI for Game Balancing}

Game balancing is a difficult task. As such, techniques using AI to facilitate or to try to automate the process have been introduced. Most work uses agents to collect data in order to evaluate the design and balance~\cite{de2017ai, silva2018exploring}.

Card games have been the focus of some of the most relevant work. Mahlmann et al. used an evolutionary algorithm to search a cardset in Dominion that would provide balanced gameplay~\cite{mahlmann2012evolving}. Jaffe et al. developed a tool that calculates balance metrics of the gameplay between restricted and standard agents, and applied such to an educational card game~\cite{jaffe2012evaluating}. Volz et al. used a multi-objective algorithm to create Top Trump decks, with win rate as one of the dimensions~\cite{volz2016demonstrating}. While these approaches are similar to the work we present, they are applied to games with lower complexity.

Other works have targeted understanding balance in a scope closer to ours. Krucher tried to automatically balance cards that were initially randomly generated~\cite{krucher2015algorithmically}. Our approach is not to make individual cards balanced, but investigate if we can make changes to the card attributes in order to balance win rate between different decks. Zook et al. investigated the impacts that changing a single card has on the design of Cardonomicon, a simplified version of Hearthstone~\cite{zook2018learning}. While their objective is to analyze how these changes reflect on player behavior, our work is targeted at understanding the level of impact changing cards can have on deck performance.

\section{Methodology and Definitions}

\subsection{Metagame and Match-ups}

 A \emph{Metagame} can be broadly defined as the set of factors outside the rules that affects the game experience. This can include the set of game objects (such as cards) that are collected by players, or less tangible factors such as heuristics on how to play a certain game situation (e.g. whether to prioritize killing Minions or dealing damage to the opposing Hero versus a specific deck) and even historical information about a certain player (e.g., upon facing the same player twice in a row in online match-making, there is a high likelihood they are playing the same deck as before).

This paper refers to a more narrow definition of metagame, focusing on the set of decks that players can build, their popularity, and expected win rate when each deck is paired against another. The metagame evolves over time as people discover new decks, and at any given time is simply called \emph{the meta} by the community. Sometimes decks that only differ by a few cards are referred to as a single deck or deck archetype. We avoid the distinction of decks and archetypes by assuming each deck is represented by a unique deck list.

A pair of decks and the expected win rate against each other is called a match-up, and the match-up between decks A and B is said to be favorable for deck A if deck A's win rate is above 50\%. Note that draws are possible, but rare in Hearthstone, so games that end in draws are ignored in our work. The match-up between two equal, or very similar decks is sometimes called \emph{the mirror}. We can also talk about a deck's win rate against the meta, which is the average win rate of all that deck's match-ups, weighted by the prevalence of the opposing deck in the metagame:
$$ W_i = \sum_{j=1}^N{W_{ij}P(j)}$$
where $W_i$ represents deck i's win rate versus the metagame, N is the total number of different decks, $W_{ij}$ is deck i's win rate versus deck j and $P(j)$ the probability of being paired with deck j in a match, also sometimes called deck j's prevalence or j's share of the metagame. Note that it includes mirror matches. In this paper, we consider $P(j) =\frac{1}{N}$ for all decks, meaning $W_i$ is simply the average win rate across all match-ups.

\subsection{Balance}

While determining whether or to what degree a game is balanced is a subject of debate by the community, one possible measure is that the metagame is more balanced as the win rates of all its match-ups approach 50\%. An alternative measure is that every deck's win rate versus the meta should be as close as possible to 50\% or that all decks take a similar share of the metagame. This definition allows us to formulate balance metrics based on the deck's pairwise match-ups, the deck's win rate against the meta, or a deck's prevalence. Because in most of our experiments we are dealing with metagames consisting of three distinct decks, we decided, for simplicity, to use pairwise match-up win rates as our metric. This will be defined in section~\ref{sec:exp1}.

While our experiments use this metric, this should not be taken as endorsement of this metric in the general case. A more nuanced view is that it is not the designer's job to perfectly balance all game objects, even if it were possible. Gutshera~\cite{gutschera} argues, in the context of balancing content for games such as Magic: The Gathering, that it can be desirable to have some game elements that are not viable (where viable means ``not strictly dominated''), because figuring out which objects are valuable can be an appealing aspect of gameplay. However, the viable objects are still expected to be balanced, while accepting that some game objects will be non-viable.

While in our experiments there are a fixed set of decks represented by a single deck list of thirty cards, the view above is especially relevant in more complex scenarios where this assumption doesn't hold. In this case, it might be important to consider not just how close each deck gets to perfect balance according to the chosen metric, but also how many reasonably balanced decks there are out of all possible decks, and how diverse these balanced decks are to each other.

We have so far assumed implicitly that the objects being balanced are decks and that we want decks to perform similarly to each other under the chosen metric. However, it is possible to balance around other objects. One could, for example, desire that a large number of different cards are playable and viable. One could also talk about the balance of strategies or heuristics, searching for metagames where a large number of strategies or heuristics are viable.

\subsection{Card Changes to Promote Game Balance}\label{changes}

While significant resources are expended during design to ensure balance, sometimes content creators misjudge the power level of a card when releasing a new set. Sometimes players find a hidden interaction between cards that leads to undesirable game states. Sometimes a metagame simply stagnates, with players converging on a consensus of what is the best deck, which halts innovation and leads to repetition. Regardless of the reason, sometimes action by the game's designers is necessary to restore balance, which is usually referred to as a balance change~\cite{ham2010rarity}.

In electronic games, a balance change typically consists of changing the attribute of one or more game objects to change their power level or to stop specific undesirable interactions between game objects. A change in card properties that makes a card more valuable is called a \emph{buff}, while one that decreases its value is called a \emph{nerf}.

In physically distributed card games (such as Magic: The Gathering), changing a card's attribute is less practical, as it would lead to players owning an outdated copy of a card, which they might not even be aware has been changed. In such games, balance changes typically take the form of banning (prohibiting the use in sanctioned tournaments) or restricting (decreasing the number of copies that can be in a deck) cards.

In this paper, we consider balance changes defined by the increase or decrease in one or more of the following attributes of one or more cards:
\begin{itemize}
    \item \textbf{ Cost} is the amount of mana required to play each card.

    \item \textbf{Attack} is a property of minion and weapon cards and indicates how much damage each deals.

    \item \textbf{Health} is a property of minion cards and indicates how much damage the minion can sustain before it is destroyed.

    \item \textbf{Durability} is a property of weapon cards that indicates the number of times a weapon can be played.

\end{itemize}

An increase in mana cost or a decrease in attack or health is a nerf while a decrease in mana cost or an increase in attack or health is a buff.

Note that cards are fully defined by more than these properties and other properties of a card can be subject to balance changes. As an example, the neutral card, Patches the Pirate, was nerfed by losing the keyword \textit{Charge}, which allowed it to attack on the same turn it was summoned. Nevertheless, we choose to focus on mana cost, attack, health, and durability as they are shared by all cards of the appropriate type, have a simple representation and allow us to  express the majority of balance changes to cards in Hearthstone. Reference \cite{cardchanges:web19} lists all of the patches and updates of Hearthstone since those implemented in the alpha phase of development. Each patch catalogues all changes to cards, including changes that were motivated by balance.

\subsection{Magnitude of Balance Changes}

We define the absolute magnitude of a balance change as the sum of the absolute value of each change in attribute, weighted by that attribute's weight:

$$M = \sum{abs(C_i) * w_i}$$

Where $C_i$ is the change in an attribute and $w_i$ equals 2 if the attribute is mana cost and 1 otherwise. We use the weight $W$ because, in practice, changing a Minion's attack or health by 1 tends to have a smaller impact than changing its mana cost by 1. In fact, it is common that, for Minions that perform similar functions but differ by 1 mana, the more expensive minion will have +1/+1 in attack/health. For this reason, we consider a change in mana cost to have double the magnitude as a change in attack or health/Durability.

\section{Experimental Setup}

While several previous approaches explore the space of possible decks and creating competitive decks \cite{bhatt2018exploring, fontaine:gecco19,garcia2016evolutionary,garcia2018automated,chen2018q}, this paper investigates the impact of small changes to card properties on the deck's meta performance, where meta performance is measured as the average win rate against the other evolved decks.

Experiment 1 aims to maximize balance in the metagame through evolutionary search, where chromosomes are changes in properties of a card represented as integer vectors. Because it is important for players that their cards maintain some consistency, Experiment 2 searches for the minimal changes to balance the metagame. Experiment 2 replicates Experiment 1 with an added criteria of minimizing the magnitude of changes to the properties of the cards. Experiment 3 further isolates the deck space to target cards that need nerfs or buffs to minimize changes while simultaneously balancing the meta-game. The approach in this paper is to start from a set of competitive decks proposed by Fontaine et al.~\cite{fontaine:gecco19} and through evolution alter the properties of the cards to achieve balance in deck performance.

\begin{table*}
\begin{tabular}{|p{1.8cm}|p{.7cm}|p{.7cm}|p{.85cm}|p{.85cm}|p{.95cm}|p{.95cm}|p{.7cm}|p{.7cm}|p{.85cm}|p{.85cm}|p{.95cm}|p{.95cm}|p{.7cm}|}
\hline
& Exp1 Hunter & Exp1 Hunter & Exp1 Paladin & Exp1 Paladin & Exp1 Warlock & Exp1 Warlock & Exp2 Hunter & Exp2 Hunter & Exp2 Paladin & Exp2 Paladin & Exp2 Warlock & Exp2 Warlock & Win rate vs. \\
& (Aggro) & (Control) & (Aggro) & (Control) & (Aggro) & (Control) & (Aggro) & (Control) & (Aggro) & (Control) &  (Aggro) & (Control) & Meta \\
\hline
Exp1:Hntr.(A) & 0.50 & 0.06 & 0.11 & 0.03 & 0.08 & 0.05 & 0.49 & 0.06 & 0.10 & 0.07 & 0.08 & 0.04 & 0.14 \\ \hline
Exp1:Hntr.(C) & 0.94 & 0.50 & 0.39 & 0.28 & 0.57 & 0.37 & 0.93 & 0.35 & 0.46 & 0.25 & 0.53 & 0.40 & 0.50 \\ \hline
Exp1:Pldn.(A) & 0.89 & 0.60 & 0.49 & 0.41 & 0.59 & 0.57 & 0.88 & 0.66 & 0.44 & 0.48 & 0.53 & 0.52 & 0.59 \\ \hline
Exp1:Pldn.(C) & 0.96 & 0.71 & 0.59 & 0.50 & 0.72 & 0.58 & 0.95 & 0.59 & 0.61 & 0.43 & 0.72 & 0.67 & 0.67 \\ \hline
Exp1:Wrlk.(A) & 0.91 & 0.42 & 0.42 & 0.28 & 0.50 & 0.36 & 0.88 & 0.36 & 0.37 & 0.29 & 0.38 & 0.38 & 0.46 \\ \hline
Exp1:Wrlk.(C) & 0.95 & 0.63 & 0.42 & 0.42 & 0.63 & 0.50 & 0.91 & 0.41 & 0.43 & 0.35 & 0.60 & 0.55 & 0.57 \\ \hline
Exp2:Hntr.(A) & 0.51 & 0.07 & 0.13 & 0.05 & 0.11 & 0.09 & 0.50 & 0.07 & 0.10 & 0.09 & 0.10 & 0.05 & 0.16 \\ \hline
Exp2:Hntr.(C) & 0.94 & 0.64 & 0.33 & 0.35 & 0.64 & 0.50 & 0.9 & 0.50 & 0.46 & 0.33 & 0.57 & 0.52 & 0.56 \\  \hline
Exp2:Pldn.(A) & 0.90 & 0.54 & 0.55 & 0.39 & 0.62 & 0.56 & 0.89 & 0.53 & 0.49 & 0.45 & 0.57 & 0.47 & 0.58 \\  \hline
Exp2:Pldn.(C) & 0.93 & 0.75 & 0.51 & 0.57 & 0.70 & 0.65 & 0.92 & 0.58 & 0.55 & 0.50 & 0.69 & 0.74 & 0.67 \\  \hline
Exp2:Wrlk(A) & 0.91 & 0.47 & 0.46 & 0.27 & 0.61 & 0.40 & 0.89 & 0.43 & 0.42 & 0.31 & 0.51 & 0.45 & 0.51 \\ \hline
Exp2:Wrlk(C) & 0.96 & 0.60 & 0.47 & 0.33 & 0.60 & 0.45 & 0.95 & 0.45 & 0.52 & 0.26 & 0.55 & 0.51 & 0.56 \\ \hline
\end{tabular}
\caption{Results from Pairwise Play of Twelve Competitive Decks 10,000 Games}
\label{table:initial10k}
\end{table*}

In Fontaine et al. \cite{fontaine:gecco19}, twelve decks were evolved for the hunter, paladin, and warlock classes playing an aggro and control strategy with two different opponent decks in evolution. These decks were evolved through a variant of the Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) algorithm~\cite{mouret:nature15} called Map-Elites with Sliding Boundaries, and were first played against a pool of starter decks composed of basic cards, and then played against those evolved to beat these starter decks. The evolved decks had access to cards in the basic and classic sets.

We then decided to evaluate all these decks against each other. Performance is measured by pairwise match-ups, each played $10,000$ times as shown in table~\ref{table:initial10k}. Interestingly, gameplay heuristics have a significant impact on deck performance: all decks perform better when evolved with the Control heuristic. This is especially visible when comparing the performance of Hunter decks evolved with the Aggro and Control heuristic

For this paper, to reduce the space of decks, we selected one deck and heuristic combination for each hero is from these twelve competitive decks. These  will be our focus on for the remainder of the paper:Exp1: Hunter (Aggro), Exp2: Paladin (Control), and Exp2: Warlock (Control).

Table~\ref{table:smallmeta} shows each of these three deck's performance when considering only the match-ups against each other. From this point on, we will call the ``Small Meta" the meta-game consisting of these three decks or the decks evolved from them in the subsequent experiments. We will denote ``Original Meta" the meta-game defined by the original twelve decks.

\begin{table*}[]
\centering
\begin{tabular}{|l|l|l|l|l|}
\hline
\textbf{Deck Name}     & \textbf{Exp1: Hunter (Aggro)} & \textbf{Exp2: Paladin (Control)} & \textbf{Exp2: Warlock (Control)} & \textbf{Individual vs. Meta} \\ \hline
Exp1: Hunter (Aggro)    & 0.5                          & 0.0666                          & 0.0384                          & 0.2018666667                  \\ \hline
Exp2: Paladin (Control) & 0.9311                       & 0.5                             & 0.7381                          & 0.7227333333                  \\ \hline
Exp2: Warlock (Control) & 0.9622                       & 0.2648                          & 0.5                             & 0.578                         \\ \hline
\end{tabular}
\caption{The performance of each deck in the Small Meta}
\label{table:smallmeta}
\end{table*}

\subsection{Experiment 1: Meta Evolution}\label{sec:exp1}

The first experiment searches to maximize game balance by evolving properties of cards in the decks chosen to represent a low, high and medium level of competitiveness: Exp1: Hunter (Aggro), Exp2: Paladin (Control), Exp2: Warlock (Control). While there are 30 cards in each deck, there are 64 unique cards. Six are spells, 56 are minions, and two are weapons. Spell cards are adjusted through their mana cost properties, while minions and weapons are adjusted through their mana cost, attack, and health properties. While spell cards can potentially be altered through the magnitude of their effects, many effects are unique (e.g. Tirion Fordring's equip a 5/3 weapon, Archmage Antonidas's whenever you cast a spell, add a 'Fireball' spell to your hand). Future work aims to categorize the effects of these spells to evolve more comprehensive changes.

In these experiments, the population is composed of chromosomes that represent the changes to all card properties in the small meta. Here chromosomes are integer vectors of length 180 as there are three decks with sixty four unique cards. Six cards are spells with only one variable property, and 58 are weapon or minion cards with three variable properties. Therefore the length of a chromosome is calculated as 180 = 58 $\times$ 3 +  6 $\times$ 1. Each gene is an integer representation of changes to either mana cost, attack, or health properties in the range of $[-3,3].$ When Blizzard changes these card properties they often change in the range of $[-2,2]$, but in rare situations properties are changed by three. For these experiments, despite what a chromosome may indicate, card properties are bounded between $[0,10]$ .

The evolutionary parameters for the experiment are a population of size 100, crossover rate of 35\%, and mutation of 20\%. Crossover is two-point, and mutation changes each number with probability of 5\%. Parents are selected through tournament selection of size 3. Individuals are evaluated by first making changes to the cards in the decks and then playing 300 games in total, with 100 match-ups between Exp1: Hunter (Aggro) and Exp2: Paladin (Control), Exp2: Paladin (Control) and Exp2: Warlock (Control), and Exp1: Hunter (Aggro) and Exp2: Warlock (Control). Fitness is calculated as follows:
$$F = \sqrt{\frac{4}{3}\sum_{i<j}{(w_{ij}-0.5})^2}$$
where $w_{ij}$ is the win rate of deck $i$ vs. deck $j$, and $\frac{4}{3}$ is a constant for normalization so that $F \in [0,1]$. That is, fitness is calculated as the (normalized) Euclidean distance between the vector of candidate match-up win rates and an ideal vector where all entries equal $0.50$. Using this definition, our original small meta set has a fitness of $0.78$. While ultimately a good and playable meta decks would have some intransitivity \cite{bhatt2018exploring} (that is, deck A might beat deck B, which beats C, which in turn beats A), the goal for candidates is to achieve complete balance with a fitness of $0.00$ meaning that no changes are necessary to achieve a win rate of $0.50$.

\begin{figure}
    \centering
    \includegraphics[width=.4\textwidth]{Exp1Results.png}
    \caption{Average, Min and Max fitness over 12 generations. Baseline is the fitness of the original Small Meta, 0.78}
    \label{fig:exp1results}
\end{figure}

The results of experiment 1 are shown in figure~\ref{fig:exp1results}. The best individual across all generations had a fitness of $0.0062$, showing that the algorithm can find card change combinations leading to an almost perfectly balanced metagame.

However upon examining this individual, the sum or magnitude of all changes to the 180 properties is 403, where the average individual in that generation had a magnitude of 402 (out of a maximum of 540). While these changes steer the meta to balance, the number of these changes would overwhelm a human designer and frustrate the game's players.

\subsection{Experiment 2: Multi-Objective Evolution} \label{sec:exp2}

\begin{figure}
    \centering
    \includegraphics[width=.4\textwidth]{ParetoFront.png}
    \caption{A scatter of points representing the individuals achieved through multi-objective optimization, with the Pareto Front (non-dominated individuals) highlighted in red. The seeded individuals (representing a metagame with no changes and the best metagame from Experiment 1) are highlighted in yellow. }
    \label{fig:paretofront}
\end{figure}

While experiment 1 found individuals that could steer the meta decks to a 50\% win rate, the distribution of the changes would be potentially cause large disruptions in current gameplay. Experiment 2 therefore aims to minimize changes while still achieving balance. Changes are measured by the sum of the values in the vector of an individual called its \emph{absolute magnitude}.

To minimize the magnitude of changes, a multi-objective algorithm called NSGA2 \cite{deb2000fast} is run. An individual is dominated when there exists another that is strictly better (i.e. smaller values for changing card properties) across all card properties of the cards. NSGA2 identifies the set of non-dominated individuals when considering both the meta balance metric (defined by the distance of the pairwise win rates to $0.50$) and the magnitude of changes metric. Selection is performed by the NSGA2 algorithm, and  crossover and mutation follow the same rates and procedures of experiment 1 (i.e. two point crossover rate of 35\% and a mutation rate of 20\%. Each run was initialized with 98 randomly generated chromosomes, plus the best individual from experiment 1 (which had a balance metric of 0.0062 and a magnitude of changes of 402) and an individual representing the unchanging meta (which has a balance metric of 0.43 and, trivially, zero magnitude of changes).

An individual's  multi-objective fitness (MOF) is defined as
$$MOF_i = (F_i,M_i)$$
where $F$ is the previously defined meta balance metric and $M_i$ the magnitude of changes metric. Note that both $F$ and $M$ are metrics we are attempting to minimize. An individual $i$ is non-dominated if, for every other individual $j$ in the population, one of the conditions below hold:
\begin{itemize}
    \item $F_i < F_j$ or $M_i < M_j$ or ($F_i = F_j$ and $M_i = M_j$)
\end{itemize}

We executed two independent runs of this experiment, for 32 and 47 generations respectively.  Figure~\ref{fig:paretofront} shows the scatterplot of all individuals of both runs, with the set of individuals that were not dominated by any individual in each experiment (also called the Pareto Front) highlighted in red. Our individual with the lowest value for the meta balance dimension $F$ had a multi-objective fitness of $(0.008,154)$, and the individual with lowest value for the magnitude of changes dimension $M$ was the starting individual with no changes, who had a multi-objective fitness of  $(0.43,0)$.

Note that our best individuals in Experiment 1 and Experiment 2 had about an equal balance score (0.006 in Experiment 1 and 0.008 in Experiment 2). Interestingly, this is not the same individual as the best individual from Experiment 1, which achieved a still low meta balance of 0.063 on this run. This is probably due to noise in the evaluation, which consist of playing 300 games per match-ups and comparing the win rates with the ideal 50\%. Nevertheless, we managed to achieve similar meta balance with less than half the magnitude of changes when compared to experiment 1 (154 versus 402).

\subsection{Experiment 3: Heuristics for selecting cards to balance}\label{section:individualnerfs}

After showing in experiment 2 that a balanced metagame can be found with a smaller magnitude of changes than that in experiment 1, experiment 3 aims to predict which cards to target with a nerf or buff to achieve the best possible balance with the least possible changes.

For this experiment we define two auxiliary metrics that apply to cards in a deck, both listed by sites that aggregate Hearthstone replays (e.g. \url{http://HSReplay.net}). \emph{Win Rate when Played} (WRP) considers only games where at least one copy of the card is played. It is defined as the number of games won when at least one copy of the card is played divided by the total number of games where at least one copy of the card is played. It is a way to measure the positive ``impact" of a card once it is played.

\emph{Win Rate when Drawn} (WRD) considers only games where at least one copy of the card is drawn (not necessarily played). It is defined as the number of games won where at least one copy of a card was drawn divided by the total number of games where at least one copy of that card was drawn. It is a way to measure the positive ``impact" of seeing a card in your hand, regardless of whether or not it was ever played over the course of the game. When compared to WRP, WRD tends to favor cheaper or more versatile cards, because cards that are expensive or situational tend to have a disproportionate impact in the game when successfully played, to compensate for the times where it cannot be played.

We define a card's \emph{Win Rate after Nerf} (WRN) as the deck's win rate when forced to play with a nerfed version of the card which costs one additional mana. This is meant to serve as a measure of a nerf's impact: the lower the WRN after nerfing a card, the more our targeted nerf was successful in balancing a dominating deck.

To compute WRN, we took every card in the Exp2 Paladin (Control) deck and, for each card ran a set of 10000 matches between Exp2 Paladin (Control) and the other 11 decks of the Original Meta, while increasing the nerfed card's mana cost by 1. Our hypothesis was that nerfing cards with higher WRP or WRD would have a bigger negative impact in the win rate of the deck. We also expected the impact to be greater for WRD, as WRD paints a more realistic picture of a card's power by taking into account situations where a card was drawn but could not be played.

For space considerations, we are unable to show the full relation of WRD, WRP and WRN for all the cards in the deck list. The card with highest WRD is Consecration, a four mana card that deals two damage to all enemy minions and the enemy hero, which serves as a check against an opponent who gets ahead on the board. The card wish highest WRP is Tirion Fordring, an expensive eight mana minion with high 6/6 stats, Taunt, Divine Shield (which prevents the first source of damage) and the ability to summon a powerful weapon when it dies. Interestingly, Consecration ranks third by WRP and Tirion Fordring ranks third by WRD. While they are both powerful cards, we suspect Consecration has WRD $>$ WRP because it is typically best played from an unfavorable position, when the opponent is ahead on board. Meanwhile, Tirion Fordring likely has WRP $>$ WRD due to it being high cost, making drawing it in the early turns a liability.

Figure~\ref{fig:WRDandWRP} shows the relationship, across all cards, of both WRD and WRP with the deck's win rate after the corresponding nerfs (WRN). Figure~\ref{fig:WRPversusWRN} shows a small negative correlation between WRP and WRN Figure~\ref{fig:WRDversusWRN} shows a slightly bigger negative correlation between WRD and WRN. A negative correlation means the deck's win rate tends to fall more sharply when a card with high WRP or WRD is nerfed, which indicates that nerfs to those cards are more effective at balancing a deck that is too dominant. While we make no claims of statistical significance of these findings, the data seems to support our initial assumptions.

\begin{figure}
    \centering
    \subfigure[WRP versus WRN]
    {
        \includegraphics[scale=.4]{WRPversusNerf.png}
        \label{fig:WRPversusWRN}
    }
    \subfigure[WRD versus WRN]
    {
        \includegraphics[scale=.4]{WRDversusNerf.png}
        \label{fig:WRDversusWRN}
    }
    \caption{A scatterplot of WRP (a) and WRD (b) versus WRN}
    \label{fig:WRDandWRP}

\end{figure}

\section{Conclusion and Future Work}

This paper proposes a method for representing balance changes in a card game such as Hearthstone and seeks to minimize the number of changes through evolutionary search while maximizing metagame balance (section~\ref{sec:exp1}). While this approach successfully tuned cards to create a balanced metagame, the tuning process in experiment 1 suggested a disruptive magnitude of changes.
To compensate, in experiment 2 card changes are evolved through multi-objective evolution with the NSGA2 algorithm
to find balance changes that simultaneously optimize for balanced metagames and minimized magnitudes of these changes.

The experiments in section~\ref{section:individualnerfs} gives us some indication that win rate when played (WRP) and especially win rate when drawn (WRD) are metrics that can help choose which cards to nerf, which in the future we expect to use as a heuristic to guide the search for a set of maximally-balancing, minimally-disruptive balance changes.

However all experiments assume that a player's deck remains the same after balance changes are implemented. However, players often respond to balance changes by altering their decks. Future work will explore deck composition in response to a balance changes by evolving decklists after applying the balance changes compared to the original metagame.

Finally, this paper defines a balanced metagame as one where all decks have close to 50\% win rate against all other decks. However, future work will explore options like optimizing a deck's \emph{average} win rate against all decks, but permit deck intransitivity \cite{de2018generatingprefloppoker,de2018generatingfullpoker} by allowing differences in a deck's efficacy against \emph{particular} other decks. We could also incorporate some metric of deck diversity (such as the number of shared cards) and require the metagame to have a large number of decks that are not only balanced with regard to their win rate, but also highly diverse. One final approach would be to formulate the problem of choosing a deck from the metagame as a two-player game in extensive form, and compute the Mixed Nash Equilibrium~\cite{nash1951non} for this game, requiring that, in the equilibrium, a large number of decks are non-dominated and have a reasonable chance of being picked.

\bibliographystyle{IEEEtran}


\section{Introduction}
\label{intro}

Recent advances in deep learning promote the innovation of many intelligent systems and applications such as autonomous driving and image recognition. Tracking the changes of focus for deep learning engineers and researchers is helpful to identify current emerging deep learning-related topics. In this work, we choose Stack Exchange to collect experimental dataset due to its popularity among the developers and researchers~\cite{DBLP:conf/kbse/HuangXXLW18}.

Previous topic tracking approaches~\cite{DBLP:conf/icml/BleiL06,DBLP:conf/icdm/AlSumaitBD08,DBLP:journals/tist/HeLGW13} are mainly based on Latent Dirichlet Allocation (LDA) \cite{DBLP:journals/jmlr/BleiNJ03}. For example, the work~\cite{DBLP:conf/icdm/AlSumaitBD08} proposes an On-line Latent Dirichlet Allocation (OLDA) model to capture the evolution of topics, where only the topic distribution of documents in the prior one time slice is considered for inferring the topics in current time slice. In~\cite{DBLP:journals/tist/HeLGW13}, the authors focus on modeling sentiment and topic changes synchronously, and the topics in all the prior time slices are involved during inferring the current topic distribution. In~\cite{DBLP:journals/corr/abs-1805-00457}, the proposed approach also selects sentiment words for each topic based on Dynamic Topic Model (DTM)~\cite{DBLP:conf/icml/BleiL06}.

Inspired by the recent work~\cite{DBLP:conf/icse/GaoZLK18}, where an adaptively online latent Dirichlet allocation approach, named IDEA, is introduced to track user opinions in user feedback, and outperforms the OLDA approach~\cite{DBLP:conf/icdm/AlSumaitBD08}, we propose a new framework \textbf{IEDL} for \textbf{I}dentifying \textbf{E}merging \textbf{D}eep \textbf{L}earning-related topics. The difference between IDEA and our approach lies in the combination styles of the prior topic distributions. In IDEA, the similarities between the topics in previous time slices and those in the previous one time slice are taken into account for inferring the topics in current time slice, while we introduce an exponential decay function in a time window. Besides, we propose a novel topic labeling approach based on the unique characteristics of Stack Exchange posts.

The experimental results on 7,076 Stack Exchange posts verify the effectiveness of IEDL in detecting topic changes and topic labeling.

The contributions of our paper are elaborated as below.
\begin{itemize}
\item We propose a framework called IEDL to automatically track topic changes and identify emerging topics from deep learning-related posts in Q\&A forum effectively.
\item We propose a novel topic interpretation method, which improve the topic coherence dramatically.
\item We visualize the variations of the captured (emerging) topics along with time slices, with the emerging ones highlighted.
\end{itemize}

\section{Methodology of IEDL}
IEDL mainly contains two parts: Emerging topic detection and automatic topic interpretation.

\subsection{Emerging Topic Detection}
In this section, we aim to detect the emerging topics of current time slice by considering the topics in previous time slices. We first introduce how we use online topic modeling to capture the topic evolutions with time going by. Then we present how we discover the emerging topics
(anomaly topics).

\subsubsection{Online Topic Modeling}
\begin{figure}[ht]
\begin{center}
\centerline{\includegraphics[width=0.85\columnwidth]{AOLDAP2.png}}
\caption{Our online topic modeling approach.}
\label{aoldap}
\end{center}
\end{figure}

The preprocessed posts are divided by time, denoted as $M=\{M^1, M^1,...,M^t...\}$ (where $t$ indicates $t$-th month in our experiment), and each post is treated as one document. The prior distributions over document-topic ($\alpha$) and topic-word distributions ($\beta$) are defined initially. $K$ represents the number of the topics, while $\phi^t_k$ is the probability distribution vector for the $k$-th topic over all the input posts. We also introduce a predefined parameter - window size $w$, which refers to the number of previous time slices to be considered for analyzing the topic distributions of the current time slice. The overview of the model is shown in Figure\ref{aoldap}.

We adaptively integrate the topic distributions of the previous $w$ time slices, denoted as $\{\phi^{t-1},...,\phi^{t-i},...,\phi^{t-w}\}$, for generating the prior $\beta^t$ of the $t$-th time slice. Since the popularity of a topic always lasts for a time period, compared to IDEA~\cite{DBLP:conf/icse/GaoZLK18} which only considers the similarity between topic distributions, we think the topics discussed last month are more related to current topics compared to those mentioned several months before. Therefore, an exponential decay factor $\mu$ is added, multiplying the similarity between topics $\gamma$ to determine the influence. And now the adaptive integration refers to sum of the topic distributions of different time slices with different weights $\gamma^i$ and $\mu^i$:
\begin{equation}
    \beta^t_k = \sum^w_{i=1}\mu^i\gamma^{i}_k\phi^{t-i}_k
\end{equation}
where $i$ denotes the $i$-th previous time slice $(1 \leq i \leq w)$. We denote the weight $\gamma^i$ as the similarity of topic distributions between the $(t$$-$$i)$-th time slice and the $(t$$-$$1)$-th time slice, which is calculated by the softmax function:
\begin{equation}
    \gamma^i_k = \frac{\exp(\phi^{t-i}_k \cdot \beta^{t-1}_k)}{\sum^w_{j=1}\phi^{t-j}_k \cdot \beta^{t-1}_k}
\end{equation}
 where the dot product $(\phi^{t-i}_k \cdot \beta^{t-1}_k)$ computes the similarity between the topic distribution $\phi^{t-i}_k$ and the prior of the $(t$$-$$1)$-th time slice $\beta^{t-1}_k$. $\mu^i$ is calculated by a simple exponential decay function:
\begin{equation}
    \mu^i = \exp(-\lambda i)
\end{equation}
where $i$ means the $i$-th time slice before the current, and $\lambda$ is a predefined exponential decay coefficient.

\subsubsection{Anomaly Discovery}
Based on the topic distribution captured by online topic model, we regard anomaly topics, which present obvious distinctions compared to those of the previous time slices, as emerging topics. To calculate the distinction of the $k$-th topics between two successive time slices, we implement the classic Jensen-Shannon (JS) divergence\footnote{\url{https://en.wikipedia.org/wiki/Jensen\%E2\%80\%93Shannon\_divergence}}. If we take $\phi^t_k$ and $\phi^{t-1}_k$ as an example:
\begin{equation}
\begin{split}
    D_{JS}(\phi^{t}_k||\phi^{t-1}_k) = \frac{1}{2}&D_{KL}(\phi^{t}_k||M) +\\ &\frac{1}{2}D_{KL}(\phi^{t-1}_k||M)
\end{split}
\end{equation}
where $M=\frac{1}{2}(\phi^{t}_k+\phi^{t-1}_k)$.And the Kullback-Leibler (KL) divergence $D_{KL}$ is utilized to measure the difference from one probability distribution $P$ to another $Q$:
\begin{equation}
    D_{KL}(P||Q) = \sum_i P(i)\log\frac{P(i)}{Q(i)}
\end{equation}
where $P(i)$ is the $i$-th item in P. The higher the JS divergence is, the larger distinction the two topic distributions have. To find anomaly topics, we set a threshold by leveraging a typical outlier detection method \cite{DBLP:journals/widm/RousseeuwH11}. For each time slice, the topics with divergences higher than the threshold are regarded as anomaly topics.

\subsection{Automatic Topic Interpretation}
The dataset we use are questions asked in Stack Exchange, which have two significant attributes ``votes" and ``views". Users can manually click the ``like" button or the ``dislike" button to show their preference, while high ``votes" represents this is a valuable question. And ``views" shows how many users or tourists have visited this page, which refers to the popularity of this post. To make good use of these two attributes, we develop a novel method for deep learning related posts interpretation. We denote it as Quality Score:
\begin{equation}
\begin{split}
    SC&ORE_{qua}(l) =\\ &\exp(-\frac{1}{\ln(v_l+1)\ln(r_l+1)}- \eta\cdot\frac{1}{\ln(h_l+1)})
\end{split}
\end{equation}
where $l$ is the post, and $v_l$, $r_l$, $h_l$ are the votes, views, and length of the post respectively. The attributes are adding $1$ in case of they are $0$. If a post has both high votes and views, it is more likely to be a good post. Also, length slightly influence the score by the predefined factor $\eta$, since long posts may contain more information. Therefore, the motivation of this Quality Score is to select questions with both high votes and views with longer length.

\section{Experiment and Result}
In this section, we introduce how we preprocess the dataset, and the performance of our IEDL model measured by topic distribution classification precision and topic coherence.

\subsection{Data Analysis}
The 7,076 deep learning-related posts we used are publicly released by Stack Exchange\footnote{\url{https://archive.org/download/stackexchange}}. To evaluate the topics inferred by our proposed topic model, we also manually labeled 507 posts into six categories for classification: Image, NLP, Game-ai, Self-driving, Programming-languages, and Reinforcement-learning. The labels are determined based on the tags provided by Stack Exchange and to maximize their distinguishability.

\subsubsection{Word Formatting}
We first convert all words into lowercase, and then perform lemmatization to change each word into its original form. We then replace some segments with general symbols, like converting websites to ``$<$url$>$'' and so on.

\subsubsection{Phrase Extraction}
Since some words have specific meanings only in phrases and we need them to interpreting topics, phrases (mainly referring to two
consecutive words in our paper, and the words in each phrase are connected with ``\_") are  extracted in the preprocessing step and trained along with all the other words. We want the topic labels in phrases to be meaningful and comprehensible, therefore, a typical phrase extraction method based on PMI (Pointwise Mutual Information)\footnote{\url{https://en.wikipedia.org/wiki/Pointwise\_mutual\_information}}, which is effective in identifying meaningful phrases based on co-occurrence frequencies, is used:
\begin{equation}
    PMI(w_i,w_j) = \log\frac{p(w_{i}w_{j})}{p(w_i)p(w_j)}
\end{equation}
where $p(w_{i}w_{j})$ refers to the co-occurrence probability of the phrase $w_{i}w_{j}$ and $p(w_i)$ and $p(w_j)$ indicates the probability of the word $w_i$ and $w_j$ in the whole post documents. High PMI values indicate that it is more likely for the combination of the two words to be a meaningful phrase. We experimentally set a threshold for PMI, and  phrases with higher PMIs are extracted.

\subsubsection{Filtering}
This step aims to eliminate non-meaningful words, such as emotional words (e.g., ``nice" and ``bad"), abbreviations (e.g., ``btw"), and useless words (e.g., ``something"). We use the predefined stop words provided by NLTK\footnote{\url{http://www.nltk.org/}}, and all words in the stop word list are filtered out. Finally, all remaining words and extracted phrases are fed into the model.

\subsection{Classification Accuracy}
To test the quality of the extracted topics, we use the topic distribution of each post as features, and classify the 507 labeled posts by SVM. The results show that our proposed model outperforms the baseline model IDEA~\cite{DBLP:conf/icse/GaoZLK18} by 5\% for average precision.
\begin{table}[h]
\caption{Classification result}
\small
\label{classification}
\begin{center}
\begin{sc}
\scalebox{0.85}{\begin{tabular}{|c|c|ccc|} \hline
Category & Model & \scriptsize{Precision} & \scriptsize{Recall} & \scriptsize{F1}\\ \hline
\multirow{2}{*}{Image} & IDEA & 0.89 & \bf 0.73 & \bf 0.80 \\
\cline{2-5} & IEDL & \bf 1.00 & 0.64 & 0.78 \\ \hline
\multirow{2}{*}{NLP} & IDEA & 0.68 & 0.76 & 0.72 \\
\cline{2-5} & IEDL & \bf 0.73 & \bf 0.94 & \bf 0.82 \\ \hline
\multirow{2}{*}{Game-ai} & IDEA & 0.83 & 0.94 & 0.88 \\
\cline{2-5} & IEDL & \bf 0.83 & \bf 0.97 & \bf 0.90 \\ \hline
\multirow{2}{*}{Self-driving} & IDEA & 0.94 & 0.89 & 0.91 \\
\cline{2-5} & IEDL & \bf 1.00 & \bf 0.94 & \bf 0.97 \\ \hline
\multirow{2}{*}{\makecell{Programming\\-language}} & IDEA & \bf 0.92 & 0.73 & 0.81 \\
\cline{2-5} & IEDL &  0.86 & \bf 0.86 & \bf 0.86 \\ \hline
\multirow{2}{*}{\makecell{Reinforcement\\-learning}} & IDEA & 0.86 & \bf 0.86 & \bf 0.86 \\
\cline{2-5} & IEDL & \bf 1.00 & 0.62 & 0.76 \\ \hline
\end{tabular}
}
\end{sc}
\end{center}
\end{table}

\subsection{Topic Coherence}
\begin{table}[h]
\centering
\small
\caption{Topic coherence of different approaches.}
\begin{sc}
\scalebox{0.85}{\begin{tabular}{|c|c|c|c|} \hline
OLDA & IDEA & IDEA+Quality Score & IEDL\\ \hline
0.133 & 0.166 & 0.217 & \textbf{0.222} \\ \hline
\end{tabular}
}
\end{sc}
\end{table}

\setcounter{figure}{2}
\begin{figure*}[ht]
\centering
\includegraphics[width=0.9\textwidth]{river.jpg}
\caption{Visualization of topic changes based on ThemeRiver~\cite{DBLP:conf/infovis/HavreHN00}. Texts highlighted in yellow are the emerging topics in the corresponding month (Oct. 2017) where the mouse is pointing at.}\label{river}
\end{figure*}

Topic coherence score~\cite{DBLP:conf/naacl/LauB16} is another way to measure the performance of models by detecting the coherence between extracted words or phrases assigned to each topic. The method we use is an extension of PMI, where $t$ refers to a topic, and $N$ is the number of words:
\begin{equation}
OC\_Auto\_PMI(t)=\sum^N_{j=2}\sum^{j-1}_{i=1}\log\frac{p(w_{i}w_{j})}{p(w_i)p(w_j)}
\end{equation}
We feed the whole 7,076 dataset into our IEDL model and compare the topic coherence score to IDEA~\cite{DBLP:conf/icse/GaoZLK18}. The result shows IEDL improves the topic coherence score by 33.7\%. The topic coherence scores with error bars are shown in Figure~\ref{TC}.

\setcounter{figure}{1}
\begin{figure}[ht]
\begin{center}
\centerline{\includegraphics[width=0.95\columnwidth]{TC.PNG}}
\caption{Topic coherence with error bars (standard error).}
\label{TC}
\end{center}
\end{figure}

To further elaborate on the coherence between topics and extracted phrases, we compared the generated phrases for topics ``NLP" and ``Image" respectively. The result shows IEDL can generate more coherent and meaningful phrases for each topic.

\begin{table}[h]
\caption{Phrases generated by IDEA and IEDL for topics ``NLP" and ``Image" respectively. Red underlined fonts highlight the phrases that are not closely related to the topic.}
\small
\label{compare}
\begin{center}
\scalebox{0.85}{\begin{tabular}{|c|c|c|c|}
  \hline
  \multicolumn{2}{|c}{NLP} & \multicolumn{2}{|c|}{Image} \\
  \hline
   IDEA & IEDL & IDEA & IEDL \\
  \hline
  {\color{red} \underline{solution space}} & word vector &cnn model & \begin{tabular}{@{}c@{}}convolutional \\ network\end{tabular}   \\
  \begin{tabular}{@{}c@{}}information \\ science\end{tabular}  & word embedding & previous layer & pixel value  \\
  {\color{red} \underline{real environment}} & feature extraction & {\color{red} \underline{specific task}} & \begin{tabular}{@{}c@{}}capsule \\ network\end{tabular} \\ \hline
\end{tabular}
}
\end{center}
\end{table}

\section{Visualization}

In this part, we visualize the the evolution deep learning topics along with time flow for better understanding. As shown in Figure~\ref{river}, all the posts constitute one river and each branch of the river indicates one topic. By moving the mouse over one topic, one can track detailed topic changes along with time slices (months in our experiment), where the emerging issues are highlighted.

The topics with wider branches are of greater concern to developers, where the width of the $k$-th branch in the $t$-th version is defined as:
\begin{equation}
width^t_k = \sum_{a}\log Count(a) \times SCORE_{qua}(l_a)
\end{equation}
where $Count(a)$ is the count of the phrase label $a$ in the post collection of the $t$-th version, and $Score_{qua}(l_a)$ denotes the quality score of $l_a$, which is the post refers to the phrase label $a$.

We visualize topic changes from January to December 2017. As shown in Figure~\ref{river}, our IEDL finds an emerging topic about self-driving, which is not detected by IDEA~\cite{DBLP:conf/icse/GaoZLK18}. We double check the dataset and find that, compared to only one post from July to September, there are eight posts about self-driving in October (may be caused by a new release of electric semi-truck of Tesla), which further proves the effectiveness of our model in detecting emerging topics.

\section{Conclusion and Future Work}
Timely and effectively detecting deep learning topics is crucial for developers to capture the trend. We propose IEDL, a novel framework for automatically identifying emerging topics from posts in Q\&A forums. The experiment results show IEDL improves the quality of topic distribution and topic coherence greatly. In the future, we will refine IEDL to be capable of defining the topic number automatically, and utilize other information like comments, accepted answers to further improve the performance.

\bibliographystyle{icml2019}


\section{Introduction}
Algorithmic composition is not a new idea. Earlier, there was the use of statistical methods to create music\cite{conklin2003music}. Research on automatic music generation has made great progress due to the development of deep neural networks\cite{dai2018music}\cite{fessahaye2019t}\cite{nam2019deep}

Compared with computer vision (CV), natural language processing (NLP) and other common fields of deep learning, automatic music generation has some inherent challenges\cite{briot2017deep}, such as the complexity of music sequence itself in structure, the difficulty of objective evaluation of music generation results. \iffalse, how to define data structure, how to define loss functions. All these make the development of AI music generation relatively slow. Some works use the symbolic sequence as a music format to create music\cite{yang2017midinet}, and some use the waveform of the music as a music format for image analysis with using the Convolutional Neural Network (CNN) to model\cite{van2016wavenet}.\fi  Our approach is to use the symbol (MIDI format) music format for automatic music generation. The model based on Recurrent Neural Network (RNN) is the most common for symbolic-domain music generation, such as Boulanger et al.\cite{boulanger2012modeling}'s RNN-based model that can learn harmonic and rhythmic probabilistic rules, Google Magenta\cite{casella2001magenta}. As well as, Waite et al.\cite{waite2016project} use Long Short-Term Memory (LSTM) to make music. The RNN-based method is relatively mature but has some limitations: The music output of the model is limited in length, and a song which is directly spliced by some fragments is not good as a whole; Most models are difficult to continue to develop.

Xiaoice Band\cite{zhu2018xiaoice} is a model that deals with multi-track music\iffalse(guitar track, piano track, bass track, drum track)\fi. It introduces the concept of music, such as chord progression and rhythm shape. However, a generated music do not reflect the relationship between the bars, and data relies on multiple tracks and chords. Midi-Net also adds chords to the model\cite{yang2017midinet}. It proposes a novel conditional mechanism to exploit available prior knowledge. Pi from song\cite{chu2016song} is based on chords to generate each section but lacks control constraints between the individual bars. The above methods of using chords to limit the music sequence have a problem of having a chord music format dependency. For this, this paper adopts the First and Last Notes (FLN) to replace the chord progression as a constraint. Therefore in the format of only the main melody track, it is possible to train and generate music with a melodic motion. As a result, it reduces dependency on the data format and improves the applicability of the model.

Using RNN to construct Generative adversarial networks (GAN) will not be able to use traditional gradient descent to optimize. SeqGAN\cite{yu2017seqgan} solves this problem with Monte Carlo tree search of Reinforcement Learning. The model works to some extent, but the Monte Carlo search greatly increases the training time as the sequence length increases. MuseGAN\cite{dong2018musegan} is a GAN model by using CNN to construct which can generate 4-bar multi-track music phrases. C-RNN-GAN\cite{mogren2016c} proposes a generative adversarial model with both Generator (G) and Discriminator/Critor (D) being LSTMs that works on continuous sequential data. MusicVAE\cite{roberts2017hierarchical} is a generative recurrent Variational Autoencoder (VAE) model that can generates melodies and drum beats.\iffalse This model has a multi-layered structure to increase the length of the generated results. \fi  Transformer\cite{huang2018music} applies the latest Attention technology to produce music which has a longer sequence. MusicVAE and Transformer do complete the extension of the sequence length, but the model is not very interpretable, and there is no fusion musical knowledge\iffalse, such as chord progression, to control the generated music more in line with human expectations\fi. Yang et al.\cite{yang2019inspecting} propose a new method to inspect the pitch and rhythm interpretations of the latent representations with the VAE model. At the same time, \iffalse the VAE is easier to converge than the GAN model itself, but the generated model is not as fine as GAN, so\fi there is also a practice of merging GAN with VAE that uses the decoder of the VAE as the generator of GAN\cite{akbari2018semi}.

Due to the problems mentioned above, we find that most of the models have high requirements on data format and just generate music fragments instead of a song. In this regard, we propose the MIDI-Sandwich for generating long-term single track symbolic music sequences that have the characteristics of musical form structure and melodic motion. Training can also be done on the dataset with only the single melody track. MIDI-Sandwich is a multi-model multi-task hierarchical architecture, which can be expound from three aspects: 1) Multi-model. We propose four models of HCVAE, HCGAN, Local Contitional VAE (L-CVAE), and Global VAE (G-VAE). Simultaneously, L-CVAE and G-VAE are sub-models of HCVAE, and HCVAE also shares decoder and part of encoder with HCGAN; 2) Hierarchical architecture. The underlying model, the L-CVAE, processes local information, while the upper model, the G-VAE, controls global trends. Compared with MusicVAE and Transformer, our hierarchical model not only increases the length of generated sequences but also practices the control of structure (musical form) and melody direction;  3) Multi-task. The process of training model can be subdivided into three tasks: training L-CVAE, training HCVAE and training HCGAN.

In summary, we make the following contributions:

1. It is first proposed to use the First and Last Notes (FLN) as constraint conditions to restrain the generation of melody. Compared with using chord as a constraint condition in other model, using the FLN as the constraint condition can not only reflect the melodic motion so that the generated melody has a sense of direction, but also reduce the need for data format. It is not necessary to rely on a chord, and the single track can be trained. Since the FLN are related to the tonic and tonality in musical theory, specifying the FLN can maintain a stable tonality of a song. \iffalse Under the effect of the FLN, the generated melodys also have more musical sense and conforms to human appreciation standards. \fi

2. We use a hierarchical model. The upper layer completes the structural control of music by analyzing the latent vector distribution of music fragments generated by the underlying layer.

3. We propose a multi-model multi-task hierarchical architecture for symbolic single-track music generation. \iffalse The generated music is not only longer, but also incorporates musical knowledge such as musical form, tonic, and melodic motion. Meanwhile, t\fi This architecture makes the training process easier to monitor and control and makes the overall model more flexible to expand.

4. We combine HCVAE and HCGAN to smooth the model training curve to improve the quality of generating music, which not only makes the HCVAE decoder as HCGAN generator but also shares the part of the HCVAE encoder with the HCGAN critor. \iffalse In this way, HCGAN obtaines HCVAE's ability of easy convergence, stratification and constraint generation of music, and HCVAE further improves the model generation effect under HCGAN's training.\fi It is a new attempt to integrate VAE and GAN on the issue of automatic music generation.

\section{Background}
\subsection{VAE,VRAE,CVAE}
Variational Auto-encoder(VAE)\cite{kingma2013auto} consists of an encoder and a decoder. A disadvantage of VAE is that, because of the injected noise and imperfect elementwise measures such as the squared error, the generated samples are often blurry. The VAE loss fuction is defined as follows:
\vspace*{-0.4\baselineskip}
\begin{equation}
L=E_{X\sim \bar{p} (X)}[E_{z\sim p(Z|X)}[-\ln q(X|Z)]+KL(p(Z|X)||q(Z))]
\vspace*{-0.2\baselineskip}
\end{equation}
where the first and second terms are the reconstruction loss and a prior regularization term that is the Kullback-Leibler (KL) divergence, respectively.

VRAE\cite{bowman2015generating} uses an RNN-based neural network unit instead of a CNN-based unit to build encoder and decoder.
Conditional Variational Autoencoder (CVAE)\cite{sohn2015learning} is an extension of VAE which can generate some data specificed by user.

\subsection{GAN,WGAN,WGAN-GP}
Generative Adversarial Network (GAN)\cite{goodfellow2014generative} simultaneously trains two models: a generative model to synthesize samples, and a discriminative model (critor) to differentiate between natural and synthesized samples. The training procedure can be formally modeled as a two-player minimax game between the generator G and the discriminator D:
\vspace*{-0.4\baselineskip}
\begin{equation}
\mathop{min}\limits_{G}\mathop{max}\limits_{D}E_{x\sim pd}[\log(D(X))]+E_{z\sim pz}[1-\log(D(G(z)))]
\vspace*{-0.2\baselineskip}
\end{equation}
where $pd$ and $pz$ represent the distribution of real data and the prior distribution of $z$.

However, GAN training is difficult to free from training instability and low-quality generated samples. Different methods have been proposed to prove GAN. For example, WGAN\cite{arjovsky2017wasserstein}, DCGAN\cite{radford2015unsupervised}, WGAN-GP\cite{gulrajani2017improved} deal with the collapse of the model, so that training tends to stabilize. We experiment with the WGAN-GP model which is proposed for some problems with WGAN. WGAN-GP uses a gradient penalty to improve the problem of extreme parameters in weight clipping. The objective function of the differential equation is defined as follows:
\vspace*{-0.4\baselineskip}
\begin{equation}
E_{x\sim pd}[D(x)]-E_{z\sim pz}[D(G(z))]+E_{\hat{x}\sim p\hat{x}}[(\nabla_{\hat{x}}||\hat{x}||-1)^2]
\vspace*{-0.2\baselineskip}
\end{equation}
where $p\hat{x}$ is defined sampling uniformly along straight lines between pairs of points sampled from $pd$ and $pg$, the model distribution. The WGAN-GP model has faster convergence for better optimal solutions and requires less parameter adjustment.

\section{MIDI-Sandwich}
In this section, we introduce the Multi-model Multi-task Hierarchical Conditional VAE-GAN networks, called MIDI-Sandwich. As shown in Figure \ref{fig:side:a} and Figure \ref{fig:side:b}, the Midi-Sandwich contains two parts: Hierarchical Conditional VAE (HCVAE) and Hierarchical GAN (HCGAN). HCVAE can also be decomposed into two submodels: Local Condition VAE (L-CVAE) and Global VAE (G-VAE).

Model training can be divided into three tasks: 1) Train Local Condition VAE (L-CVAE); 2) Train HCVAE. G-VAE is a upper layer of HCVAE, while decoder and encoder of L-CVAE are integrated into HCVAE as the bottom layer. 3) Train HCGAN. We use the complete part of HCVAE decoder as the HCGAN generator, and we integrate the part of HCVAE encoder into the Critor of HCGAN. The multi-task mode makes the whole training process more controllable, more explanatory and easier to expand functions than the end-to-end model.

Compaired with CVAE-GAN or other common methods, MIDI-Sandwich has different ways to combine GAN with VAE. It not only makes VAE decoder as GAN generator but also shares parts of VAE encoder with GAN Critor. We do this for two benefits: 1) Smooth the learning curve; 2) Improve the quality of generated results.
\vspace*{-1.2\baselineskip}
\begin{figure}
	\begin{minipage}[t]{0.5\linewidth}
		\centering
		\includegraphics[width=1.5in]{pic1.png}
		\caption{Hirerarchical Conditional Variational Autoencoder (HCVAE)}
		\label{fig:side:a}
	\end{minipage}%
	\begin{minipage}[t]{0.5\linewidth}
		\centering
		\includegraphics[width=1.5in]{pic2.png}
		\caption{Hirerarchical Conditional Generative Adversarial Network (HCGAN)}
		\label{fig:side:b}
	\end{minipage}
\vspace*{-1.5\baselineskip}
\end{figure}

\subsection{Hirerarchical Conditional VAE}

HCVAE consists of hierarchical encoder and hierarchical decoder based on RNN, and hierarchical decoder/encoder is layered as L-CVAE decoder/encoder and G-VAE decoder/encoder. As shown in Figure \ref{fig:side:a}, we first divide a song into several music sections, and L-CVAE decoder is used to map each music section into an latent vector, so as to obtain an latent vector sequence. Then G-VAE encodes, samples, and decodes the latent vector sequence to analyze the manifestation of musical form structure in the latent vector level. Finally, latent vector sequence regenerated by G-VAE decoder is used as the input for L-CVAE decoder to generate music bars which are then composed into a song. We train the L-CVAE first (Task 1), whereafter, we add the trained L-CVAE to HCVAE, then we train the HCVAE (Task 2).

\subsubsection{Local Condition VAE}
On the basis of VAE, we propose the L-CVAE network which uses the First and last notes (FLN) as the constraint conditions for dealing with music fragments. The network structure diagram is shown in Figure \ref{fig:side:c}.

First, we count and sort the frequency of the FLN that appeares in each music fragment in the data set. We take top K higher frequency in the list of FLN and regard them as K classes. This transforms the conditional constraint problem into the K classification constraint problem.

Based on the original VAE model, a dense layer is added to learn the mapping of class labels $c$ to class mean $cm$. This class means $cm$ is added to the latent vector $z$, and the result is used as the input to the decoder. The loss function of L-CVAE is defined as follows:
\vspace*{-0.5\baselineskip}
\begin{equation}
L_{\mu,\sigma^2}=\frac{1}{2}\sum_{i=1}^{d}[(\mu_{(i)}-\mu_{(i)}^c)^2+\sigma_{(i)}^2-\log \sigma_{(i)}^2-1]
\vspace*{-0.5\baselineskip}
\end{equation}
where $\mu_{(i)}^c$ is the learned class mean $cm_{i}$ (cm in Fig \ref{fig:side:c}). The purpose of this is to make the latent vector z of music bar of the same constraint class approximate the mean of this class. Thus, the way to generate the music fragments of the specified constraint is to set the input $z$ of the decoder to the $cm_{i}$, which is the class mean of the specified constraint, plus a Gaussian random errors, then let the L-CVAE decoder generate automatically.
\vspace*{-1.2\baselineskip}
\begin{figure}

	\begin{minipage}[t]{0.5\linewidth}
		\centering
		\includegraphics[width=1.4in]{level1.png}
		\caption{Task1 model: L-CVAE}
		\label{fig:side:c}
	\end{minipage}%
	\begin{minipage}[t]{0.5\linewidth}
		\centering
		\includegraphics[width=1.4in]{level2.png}
		\caption{Task2 model: HCVAE}
		\label{fig:side:d}
	\end{minipage}
\vspace*{-1.5\baselineskip}
\end{figure}

\subsubsection{Global VAE}
As shown in Figure \ref{fig:side:d}, the Global VAE (G-VAE) is the upper-level model of HCVAE for analyzing the latent vector sequence (The blue circle in Figure \ref{fig:side:d}) encoded by L-CVAE, discovering the implied relation between music section, and rebuilding/generating the latent vector sequence as input subsequently of the L-CVAE decoder.

There are three points to note here:

1. Model training needs to freeze the L-CVAE decoder and encoder. We only train the G-VAE part in Task2;

2. The VAE process is encoding, sampling, and decoding, and the latent vector of the VAE is generated after sampling. The sample of L-CVAE is defined as follows:
\vspace*{-0.5\baselineskip}
\begin{equation}
z = \mu(X)+\sigma^\frac{1}{2}(X)*\epsilon
\vspace*{-0.5\baselineskip}
\end{equation}
where $\epsilon \sim N(0,1)$. The L-CVAE sampling is arranged after G-VAE decoding rather than before G-VAE encoding. The first reason is to avoid random noise. When sampling, $\epsilon$ is introduced  into latent vector as a random error subject to Gaussian distribution, which would interfere with the subsequent latent vector analysis of G-VAE; The second reason is to improve the quality of output. A VAE decoder works best when the input is subject to Gaussian distribution. Reconstructed/Generated latent vectors generated by G-VAE encoder do not necessarily subject to Gaussian distribution exactly, so the input of the L-CVAE decoder is subject to Gaussian distribution forcibly to improve the generation effect when the sampling is arranged after the decoding of G-VAE;

3. The class means $cm$ interfere with the analysis of G-VAE. For example, if the FLN of two music bars are different and other music symbols are the same, the addition of different class means can cause a big difference between the two latent vectors. So in Figure \ref{fig:side:d}, we subtract $cm$ before G-VAE encoding and add $cm$ after L-CVAE sampling.

Finally, There are two ways to specify the FLN sequence of a song which will be added to the input for L-CVAE decoder during the generation phase of HCVAE. One is to specify directly artificially, such as using the FLN sequence of the sample in the dataset. The other is to construct an ordinary VAE to generate it.

\subsection{Hirerarchical Conditional GAN}
As shown in Figure \ref{fig:side:b}, On the basis of using the WGAN-GP model, we let HCVAE decoder be the generator of WGAN-GP. At the same time, we also share the encoder layer of L-CVAE and put it into the Critor of WGAN-GP in order to better smooth the training curve and solve the problem of mode collapse. In this way, HCGAN obtains the ability of HCVAE conditional constraints and stratification. The training of HCVAE (Task1 and Task2) as a pre-training of HCGAN training (Task3) makes WGAN-GP skip the difficult problem of convergence, and also expands the HCVAE generation effect through HCGAN model.
\section{Experiment}

\subsection{Experiment Details}
\subsubsection{Dataset}
The dataset of the paper uses the Nottingham Dataset, which is equivalent to mnist in the field of music generation. The Nottingham Dataset provides music in both MIDI format and ABC format. In our experiment, we selecte the widely used MIDI format music file. The Nottingham Dataset also provides files for MIDI music with a chord version and a clean version without a chord. Since the purpose of this paper is to generate single track music, we select the latter.
\subsubsection{Data Preprocessing}
First, we convert the music to 12 majors, the speed is adjusted to 120bpm. Then, we convert the MIDI file into a piano roll format, which is a 2-dimensional matrix. The horizontal dimension of the matrix represents time, and the vertical dimension represents 128 pitches. For L-CVAE, we split all the songs in the data set into music phrases with a shape of (50, 128) and a length of 16 beats. At the same time, we choose the FLN of each phrase to form a note pair, representing the FLN condition. We add a note pair with frequnecy more than 20 times to the note pair class dictionary, and finally, the dictionary length is 125. These note pairs are labed from 1 to 125, and we add additional two labels: 126th label is as the other unconstrained tonic tag, and 0th label as the empty class tag. So we get total of 127 categories. We convert it to a One-Hot form, as a constraint tag for each phrase, participating in the training of the model.
For HCVAE, We select 17 phrases with the highest frequency of occurrence as the uniform length. Each song only selects the first 17 phrases, and the rest is discarded. The shape of the cut is (850, 128)
\subsubsection{Parameter Details}
The batch size for both HCVAE (Task2) and L-CVAE (Task3) is 32. In L-CVAE, a latent vector size is 32, and the sampling error variance is 0.01. In G-VAE, a latent vector size is 256, and the variance of the sampling error is set to 0.1. For both LSTM of L-CVAE and G-VAE, an intermediate-dim is 256.
The experiment is performed on the NVIDIA P100 with 16G memory, and Python3 and Keras deep learning framework based on the Tensorflow backend are built under the docker image. Complete training can be completed in one day.

\subsection{Result}
In view of the music generation experiment is difficult to evaluate, we investigate the experimental part of the classic well-known papers in the field of music generation. MuseGAN\cite{dong2018musegan} proposes two evaluation methods: Objective Evaluation and User Study. MidiNet\cite{yang2017midinet} provides a result of the user study and online audio examples.
Xiaoice band\cite{zhu2018xiaoice} uses Human Evaluation to evaluate rhythm, melody, integrity, singability, and uses Chord Accuracy to evaluate chords. Pi from song\cite{chu2016song} provides reports of 27 volunteers voted and provides online samples. Transformer\cite{huang2018music} shows the Validation NLL and Human Evaluation of their models.

Considering the characteristics of our model, we propose a series of methods to verify the comprehensive quality of the model. We employ to MuseGAN's Objective Evaluation to evaluate the quality of the music generated by the HCVAE and HCGAN. To verify the effectiveness of the First and Last Notes (FLN), we propose FLN Accuracy inspired by Xiaoice's Chord Accuracy. After that, we verify the model from the perspective of length and musical form structure. We also use volunteers to vote on the six indicators of music to verify the quality of the generated music. Finally, for more audio examples generated by MIDI-Sandwich, please go to \url{https://github.com/LiangHsia/MIDI-Sandwich}.

\subsubsection{Objective Evaluation}
We employ the MuseGAN evaluation method Objective Metrics for evaluation. Since the MIDI-Sandwich generates single-track music, we remove the drum pattern and the tonal distance which are from the original MuseGAN evaluation method. The irregular tone ratio is added as our evaluation indicator. We evaluate the real experimental set (dataset), generation of L-CVAE (Task1), HCVAE (Task2) and MIDI-Sandwich (Task3). The result is shown in Table \ref{tab:aStrangeTable1}.

\begin{table}[!htbp]
	\vspace*{-0.5\baselineskip}
	\centering
	\caption{Objective Metrics Evaluation(EB: ratio of empty bars(in \%), UPC: number of used pitch classes per bar (from 0 to 12), QN: ratio of "qualified" notes, IT: ratio of irregular tone (in \%)).}\label{tab:aStrangeTable1
	\begin{tabular}{c|c|c|c|c}
		\hline
		& empty bars & used pitch classes& qualified notes& irregular tone\\
		& (EB: \%) & (UPC) & (QN: \%) & (IT: \%) \\
		\hline\hline
		Dataset & \textbf{8.06} & \textbf{1.71} & \textbf{90.0} & \textbf{0.00}\\
		\hline\hline
		from L-CVAE  & 6.22 & 3.64 & 63.0 & 6.52\\
		from HCVAE  & 5.92 & 3.28& 71.2 & 6.13\\
		from MIDI-Sandwich & \textbf{6.71} & \textbf{2.67}& \textbf{76.7} & \textbf{2.12}\\
		\hline
	\end{tabular}

\end{table}

As can be seen from the Table \ref{tab:aStrangeTable1}, music generated by MIDI-Sandwich is more fluent than that by HCVAE and L-CVAE, and the probability of crowded notes and irregular sounds is reduced. It  proves that MIDI-Sandwich which combines HCVAE and HCGAN has better effect than a single model.

\subsubsection{Length Comparison}

\begin{table}[!htbp]

	\centering
	\caption{Contrast Length}\label{tab:aStrangeTable2
	\begin{tabular}{cccccccc}
		\hline
		& Pi& Xiaoice & MusicVAE &MIDI-GAN &Musegan &MagentaRNN &MIDI-Sandwich\\
		\hline
		Length/bar& 8& 8& 16& 8& 8& 8& \textbf{34}\\
		\hline
	\end{tabular}

	\vspace*{-0.5\baselineskip}
\end{table}

As can be seen from the Table \ref{tab:aStrangeTable2}, MIDI-Sandwich is compared with the classic model and the popular models in recent years. Our model length is 34 bars (34x4 beats). It can be seen that our model generates the longest length of valuable music sequences. Compared with MusicVAE and Transormer, MIDI-Sandwich has a conditional constraint mechanism and introduces the knowledge of music theory such as musical form, melodic motion and tonic, which makes the melody more directional and closer to human standards of appreciation.

\subsubsection{Musical Form}
We prove the structural validity of the music sequence generated by this model from the perspective of comparing the latent vectors.

As shown in Figure \ref{fig:side:a1}, we extract three fragments in the same song: a, b, and c. Figure \ref{fig:side:b1} prestens L-CVAE latent vector of three fragments (after subtracting the $cm$), we can observe that the structural relationship at the music level can be expressed at the latent vector level. That is, the difference in the dimensions of latent vector is less than one thousandth for same music fragments. The dimensions of latent vector is mostly similar for similar music fragments. And the difference of latent vector dimensions between the two different music fragments is also significant.
\begin{figure}
	\begin{minipage}[t]{0.48\textwidth}
		\centering
		\includegraphics[width=1.4in]{fragment3.png}
		\caption{Three music fragments within a song that have relationships.}
		\label{fig:side:a1}
	\end{minipage}%
	\begin{minipage}[t]{0.48\textwidth}
		\centering
		\includegraphics[width=1.4in]{latent3.png}
		\caption{The comparison of different structural relationships of music at latent.
			Top left: ab similar, top right: bc sandhi, bottom: cc' repeat.}
		\label{fig:side:b1}
	\end{minipage}
\vspace*{-1.5\baselineskip}
\end{figure}

As shown in the Figure \ref{fig:side:b11}, it is a music score generated by the MIDI-Sandwich. the music clip on the blue line reflects the repeating structure of the paragraph.
The clip on the pink line has a slight change after the same repeating music segment. The fragments on the purple line reflect the rise and fall of the melody. They present that the music generated by our model is composed of repeating, similar, transposing musical form structures.
\vspace*{-1.2\baselineskip}
\begin{figure}
	\begin{minipage}[t]{0.48\textwidth}
		\centering
		\includegraphics[width=1.4in]{phrase.png}
		\caption{Long-term music clips generated by MIDI-Sandwich.}
		\label{fig:side:b11}
	\end{minipage}%
	\begin{minipage}[t]{0.48\textwidth}
		\centering
		\includegraphics[width=1.4in]{tonic.png}
		\caption{Three music fragments.}
		\label{fig:side:b22}
	\end{minipage}
\vspace*{-1.5\baselineskip}
\end{figure}

\subsubsection{The First and Last Notes}
There are three music fragments in Figure \ref{fig:side:b22}: a sample of the first and last notes (FLN) and two music fragments generated based on this sample constrains.
It can be clearly seen that the generated music fragments satisfy the constraint and also have diversity.
FLN Accuracy method is used to evaluate the accuracy of generating music bars to obey the FLN constraint. The result shows the accuracy can reach 94\%, proving that the majority of generated music fragments almost satisfy the constraint of the FLN, which leads generated musics have stable tonal performance and melodic motion.

\subsubsection{User Study}

\begin{table}[!htbp]
\vspace*{-2\baselineskip}
	\centering
	\caption{User Study (R: Rhythm, M: Melody, I: Integrity, Si: Singability, St: Structrue, MM: Melodic Motion.)}\label{tab:aStrangeTable3
	\begin{tabular}{c|cccccc|c}
	\hline\hline
	Methods   & R& M& I& Si &St & MM &Average\\
	\hline
	Magenta-RNN& \textbf{3.42}& \textbf{3.52} &3.23 &\textbf{2.57} &2.90 &2.95 &3.10\\
	MidiNet(GAN)& 3.09& 3.19 &2.38 &2.14 &2.47 &3.09 &2.56\\
	VAE-GAN &1.90& 2.33 &2.52 &2.09 &2.23 &2.42 &2.25\\
	\hline
	Sandwich(HCVAE)& 2.52& 3.14 &3.28 &2.14 &3.57 & 3.42&3.01\\
	Sandwich(HCVAE-GAN)& 2.76& 3.38 &\textbf{3.33} &2.28 &\textbf{3.66} & \textbf{3.47}&\textbf{3.15}\\
	\hline\hline
	\end{tabular}
\vspace*{-0.5\baselineskip}

\end{table}

We randomly invited 21 volunteers online to compare songs generated by MIDI-Sandwich, Magenta-RNN, MIDI-Net, and VAE-GAN. As shown in the Table \ref{tab:aStrangeTable3}, we asked them to rate these songs from 1 to 5 for 6 indicators. The evaluation shows that MIDI-Sandwich performs well on both structrue, melodic motion indicators and average of songs. Melody, integrity, singability are similar to others generated by other models. Our model is slightly weak in rhythm.

\section{Conclusion}
In this paper, we propose a multi-task multi-model hierarchical conditional VAE-GAN network, named MIDI-Sandwich. The MIDI-Sandwich has four models (L-CVAE, G-VAE, HCVAE, HCGAN) and three tasks to product a long-term symbol single-track music. At first, we train the L-CVAE (Task 1), to generate music fragments which are pre-specified the First and Last Notes (FLN) constraint. Then, We train HCVAE (Task2), which consists of L-CVAE and G-VAE, to generate songs. The underlying L-CVAE deals with the local music fragments. And the upper G-VAE controls global structure and the melody direction of the song by analyzing latent vector sequences from L-CVAE encoder and providing L-CVAE decoder with the FLN sequences. After HCVAE training, the decoder of HCVAE is regarded as the generator of HCGAN, and some parts of HCVAE encoder and CNN layer are used as the critor of HCGAN. Then we train HCGAN (Task3) to further improve the quality of generating songs.

Through experiments, they prove that songs generated by MIDI-Sandwich have three advantages. First, the MIDI-Sandwich directly outputs a song which has a long length instead of a music fragment. Second, The MIDI-Sandwich makes the generated music have a musical form structure by layered network architecture. Finally, the FLN is used instead of the chord progression which is commonly used in multi-track music as a constraint, which has low requirements on the data format and enhances the applicability of the networks. Moreover, the FLN constraints also keep the melody stable in tonality. At the same time, the MIDI-Sandwich uses a multi-model and multi-task architecture. Each sub-model can be flexibly expanded or replaced. Each sub-task can also be easily evaluated. In the future, we will continue to improve the network model in both rhythm and multi-track, and try to use the model in other artificial intelligence symbol music fields.