\section{Introduction}
\label{sec:introduction}

The emergence of symbolic language has always been an important issue, 
which attracts attentions from a broad range of communities,
including philology~\cite{}, biology~\cite{}, and computer
science~\cite{}. Especially in computer science, efforts in recent years try to explore
the emergence of symbolic language in virtual multi-agent environments, where
agents are trained to communicate with neural network based methods such as deep
reinforcement learning~\cite{}. 
%Such works can be roughly classified into two categories,
%referential game~\cite{} and multi-agent reinforcement learning (MARL)~\cite{}, based on
%the environment setting.  


The quality of emergent symbolic language is typically measured by its \emph{compositionality}.
Compositionality is a principle that determines
whether the meaning of a complex expression (e.g, phrase), which is assembled out of a
given set of simple components (e.g., symbols), can be determined by its
constituent components and the rules that combines them~\cite{}.
\note{For example, the expression "AAAI is a conference'' consists of two
meaningful words ``AAAI'' and ``conference'', and a rule for definition (``is'').
More recently, measuring the compositionality \note{xxxxx}.}


%It
%is a concept in the philosophy of language [1], which describes and quantifies
%how complex expressions can be assembled out of simpler parts [2]. For example,
%Figure1(a) shows a perfect compositional language (with maximum
%compostionality). In this example, each shape is represented by a unique value
%of symbol $s_0$ and each color is represented by symbol $s_1$. Figure1(b) shows a
%language with low compostionality. Colors and shapes are ambiguous if only we
%extract information from a single symbol.
%
%
\begin{figure}[t]
  \centering
  \includegraphics[width=0.9\columnwidth]{fig/occupy}
  \caption{\rmk{compositionality.}}
  \label{fig:induction}
  \end{figure}

Prior studies focus on achieving high compositional symbolic language 
through \emph{deliberately handcrafted} inductions, e.g., small vocabulary
sizes~\cite{}, memoryless~\cite{}, carefully constructed rewards~\cite{}, and
ease-of-teaching~\cite{}. \note{The basic intuition is that high compositional symbolic
language cannot emerge without induction in existing multi-agent environment.}
Figure~\ref{fig:induction} reports the compositionality when training two agents in the widely-used
listener-speaker referential game, and it can be observed that \note{the compositionality
of emerged symbolic language is extremely low without any induction}.
Though such unnatural inductions are useful, they prevent us from better understanding the mystery of
the emergence of language and even intelligence among our pre-human ancestors.
Yet, few works investigate the emergence of high compositional symbolic language
\emph{naturally}, i.e., without handcrafted inductions.
In other words, it is never clear whether \emph{natural}
environment and agents are sufficient for achieving high compositionality. 

In this paper, we are the first work to achieve high compositional
symbolic language without any deliberately handcrafted induction. Concretely, 
by thoroughly analyzing the compositionality of emerged symbolic
language after removing the inductions in a listener-speaker referential game framework, 
we observe that the agent capacity 
plays a key role in improving the compositionality, and thus we can achieve
 a high compositional symbilic language in such a natural environment. 

%Figure~\ref{fig:comp} reports the compositionality when train two
%agents in a listener-speaker referential game. It can be observed that \note{it
%  is challenging to achieve high compositionality without induction as
%  xxxxxx}. Moreover, we observe that the agent capacity plays a key role in
%compositionality, see Figure xxx.

%focus on the natural emergence of high compositional symbolic language
%naturally without any handcrafted induction.
%Initially, we thoroughly analyze the compositionality of emerged symbolic
%language after removing the \emph{deliberately handcrafted}
%inductions. Figure~\ref{fig:comp} reports the compositionality when train two
%agents in a listener-speaker referential game. It can be observed that \note{it
%  is challenging to achieve high compositionality without induction as
%  xxxxxx}. Moreover, we observe that the agent capacity plays a key role in
%compositionality, see Figure xxx.

The quantitative relationship between the agent capacity and the compositionality 
of symbolic language is revealed both theoretically and experimentally.
%theoretically
Regarding the theoretical analysis, we use the
\note{Markov Series Channel (MSC)~\cite{} to model the language transmission process and a
novel mutual information-based metric to measure the compositionality quantitatively}. 
%experimentally
Regarding the experimental validation, two different dedicated experiments, i.e.,
\note{XXX and XXX, are utilized for XXX}.
%Regarding the experimental validation, it is conducted on a listener-speaker
%referential game framework with eliminated unnatural inductions.
Both theoretical analysis and
  experimental results lead to a counter-intuitive conclusion that lower agent
  capacity facilitates the emergence of symbolic language with higher
  compositionality.
  

%Prior studies focus on investigating how to affect the
%compositionality of the emergent language. Researchers
%have found that various environmental pressures would affect compositionality,
%e.g., small vocabulary sizes[3], memoryless[4], 
%carefully constructed rewards[5] and ease-of-teaching[6]. However, these works
%only consider \emph{nurture} [7] (i.e., environmental factors), rather than
%\emph{nature} (i.e., hereditary factors from agents), when inducing or exploring
%the emergent language without exception. Moreover, some environmental pressures,
%like regrading the entropy as an item of additional rewards, may be too ideal to
%exist in the real world. 

