# The Investment Management Game:
Extending the Scope of the Notion of Core

Vijay V. Vazirani111Supported in part by NSF grant CCF-2230414. University of
California, Irvine

###### Abstract

The core is a dominant solution concept in economics and cooperative game
theory; it is predominantly used for profit — equivalently, cost or utility —
sharing. This paper demonstrates the versatility of this notion by proposing a
completely different use: in a so-called investment management game, which is
a game against nature rather than a cooperative game. This game has only one
agent whose strategy set is all possible ways of distributing her money among
investment firms.

The agent wants to pick a strategy such that in each of exponentially many
future “scenarios”, sufficient money is available in the “right” firms so she
can buy an “optimal investment” for that scenario. Such a strategy constitutes
a core imputation under a broad interpretation, though traditional formal
framework, of the core.

Our game is defined on perfect graphs, since the maximum stable set problem
can be solved in polynomial time for such graphs. We completely characterize
the core of this game, analogous to Shapley and Shubik’s characterization of
the core of the assignment game. A key difference is the following technical
novelty: whereas their characterization follows from total unimodularity, ours
follows from total dual integrality.

##  1 Introduction

The core is a dominant solution concept in economics and game theory. Its
origins lie in the 19th century book of Edgeworth [Edg81] in which it was
referred to as the contract curve and was first used in general equilibrium
theory. In 1959, Gillies [Gil59] gave an improved definition which started
being used in cooperative game theory for “fair” profit sharing. Since then,
the stature of this solution concept grew considerably and today it is
considered the gold standard for profit sharing and much more desirable than
other notions, e.g., least core and nucleolus222Some drawbacks of these two
notions are mentioned in [Vaz22a]..

The following question arises, “How versatile is this solution concept?” Let
us first consider this question in the context of Nash equilibrium, which is
perhaps the most important solution concept in game theory. Even for the
special case of bimatrix games, it provides deep insights in a rich milieu of
situations, each having its own special character, e.g., Prisoner’s Dilemma,
Matching Pennies, Battle of the Sexes, and Rock-Paper-Scissor; the last game
is in fact zero-sum. Indeed, most “big” solution concepts tend to be similarly
multi-faceted. In contrast, within game theory, the core has been used for
profit — equivalently, cost or utility — sharing only.

The purpose of this paper is to show that the notion of core is more versatile
than previously believed. For this, we need to first pick an appropriate
definition of core, since adopting a narrow definition would be self-
defeating; the latter says that this notion is meant for sharing profit in
such a way that stability is ensured. Under this definition, a core imputation
shares the profit of the grand coalition among agents so that no sub-coalition
can make more profit by itself and therefore will not succeed from the grand
coalition. Clearly, we need to interpret core in more general terms; however,
we do not wish to take liberties with its formal framework, see Section 3.
Fortunately, a middle ground exists, as described in Section 4.

Definition 1 introduces the investment management game, whose core we will
characterize. Interestingly, it is not a cooperative game; in fact, it has
only one agent. Our game is best viewed as a game against nature, i.e., a game
against a player whose pay-offs, as well as probability distribution over
strategies, are unknown. The origin of this name comes from the experience of
farmers from a time when weather prediction and irrigation systems were not
well developed, making it difficult for them to predict the best choice of
crops and forcing them to play in complete ignorance [BB97]. Our game has
exactly this character, see Definition 1. The saving grace is that in our
game, a core imputation helps salvage the situation by enabling the agent to
invest in such a way she is able to respond to every strategy of nature
optimally!

After defining our game, in Remark 1 we draw a clear distinction between the
manner in which the core is applied in cooperative game theory and in our
game. In Section 4, we define our game on a graph. Its main computational
problem that arises in it is to find a maximum weight independent set, which
is ${\cal NP}$-hard in arbitrary graphs. However, the restriction of this
problem to perfect graphs (Section 5) is in ${\cal P}$ [GLS88]; this will be
the setting for our game.

In Section 5 we characterize the core of this game. A good way of describing
this result is by drawing an analogy with the classic paper of Shapley and
Shubik [SS71] which characterized the core of the assignment game. They showed
that the core of this game is precisely the set of optimal solutions to the
dual of the LP-relaxation of the maximum weight matching problem in the
underlying bipartite graph, see Section 3. As observed in [DIN99, DD10,
Vaz23], at the heart of the Shapley-Shubik proof lies the fact that the
polytope defined by the constraints of this LP is integral, see Definition 6.
In turn, integrality follows from the fact that the constraint matrix of this
LP is totally unimodular (TUM), see Definition 7. The underlying reason for
this requirement of integrality is an inherent indivisibility in the game,
e.g., in a cooperative game, such as the assignment game, agents are
indivisible.

Integrality holds for the maximum weight independent set problem for perfect
graphs as well. However, the underlying reason is not TUM, but the more
general condition of total dual integrality (TDI), see Definition 8. Building
on this fact, we show that the set of core imputations of our game is
precisely the set of optimal solutions to the dual of the LP-relaxation of the
maximum weight independent set problem for perfect graphs. Ours appears to be
the first work which uses TDI for characterizing the core of a game; previous
characterizations were based on TUM, see Section 2.

Another novelty of our work is the following: In cooperative games, the profit
of a sub-coalition under an imputation was defined via a bottom-up process in
which the worth of the game was distributed among agents and the profit of a
sub-coalition was simply the sum of profits of agents in it. In our game there
is only one agent and the natural process is top-down, as described in Section
4 and summarized in Remark 2.

######  Definition 1.

The investment management game involves one agent, a set $V$ of assets with a
cost function $w:V\rightarrow\boldsymbol{\mathit{Q}}_{+}$, and a set
$\mathcal{M}$ of investment firms. For concreteness, assume that assets are
shares of specific companies, each worth a specific dollar amount; obviously,
the number of shares in an asset changes according to the going price. Assume
further that, much like a mutual fund, each investment firm specializes in
holding shares of specific types of companies, e.g., Internet companies,
software companies, computer hardware companies, automobile companies, etc.
The difference is that whereas each share of a mutual fund represents a
collection of assets in some predetermined proportions, in our setting, the
agent can buy individual assets from a firm.

The set of assets sold by a specific firm $f\in\mathcal{M}$ is denoted by
$Q_{f}\subseteq V$. The same asset, such as “five thousand dollars worth of
Microsoft”, may be sold by more than one firm, e.g., this asset may be sold by
a firm specializing in Internet companies as well as a firm specializing in
software companies. Each subset $S\subseteq V$ of assets is called a scenario;
hence there are exponentially many, namely $2^{|V|}$, scenarios.

Two or more assets which are sold by the same firm have obvious correlations
and therefore do not constitute a low-risk investment. On the other hand, a
set of assets which picks at most one asset from any investment firm
constitutes a diversified portfolio — it avoids correlations and is therefore
considered a “healthy” investment. An optimal investment for a scenario $S$ is
a largest possible diversified portfolio in it; formally, it is defined to be
a maximum cost set $S^{\prime}\subseteq S$ which picks at most one asset from
any investment firm.

The total money, $T\in\boldsymbol{\mathit{Q}}_{+}$ of the agent is just
sufficient to buy an optimal investment in scenario $V$. The strategy set of
the agent is all possible ways of distributing money $T$ among the firms; each
strategy will also be called an imputation. The rules of this game dictate
that the money allocated to a firm $f\in\mathcal{M}$ is available for use at
any asset $v\in Q_{f}$. Note that this money need not be used for buying $v$;
it is simply available at $v$. Therefore, the money available in scenario $S$
is the sum of money allocated to all firms which have at least one asset in
$S$. Clearly, our game is a transferable utility (TU) game.

The game is the following: Find an imputation such that when, at a certain
time in the future, nature picks a strategy, i.e., a scenario $S\subseteq V$,
the money available in $S$ is sufficient to buy an optimal investment in $S$.
Such an imputation is said to be in the core of the game. Thus a core
imputation enables the agent to invest $T$ money in firms in such a way she is
able to respond to every strategy of nature optimally.

######  Remark 1.

In light of Definition 1, a clear distinction can be given between the manner
in which the core is applied in cooperative game theory and in our game.
Whereas in the former, a core imputation defines payoffs of all players that
results in the stability of the grand coalition, in the latter, a core
imputation captures an investment strategy, of the unique player, that
encapsulates risk aversion (for the stated definition of “risk”) under every
future scenario.

##  2 Related Works

Results characterizing cores of natural Transferable Utility (TU) games are
given below. First, we mention the stable matching game, defined by Gale and
Shapley [GS62], in which preferences are ordinal, i.e., it is an NTU game. The
only coalitions that matter in this game are ones formed by one agent from
each side of the bipartition. A stable matching ensures that no such coalition
has the incentive to secede and the set of such matchings constitute the core
of this game. Vande Vate [Vat89] and Rothblum [Rot92] gave linear programming
formulations for stable matchings; the vertices of their underlying polytopes
are integral and are stable matchings. Interestingly enough, Kiraly and Pap
[KP08] showed that the linear system of Rothblum is in fact TDI.

A core imputation has to ensure that each of the exponentially many sub-
coalitions is “satisfied” — clearly, that is a lot of constraints. As a
result, the core is known to be non-empty only for a handful of games, some of
which are mentioned below; total unimodularity plays a key role in these
results.

Deng et al. [DIN99] observed the role of integrality in the Shapley-Shubik
Theorem and used this insight to distilled its underlying ideas to obtain a
general framework which helps characterize the cores of several games that are
based on fundamental combinatorial optimization problems, including maximum
flow in unit capacity networks both directed and undirected, maximum number of
edge-disjoint $s$-$t$ paths, maximum number of vertex-disjoint $s$-$t$ paths
and maximum number of disjoint arborescences rooted at a vertex $r$.

The survey of Demange and Deng [DD10] on the notion of balancedness of
Bondareva and Shapley [Bon63, Sha65] explored the role of integrality in
depth. Towards the end of their paper, they note that TDI of a linear system
is a very general condition that leads to integrality and therefore non-
emptyness of the core and balancedness. However, they did not give the example
of any game for which TUM does not hold and TDI has to be invoked for
establishing integrality.

A natural generalization of the assignment game is the $b$-matching game in
bipartite graphs. Biro et al. [BKP12] showed that the core non-emptiness and
core membership problems for the $b$-matching game are solvable in polynomial
time if $b\leq 2$ and are co-NP-hard even for $b=3$. More recently, Vazirani
[Vaz22b] showed that if $b$ is the constant function, then core imputations
are precisely optimal solutions to the dual LP; this is analogous to the
Shapley-Shubik theorem. Furthermore, Vazirani [Vaz22b] showed that if $b$ is
arbitrary, then every optimal solutions to the dual LP is a core imputations;
however, there are core imputations that are not optimal solutions to the dual
LP.

We next describe results for the facility location game. First, Kolen [Kol83]
showed that for the unconstrained facility location problem, each optimal
solution to the dual of the classical LP-relaxation is a core imputation if
and only if this relaxation has no integrality gap. Later, Goemans and
Skutella [GS04] showed a similar result for any kind of constrained facility
location game. They also proved that in general, for facility locations games,
deciding whether the core is non-empty and whether a given allocation is in
the core is NP-complete.

Samet and Zemel [SZ84] study games which are generated by linear programming
optimization problems; these are called LP-games. For such games, It is well
known that the set of optimal dual solutions is contained in the core and
[SZ84] gives sufficient conditions under which equality holds. These games do
not ask for integral solutions and are therefore different in character from
the ones studied in this paper.

Granot and Huberman [GH81, GH84] showed that the core of the minimum cost
spanning tree game is non-empty and gave an algorithm for finding an
imputation in it. Koh and Sanita [KS20] settle the question of efficiently
determining if a spanning tree game is submodular; the core of such games is
always non-empty. Nagamochi et al. [NZKI97] characterize non-emptyness of core
for the minimum base game in a matroid; the minimum spanning tree game is a
special case of this game.

##  3 Definitions and Preliminary Facts

In this section, we will give the standard definition of core in the setting
of a cooperative game. For completeness, we will also formally state the
characterization of the core of the assignment game given by Shapley and
Shubik. In Section 4 we will modify some of these definitions, and
appropriately rename others, so that the notion of core can be used to study
the investment management game.

We will study transferable utility (TU) games, i.e., a games in which
utilities of the agents are stated in monetary terms and side payments are
allowed. For an extensive coverage of these notions, see the book by Moulin
[Mou14].

######  Definition 2.

A cooperative game consists of a pair $(N,c)$ where $N$ is a set of $n$ agents
and $v$ is the characteristic function; $c:2^{N}\rightarrow\mathcal{R}_{+}$,
where for $S\subseteq N,\ c(S)$ is the worth that the sub-coalition $S$ can
generate by itself. $N$ is also called the grand coalition.

######  Definition 3.

An imputation gives a way of dividing the worth of the game, $v(N)$, among the
agents. It can be viewed as a function
$x:{N}\rightarrow\boldsymbol{\mathit{Q}}_{+}$. For each sub-coalition
$S\subseteq N$, we will define its profit as $\mbox{\rm profit}(S)=\sum_{i\in
S}{x(i)}$.

######  Definition 4.

Let $x$ be an imputation and $S\subseteq N$ a sub-coalition. We will say that
$x$ satisfies $S$ if its profit is at least as large as its worth, i.e.,
$\mbox{\rm profit}(S)\geq\mbox{\rm worth}(S)$.

######  Definition 5.

An imputation $x$ is said to be in the core of the game if it satisfies each
sub-coalition $S\subseteq N$.

The assignment game, consists of a bipartite graph $G=(U,V,E)$ and a weight
function $w:E\rightarrow\boldsymbol{\mathit{Q}}_{+}$. The agents of this game
are $U\cup V$ and for each sub-coalition $(S_{u}\cup S_{v})$, with
$S_{u}\subseteq U$ and $S_{v}\subseteq V$, its worth is defined to be the
weight of a maximum weight matching in $G(S_{u}\cup S_{v})$, where the latter
is the subgraph of $G$ induced on the vertices $(S_{u}\cup S_{v})$.

Linear program (5) gives the LP-relaxation of the problem of finding such a
matching. In this program, variable $x_{ij}$ indicates the extent to which
edge $(i,j)$ is picked in the solution.

∑_(i, j) ∈E w_ij x_ij ∑_(i, j) ∈E x_ij≤1 ∀i ∈U ∑_(i, j) ∈E x_ij≤1 ∀j ∈V
x_ij≥0∀(i, j) ∈E

The constraint matrix of LP (5) is totally unimodular (TUM), see Definition 7,
and therefore the polytope defined by its constraints is integral, e.g., see
[LP86]. Taking $u_{i}$ and $v_{j}$ to be the dual variables for the first and
second constraints of (5), we obtain the dual LP:

∑_i ∈U u_i + ∑_j ∈V v_j u_i + v_j ≥w_ij ∀(i, j) ∈E u_i≥0∀i ∈U v_j≥0∀j ∈V

######  Theorem 1.

(Shapley and Shubik [SS71]) The imputation $(u,v)$ is in the core of the
assignment game if and only if it is an optimal solution to the dual LP, (5).

######  Definition 6.

We will say that a polytope is integral if its vertices have all integral
coordinates.

######  Definition 7.