%In contrast to prior work, we investigate the compositionality of emergent
%language from a new perspective, i.e., the agent capacity. Different from
%previous work that only considers external environmental factors, we study the
%impact of agent internal capacity on the compositionality of emergent
%language. Specifically, we first analyze the correlation between agent capacity
%and compositionality theoretically, and propose a novel metric to evaluate
%compostionality quantitatively. Then, on the basis of the theoretical analysis
%and the metric proposed, we verify the relationship between agent capacity and
%compostionality experimentally. 
%
%
%Theoretically, on the basis of mutual information theory[8], we analyse the
%correlation between compostionality of the emergent language and complexity of
%the semantic information carried by a symbol. Such semantic information can be
%characterized in neural network-based agents and requires the certain capacity
%(i.e., the count of neural nodes in the hidden layer). Specifically, we use the
%MSC (Markov Series Channel)[9] to model the language transmission process and
%use the probability distribution of symbols and concepts to model policies of
%agents. After modelling, we use the mutual information matrix $MRI^B$ to
%quantitatively represent the semantic information, and each column of $MRI^B$
%correspond to information carried by one symbol. We find that each column of the
%matrix should be an one-hot vector for a perfectly compositional language, cause
%a symbol only transmit information of a certain concept exclusively. Therefore,
%the average similarity between the columns of $MRI^B$ and a one-hot vector is
%higher, indicating that the emergent language is more compostional (i.e., the
%compostionality is higher). We propose the metric \emph{MIS} to measure
%compositionality by calculating such average similarity
%quantitatively. Different from other metrics, such as \emph{topographic
%  similarity}[10] and \emph{posdis}[11], \emph{MIS} is a bilateral metric
%because it takes both listener and speaker's understanding of semantics into
%account. Moreover, \emph{MIS} comes lower indicates that the emergent language
%tends to delivery semantic information about more concepts in each symbol, so
%that the complexity of semantic information carried by one symbol tend to be
%higher. As a result, higher agent capacity is required to characterize the more
%complex semantic information when \emph{MIS} (i.e., compositionality) is lower. 
%
%Experimentally, we verify the relationship between agent capacity and
%compostionality. We build a listener-speaker referential game as experimental
%framework, and train agents of Stochastic Policy Gradient Algorithm[12] with the
%correctness of forecast output from the listener as the criterion (i.e.,
%reward). The criterion does not imply any environmental pressures on the
%agents. Therefore, we can study the impact of capacity on the compositionality
%without any environmental pressures’ affection. Moreover, to study the impact of
%capacity on the compositionality under a more ‘natural’ environment, the speaker
%and listener are disconnected models without sharing parameters. Our first
%experiment is to verify that agent need higher capacity to master an artificial
%language with lower compositionality under a scenario of language
%teaching. Specifically, we fabricate the speaker to output preassigned languages
%with different compostionality respectively, and train the listener to interpret
%the preassigned language. For all artificial language, we compare the accuracy
%curve during training process of the listener with different capacity, and show
%how capacity affect learning languages with different compostionality. Our
%second experiment is to verify that lower agent capacity would facilitate higher
%compostionality of the emergent language under a scenario of language
%inducing. Specifically, we training a speaker and a listener to create a
%communication protocol (i.e., emergent language), so that the listener can
%select the same object which is received by the speaker. By adjusting capacity
%and comparing the compositionality of emergent language, we show that the
%emergent language attend to have higher compositionality when agent capacity is
%restricted more stringently. As a result, these two experiments verify the
%negative correlation between agent capacity and compostionality both in language
%teaching and language inducing. 


%
%This paper makes the following contributions:
%
%We propose a ‘bilateral’ metric \emph{MIS}, which takes both listener and speaker's understanding of semantics into account. Compare to previous ‘unilateral’ metrics, \emph{MIS} can handle situations where the semantics of the listener and the speaker are not exactly the same (, we discuss the problem in next section). 
%
%We analyse the relationship between compostionality and agent capacity theoretically.
%
%We verify the negative correlation between agent capacity and compostionality both in language teaching and language inducing.
%%\endsection


In this paper, we made the following contributions:
\begin{itemize}[topsep=0pt,itemsep=0cm]
\item To our best knowledge, we are the first work to successfully achieve 
high compositional symbolic
  language naturally, without any deliberately handcrafted induction.
\item We thoroughly analyze the compositionality of emerged symbolic language
  after removing deliberately handcrafted inductions, and confirm that the agent
  capacity acts as a key factor for compositionality.
\item We experimentally verified the conclusion for relationship between agent
  capacity. Both theoretical analysis and
  experimental results lead to a counter-intuitive conclusion that lower agent
  capacity facilitates the emergence of symbolic language with higher
  compositionality.
\end{itemize}