Let $Ax\leq b$ be a linear system where $A$ is an $m\times n$ matrix and $b$
an $m$-dimensional vector, both with integral entries. $A$ is said to be
totally unimodular (TUM) if every submatrix of $A$ has determinant $0,1$ or
$-1$. If so, the polytope of this linear system is integral.

######  Definition 8.

Let $Ax\leq b$ be a linear system where $A$ is an $m\times n$ matrix and $b$
an $m$-dimensional vector, both with rational entries. We will say that this
linear system is totally dual integral (TDI) if for any integer-valued vector
$c^{T}$ such that the linear program

$\max\\{cx:Ax\leq b\\}$

has an optimum solution, the corresponding dual linear program has an integer
optimal solution. If so, the polytope of this linear system is integral.

Note that TDI is a more general condition than TUM for integrality of
polyhedra. If $A$ is TUM then the polyhedron of the linear system $Ax\leq b$
is integral for every integral vector $b$. However, even if $A$ is not TUM,
for specific choices of an integral vector $b$, the polytope of the linear
system $Ax\leq b$ may be integral, and TDI may apply in this situation. It is
important to remark that TDI is not a property of the polytope but of the
particular linear system chosen to define it. See [GLS88, Sch86] for further
details.

##  4 The Investment Management Game Defined on a Graph

As stated in the Introduction, the investment management game, which is
described at a high level in Definition 1, is a game against nature and it is
not a cooperative game; in fact it has only one agent. A natural setting for
this game is a graph, as described below. This is a TU game: the money
available at a firm can be used to buy assets from other firms, as specified
below. In order to study its core, we will modify some of the standard
definitions given in Section 3, and appropriately rename others.

Let $G=(V,E)$ be a graph whose vertices are assets; let $|V|=n$. The function
$w:V\rightarrow\boldsymbol{\mathit{Q}}_{+}$ defines the cost of each asset.
Every maximal clique333It is easy to see that our result will hold even if we
had defined every clique to be an investment firm. However, under that
formulation, there would be numerous pairs of firms $f,f^{\prime}$ with
$Q_{f^{\prime}}\subset Q_{f}$, making firm $f^{\prime}$ redundant. Restricting
to maximal cliques avoids this deficiency in the formulation. in $G$ is an
investment firm; let ${\cal M}$ denote the set of all firms. For each firm
$f\in\mathcal{M}$, the assets sold by $f$ are represented by the vertices in
its clique, $Q_{f}\subseteq V$. As stated in Definition 1, each investment
firm specializes in holding shares of a specific type of companies. As a
result, two or more assets held by the same firm will have obvious
correlations.

We now explain why investment firms are defined to be cliques, via the
following analogy. Consider all the ATMs in the US of a certain bank. Since
the money deposited in this bank, or in an ATM of this bank, can be withdrawn
from any of its ATMs, the set of all ATMs of this bank can be viewed as a
clique, interconnected via a network. Similarly, since the money allocated to
an investment firm is available for use at any of its assets, as stated in
Definition 1, we have defined the investment firm to be a clique — over its
assets.

Every set $S\subseteq V$ is called a scenario, i.e., scenario plays the same
role as sub-coalition in a cooperative game. Let $G(S)$ denote the subgraph of
$G$ induced on vertices in $S$. As required by Definition 1, an optimal
investment in scenario $S$ is defined to be any maximum cost independent
set444An independent set is also called a stable set, see Definition 11. in
$G(S)$; clearly, this is a diversified investment since it picks at most one
asset from any investment firm. Let $O_{S}\subseteq S$ denote such an
investment and define

$\mbox{\rm cost}(S):=\sum_{v\in O_{S}}{w_{v}}.$

Note that cost plays the same role as worth in Definition 2 and the function
$\mbox{\rm cost}:2^{V}\rightarrow\boldsymbol{\mathit{Q}}_{+}$ plays the same
role as the characteristic function. The total money of the agent is defined
to be $T=\mbox{\rm cost}(V)$, i.e., just sufficient to buy an optimal
investment in $G$.

A function $y:\mathcal{M}\rightarrow\boldsymbol{\mathit{Q}}_{+}$ where
$\sum_{Q\in\mathcal{M}}{y_{Q}}=T$ is called an imputation, i.e., it is a way
of distributing $T$ money among the investment firms. The set of all such
functions $y$ can also be viewed as the strategy set of the unique agent in
the game. For any scenario $S$, the money available for buying assets in $S$
is defined to be the sum of money in all investment firms which contain at
least one asset from $S$, i.e.,

$\mbox{\rm money}(S):=\sum_{Q\in G(S):\ Q\cap S\neq\emptyset}{y_{Q}},$

where “$Q\in G(S)$” is short for “clique $Q$ in $G(S)$”. Strictly speaking,
the summation should be over maximal cliques, but since for a non-maximal
clique $Q$, $y_{Q}$ can be assumed to be zero, this distinction can be
dropped. Notice that $\mbox{\rm money}(S)$ plays the role of profit of $S$ in
a cooperative game.

By Definition 4, scenario $S$ is satisfied by imputation $y$ if $\mbox{\rm
money}(S)\geq\mbox{\rm cost}(S)$ and by Definition 5, imputation $y$ is said
to be in the core of this game if it satisfies every scenario, i.e.,

$\forall S\subseteq V,\ \ \mbox{\rm money}(S)\geq\mbox{\rm cost}(S).$

Remark 2 summarizes the definitions given above and points out an important
difference from the setting of cooperative games.

######  Remark 2.

In a cooperative game, an imputation distributes the total worth of the game
among agents and the profit of a sub-coalition is defined to be the sum of the
profits of its agents; the latter can be viewed as a bottom-up process.
Clearly these processes do not apply to our game, since it has a unique agent
and the notion of a “sub-coalition” is replaced by that of a scenario.

The natural way of defining an imputation and the money available in a
scenario can be summarized as follows: an imputation distributes the total
money of the game among “large” objects — the firms, which are maximal cliques
— and the money available in a scenario is defined via a top-down process, by
summing the money of all cliques which intersect this scenario.

###  4.1 Limitations of this Model, and Desired Properties

The problem of computing a maximum cost independent set in an arbitrary graph
is NP-hard, even if all vertex costs are unit. This NP-hardness also indicates
that the game defined above lacks structural properties that could lead to an
understanding of its core. In sharp contrast, the assignment game is in $\cal
P$ and its LP-relaxation supports integrality of the underlying polytope,
therefore leading to a characterization of its core. Hence, the model defined
above, on an arbitrary graph, is too general to be useful.

To be useful, the model should allow for:

  1. 1.

A characterization of the core; in particular, determine if the core is non-
empty.

  2. 2.

Efficient computation of $T$, and $\mbox{\rm cost}(S)$ for any scenario $S$.

  3. 3.

An efficient algorithm for computing an imputation in the core.

In the next section, we show that restricting the game to perfect graphs gives
all these properties.

##  5 The Investment Management Game on Perfect Graphs

In this section, we will study a restriction of the investment management game
to perfect graphs. In Section 5.1 we give the required definitions and facts
from the (extensive) theory of perfect graphs. We will not credit individual
papers for these facts; instead, we refer the reader to Chapter 9 of the book
[GLS88] as well as the remarkably clear and concise exposition of this theory,
presented as an “appetizer” by Groetschel [Grö99]. In Section 5.2 we will use
these facts to characterize the core of this game.

###  5.1 Definitions and Preliminaries

######  Definition 9.

Given a graph $G=(V,E)$, $\omega(G)$ denotes its clique number, i.e., the size
of the largest clique in it and $\chi(G)$ denotes its chromatic number, i.e.,
the minimum number of colors needed for its vertices so that the two endpoints
of any edge get different colors.

######  Definition 10.

A graph $G=(V,E)$ is said to be perfect if and only if the clique number and
chromatic number are equal for each vertex-induced subgraph of $G$, i.e.,

$\forall S\subseteq V,\ \omega(G(S))=\chi(G(S)).$

Let $\overline{G}$ denote the complement of $G$, i.e.,
$\overline{G}=(V,\overline{E})$, where $\overline{E}$ is the complement of
$E$, with $\forall\ u,v\in V,(u,v)\in E$ if and only if
$(u,v)\notin\overline{E}$. A central fact about perfect graphs is that $G$ is
perfect if and only if $\overline{G}$ is perfect.

######  Definition 11.

Set $S\subseteq V$ is said to be a stable set in $G$, also sometimes called an
independent set, if no two vertices of $S$ are connected by an edge, i.e.,
$\forall\ u,v\in S,\ (u,v)\notin E$. Let
$w:V\rightarrow\boldsymbol{\mathit{Q}}_{+}$ be a weight function on the
vertices of $G$.

Let $G$ be an arbitrary graph. Clearly any clique in $G$ can intersect a
stable set in at most one vertex, and therefore the constraint in LP (11) is
satisfied by every stable set; note that variable $x_{v}$ indicates the extent
to which $v$ is picked in a fractional stable set. LP (11) contains such a
constraint for each clique in $G$ and is an LP-relaxation of the maximum
weight stable set problem in $G$. However, LP (11) has exponentially many
constraints, one corresponding to each clique in $G$; moreover, it is NP-hard
to solve in general [GLS88].

∑_v ∈V w_v x_v x(Q)≤1 ∀ clique $Q$ in G x_v≥0∀v ∈V

The situation is salvaged in case $G$ is a perfect graph: with the help of the
Lovasz theta function, one can can show that LP (11) can be solved in
polynomial time using the ellipsoid algorithm [GLS88, Grö99].

Below is the dual LP, which is obtained by taking $y_{Q}$ to be the dual
variable for the constraint of LP (11). The dual LP is solving a clique
covering problem.

∑_clique $Q$ in G y_Q ∑_Q ∋v y_Q ≥w_v ∀v ∈V y_Q≥0∀ clique $Q$ in G

A key fact for our purpose is that the linear system of LP (11) is totally
dual integral (TDI), see Definition 8, for perfect graphs [GLS88, Grö99]. We
provide a proof sketch below.

By Definition 9, if $G$ is perfect, $\omega(G)=\chi(G)$. Next, consider the
complement of $G$, namely $\overline{G}$; two vertices are adjacent in $G$ if
and only if they are not adjacent in $\overline{G}$. Denote by $\alpha(G)$ and
$\overline{\chi}(G)$ the size of the largest stable set and the minimum number
of disjoint cliques needed to cover all vertices of $G$, respectively.
Clearly, $\omega(G)=\alpha(\overline{G})$ and
$\chi(G)=\overline{\chi}(\overline{G})$. Furthermore, since the complement of
a perfect graph is also perfect, we get that for a perfect graph $G$,
$\alpha(G)=\overline{\chi}(G)$.

Consider LP (11) and its integer programming formulation for the case that the
weight function $w\in\\{0,1\\}^{n}$, and let $L_{p}(w)$ and $I_{p}(w)$ denote
their optimal objective function values. For the same restriction on $w$, let
$L_{d}(w)$ and $I_{d}(w)$ denote the optimal objective function values of LP
(11) and its integer programming formulation. Now,

$I_{p}(w)\leq L_{p}(w)=L_{d}(w)\leq I_{d}(w),$

where the equality follows from the LP-duality theorem, and the inequalities
follow from the relation between integral and fractional solutions.

For $w\in\\{0,1\\}^{n}$, let $G^{\prime}$ be the subgraph of $G$ induced on
vertices $v$ for which $w_{v}=1$. Since $G^{\prime}$ is also perfect,
$I_{p}(w)=\alpha(G^{\prime})$ and $I_{d}(w)=\overline{\chi}(G^{\prime})$.
Since $\alpha(G^{\prime})=\overline{\chi}(G^{\prime})$, we get that
$I_{p}(w)=I_{d}(w)$ and hence equality holds for all four programs defined
above.

To show that LP (11) is TDI we must show that for every weight function
$w\in\boldsymbol{\mathit{Z}}_{+}^{n}$, the optimal objective function value of
the dual is integral. Since $L_{d}(w)=I_{d}(w)$, this is the case if
$w\in\\{0,1\\}^{n}$. Finally, the results of Fulkerson [Ful72] and Lovasz
[Lov72] show that this integrality implies integrality of the optimal dual
even if $w\in\boldsymbol{\mathit{Z}}_{+}^{n}$. Therefore the linear system of
LP (11) is TDI and hence the polytope defined by it is integral; the vertices
of this polytope are stable sets.

###  5.2 Characterizing the Core of the Game

Since the firms in the investment management game are maximal cliques, we
first restrict the constraint in LP(11) to maximal cliques only to obtain LP
(5.2). Observe that if $Q$ is a clique in $G$ and $Q^{\prime}$ is a sub-clique
of $Q$, then the constraint in LP (11) corresponding to $Q^{\prime}$ is
redundant and can be removed, since it is implied by the constraint
corresponding to $Q$. Continuing in this manner, we are left with constraints
corresponding to maximal cliques only. Therefore, the two LPs are equivalent.

∑_v ∈V w_v x_v x(Q)≤1 ∀ maximal clique $Q$ in G x_v≥0∀v ∈V

The dual of LP (5.2) is given below.

∑_clique $Q$ in G y_Q ∑_Q ∋v y_Q ≥w_v ∀v ∈V y_Q≥0∀ maximal clique $Q$ in G

We next show that the linear system of LP (5.2) is also TDI. This is not
immediate, since as stated after Definition 8, TDI is not a property of the
polytope but of the particular linear system chosen to define it.

######  Lemma 1.

The linear system of LP (5.2) is TDI.

###### Proof.

Let $Q$ be a maximal clique in $G$, $Q^{\prime}$ be its sub-clique and $x$ be
a vector of variables $x_{v}$ for each vertex $v\in V$. For any $x$ whose
coordinates have been set to non-negative numbers, if $x(Q)\leq 1$ then
$x(Q^{\prime})\leq 1$, i.e., the latter constraint is redundant. Therefore the
linear system of (5.2) is obtained by removing redundant constraints from the
linear system of (11). Hence the two primal LPs (11) and (5.2) are equivalent.

Since the linear system of LP (11) is TDI, for any integer-valued cost vector
$w$ such that the linear program (11) has an optimum solution, the dual linear
program (11) has an integer optimal solution. We will use this fact to show
that the same holds for LPs (5.2) and (5.2) as well.

Let $w$ be an integer-valued cost vector such that the linear program (11) has
an optimum solution and let $y$ be the corresponding integer optimal solution
to LP (11). Since the two primal LPs given above are equivalent, LP (5.2) also
has an optimum solution for $w$.

Use $y$ to construct a dual solution $y^{\prime}$ for LP (5.2) using the
following operation: Suppose $y_{Q^{\prime}}>0$, where $Q^{\prime}$ is not a
maximal clique. Let $Q$ be any maximal clique of which $Q^{\prime}$ is a sub-
clique. Now subtract $y_{Q^{\prime}}$ from $y_{Q^{\prime}}$ and add it to
$y_{Q}$. Observe that new dual obtained is integral, its objective value
remains unchanged and it is feasible for LP (11) since for each vertex $v$,
${\sum_{Q\ni v}{y_{Q}}}$ remains unchanged.

Repeat this operation until $y_{Q}>0$ only if $Q$ is a maximal clique. Call
the resulting dual $y^{\prime}$. Clearly, $y^{\prime}$ is an integral optimal
dual for LP (5.2). Therefore LP (5.2) is TDI. ∎

In our setting, an optimal dual distributes the worth of the game among the
maximal cliques of $G$. However, dividing the money $y_{Q}$, given to clique
$Q$, among the vertices in the clique in not very meaningful, see Example 1
for a detailed explanation. As described in Theorem 2, in our game, the money
available to a any scenario is defined via a different process, see also
Remark 2.

######  Example 1.

The $3\times 3$ Paley graph, which is a perfect graph, is shown in Figure 1.
It has three disjoint maximum stable sets of size three each, one of each
color, and three disjoint maximal cliques, one of which is shown in bold.
Under unit cost for each asset, the worth of the investment management game on
this graph is 3 and the optimal dual assigns 1 to each of the three cliques.
Consider three scenarios, each consisting of a maximum stable set. The optimal
investment in each scenario is to buy all three of its assets, requiring 3
units of money. If the cliques were to distribute their unit money to the
assets, then at most one of these scenarios can be satisfied: by each clique
allocating its money to a different colored asset of the same scenario.
Therefore, the dual on a clique cannot be distributed among its vertices.

Figure 1: The $3\times 3$ Paley graph for Example 1

######  Theorem 2.

An imputation $y$ is in the core of the stable set game over a perfect graph
if and only if it is an optimal solution to the dual LP(5.2).

###### Proof.

($\Leftarrow$) Let $y$ be an optimal solution to the dual LP(5.2). By Lemma 1,
the linear system of LP(5.2) is TDI and therefore a maximum cost stable set in
$G$ is an optimal solution to this LP. This fact together with the LP-duality
theorem give:

$T=\mbox{\rm cost}(V)=\sum_{Q\in G}{y_{Q}}=\mbox{\rm money}(V).$

Therefore $y$ is an imputation.

Consider a scenario $S\subseteq V$. By Definition 3,

$\mbox{\rm money}(S):=\sum_{Q\in G:\ Q\cap S\neq\emptyset}{y_{Q}}.$

Clearly $Q\cap S$ is a clique in $G(S)$. Next, we will define a function, $z$,
on cliques in $G(S)$ as follows: For a clique $Q^{\prime}$ in $G(S)$, define

$z_{Q^{\prime}}:=\sum_{Q\in G:\ Q\cap S=Q^{\prime}}{y_{Q}}.$

Since each clique $Q$ of $G$ which has a non-empty intersection with $S$ will
contribute to exactly one clique in $G(S)$, namely $Q\cap S$, we get

$\mbox{\rm money}(S)=\sum_{Q^{\prime}\in G(S)}{z_{Q}^{\prime}}.$

Next, we observe that $z$ is a feasible solution to the restriction of LP (11)
to $G(S)$ because

$\forall v\in S:\ \sum_{Q^{\prime}\in G(S):\ Q^{\prime}\ni
v}{z_{Q^{\prime}}}=\sum_{Q\in G:\ Q\ni v}{y_{Q}}\geq w_{v}.$

Since the subgraph of a perfect graph is also perfect, $G(S)$ is a perfect
graph and the restriction of LP (11) to $G(S)$ satisfies TDI. Therefore a
maximum cost stable set in $G(S)$ is an optimal solution to the latter LP.
This fact together with weak duality give us

$\mbox{\rm cost}(S)\leq\sum_{Q\in G(S)}{z_{Q}}=\mbox{\rm money}(S),$

i.e., imputation $y$ satisfies scenario $S$. Therefore $y$ is a core
imputation.

($\Rightarrow$) Next, assume that $y$ is a core imputation of the investment
management game over a perfect graph $G$.

For $v\in V$, consider the scenario $S=\\{v\\}$. Since $y$ is in the core, by
Definition 5,

$\mbox{\rm money}(S)=\sum_{Q\in G:\ Q\cap S\neq\emptyset}{y_{Q}}\leq\mbox{\rm
cost}(S)=w_{v}.$

Therefore, $y$ is a feasible solution for LP(5.2).

By Definition 3,

$\mbox{\rm money}(V)=\sum_{Q\in G}{y_{Q}}=T=\mbox{\rm cost}(V).$

Therefore by the TDI of LP(5.2), the objective function value of $y$ is the
same as that of the optimal value of the primal. This together with the
feasibility of $y$ establishes that $y$ is an optimal solution to the dual
LP(5.2). ∎

######  Corollary 1.

The core of the stable set game over a perfect graph is non-empty.

##  6 Discussion

As stated in the Introduction, the notion of core was given in the nineteenth
century by Edgeworth [Edg81] in the context of general equilibrium theory, and
it was ported to cooperative game theory in the 1950s by Gillies [Gil59].
However, we have applied this notion in the context of a game against nature.
Hence perhaps the most important question raised by our work is determining
the “natural home” of this notion within game theory. A related question is
the following: Remark 1 draws a clear contrast between the way the core is
used in cooperative game theory and in our game. Are there other ways of
interpreting and using the notion of core, without taking liberties with its
formal framework?

A simple way of defining the game presented in this paper would use the graph-
theoretic language of stable sets and cliques. Definition 1 moves a step
towards modeling an economic situation. There is no doubt that our model falls
short of providing a solution concept for a realistic economic situation;
however, that was not the intent of this paper. We simply wanted to provide
evidence that the beautiful solution concept of core is more versatile than
previously envisaged. We hope other researchers will be able to build on this
viewpoint to find realistic applications of the notion of core outside of
cooperative game theory.

##  7 Acknowledgements

I wish to thank Martin Bullinger insightful comments on the writeup, and
Gerard Cornuejols, Federico Echenique, Naveen Garg, Martin Groetschel, Ruta
Mehta, Joseph Root, Thorben Trobst and Richard Zeckhauser for valuable
discussions.

## References

  * [BB97] Tapan Biswas and Tapan Biswas.  Games against nature and the role of information in decision-making under uncertainty.  Decision-making under Uncertainty, pages 185–196, 1997.
  * [BKP12] Péter Biró, Walter Kern, and Daniël Paulusma.  Computing solutions for matching games.  International journal of game theory, 41(1):75–90, 2012.
  * [Bon63] Olga N Bondareva.  Some applications of linear programming methods to the theory of cooperative games.  Problemy Kibernetiki, 10(119):139, 1963.
  * [DD10] Gabrielle Demange and Xiaotie Deng.  Universally balanced combinatorial optimization games.  Games, 1(3):299–316, 2010.
  * [DIN99] Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi.  Algorithmic aspects of the core of combinatorial optimization games.  Mathematics of Operations Research, 24(3):751–766, 1999.
  * [Edg81] Francis Ysidro Edgeworth.  Mathematical psychics: An essay on the application of mathematics to the moral sciences, volume 10.  CK Paul, 1881.
  * [Ful72] Delbert R Fulkerson.  Anti-blocking polyhedra.  Journal of Combinatorial Theory, Series B, 12(1):50–71, 1972.
  * [GH81] Daniel Granot and Gur Huberman.  Minimum cost spanning tree games.  Mathematical programming, 21(1), 1981.
  * [GH84] Daniel Granot and Gur Huberman.  On the core and nucleolus of minimum cost spanning tree games.  Mathematical programming, 29(3):323–347, 1984.
  * [Gil59] Donald B Gillies.  Solutions to general non-zero-sum games.  Contributions to the Theory of Games, 4(40):47–85, 1959.
  * [GLS88] M. Grotschel, L. Lovasz, and A. Schirjver.  Geometric Algorithms and Combinatorial Optimization.  Springer-Verlag, 1988.
  * [Grö99] Martin Grötschel.  My favorite theorem: characterizations of perfect graphs.  1999\.
  * [GS62] David Gale and Lloyd S Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [GS04] Michel X. Goemans and Martin Skutella.  Cooperative facility location games.  Journal of Algorithms, 50(2):194–214, 2004.
  * [Kol83] Antoon Kolen.  Solving covering problems and the uncapacitated plant location problem on trees.  European Journal of Operational Research, 12(3):266–278, 1983.
  * [KP08] Tamás Király and Júlia Pap.  Total dual integrality of rothblum’s description of the stable-marriage polyhedron.  Mathematics of Operations Research, 33(2):283–290, 2008.
  * [KS20] Zhuan Khye Koh and Laura Sanità.  An efficient characterization of submodular spanning tree games.  Mathematical Programming, 183(1):359–377, 2020.
  * [Lov72] László Lovász.  Normal hypergraphs and the perfect graph conjecture.  discrete Mathematics, 2(3):253–267, 1972.
  * [LP86] L. Lovász and M.D. Plummer.  Matching Theory.  North-Holland, Amsterdam–New York, 1986.
  * [Mou14] Hervé Moulin.  Cooperative microeconomics: a game-theoretic introduction, volume 313.  Princeton University Press, 2014.
  * [NZKI97] Hiroshi Nagamochi, Dao-Zhi Zeng, Naohiśa Kabutoya, and Toshihide Ibaraki.  Complexity of the minimum base game on matroids.  Mathematics of Operations Research, 22(1):146–164, 1997.
  * [Rot92] Uriel G Rothblum.  Characterization of stable matchings as extreme points of a polytope.  Mathematical Programming, 54(1):57–67, 1992.
  * [Sch86] A. Schrijver.  Theory of Linear and Integer Programming.  John Wiley & Sons, New York, NY, 1986.
  * [Sha65] Lloyd S Shapley.  On balanced sets and cores.  Technical report, RAND Corp Santa Monica, California, 1965.
  * [SS71] Lloyd S Shapley and Martin Shubik.  The assignment game I: The core.  International Journal of Game Theory, 1(1):111–130, 1971.
  * [SZ84] Dov Samet and Eitan Zemel.  On the core and dual set of linear programming games.  Mathematics of Operations Research, 9(2):309–316, 1984.
  * [Vat89] John H Vande Vate.  Linear programming brings marital bliss.  Operations Research Letters, 8(3):147–153, 1989.
  * [Vaz22a] Vijay V Vazirani.  The general graph matching game: Approximate core.  Games and Economic Behavior, 132, 2022.
  * [Vaz22b] Vijay V Vazirani.  New characterizations of core imputations of matching and $b$-matching games.  In Foundations of Software Technology and Theoretical Computer Science, 2022.
  * [Vaz23] Vijay V Vazirani.  Lp-duality theory and the cores of games.  arXiv preprint arXiv:2302.07627, 2023.


somespace rowpostcode =somespace, margins = centering

# Investigation of Densely Connected Convolutional Networks with Domain
Adversarial Learning for Noise Robust Speech Recognition

Chia Yu Li, Ngoc Thang Vu

###### Abstract

We investigate densely connected convolutional networks (DenseNets) and their
extension with domain adversarial training for noise robust speech
recognition. DenseNets are very deep, compact convolutional neural networks
which have demonstrated incredible improvements over the state-of-the-art
results in computer vision. Our experimental results reveal that DenseNets are
more robust against noise than other neural network based models such as deep
feed forward neural networks and convolutional neural networks. Moreover,
domain adversarial learning can further improve the robustness of DenseNets
against both, known and unknown noise conditions.

##  1 Introduction

In the last years, automatic speech recognition (ASR) performance has been
significantly improved through the use of neural networks with deep structures
[1, 2, 3]. Various neural network architectures have been developed to improve
ASR performance. They are variations of time delay neural networks (TDNNs)
[4], convolutional neural networks (CNNs) [5] recurrent neural networks (RNNs)
[6], and their combinations [7]. Among them, very deep CNNs demonstrate
impressive performance [8, 9, 10] especially in noisy conditions [8].

Recently in the computer vision research community, densely connected
convolutional networks (DenseNets) have obtained significant improvements over
the state-of-the-art networks on four highly competitive object recognition
benchmark tasks [11]. The idea is to introduce shorter connections between
layers close to the input and those close to the output which alleviate the
vanishing-gradient problem. Furthermore, DenseNets require fewer parameters
than traditional CNNs with the same deep structure [11]. In [12], we showed
that DenseNets can be used for acoustic modeling achieving impressive
performance.

In this paper, we explore noise robustness of DenseNets and their extension
with domain adversarial learning. This method was originally proposed by Ganin
et al. [13] for unsupervised domain adaptation in natural language processing
and was then applied to deep feed forward neural networks (DNNs) for noise
robust speech recognition [14, 15]. However to the best of our knowledge,
domain adversarial learning has never been examined with a complex network
like DenseNets before. Our experimental results on noisy data demonstrate that
DenseNets can effectively improve the noise robustness of the system
outperforming other neural based models. Using domain adversarial learning can
further improve their robustness against both, known and unknown noise
conditions.

##  2 Methods

###  2.1 DenseNets Acoustic Models

In this subsection, we first describe DenseNets and review the method how to
use DenseNets for acoustic modeling [12]. The key idea of DenseNets is the
introduction of shorter connections between layers close to the input and
those close to the output which alleviate the vanishing-gradient problem. For
acoustic modeling, DenseNets take the unadapted features 40-dimensional log
Mel filterbank as input and predict the context dependent HMM states (senones)
[12].

Given an input $x_{0}$ and a CNN with $N$ layers, where each layer $n$ is
equipped with a nonlinear transformation $H_{n}(\cdot)$ which is the
composition of three consecutive operations: batch normalization, followed by
a ReLU and a $3\times 3$ convolution, DenseNets introduce direct connections
from any layer to all subsequent layers. The output of $n^{th}$ layer is:

$x_{n}=H_{n}([x_{0},x_{1},x_{2},...,x_{n-1}])$ (1)

where $[x_{0},x_{1},x_{2},...,x_{n-1}]$ refers to the concatenation of the
feature maps yielded in all the previous layers. Fig. 1 illustrates the dense
connectivity structure, in which each layer takes all preceding feature-maps
as input. This structure is called dense block.

Figure 1: A 3-layer dense block, in which each layer takes all preceding
feature-maps as input

DenseNets consist of multiple dense blocks, connected in series and separated
by transition layers. Each transition layer consists of a $1\times 1$
convolution layer and a $2\times 2$ average pooling layer. Fig. 2 illustrates
how these dense blocks and transition layers are composed in DenseNets. Note
that pooling is only performed outside of dense blocks.

Figure 2: A DenseNet architecture with three dense blocks connected via
transition layers

Furthermore, DenseNets reduce the number of feature-maps by $1\times 1$
convolution layer in the transition layer to improve model compactness. For
example, if a dense block has $y$ feature-maps, the transition layer generates
$\lfloor\theta y\rfloor$ output feature-maps, where $\theta$ is the
compression factor and the range is $0<$ $\theta$ $\leq 1$. The growth rate of
DenseNets is the number of channels in their convolution layers. By equation
(1), the $n^{th}$ layer within a dense block has $k\times(n-1)+k_{0}$ input
feature-maps, where $k_{0}$ is the number of input channels and $k$ (the
model’s growth rate) is the number of channels for subsequent convolution
layers. DenseNets have better performance when $k$ is a small integer, e.g.
$k=12$ [11].

###  2.2 Domain Adversarial Learning

In this subsection, we introduce the extension of DenseNets with domain
adversarial learning [13]. In this context, noisy conditions act as domain
information.

The overall architecture of the domain adversarial learning of DenseNets is
shown in Fig 3. It consists three sub-networks: the sub-network ($y$) is for
senone classification, the sub-network ($z$) is for domain classification and
the share-network ($x$) is the share part of the two tasks. The shared-network
($x$) can be seen as a feature extractor to convert an input vector to its
latent representation. Each output sub-network acts as a classifier to
calculate posterior probabilities of classes given the this latent
representation [14, 15]. In the domain adversarial learning, the
representation is learned adversarially to the domain classification and
friendly to the senone classification, so that domain-dependent information to
the senone classifier is removed from the representation.

Figure 3: An architecture of DenseNets with domain adversarial learning which
consists of there sub-networks: features extractor sub-network (x), senone
classification sub-network (y) and domain classification sub-network (z)

Let $\theta_{x},\theta_{y},\theta_{z}$ denote the parameters of the share-
network (x), sub-network (y) and sub-network (z), respectively. The cross-
entropy loss functions for the senone classifier and domain classifier are
defined as

$\mathcal{L}_{y}(\theta_{x},\theta_{y})=-\sum_{i}logP(y_{i}|x_{i};\theta_{x},\theta_{y})$
(2)
$\mathcal{L}_{z}(\theta_{x},\theta_{z})=-\sum_{i}logP(z_{i}|x_{i};\theta_{x},\theta_{z})$
(3)

The parameters are updated as

$\theta_{y}\leftarrow\theta_{y}-\epsilon\dfrac{\partial\mathcal{L}_{y}}{\partial\theta_{y}}$
(4)
$\theta_{z}\leftarrow\theta_{z}-\epsilon\dfrac{\partial\mathcal{L}_{z}}{\partial\theta_{z}}$
(5)
$\theta_{x}\leftarrow\theta_{x}-\epsilon(\dfrac{\partial\mathcal{L}_{y}}{\partial\theta_{x}}-\lambda\dfrac{\partial\mathcal{L}_{z}}{\partial\theta_{x}})$
(6)

where $\lambda$ is the gradient reversal coefficient which is a positive
scalar parameter to adjust the strength of the regularization.

The first layer of the sub-network ($z$) is the gradient reversal layer (GRL)
as proposed in [14]. In the forward propagation phase, the GRL just passes the
input to the output as follows:

$\xi_{out}\leftarrow\xi_{in}$ (7)

where $\xi_{in}$ and $\xi_{out}$ represent input and output vectors of the
layer, respectively. In the backward propagation phase, the GRL reverses the
gradient by multipling it with $\lambda$ as follows:

$\dfrac{\partial\mathcal{L}}{\partial\xi^{in}}\leftarrow-\lambda\dfrac{\partial\mathcal{L}}{\partial\xi^{out}}$
(8)

Hence the shared-network (x) is trained adversarially to the sub-network (y)
for the domain classification. When the training is finished, the output of
the entire network (x, y) for the senone classification is used for decoding.

##  3 Setup

Two experiments are conducted in this paper. The goal for the first experiment
is to explore DenseNets’ robustness at different levels of noise. We compare
the baseline models, which are deep neural networks (DNNs), CNNs and TDNNs,
and DenseNets on noise corrupted DARPA 1000-words English language Resource
Managemen (RM). The second experiment examines the effectiveness of domain
adversarial learning, in which we compare the performance of DenseNets,
DenseNets-AD and the best baseline model TDNNs on noise corrupted RM and
Aurora 4 Task (Aurora4).

###  3.1 Resources

####  Data

The noise corrupted RM is made by artificially adding different types of noise
at different values of SNR 111Signal-to-Noise ratio (SNR) is defined as the
ratio of the power of a signal to the power of noise
($\frac{P_{signal}}{P_{noise}}$) to RM [16] using the large-scale open-source
acoustic simulator developed in [17]. It contains 1,993 noisy conditions:
1,500 are used for training and 493 for testing. We created three noise
corrupted data sets with different SNRs: Data-1 (SNR from 0 to 4), Data-2 (SNR
from 0 to 8) and Data-3 (SNR from 0 to 12). Figure 4 shows the data
distribution of Data-1, Data-2 and Data-3. For example, 19.9% utterances in
Data-1 are adding noise (randomly chosen) at SNR=0, 20.3% of them are at
SNR=1, 19.6% of them are at SNR=2, 21.2% of them are at SNR=3 and 19% of them
are at SNR=4. Two noise corrupted test sets are used in this paper. In the
"known-noise test set" (KNN), the noise is randomly picked from 1,500 training
noise and added to the utterance at the same range of SNR used in the training
set. On the contrary in the "unknown-noise test set" (UKN), the noise is
selected from 493 testing noises and added to the utterance.

Figure 4: The data composition of Data-1, Data-2 and Data-3 from left to
right.

The Aurora 4 task, which is a medium vocabulary task speech recognition task,
is based on the Wall Street Journal (WSJ0) dataset [18]. It contains 16 kHz
speech data in the presence of six additive noises (car, crowd of people,
restaurant, street, airport and train station) with linear convolutional
channel distortions. The multi-condition training set with 7138 utterances
from 83 speakers includes a combination of clean utterance and utterance
corrupted by one of six different noises at 10-20 dB SNR. 3,569 utterances are
from the primary Sennheiser micro-phone and 3,569 utterances are from the
secondary microphone. The test data is made using the same types of noise and
microphones, and these can be classified into five test-conditions: clean,
noisy, clean with channel distortion, noisy with channel distortion, and all
of them which will be referred to as A, B, C, D and Average respectively.

####  Baseline systems

The baseline models in our experiments are DNNs, CNNs and TDNNs. DNNs take the
40-dimensional log Mel filterbank features as input and contain six hidden
layers with sigmoid activation functions and one fully-connected output layer
with a softmax activation. Each hidden layer has 1024 units. CNNs are composed
of two convolution layers and max-pooling layers, and four affine layers with
sigmoid activation function. Each affine layer contains 1024 units and is
trained using 40-dimensional log Mel filterbank features with the first and
the second time derivatives. Both DNNs and CNNs use the same context window of
five and batch size of 256. The best TDNNs in Kaldi use in addtion iVector for
speaker adapted systems. They contain five weight layers with different
context specifications (subsampling). Furthermore, the TDNNs recipe applies
data augmentation technique which does speed perturbation of the training data
in order to emulate vocal tract length perturbations and speaking rate
perturbation. All the ASR systems are built up with the Kaldi speech
recognition toolkit [19]. The acoustic models except TDNNs are implemented
with PDNN (A Python Deep learning toolkit) [20], Theano [21], Lasagne [22] and
DenseNets source code [11].

####  Hyperparameters for DenseNets and DenseNets-AD

The architecture of DenseNets in this paper is the same as the best model in
the previous work [12]: the first layer is $3\times 3$ convolution which is
followed by 4 dense blocks. Each block contains 14 $3\times 3$ convolutional
layers. Each dense block except the last one is followed by a transition which
consists of $1\times 1$ convolution and $2\times 2$ average pooling. The depth
is 65, the growth rate is 12 and the compression ratio is 0.5. All the
convolutional layer use kernel size $3X3$. The architecture of DenseNets-AD is
mentioned in figure 3 except the shared layer is only the first convolutional
layer and the following layers are training for senone (phoneme) recognition
task. The gradient reversal coefficient $\lambda$ is 0.5. The input features
for both models is 40-dimensional log Mel filterbank features with the first
and the second time derivatives.

Figure 5: The WERs of TDNN, DenseNets and DenseNets-AD on noisy test sets at
different SNR ranges; DNNs(KNN) means the WER of DNNs on known-noise test set
(KNN) and DNNs(UKN) means the WER of DNNs on unknown-noise test set (UKN).

##  4 Results and Discussion

Figure 5 shows the WERs of all the baseline models and DenseNets on noise
corrupted RM test set at different ranges of SNR. Note that all the models are
examined on the noise corrupted test set at the same range of SNR as the
training. For example, the model are trained on the noise corrupted training
set at the SNR range from 0 to 4 and tested on the noise corrupted test set at
the same SNR range. The experimental results in figure 5 show that the WERs of
DNNs and CNNs increase when the SNR decreases. However, TDNNs and DenseNets
are relatively stable when reducing SNR. Overall, DenseNets outperform the
baseline models on all the test sets.

SNR | System | KNN | UKN
---|---|---|---
| TDNNs | 6.93 | 8.59
0-12 | DenseNets | 6.30 | 7.64
| DenseNets-AD | 6.11 | 6.97
| TDNNs | 9.16 | 9.18
0-8 | DenseNets-AD | 8.02 | 8.20
| DenseNets-AD | 7.84 | 7.95
| TDNNs | 10.07 | 12.21
0-4 | DenseNets | 9.33 | 10.48
| DenseNets-AD | 8.64 | 9.68
Table 1: The WERs of TDNN, DenseNets and DenseNets-AD on KNN and UKN test sets. Where KNN means known-noise test set and UKN means uknow-noise test set. System | A | B | C | D | Average
---|---|---|---|---|---
TDNNs | 3.47 | 7.44 | 10.14 | 21.91 | 13.57
DenseNets | 3.57 | 7.29 | 7.12 | 16.56 | 11.53
DenseNets-AD | 3.58 | 6.58 | 6.76 | 16.42 | 10.21
Table 2: WERs of TDNNs, DenseNets and DenseNets-AD on Aurora4 test set with A,
B, C, D conditions. (A: clean and Sennheiser mic, B: Sennheiser mic and noise
added, C: clean and 2nd mic, D: 2nd mic and noise added)

Table 1 and Table 2 show the comparison between TDNNs, DenseNets and densely
connected convolutional networks with domain adversarial learning (DenseNets-
AD) on the noise corrupted RM and Aurora4. As expected, the WERs of three
models increase when the SNR decreases. However, DenseNets-AD achieves best
performance on both KNN and UKN test sets at all three SNR ranges. One of the
reason is that TDNNs and DenseNets recognize noise as speech when the noise
becomes severe. Table 3 shows one example of TDNNs and DenseNets failing to
distinguish the noise and speech while DenseNets-AD was unaffected.

Reference | LIST FULL LOCATION DATA FOR TRACK FFF088
---|---
TDNNs |  LIST FULL LOCATION DATA FOR TRACK FFF088 TO EIGHT
DenseNets |  LIST FULL LOCATION DATA FOR TRACK FFF088 IN THE EIGHT
DenseNets-AD | LIST FULL LOCATION DATA FOR TRACK FFF088
Table 3: The references and the ASR outputs from TDNNs, DenseNets and
DenseNets-AD of an utterance when adding dumpster truck noise at SNR=1

##  5 Conclusions

This paper investigates noise robustness of DenseNets and their extension with
domain adversarial learning. Our experimental results demonstrate that
DenseNets are more robust against noise than other types of neural networks.
Furthermore, we show that applying domain adversarial learning improves the
performance of DenseNets and model generalization.

## References

  * Hinton et al. [2012] Hinton, G., L. Deng, D. Yu, G. Dahl, A. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. Sainath, and B. Kingsbury: _Deep neural networks for acoustic modeling in speech recognition_.  In _IEEE Signal Process. Mag._ , vol. 29(6), pp. 82–97. 2012.
  * Seide et al. [2011] Seide, F., G. Li, and D. Yu: _Conversational speech transcription using context-dependent deep neural networks_.  In _Proc. of the Interspeech_. 2011.
  * Dahl et al. [2012] Dahl, G. E., D. Yu, L. Deng, and A. Acero: _Context-dependent pre-trained deep neural networks for large-vocabulary speech recognition_.  _IEEE Transactions on audio, speech, and language processing_ , 2012\.
  * Waibel et al. [1990] Waibel, A., T. Hanazawa, G. Hinton, K. Shikano, and K. J. Lang: _Phoneme recognition using time-delay neural networks_.  In _Readings in speech recognition_. 1990.
  * Abdel-Hamid et al. [2012] Abdel-Hamid, O., A.-r. Mohamed, H. Jiang, and G. Penn: _Applying convolutional neural networks concepts to hybrid nn-hmm model for speech recognition_.  In _Proc. of ICASSP_. 2012.
  * Graves et al. [2013] Graves, A., A.-r. Mohamed, and G. Hinton: _Speech recognition with deep recurrent neural networks_.  In _Proc. of the ICASSP_. 2013.
  * LeCun and Bengio [1995] LeCun, Y. and Y. Bengio: _Convolutional networks for images, speech, and time series_.  In _The Handbook of Brain Theory and Neural Networks_. 1995.
  * Qian and Woodland [2016] Qian, Y. and P. C. Woodland: _Very deep convolutional neural networks for robust speech recognition_.  In _Proc. of the IEEE SLT_. 2016.
  * Yu et al. [2016] Yu, D., W. Xiong, J. Droppo, A. Stolcke, G. Ye, J. Li, and G. Zweig: _Deep convolutional neural networks with layer-wise context expansion and attention_.  In _Proc. of Interspeech_. 2016.
  * Xiong et al. [2018] Xiong, W., L. Wu, F. Alleva, J. Droppo, X. Huang, and A. Stolcke: _The microsoft 2017 conversational speech recognition system_.  In _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 5934–5938. IEEE, 2018\.
  * Huang et al. [2017] Huang, G., Z. Liu, L. Van Der Maaten, and K. Q. Weinberger: _Densely connected convolutional networks_.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. 2017.
  * Li and Vu [2018] Li, C.-Y. and N. T. Vu: _Densely connected convolutional networks for speech recognition_.  In _Proc. of the 13th ITG conference on Speech Communication_. 2018.
  * Ganin et al. [2016] Ganin, Y., E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky: _Domain-adversarial training of neural networks_.  _The Journal of Machine Learning Research_ , 2016.
  * Shinohara [2016] Shinohara, Y.: _Adversarial multi-task learning of deep neural networks for robust speech recognition_.  In _Proc. of the Interspeech_. 2016.
  * Denisov et al. [2018] Denisov, P., N. T. Vu, and M. Ferras: _Unsupervised domain adaptation by adversarial learning for robust speech recognition_.  In _Proc. of the 13th ITG conference on Speech Communication_. 2018.
  * Price et al. [1988] Price, P., W. M. Fisher, J. Bernstein, and D. S. Pallett: _The DARPA 1000-word resource management database for continuous speech recognition_.  In _Proc. of the ICASSP_. 1988.
  * Ferras et al. [2016] Ferras, M., S. Madikeri, P. Motlicek, S. Dey, and H. Bourlard: _A large-scale open-source acoustic simulator for speaker recognition_.  _IEEE Signal Processing Letters_ , 2016.
  * Parihar et al. [2004] Parihar, N., J. Picone, D. Pearce, and H.-G. Hirsch: _Performance analysis of the aurora large vocabulary baseline system_.  In _Proc. of the 12th European Signal Processing Conference_. 2004.
  * Povey et al. [2011] Povey, D., A. Ghoshal, G. Boulianne, L. Burget, O. Glembek, N. Goel, M. Hannemann, P. Motlicek, Y. Qian, P. Schwarz et al.: _The kaldi speech recognition toolkit_.  In _Proc. of the IEEE ASRU_. 2011.
  * Miao [2014] Miao, Y.: _Kaldi+pdnn: Building dnn-based ASR systems with kaldi and PDNN_.  In _arXiv e-prints:1401.6984_. 2014.
  * Theano Development Team [2016] Theano Development Team: _Theano: A Python framework for fast computation of mathematical expressions_.  In _arXiv e-prints:1605.02688_. 2016.
  * Dieleman and et al. [2015] Dieleman, S. and et al.: _Lasagne: First release_.  2015\.