title: Discrete Word Embedding for Logical Natural Language Understanding
authors: Masataro Asai Zilu Tang
text: 
  Gallai-Ramsey numbers for graphs with five vertices and eight edges
  
      Xueli Su, Yan Liu
  
  School of Mathematical Sciences, South China Normal University,
  
   Guangzhou, 510631, P.R. China  This work is supported
  by the Scientific research fund of the Science and Technology Program of Guangzhou, China(No.202002030183), by the Natural Science Foundation of Qinghai, China (No.2020-ZJ-924).
   Correspondence should be addressed to Yan
  Liu(e-mail:liuyan@scnu.edu.cn)
      
  ==========================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  We propose an unsupervised neural model for learning a discrete embedding of words.
  Unlike existing discrete embeddings, our binary embedding supports vector arithmetic operations similar to continuous embeddings.
  Our embedding represents each word as a set of propositional statements describing a transition rule in classical/STRIPS planning formalism.
  This makes the embedding directly compatible with symbolic, state of the art classical planning solvers.
  
  
  
  
  § INTRODUCTION
  
  
  
  When we researchers write a manuscript for a conference submission,
  we do not merely follow the probability distribution crystalized in our brain cells.
  Instead, we modify, erase, rewrite sentences over and over,
  while only occasionally let the fingers produce a long stream of thought.
  This writing process tends to be a zero-shot attempt to
  materialize and optimize a novel work that has never been written.
  Except for casual writing (e.g. online messages),
  intelligent writing inevitably contains an aspect of backtracking and heuristic search behavior,
  and thus is often like planning for information delivery while optimizing various metrics,
  such as the impact, ease of reading, or conciseness.
  
  After the initial success of the distributed word representation in Word2Vec <cit.>,
  natural language processing techniques have achieved tremendous progress in the last decade,
  propelled primarily by the advancement in data-driven machine learning approaches based on neural networks.
  However, these purely data-driven approaches that blindly follow the highest probability interpolated from data at each time step
  could suffer from biased decision making <cit.> and is heavily criticized recently.
  
  
  Meanwhile, in recent years,
  significant progress has been made <cit.>
  in the field of Automated Planning
  on resolving the so-called Knowledge Acquisition Bottleneck <cit.>,
  the common cost of human involvement in converting real-world problems into the inputs for symbolic AI systems.
  Given a set of noisy visual transitions in fully observable puzzle environments,
  they can extract a set of latent propositional symbols and latent action symbols
  entirely without human supervision.
  Each action symbol maps to a description of the propositional transition rule
  in STRIPS classical planning <cit.> formalism
  that can be directly fed to the optimized implementations of the off-the-shelf classical planning solvers.
  
  To answer the high-level question of whether a zero-shot sentence generation is a planning-like symbolic processing,
  we focus on the most basic form of language models, i.e., word embedding.
  Building on the work on word embedding and STRIPS action model learning,
  we propose a discrete, propositional word embedding directly compatible with
  symbolic, classical planning solvers. 
  We demonstrate its zero-shot unsupervised phrase generation using classical planners,
  where the task is to compose a phrase that has the similar meaning as the target word.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § PRELIMINARY AND BACKGROUND
  
  
  
  
  We denote a multi-dimensional array in bold and
  its subarrays with a subscript (e.g., ∈^N× M, _2 ∈^M),
  an integer range n<i<m by n..m,
  and the i-th data point of a dataset by a superscript ^i which we may omit for clarity.
  Functions (e.g., log,exp) are applied to the arrays element-wise.
  
  We assume background knowledge of discrete VAEs with continuous relaxations (See appendix sec:vae),
  such as Gumbel-Softmax (GS) and Binary-Concrete (BC) <cit.>.
  Their activations are denoted as  and , respectively.
  
  
  
  
    
  Word2Vec Continuous Bag of Word (CBOW) with Negative Sampling.
  
  
  The CBOW with Negative Sampling <cit.> language model
  is a shallow neural network that 
  predicts a specific center word of a 2c+1-gram from the rest of the words (context words).
  The model consists of two embedding matrices W, W' ∈^V× E
  where V is the size of the vocabulary and E is the size of the embedding.
  For a 2c+1-gram x^i-c, …, x^i+c (x^i∈ 1..V)
  in a dataset X=x^i,
  it computes the continuous-bag-of-words representation ^i=∑_-c≤ j ≤ c, j≠0 W_x^i+j.
  While it is possible to map this vector to the probabilities over V vocabulary words with a linear layer,
  it is computationally expensive due to the large constant V.
  To avoid this problem, Negative Sampling maps the target word x^i to an embedding W'_x^i,
  sample K words r^k (k∈ 1..K) over V, extracts their embeddings W'_r^k,
  then maximizes the loss:
  logσ (^i · W'_x^i) + ∑_k=1^Klogσ (-^i · W'_r^k).
  
  
  
    
  Classical Planning.
  
  
  Classical Planning is a formalism for deterministic, fully-observable high-level sequential decision making problems.
  High-level decision making deals with a logical chunk of actions (e.g. opening a door)
  rather than low-level motor actuations, thus is considered fundamental to intelligence and has been
  actively studied since the early history of AI.
  Its input is encoded in a modeling language called Planning Domain Description Language (PDDL),
  which contains extensions from its most basic variant STRIPS.
  
  A grounded (propositional) unit-cost STRIPS Planning problem <cit.>
  is defined as a 4-tuple P,A,I,G
  where
   P is a finite set of propositions,
   A is a finite set of actions,
   I⊆ P is an initial state, and
   G⊆ P is a goal condition.
  Here, a state is represented by a set of propositions s⊆ P,
  where each p∈ s corresponds to the proposition whose truth value is ⊤,
  thus can be interpreted conjunctively, i.e, a set p_1,p_2 represents p_1 p_2.
  Each state s⊆ P can also be encoded as a bit vector ∈0,1^|P| where,
  for each j-th proposition p_j∈ P, _j=1 when p_j∈ s, and _j=0 when p_j∉s.
  The entire set of states expressible in P is a power set 2^P.
  
  While the propositional representation provides a syntax for denoting the environment,
  actions provides the rules for the time evolution, which plays a role similar to those of semantic and grammatical rules.
  Each action a∈ A is a 3-tuple a,a,a where
  a, a, a⊆ P are preconditions, add-effects, and delete-effects, respectively.
  Without loss of generality a∩a = ∅.
  An action a is applicable when s satisfies a, i.e., a⊆ s.
  Applying an action a to s yields a new successor state
  s' = a(s) = (s ∖a) ∪a.
  A solution to a classical planning problem is called a plan,
  which is a sequence of actions π=a_1, a_2, … a_|π|
  that leads to a terminal state s^*=a_|π|∘…∘ a_1(s)
  that satisfies the goal condition, i.e., G⊆ s^*.
  Optimal plans are those whose lengths are the smallest among possible plans.
  
  
  
  
  
    
  STRIPS action modeling with neural networks.
  
  
  Cube-Space AutoEncoder <cit.> proposed a method for learning
  a binary latent representation s of visual time-series data while guaranteeing that
  every state transition in the latent representation can be expressed in STRIPS action rule
  s_t+1 = a(s_t) = (s_t ∖a) ∪a for some action a.
  Therefore,
  it is able to encode raw inputs (time-series data)
  into a state and an action representation compatible with STRIPS planners.
  
  Cube-Space AE does so by using a unique architecture called
  Back-to-Logit (BTL) that regularizes the state transitions.
  Since directly regularizing the discrete dynamics proved to be difficult,
  BTL performs all latent dynamics operations in the continuous space and discretizes the results as follows:
  It converts a given discrete state vector into a continuous vector using Batch Normalization (BN) <cit.>,
  takes the continuous sum with an effect embedding of an action,
  and discretizes the sum (logit) using Binary Concrete.
  Formally, given an action label , its embedding effect()
  and a binary vector ,
  the next state  is predicted by:
  
      ≈(a,)=(()+).
   
  
  The state representation  trained with BTL has the following properties:
  [<cit.>]
  Under the same action a, state transitions are bitwise monotonic, deterministic, and restricted to three mutually exclusive modes.
  For each bit j:
  
      (add:)    ∀ i; (_j,_j)∈(0,1), (1,1) i.e. _j ≤_j
      
       (del:)    ∀ i; (_j,_j)∈(1,0), (0,0) i.e. _j ≥_j
      
       (nop:)    ∀ i; (_j,_j)∈(0,0), (1,1) i.e. _j =_j.
  
  
  It guarantees that
  each action deterministically turns a certain bit on and off in the binary latent space,
  thus the resulting action theory and the bit-vector representation satisfies
  the STRIPS state transition rule s' = (s ∖a) ∪a
  and a constraint a∩a=∅.
  (Proof is straightforward from the monotonicity of  and  – See Appendix btl.)
  
  
  
  
  
  
  
  § ZERO-SHOT SEQUENCE GENERATION AS PLANNING
  
  
  To establish the connection between planning and zero-shot sequence generation,
  we first show the equivalence of classical planning and the basic right-regular formal grammar
  by mutual compilation.
  A formal grammar is a 4-tuple N,Σ,R,S which consists of non-terminal and terminal symbols N,Σ,
  production rules R, and a start symbol S∈ N.
  A zero-shot sequence generation can be seen as a problem of
  producing a string of terminal symbols by 
  iteratively applying one production rule r∈ R at a time to expand the current sequence,
  starting from the start symbol S.
  Right-regular grammar is a class of grammar
  whose rules are limited to 
  X→α Y, X→α, and X→ϵ
  where X,Y∈ N, α∈Σ and ϵ is an empty string.
  With actions as production rules and plans as sentences,
  a classical planning problem forms a right-regular grammar.
  Moreover, any right-regular grammar can be modeled as a classical planning problem.
  
  
  A classical planning problem P,A,I,G maps to the following grammar:
  (1) Σ consist of actions, i.e., Σ = A.
  (2) N contains the entire states, i.e., N = 2^P.
  (3) S is equivalent to the initial state I.
  (4) For each action a=a,a,a∈ A and each state s where a is applicable (a⊆ s),
  we add a production rule s→ sas' where s' is a successor state s' = (s∖a)∪a.
  Note that s,s' are both non-terminal.
  (6) Finally, for every goal state s^* that satisfies the goal condition G (G⊆ s^*),
  we add a production rule s^*→ϵ.
  
  
  A right-regular grammar maps to a classical planning problem P,A,I,G as follows:
  (1)P consists of non-terminal symbols N and a special proposition g, i.e. P=N∪g.
  (2)I is a set S where S is a start symbol.
  (3)For a rule X→α Y where X,Y∈ N, α∈Σ,
  we add an action X,Y,X.
  (4)For a rule X→α and X→ϵ,
  we add an action X,g,X.
  (5)The goal condition G consists of a single proposition g, i.e. G=g.
  
  
  Under this framework, the task of zero-shot sentence generation under a right regular grammar can be formalized as a classical planning problem.
  Notice that preconditions of each action plays a role similar to semantic and grammatical rules.
  While the simplicity of regular grammar may give a wrong impression that planning is easy,
  it is in fact PSPACE-hard and the search space explodes easily due to the exponential number of non-terminals (N = 2^P).
  A similar result between
  a more expressive planning formalism (Hierarchical Task Network planning <cit.>) and
  a more expressive Context Free Grammar
  is reported by <cit.>.
  In general, this connection between planning formalisms and formal grammars is often overlooked.
  
  
  
  
  § DISCRETE SEQUENTIAL APPLICATION OF WORDS (DSAW)
  
  
  
  Common downstream tasks and embedding evaluation tasks in modern natural language processing with
  word embedding involve arithmetic vector operations that aggregate the embedding vectors.
  Analogy task <cit.> is one
  such embedding evaluation task that requires a sequence of arithmetic manipulations over the embeddings.
  Given two pairs of words “a is to a^* as b is to b^*”,
  the famous example being “man is to king as woman is to queen”,
  the model predicts b^* by manipulating the embedded vectors of the first three words.
  The standard method for obtaining such a prediction is 3cosadd <cit.>,
  which attempts to find the closest word embedding to a vector ^*-+
  measured by the cosine distance cos(_1,_2)=1-_1·_2/|_1||_2|,
  assuming that the result is close to the target embedding ^*.
  This, along with other analogy calculation methods
  <cit.>,
  uses simple vector arithmetic
  to obtain the result embedding used to predict the target word. In addition, text classification evaluation methods
  sometimes build classifiers based on the mean or the sum of the word vectors in a sentence or a document <cit.>.
  
  On the other hand, symbolic natural language methods rely on logical structures 
  to extract and process information.
  For example,
  Abstract Meaning Representation (AMR) <cit.> encodes a
  natural language sentence into a tree-structured representation with which a logical query can be performed.
  However, while there are systems that try to extract AMR from
  natural language corpora <cit.>,
  these approaches rely on annotated data and hand-crafted symbols
  such as  or .
  In addition to the annotation cost, these symbols are opaque and lack the 
  internal structure which allows semantic information to be queried and logically analyzed.
  For example, a node  does not by itself carry information that it is
  inhabited by the local people and is a larger version of a .
  In contrast, a Word2Vec embedding may encode such information in its own continuous vector.
  
  Provided that the zero-shot sentence generation under regular grammar can be seen as a
  classical planning problem, we aim to generate a classical planning model from a natural language corpus.
  This approach addresses the weaknesses above of existing symbolic NLP approaches — dependency to human symbols and opaqueness —
  by generating a set of propositional symbols by itself.
  Our embedding scheme thus stands upon propositional logic (like AMR) while
  supporting vector arithmetic (like continuous embedding).
  To achieve this goal, we combine the existing discrete variational method with
  CBOW Word2Vec and obtain atomic propositional representations of words.
  
  
  
  
  To introduce the model, we modify the CBOW Word2Vec (fig:cbow, left) in two steps.
  We first identify that CBOW can be seen as a simple constant recurrent model (fig:cbow, middle).
  This trivial “recurrent” model merely adds the input embedding to the current state.
  Unlike the more complex, practical RNNs, such as LSTM <cit.> or GRU <cit.>,
  this model lacks any form of weights or nonlinearity
  that transforms the current state to the next state.
  
  This interpretation of CBOW yields several insights:
  First, there is a concept of “initial states” s^0, like any other recurrent model, that are 
  inherited by the surrounding context outside the ngram and manipulated by the effects W_x^i
  into the output state ^i+c=^0+∑_-c≤ j ≤ c, j≠0 W_x^i+j.
  Coincidentally, this output state is merely the sum of the effect vectors if s^0 is a zero vector,
  resulting in the equivalent formulation as the original CBOW.
  This also helps us understand the optimization objective behind CBOW:
  The effect of the target resembles the accumulated effect of the context.
  
  Second, upon discretizing some of the elements in this model in the next step,
  we should preserve the fundamental ability of CBOW to add(+), remove(-) or keep(0) the value
  of each dimension of the state vector.
  It is important to realize that a simple binary or categorical word embedding, such as the work done by
  <cit.> (for a significantly different purpose),
  is incompatible with the concept of adding, removing or keeping.
  Notice that unlike continuous values,
  categorical values lack the inherent ordering (total or partial).
  Therefore, categorical values 
  are not able to define 
  adding and removing as the inverse operations, as well as keeping as an identity.
  Also notice that this adding and removing directly corresponds to the add/delete effects in
  classical planning formalism.
  An arbitrary binary representation that is not regularized to have these elements
  cannot be compactly represented in the STRIPS semantics, precluding efficient planning.
  
  Based on the observations above, we propose Discrete Sequential
  Application of Words (DSAW, fig:cbow, right), which addresses the
  issues in continuous embeddings, naive discrete models, or
  hand-crafted symbolic models (AMR) by using two binary vectors to
  represent each word.
  
  DSAW sequentially applies the BTL technique to an initial state vector ^0.
  It applies a Bernoulli(0.5) prior to every state,
  therefore ^0 is sampled from Bernoulli(0.5) and
  each recurrent latent state ^i+j (-c≤ j ≤ c) is sampled from Binary Concrete, a continuous relaxation.
  The embedding matrix W itself is not discrete.
  However, due to Theorem 1,
  we can extract two binary vectors
  x, x of a word x that satisfy
  ^i+1=(^i  x) x,
  which is a bit-vector implementation of set-based STRIPS action application
  s^i+1=(s^i ∖a) ∩a.
  
  
  Since state vectors are activated by Binary Concrete,
  which behaves like a Sigmoid function in high temperature and as a step function in low temperature,
  all state vectors reside in the unit hypercube [0,1]^E.
  This means that we cannot directly apply the traditional objective function
  logσ (·) in Word2Vec to the output state vector
  because it assumes that the distribution of ,∈^E is centered around the origin,
  while our discrete output states are heavily biased toward the positive orthant.
  To address this issue,
  we shift the mean by subtracting 0.5 from the output vector before computing the loss.
  Formally, our maximization objective (including negative sampling with {r^1,… r^K})
  is defined as shown below,
  where
  ^i=(x^i, ^0),
  ^i-c=(x^i-c, ^0),
  ^i+1=(x^i+1, ^i-1),
  ^i+j=(x^i+j, ^i+j-1) (j∉-c,0,1).
  (Note that the formula below omits the variational loss. See Appendix training-details for the full form.)
  
      logσ ((^i+c-0.5) · (^i-0.5)) + ∑_k=1^Klogσ (-(^i+c-0.5) · ((r^k, ^0)-0.5)).
  
  
  Once the training has been completed,
  we compute one forward recurrent step for each word x
  with two initial state vectors 0, each consisting of all 0s and all 1s.
  We can then determine the effect in each dimension j:
  x_j=1 if (x,0)_j = 1, and
  x_j=1 if (x,1)_j = 0.
  
  
  
   §.§ Inference in the discrete space
  
  
  
  An important question about our model is how to perform arithmetic operations with the discrete representation.
  Specifically, to perform the word analogy task <cit.>,
  the representation must support both addition and subtraction of words,
  which is non-trivial for discrete vectors.
  We propose to use the STRIPS progression (applying an action) and regression (reversing an action)
   <cit.>
  as the vector addition and subtraction operation for our binary word embedding.
  Recall that, in the continuous effect model, vector subtraction is equivalent to
  undoing the effect of the action (= vector addition).
  Similarly,
  for a state s^i+1 generated by applying an action a to s^i
  (s^i+1=(s^i ∖a) ∩a),
  a STRIPS regression
  [
  We assume that the effect always invoke changes to the state
  in order to obtain a deterministic outcome from regression.
  In the standard setting, regression is nondeterministic
  unless warranted by the preconditions, e.g., if p_1 ∈a p_1∈a,
  then p_1 is guaranteed to be true before applying the action a.
  ]
  restores the previous state by
  s^i=(s^i+1∖a) ∩a.
  For a word x, we denote the corresponding bitwise operations as s  x and s  x.
  We note that our operation is not associative or commutative.
  That is, the result of “king-man+woman” may be different from “king+woman-man” etc.
  
  Next, for a sequence of operations s R_1 x_1 … R_n x_n(R_i∈,),
  we denote its combined effects as e=R_1 x_1 … R_n x_n.
  Its add/delete-effects, e,e, are recursively defined as follows:
  
      e x   =e∖x∪x,    e x   =e∖x∪x,
      e x   =e∖x∪x,    e x   =e∖x∪x.
  
  
  In the following artificial examples,
  we illustrate that (1) our set-based arithmetic is able to
  replicate the behavior of the classic word analogy “man is to king as woman is to queen”,
  and (2) our set-based operation is robust against semantic redundancy.
  
  
   Assume a 2-dimensional word embedding,
   where each dimension is assigned a meaning [female, status].
   Assume each word has the effects as shown in tab:example.
   Then the effect of “king-man+woman” applied to a state s is equivalent to those of “queen”:
   
   
      s kingmanwoman   =  s ∖female∪status∖∅∪female∖∅∪female
        =  s queen.
  
  
  
   The effect of “king+man” is equivalent to “king” itself as the semantic redundancy
   about “female” disappears in the set operation.
   
   
      s kingman   =  s ∖female∪status∖female∪∅
         =  s king.
  
  
  
  
  
  
  § EVALUATION
  
  
  We trained a traditional CBOW (our implementation) and our DSAW on 
  1 Billion Word Language Model Benchmark dataset <cit.>.
  Training details are available in the appendix training-details.
  We first compared the quality of embeddings on several downstream tasks.
  
  
  
   §.§ Embedding Evaluation Tasks
  
  
  Word similarity task is the standard benchmark for measuring 
  attributional similarity <cit.>.
  Given a set of word pairs,
  each embedding is evaluated by
  computing the Spearman correlation between
  the similarity scores assigned by the embedding
  and those assigned by human <cit.>. 
  The scores for CBOW are obtained by the cosine similarity.
  For the DSAW embedding,
  the standard cosine distance is not directly applicable as each embedding consists of two binary vectors.
  We, therefore, turned the effect of a word x into
  an integer vector of tertiary values {1,0,-1} by x-x, then computed the cosine similarity.
  We tested our models with the baseline models on 5 different datasets
  <cit.>. 
  
  
  
  
  
  Next, we evaluated Word Analogy task
  using the test dataset provided by <cit.>.
  For CBOW models, we used 3cosadd method (sec:motivation) to approximate the target word.
  For the proposed models, we perform a similar analogy,
  seqAdd,
  which computes the combined effects e,
  turns it into the tertiary representation,
  then finds the most similar word using the cosine distance.
  Since our set-based arithmetic is not associative or commutative,
  we permuted the order of operations and report the best results obtained from e=^*.
  We counted the number of correct predictions in the top-1 and top-10 nearest neighbors.
  We excluded the original words (a, a^* and b) from the candidates,
  following the later analysis of the Word2Vec implementations <cit.>.
  
  
  Finally,
  we used our embeddings for 
   semantic text classification,
  in which the model must capture the semantic information to perform well.
  We evaluated our model in two datasets: “20 Newsgroup” <cit.>
  and “movie sentiment treebank” <cit.>.
  We created binary classification tasks 
  following the existing work <cit.>:
  For 20 Newsgroup, we picked 4 sets of 2 groups to produce 4 sets of classification problems:
  SCI (science.med vs. science.space),
  COMP (ibm.pc.hardware vs. mac.hardware),
  SPORT (baseball vs. hockey),
  RELI (alt.atheism vs. soc.religion.christian).
  For movie sentiment (MS),
  we ignored the neutral comments and set a threshold for the sentiment values:
  ≤ 0.4 as 0, and > 0.6 as 1.
  In both the CBOW and the DSAW model, we aggregated the word embeddings (by + or ) in a
  sentence or a document to obtain the sentence / document-level embedding.
  We then classified the results with a default L2-regularized logistic regression model in Scikit-learn.
  We recorded the accuracy in the test split and compared it across the models.
  We normalized the imbalance in the number of questions between subtasks
  (SCI,…,RELI have ≈ 2000 questions each
  while MS has ≈ 9000) and reported the averaged results.
  
  
  
    
  Results
  tab:similarity shows that the performance of our discrete embedding is comparable
  to the continuous CBOW embedding in these three tasks.
  This is a surprising result given that discrete embeddings are believed to carry less information
  in each dimension compared to the continuous counterpart and
  are believed to fail because they cannot model uncertainty.
  The training/dataset detail and the more in-depth analyses can be found in the appendix sec:ml-experiments-detail.
  
  
  
  
   §.§ Zero-Shot Paraphrasing with Classical Planning
  
  
  Next, with a logically plausible representation of words,
  we show how it can be used by a symbolic AI system.
  We find “paraphrasing” an ideal task, where we provide an input word y
  and ask the system to zero-shot discover the phrase that shares the same concept.
  Given a word y, we generate a classical planning problem 
  whose task is to sequence several words in the correct order to achieve the same effects that y has.
  
  
  Formally, the instance P,A,I,G(y) is defined as follows:
  P=P_add∪ P_del=p^a_i| i∈ 1..E∪p^d_i| i∈ 1..E,
  where p^a_i, p^d_i are propositional symbols with unique names.
  Actions a(x)∈ A are built from each word x in the vocabulary while excluding the target word y:
  a(x) = ∅,
  a(x)=p^a_i|x_i = 1∪p^d_i|x_i = 1,
  a(x)=p^d_i|x_i = 1∪p^a_i|x_i = 1.
  Finally, I=∅ and G(y)=p^a_i |y_i = 1∪p^d_i |y_i = 1.
  Note that y, x etc. are bit-vectors, while a(x) etc. are sets expressed in PDDL.
  Finding the optimal solution of this problem is NP-Complete
  due to a(x) = ∅ <cit.>.
  Due to its worst-case hardness, we do not try to find the optimal solutions.
  We solved the problems with
  LAMA planner <cit.> in Fast Downward planning system <cit.>,
  the winner of International Planning Competition 2011 satisficing track <cit.>.
  
  Notice that the goal condition of this planning problem is overly specific
  because it requires to perfectly match the target effect,
  while the neighbors of an embedding vector often also carry a similar meaning.
  In fact, LAMA classical planner were able to prove that
  there are no precise paraphrasing to all queries we provided.
  This ability to answer the inexistence of solutions is offered by
  the deterministic completeness of the algorithms (Greedy Best First Search and Weighted )
  in these planners, which guarantees that the algorithm returns a solution in finite time
  whenever there is a solution, and returns “unsolvable” when there are no solutions.
  Such finite deterministic completeness is typically missing
  in probabilistic search algorithm such as Monte-Carlo Tree Search <cit.>,
  or greedy approach such as Beam Search commonly used in NLP literature.
  Also, the recent language model such as GPT-3 <cit.> are known to
  generate a bogus answer to a bogus question with high confidence <cit.>.
   
  
  We can still address this issue in a non-probability-driven manner
  by net-benefit planning formalism <cit.>,
  an extension of classical planning that allows the use of soft-goals.
  Net-benefit planning task P,A,I,G(y),c,u is same as the unit-cost classical planning
  except the cost function c: A→^+0 and u: G(y)→^+0.
  The task is to find an action sequence π minimizing the cost
  ∑_a ∈π c(a) + ∑_p∈ G(y)∖ s^* u(p), i.e.,
  the planner tries to find a cheaper path
  while also satisfying as many goals as possible at the terminal state s^*.
  We used a simple compilation approach <cit.>
  to convert this net-benefit planning problem into a normal classical planning problem.
  The compilation details can be found in the Appendix sec:planning-compilation.
   
  We specified both costs a constant: c(a)=E for all actions 
  and u(p)=U for all goals,     
  where we heuristically chose U=100.
  The LAMA planner searches for suboptimal plans,
  iteratively refining the solution by setting the upper-bound based on the cost of the last solution.
  We generated 68 problems from the hand-picked target words y.
  A was generated from the 4000 most-frequent words
  in the vocabulary (V≈ 219k) excluding y, function words
  (e.g., “the”, “make”), and compound words (e.g., plurals).
  For each problem, we allowed the maximum of 4 hours runtime and 16GB memory.
  Typically the planner found the first solution early, and
  continued running until the time limit finding multiple better solutions.
  We show its example outputs in tab:planning-example.
  See Appendix sec:more-paraphrase for the more variety of paraphrasing results using the 300 words
  randomly selected from the vocabulary.
  
  
  
  
  
  
  § RELATED WORK
  
  
  The study on the hybrid systems combining the connectionist and symbolic approaches has a long history
  <cit.>.
  <cit.>
  proposed a discrete sentence representation,
  treating each sentence as an action.
  <cit.> 
  improved the training efficiency
  with an intermediate discrete code between
  the vocabulary V and the continuous embedding.
  These representations lack the STRIPS compatibility since the discrete dynamics is not regularized.
  In the intersection of planning and natural language processing,
  <cit.> introduced a system
  which models conversations as probabilistic planning and learns a reactive policy from interactions.
  Recent approaches extract a classical planning model from a
  natural language corpus <cit.>, but using the opaque human symbols.
  
  
  
  § CONCLUSION
  
  
  We proposed an unsupervised learning method for discrete binary word embeddings
  that preserve the vector arithmetic similar to the continuous embeddings.
  Our approach combines three distant areas:
  Unsupervised representation learning method for natural language,
  discrete generative modeling, and STRIPS classical planning formalism
  which is deeply rooted in the symbolic AIs and the propositional logic.
  Inspired by the recurrent view of the Continuous Bag of Words model,
  our model represents each word as a symbolic action
  that modifies the binary (i.e., propositional) recurrent states through effects.
  
  We answered an important connection between zero-shot sequence generation, formal language grammar and planning as heuristic search.
  This is done by first establishing the theoretical connection between right-regular grammar and classical planning,
  then by proposing a system that learns a propositional embedding compatible with planning,
  then demonstrating that the planner can meaningfully compose words within the regular grammar.
  Future directions include learning hierarchical plannable actions and goals 
  by taking advantage of Hierarchical Task Network planning formalism <cit.>
  which corresponds to Context Free Grammar,
  and probabilistic CFG grammar induction methods <cit.>. 
  Additionally, our goal-oriented sentence generation approach
  can be further expanded to the task of machine translation (same goal, different set of actions), 
  or code generation where the grammar is stricter than in natural language.
  
  
  
  
  9.5pt10.5pt
  72
  
  
  urlstyle
  
  [Agirre et al.(2009)Agirre, Alfonseca, Hall, Kravalova, Pasca, and
    Soroa]agirre2009study
  Eneko Agirre, Enrique Alfonseca, Keith Hall, Jana Kravalova, Marius Pasca, and
    Aitor Soroa.
  A Study on Similarity and Relatedness Using Distributional and
    WordNet-based Approaches.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  19, 2009.
  
  [Alcázar et al.(2013)Alcázar, Borrajo, Fernández, and
    Fuentetaja]alcazar2013revisiting
  Vidal Alcázar, Daniel Borrajo, Susana Fernández, and Raquel Fuentetaja.
  Revisiting Regression in Planning.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), 2013.
  
  [Amado et al.(2018a)Amado, Pereira, Aires, Magnaguagno,
    Granada, and Meneguzzi]amado2018goal
  Leonardo Amado, Ramon Fraga Pereira, Joao Aires, Mauricio Magnaguagno, Roger
    Granada, and Felipe Meneguzzi.
  Goal Recognition in Latent Space.
  In Proc. of International Joint Conference on Neural Networks
    (IJCNN), 2018a.
  
  [Amado et al.(2018b)Amado, Pereira, Aires, Magnaguagno,
    Granada, and Meneguzzi]amado2018lstm
  Leonardo Amado, Ramon Fraga Pereira, Joao Aires, Mauricio Magnaguagno, Roger
    Granada, and Felipe Meneguzzi.
  LSTM-based Goal Recognition in Latent Space.
  arXiv preprint arXiv:1808.05249, 2018b.
  
  [Asai & Fukunaga(2018)Asai and Fukunaga]Asai2018
  Masataro Asai and Alex Fukunaga.
  Classical Planning in Deep Latent Space: Bridging the
    Subsymbolic-Symbolic Boundary.
  In Proc. of AAAI Conference on Artificial Intelligence,
    2018.
  
  [Asai & Muise(2020)Asai and Muise]Asai2020
  Masataro Asai and Christian Muise.
  Learning Neural-Symbolic Descriptive Planning Models via Cube-Space
    Priors: The Voyage Home (to STRIPS).
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), 2020.
  
  [Banarescu et al.(2013)Banarescu, Bonial, Cai, Georgescu, Griffitt,
    Hermjakob, Knight, Koehn, Palmer, and Schneider]banarescu2013abstract
  Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf
    Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider.
  Abstract Meaning Representation for Sembanking.
  In Proc. of the 7th Linguistic Annotation Workshop and
    Interoperability with Discourse, pp.  178–186, 2013.
  
  [Bolukbasi et al.(2016)Bolukbasi, Chang, Zou, Saligrama, and
    Kalai]bolukbasi2016man
  Tolga Bolukbasi, Kai-Wei Chang, James Y. Zou, Venkatesh Saligrama, and
    Adam Tauman Kalai.
  Man is to Computer Programmer as Woman is to Homemaker? Debiasing
    Word Embeddings.
  In Advances in Neural Information Processing Systems, pp.  4349–4357, 2016.
  
  [Brown et al.(2020)Brown, Mann, Ryder, Subbiah, Kaplan, Dhariwal,
    Neelakantan, Shyam, Sastry, Askell, Agarwal, Herbert-Voss, Krueger,
    Henighan, Child, Ramesh, Ziegler, Wu, Winter, Hesse, Chen, Sigler, Litwin,
    Gray, Chess, Clark, Berner, McCandlish, Radford, Sutskever, and Amodei]gpt3
  Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan,
    Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda
    Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom
    Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens
    Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott
    Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec
    Radford, Ilya Sutskever, and Dario Amodei.
  Language Models are Few-Shot Learners.
  CoRR, abs/2005.14165, 2020.
  URL <https://arxiv.org/abs/2005.14165>.
  
  [Bruni et al.(2014)Bruni, Tran, and Baroni]bruni2014multimodal
  Elia Bruni, Nam-Khanh Tran, and Marco Baroni.
  Multimodal Distributional Semantics.
  J. Artif. Intell. Res.(JAIR), 49:0 1–47, 2014.
  
  [Bylander(1994)]bylander1994
  Tom Bylander.
  The Computational Complexity of Propositional STRIPS Planning.
  Artificial Intelligence, 690 (1):0 165–204,
    1994.
  
  [Caliskan et al.(2017)Caliskan, Bryson, and
    Narayanan]caliskan2017semantics
  Aylin Caliskan, Joanna J Bryson, and Arvind Narayanan.
  Semantics derived automatically from language corpora contain
    human-like biases.
  Science, 3560 (6334):0 183–186, 2017.
  
  [Chelba et al.(2014)Chelba, Mikolov, Schuster, Ge, Brants, Koehn, and
    Robinson]chelba2014one
  Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp
    Koehn, and Tony Robinson.
  One Billion Word Benchmark for Measuring Progress in Statistical
    Language Modeling.
  In Proc. of Annual Conference of the International Speech
    Communication Association, 2014.
  
  [Chen et al.(2018)Chen, Min, and Sun]chen2018kway
  Ting Chen, Martin Renqiang Min, and Yizhou Sun.
  Learning K-way D-dimensional Discrete Codes for Compact Embedding
    Representations.
  In Proc. of the International Conference on Machine
    Learning, volume 80 of Proceedings of Machine Learning Research,
    pp.  853–862, 2018.
  
  [Cho et al.(2014)Cho, van Merrienboer, Gülçehre, Bahdanau,
    Bougares, Schwenk, and Bengio]cho2014gru
  Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry
    Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.
  Learning Phrase Representations using RNN Encoder-Decoder for
    Statistical Machine Translation.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  1724–1734, 2014.
  
  [Cullen & Bryman(1988)Cullen and Bryman]cullen88
  J Cullen and A Bryman.
  The Knowledge Acquisition Bottleneck: Time for Reassessment?
  Expert Systems, 50 (3), 1988.
  
  [Drozd et al.(2016)Drozd, Gladkova, and Matsuoka]Drozd2016Word
  Aleksandr Drozd, Anna Gladkova, and Satoshi Matsuoka.
  Word Embeddings, Analogies, and Machine Learning: Beyond
    King-Man+Woman=Queen.
  In Proc. of the International Conference on Computational
    Linguistics, pp.  3519–3530, 2016.
  
  [Faruqui & Dyer(2014)Faruqui and Dyer]faruqui2014community
  Manaal Faruqui and Chris Dyer.
  Community Evaluation and Exchange of Word Vectors at
    Wordvectors.org.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  19–24, 2014.
  
  [Feng et al.(2018)Feng, Zhuo, and Kambhampati]feng2018extracting
  Wenfeng Feng, Hankz Hankui Zhuo, and Subbarao Kambhampati.
  Extracting Action Sequences from Texts Based on Deep Reinforcement
    Learning.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), 2018.
  
  [Fikes et al.(1972)Fikes, Hart, and Nilsson]FikesHN72
  Richard E Fikes, Peter E. Hart, and Nils J. Nilsson.
  Learning and Executing Generalized Robot Plans.
  Artificial Intelligence, 30 (1-3):0
    251–288, 1972.
  
  [Finkelstein et al.(2001)Finkelstein, Gabrilovich, Matias, Rivlin,
    Solan, Wolfman, and Ruppin]finkelstein2001placing
  Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias, Ehud Rivlin, Zach Solan,
    Gadi Wolfman, and Eytan Ruppin.
  Placing Search in Context: The Concept Revisited.
  In Proc. of the International Conference on World Wide Web,
    pp.  406–414, 2001.
  
  [Flanigan et al.(2014)Flanigan, Thomson, Carbonell, Dyer, and
    Smith]flanigan2014discriminative
  Jeffrey Flanigan, Sam Thomson, Jaime G. Carbonell, Chris Dyer, and Noah A.
    Smith.
  A Discriminative Graph-Based Parser for the Abstract Meaning
    Representation.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  1426–1436, 2014.
  
  [Geib & Steedman(2007)Geib and Steedman]geib2007on
  Christopher W. Geib and Mark Steedman.
  On Natural Language Processing and Plan Recognition.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), pp.  1612–1617, 2007.
  
  [Ghallab et al.(2004)Ghallab, Nau, and Traverso]ghallab2004automated
  Malik Ghallab, Dana Nau, and Paolo Traverso.
  Automated Planning: Theory and Practice.
  Elsevier, 2004.
  
  [Haslum et al.(2019)Haslum, Lipovetzky, Magazzeni, and Muise]pddlbook
  Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, and Christian Muise.
  An Introduction to the Planning Domain Definition Language.
  Synthesis Lectures on Artificial Intelligence and Machine
    Learning, 130 (2):0 1–187, 2019.
  
  [Helmert(2006)]Helmert2006
  Malte Helmert.
  The Fast Downward Planning System.
  J. Artif. Intell. Res.(JAIR), 26:0 191–246, 2006.
  
  [Higgins et al.(2017)Higgins, Matthey, Pal, et al.]higgins2017beta
  Irina Higgins, Loïc Matthey, Arka Pal, et al.
  β-VAE: Learning Basic Visual Concepts with a Constrained
    Variational Framework.
  In Proc. of the International Conference on Learning
    Representations, 2017.
  
  [Hill et al.(2015)Hill, Reichart, and Korhonen]hill2015simlex
  Felix Hill, Roi Reichart, and Anna Korhonen.
  Simlex-999: Evaluating Semantic Models with (Genuine) Similarity
    Estimation.
  Computational Linguistics, 410 (4):0 665–695,
    2015.
  
  [Hochreiter & Schmidhuber(1997)Hochreiter and
    Schmidhuber]hochreiter1997long
  Sepp Hochreiter and Jürgen Schmidhuber.
  Long Short-Term Memory.
  Neural Computation, 90 (8):0 1735–1780, 1997.
  
  [Hoffmann & Nebel(2001)Hoffmann and Nebel]hoffmann01
  Jörg Hoffmann and Bernhard Nebel.
  The FF Planning System: Fast Plan Generation through Heuristic
    Search.
  J. Artif. Intell. Res.(JAIR), 14:0 253–302, 2001.
  
  [Ioffe & Szegedy(2015)Ioffe and Szegedy]ioffe2015batch
  Sergey Ioffe and Christian Szegedy.
  Batch Normalization: Accelerating Deep Network Training by Reducing
    Internal Covariate Shift.
  In Proc. of the International Conference on Machine
    Learning, pp.  448–456, 2015.
  
  [Jang et al.(2017)Jang, Gu, and Poole]jang2017categorical
  Eric Jang, Shixiang Gu, and Ben Poole.
  Categorical Reparameterization with Gumbel-Softmax.
  In Proc. of the International Conference on Learning
    Representations, 2017.
  
  [Jia & Liang(2017)Jia and Liang]jia2017adversarial
  Robin Jia and Percy Liang.
  Adversarial Examples for Evaluating Reading Comprehension Systems.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  2021–2031, 2017.
  
  [Keyder & Geffner(2009)Keyder and Geffner]emil2009soft
  Emil Keyder and Hector Geffner.
  Soft goals can be compiled away.
  J. Artif. Intell. Res.(JAIR), 36:0 547–556, 2009.
  10.1613/jair.2857.
  URL <https://doi.org/10.1613/jair.2857>.
  
  [Kim et al.(2019)Kim, Dyer, and Rush]kim2019compound
  Yoon Kim, Chris Dyer, and Alexander M Rush.
  Compound Probabilistic Context-Free Grammars for Grammar Induction.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  2369–2385, 2019.
  
  [Kingma & Welling(2013)Kingma and Welling]kingma2013auto
  Diederik P Kingma and Max Welling.
  Auto-Encoding Variational Bayes.
  In Proc. of the International Conference on Learning
    Representations, 2013.
  
  [Kocmi & Bojar(2017)Kocmi and Bojar]kocmi2017initialization
  Tom Kocmi and Ondrej Bojar.
  An Exploration of Word Embedding Initialization in Deep-Learning
    Tasks.
  In Proceedings of the 14th International Conference on Natural
    Language Processing, ICON, pp.  56–64, 2017.
  
  [Kocsis & Szepesvári(2006)Kocsis and
    Szepesvári]kocsis2006bandit
  Levente Kocsis and Csaba Szepesvári.
  Bandit Based Monte-Carlo Planning.
  pp.  282–293, 2006.
  
  [Kurutach et al.(2018)Kurutach, Tamar, Yang, Russell, and
    Abbeel]kurutach2018learning
  Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart Russell, and Pieter Abbeel.
  Learning Plannable Representations with Causal InfoGAN.
  In Advances in Neural Information Processing Systems, 2018.
  
  [Lacker(2020)]gpt3-turing-test
  Kevin Lacker.
  Giving GPT-3 a Turing Test, 2020.
  URL
    <https://lacker.io/ai/2020/07/06/giving-gpt-3-a-turing-test.html>.
  
  [Lang(1995)]lang1995newsweeder
  Ken Lang.
  Newsweeder: Learning to Filter Netnews.
  In Proc. of the International Conference on Machine
    Learning, pp.  331–339, 1995.
  
  [Levy & Goldberg(2014)Levy and Goldberg]levy2014linguistic
  Omer Levy and Yoav Goldberg.
  Linguistic Regularities in Sparse and Explicit Word
    Representations.
  In Proc. of Conference on Computational Natural Language
    Learning, pp.  171–180, 2014.
  
  [Lindsay et al.(2017)Lindsay, Read, Ferreira, Hayton, Porteous, and
    Gregory]lindsay2017framer
  Alan Lindsay, Jonathon Read, Joao F Ferreira, Thomas Hayton, Julie Porteous,
    and Peter J Gregory.
  Framer: Planning Models from Natural Language Action Descriptions.
  In Proc. of the International Conference on Automated Planning
    and Scheduling(ICAPS), 2017.
  
  [Liu et al.(2019)Liu, Jiang, He, et al.]liu2019variance
  Liyuan Liu, Haoming Jiang, Pengcheng He, et al.
  On the Variance of the Adaptive Learning Rate and Beyond.
  arXiv:1908.03265, 2019.
  
  [López et al.(2015)López, Celorrio, and
    Olaya]lopez2015deterministic
  Carlos Linares López, Sergio Jiménez Celorrio, and Ángel García
    Olaya.
  The Deterministic Part of the Seventh International Planning
    Competition.
  Artificial Intelligence, 223:0 82–119, 2015.
  
  [Luong et al.(2013)Luong, Socher, and Manning]Luong2013better
  Minh-Thang Luong, Richard Socher, and Christopher D. Manning.
  Better Word Representations with Recursive Neural Networks for
    Morphology.
  In Proc. of Conference on Computational Natural Language
    Learning, 2013.
  
  [Maddison et al.(2016)Maddison, Mnih, and Teh]maddison2016concrete
  Chris J Maddison, Andriy Mnih, and Yee Whye Teh.
  The concrete distribution: A continuous relaxation of discrete random
    variables.
  arXiv preprint arXiv:1611.00712, 2016.
  
  [Maddison et al.(2017)Maddison, Mnih, and Teh]maddison2017concrete
  Chris J. Maddison, Andriy Mnih, and Yee Whye Teh.
  The Concrete Distribution: A Continuous Relaxation of Discrete
    Random Variables.
  In Proc. of the International Conference on Learning
    Representations, 2017.
  
  [Mikolov et al.(2013a)Mikolov, Chen, Corrado, and
    Dean]mikolov2013cbow
  Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.
  Efficient Estimation of Word Representations in Vector Space.
  In Proc. of the International Conference on Learning
    Representations, 2013a.
  
  [Mikolov et al.(2013b)Mikolov, Sutskever, Chen, Corrado,
    and Dean]mikolov2013distributed
  Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.
  Distributed Representations of Words and Phrases and Their
    Compositionality.
  In Advances in Neural Information Processing Systems, pp.  3111–3119, 2013b.
  
  [Mikolov et al.(2013c)Mikolov, Yih, and
    Zweig]mikolov2013linguistic
  Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig.
  Linguistic Regularities in Continuous Space Word Representations.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  746–751,
    2013c.
  
  [Miller & Charles(1991)Miller and Charles]miller1991contextual
  George A. Miller and Walter G. Charles.
  Contextual Correlates of Semantic Similarity.
  Language and Cognitive Processes, 60 (1):0
    1–28, 1991.
  
  [Myers et al.(2010)Myers, Well, and Lorch]myers2010research
  J.L. Myers, A. Well, and R.F. Lorch.
  Research Design and Statistical Analysis.
  Routledge, 2010.
  ISBN 9780805864311.
  URL <https://books.google.com/books?id=nbsOIJ_saUAC>.
  
  [Neishi et al.(2017)Neishi, Sakuma, Tohda, Ishiwatari, Yoshinaga, and
    Toyoda]neishi2017bagoftrick
  Masato Neishi, Jin Sakuma, Satoshi Tohda, Shonosuke Ishiwatari, Naoki
    Yoshinaga, and Masashi Toyoda.
  A Bag of Useful Tricks for Practical Neural Machine Translation:
    Embedding Layer Initialization and Large Batch Size.
  In Proceedings of the 4th Workshop on Asian Translation,
    pp.  99–109, 2017.
  
  [Nissim et al.(2020)Nissim, van Noord, and van der
    Goot]nissim2019fair
  Malvina Nissim, Rik van Noord, and Rob van der Goot.
  Fair is Better than Sensational: Man is to Doctor as Woman is to
    Doctor.
  Computational Linguistics, Just Accepted, 2020.
  
  [Payan(1992)]payan1992chromatic
  Charles Payan.
  On the Chromatic Number of Cube-Like Graphs.
  Discrete mathematics, 1030 (3), 1992.
  
  [Pearson(1901)]pearson1901liii
  Karl Pearson.
  LIII. On Lines and Planes of Closest Fit to Systems of Points in
    Space.
  The London, Edinburgh, and Dublin Philosophical Magazine and
    Journal of Science, 20 (11):0 559–572, 1901.
  
  [Radinsky et al.(2011)Radinsky, Agichtein, Gabrilovich, and
    Markovitch]radinsky2011word
  Kira Radinsky, Eugene Agichtein, Evgeniy Gabrilovich, and Shaul Markovitch.
  A Word at a Time: Computing Word Relatedness using Temporal Semantic
    Analysis.
  In Proc. of the International Conference on World Wide Web,
    pp.  337–346, 2011.
  
  [Resnik(1995)]resnik1995using
  Philip Resnik.
  Using Information Content to Evaluate Semantic Similarity in a
    Taxonomy.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), pp.  448–453, 1995.
  
  [Richter & Westphal(2010)Richter and Westphal]richter2010lama
  Silvia Richter and Matthias Westphal.
  The LAMA Planner: Guiding Cost-Based Anytime Planning with
    Landmarks.
  J. Artif. Intell. Res.(JAIR), 390 (1):0
    127–177, 2010.
  
  [Rieser & Lemon(2009)Rieser and Lemon]rieser2009natural
  Verena Rieser and Oliver Lemon.
  Natural Language Generation as Planning Under Uncertainty for Spoken
    Dialogue Systems.
  In Proceedings of the 12th Conference of the European
    Chapter of the ACL (EACL 2009), pp.  683–691, 2009.
  
  [Rubenstein & Goodenough(1965)Rubenstein and
    Goodenough]rubenstein1965contextual
  Herbert Rubenstein and John B Goodenough.
  Contextual Correlates of Synonymy.
  Communications of the ACM, 80 (10):0 627–633,
    1965.
  
  [Schakel & Wilson(2015)Schakel and Wilson]schakel2015measuring
  Adriaan M. J. Schakel and Benjamin J. Wilson.
  Measuring Word Significance using Distributed Representations of
    Words.
  CoRR, abs/1508.02297, 2015.
  
  [Socher et al.(2013)Socher, Perelygin, Wu, Chuang, Manning, Ng, and
    Potts]socher2013recursive
  Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning,
    Andrew Y Ng, and Christopher Potts.
  Recursive Deep Models for Semantic Compositionality over a Sentiment
    Treebank.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  1631–1642, 2013.
  
  [Towell & Shavlik(1994)Towell and Shavlik]towell1994knowledge
  Geoffrey G Towell and Jude W Shavlik.
  Knowledge-Based Artificial Neural Networks.
  Artificial Intelligence, 700 (1-2):0
    119–165, 1994.
  
  [Tsvetkov et al.(2015)Tsvetkov, Faruqui, Ling, Lample, and
    Dyer]Tsvetkov2015Evaluation
  Yulia Tsvetkov, Manaal Faruqui, Wang Ling, Guillaume Lample, and Chris Dyer.
  Evaluation of Word Vector Representations by Subspace Alignment.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  2049–2054, 2015.
  
  [Wang et al.(2015)Wang, Xue, and Pradhan]wang2015transition
  Chuan Wang, Nianwen Xue, and Sameer Pradhan.
  A Transition-based Algorithm for AMR Parsing.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  366–375,
    2015.
  
  [Wermter & Lehnert(1989)Wermter and Lehnert]wermter1989hybrid
  Stefan Wermter and Wendy G Lehnert.
  A Hybrid Symbolic/Connectionist Model for Noun Phrase
    Understanding.
  Connection Science, 10 (3):0 255–272, 1989.
  
  [Wilson & Schakel(2015)Wilson and Schakel]wilson2015controlled
  Benjamin J. Wilson and Adriaan M. J. Schakel.
  Controlled Experiments for Word Embeddings.
  CoRR, abs/1510.02675, 2015.
  
  [Xing et al.(2015)Xing, Wang, Liu, and Lin]xing2015normalized
  Chao Xing, Dong Wang, Chao Liu, and Yiye Lin.
  Normalized Word Embedding and Orthogonal Transform for Bilingual
    Word Translation.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  1006–1011,
    2015.
  
  [Yogatama & Smith(2014)Yogatama and Smith]Yogatama2014Linguistic
  Dani Yogatama and Noah A Smith.
  Linguistic Structured Sparsity in Text Categorization.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  786–796, 2014.
  
  [Zhao et al.(2018)Zhao, Lee, and Eskénazi]zhao2018unsupervised
  Tiancheng Zhao, Kyusong Lee, and Maxine Eskénazi.
  Unsupervised Discrete Sentence Representation Learning for
    Interpretable Neural Dialog Generation.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  1098–1107, 2018.
  
  
  
  
  
  
  
  
  
  
  § EXTENDED BACKGROUNDS
  
  
  
   §.§ Variational AutoEncoder with Gumbel Softmax and Binary Concrete distribution
  
  
  
  Variational AutoEncoder (VAE) is a framework for reconstructing the observation x from a
  compact latent representation z that follows a certain prior distribution, which is often
  a Normal distribution (0,1) for a continuous z. Training is performed by maximizing the sum of the
  reconstruction loss and the KL divergence between the latent random distribution
  q(z|x) and the target distribution p(z)=(0,1),
  which gives a lower bound for the likelihood p(x) <cit.>.
  Gumbel-Softmax (GS) VAE <cit.> and its binary special case
  Binary Concrete (BC) VAE <cit.> instead use a discrete,
  uniform categorical distribution as the target distribution,
  and further approximate it with a continuous relaxation
  by annealing the controlling parameter (temperature τ) down to 0.
  The latent value z of Binary Concrete VAE is activated from an input logit x by
  z=(x)=Sigmoid((x+Logistic(0,1))/τ),
  where Logistic(0,1)=log u-log(1-u) and
  u∈ [0,1] is sampled from Uniform(0,1).
  BinConcrete converges to the Heaviside step function at the limit τ→ 0:
  BinConcrete(x)→step(x) (step function thresholded at 0).
  
  
  
   §.§ Learning Discrete Latent Dynamics using Back-To-Logit
  
  
  
  
  Cube-Space AutoEncoder <cit.> proposed a method for learning
  a binary latent representation s of visual time-series data while guaranteeing that
  every state transition / dynamics in the latent representation can be expressed in STRIPS action rule
  s_t+1 = a(s_t) = (s_t ∖a) ∪a for some action a.
  It does so by using a unique architecture called
  Back-to-Logit (BTL) that regularizes the state transitions.
  BTL places a so-called cube-like graph prior on the binary latent space / transitions.
  To understand the prior, the background of cube-like graph is necessary.
  
  
  
  cube-like graph <cit.> is a graph class originating from graph theory.
  <cit.> identified that state transition graphs of STRIPS planning problems is equivalent to directed cube-like graph.
  A cube-like graph G(S,D)=(V,E) is a simple[No duplicated edges between the same pair of nodes]
  undirected graph defined by the sets S and D.
  Each node v∈ V is a finite subset of S, i.e., v⊆ S.
  The set D is a family of subsets of S,
  and for every edge e = (v,w) ∈ E, the symmetric difference
   d = v⊕ w = (v∖ w) ∪ (w∖ v) must belong to D.
  For example, a unit cube is a cube-like graph because
  S=x,y,z,
  V=∅,x,…x,y,z,
  E=(∅,x),… (y,z,x,y,z),
  D=x,y,z.
  The set-based representation can be alternatively represented as a bit-vector, e.g.,
  V'=(0,0,0),(0,0,1),… (1,1,1).
  
  
  
  
  Consider coloring a graph which forms a unit cube (cube-like) and has binary node embeddings.
  A cube-like graph on the left can be efficiently (i.e., by fewer colors) colored by
  the difference between the neighboring embeddings.
  Edges can be categorized into 3 labels (6 labels if directed),
  where each label is assigned to 4 edges which share the node embedding differences,
  as depicted by the upward arrows with the common node difference (0,0,+1) in the figure.
  This node embedding differences correspond to the set D,
  and each element of D represents an action.
  In contrast, the graph on the right has the node embeddings that are randomly shuffled.
  Despite having the same topology and the same embedding size,
  this graph lacks the common patterns in the embedding differences like we saw on the left,
  thus cannot be efficiently colored by the node differences.
  
  
  In STRIPS modeling, <cit.> used a directed version of this graph class.
  For every edge e = (v,w) ∈ E,
  there is a pair of sets d=(d^+,d^-)=(w ∖ v, v ∖ w)∈ D which satisfies the asymmetric difference
  w=(v ∖ d^-) ∪ d^+.
  It is immediately obvious that this graph class corresponds to
  the relationship between binary states and action effects in STRIPS, s'=(s ∖a) ∪a.
  
  
  Cube-Space AE restricts the binary latent encoding and the transitions to directed cube-like graph,
  thereby guaranteeing the direct translation of latent space into STRIPS action model.
  However, since discrete representation learning is already known to be a challenge,
  adding a prior to it makes the training particularly difficult.
  Back-to-Logit (btl-only) was proposed in order to avoid directly operating on the discrete vectors.
  Instead, it converts a discrete current state  back to a continuous logit using Batch Normalization <cit.>,
  takes a sum with a continuous effect vector produced by an additional MLP ,
  and re-discretize the resulting logit using Binary Concrete.
  Formally,
  
      =(a,)=(()+).
  
  
  States learned by BTL has the following property:
  
  <cit.> (same as Theorem 1)
  Under the same action a, state transitions are bitwise monotonic, deterministic, and restricted to three mutually exclusive modes,
  i.e., for each bit j:
  
      (add:)    ∀ i; (_j,_j)∈(0,1), (1,1) i.e. _j ≤_j
      
       (del:)    ∀ i; (_j,_j)∈(1,0), (0,0) i.e. _j ≥_j
      
       (nop:)    ∀ i; (_j,_j)∈(0,0), (1,1) i.e. _j =_j
  
  
  
  This theorem guarantees that
  each action deterministically sets a certain bit on and off in the binary latent space.
  Therefore, the actions and the transitions satisfy
  the STRIPS state transition rule s' = (s ∖a) ∪a,
  thus enabling a direct translation from neural network weights to PDDL modeling language.
  
  The proof is straightforward from the monotonicity of the BatchNorm and Binary Concrete.
  Note that we assume BatchNorm's additional scale parameter γ is kept positive or disabled.
  
  
  For readability, we omit j and assumes a 1-dimensional case. Let e=[]∈.
  Note that e is a constant for the fixed input [].
  At the limit of annealing, Binary Concrete becomes a step function, which is also monotonic.
  is monotonic because we assumed the scale parameter γ of is positive,
  and the main feature of also only scales the variance of the batch, which is always positive.
  Then we have
  
      =step(()+e).
  
  
  The possible values a pair (,) can have is (0,0),(0,1),(1,0),(1,1).
  Since both step and are deterministic at the testing time (See <cit.>),
  we consider the deterministic mapping from  to .
  There are only 4 deterministic mappings:
   (0,1), (1,1),
   (1,0), (0,0),
   (0,0), (1,1), and lastly (0,1), (1,0).
  Thus our goal is now to show that the last mapping is impossible in latent space …(,)….
  
  To prove this, first, assume (,)=(0,1) for some index i. Then
  
      1=step((0)+e). ⇒(0)+e>0. ⇒(1)+e>0. ⇒∀ i; ()+e > 0.
  
  The second step is due to the monotonicity (0)<(1).
  This shows  is constantly 1 regardless of ,
  therefore it proves that (,)=(1,0) cannot happen in any i.
   
  Likewise, if (,)=(1,0) for some index i,
  
      0=step((1)+e). ⇒(1)+e<0. ⇒(0)+e<0. ⇒∀ i; ()+e < 0.
  
  Therefore, =0 regardless of ,
  and thus (,)=(0,1) cannot happen in any i.
  
  Finally, if the data points do not contain (0,1) or (1,0), then by assumption they do not coexist.
  Therefore, the embedding learned by BTL cannot contain (0,1) and (1,0) at the same time.
  
  
  
  
  
  
  
  § MACHINE LEARNING EXPERIMENTS
  
  
  
  
  
   §.§ Source code directory 
  
  
  The directory  contains the source code for reproducing
  our experiments, including training, evaluation, plotting and paraphrasing.
  For details, find the enclosed  file in the directory.
  
  
  
   §.§ Training dataset preparation
   
  
  
  For the model training, we used 
  1 Billion Word Language Model Benchmark dataset <cit.>
  available from <https://www.statmt.org/lm-benchmark/>.
  Since the archive contains only the training set and the test set, we split 
  the training set into the training and the validation set by 99:1.
  The dataset is already tokenized. However, we further downcased each word
  in order to reduce the size of the vocabulary.
  Since the vocabulary does not distinguish certain proper nouns,
  this will equally affect the accuracy across all models trained and evaluated in this paper.
  
  After the split, we pruned the words that appear less than 10 times in the corpus.
  We further reduced the size of the corpus by removing the frequent words,
  as suggested in the original Word2Vec paper <cit.>.
  However, the formula for computing the probability of dropping a word described in the paper is
  different from the actual implementation published on their website
  <https://code.google.com/archive/p/word2vec/>.
  We followed the actual implementation for calculating the probability.
  
  In the paper, the probability p(x) of dropping a word x in the corpus is given by
  
      p(x) = 1- √(t/f(x))
  
  where t is a threshold hyperparameter and f(x) is a frequency of the word in the corpus.
  For example, if the word appeared 5 times in a corpus consisting of 100 words, f(x)=0.05.
  The paper recommends t=10^-5.
  However, the actual implementation uses the formula
  
      p(x) = 1- √(f(x)/t)+1t/f(x)
  
  with t=10^-4 as the default parameter.
  
  
  
  
  
   §.§ Training details
  
  
  
  The training is performed by batched stochastic gradient descent using
  Rectified Adam optimizer <cit.> for 8 epochs, batch-size 1000.
  Each training took maximum of around 32 hours on a single Tesla V100 GPU.
  For CBOW, the loss function is same as that of the original work:
  
  
      logσ (^i · W'_x^i) + ∑_k=1^Klogσ (-^i · W'_r^k).
  
  
  For DSAW, where
  
      ^i   =(x^i, ^0),
      ^i-j   =(x^i-j, (…(x^i-c,^0))…),
      ^i+j   =(x^i+j, (…(x^i+1, (x^i-1, …(x^i-c,^0))))),
  
  for 1≤ j ≤ c, the total loss to maximize is:
  
      logσ ((^i+c-1/2) · (^i-1/2))
      -    ∑_k=1^Klogσ (-(^i+c-1/2) · ((r^k, ^0)-1/2)) 
      
      - ∑_-c≤ j ≤ c, j∉0,1   β(q(^i+j|x^i+j,^i+j-1)||p(^i+j)) 
      
      -    β(q(^i+1|x^i+1,^i-1)||p(^i+1)) 
      
      -    β(q(^i|x^i,^0)||p(^i))
  
  where
  p(^i+j)=Bernoulli(0.5) for all i,j,
  ^0∼Bernoulli(0.5),
   (q(·)||p(·)) 
  is the KL divergence for each discrete variational layer and
  β is the scale factor as in β-VAE <cit.>.
  
  The temperature parameter τ for the Binary Concrete at the epoch t
  (0≤ t ≤ 8, where t could be a fractional number, proportionally spread across the mini-batches)
   follows a stepped schedule below:
  
      τ(t) = {[                                5                      (0 ≤ t < T); 5 ·exp (log0.7/5·⌊t-T/0.2⌋· 0.2)                      (T < t ≤ 8) ].
  
  where T is a hyperparameter that determines when to start the annealing.
  τ approaches 0.7 at the end of the training.
  
  
  
  
  
  
  We performed a grid search in the following hyperparameter space:
  Embedding size V∈200, 500, 1000,
  learning rate  lr∈0.001, 0.003, 0.0001,
  scaling factor β∈0.0, 0.1, 1.0,
  annealing start epoch T∈1,7,
  and a boolean flag A∈⊤, that controls
  whether the Batch Normalization layers in BTL use the Affine transformation.
  We kept c=2 words context window before and after the target words
  and the number of negative-samples K=5 for all experiments.
  We initialize the weight matrix with Gaussian noise for CBOW,
  and with Logistic noise for DSAW, as we discuss in sec:initialization.
  
  
  
  
  
   §.§ Additional experiments: Weight initialization with Logistic(0,1) distribution
  
  
  
  In the original Word2Vec CBOW, the embedding weights are initialized by Uniform noise.
  Gaussian noise N(0,1) is also used in some studies <cit.>,
  and they show comparable results.
  The row W_x selected by the word index x is directly used as the continuous effects in each recurrent step.
  In contrast, DSAW applies BinConcrete in each step,
  which contains a squashing function (sigmoid) 
  and a noise that follows Logistic distribution Logistic(0,1),
  which has a shape similar to Gaussian noise N(0,1) but has a fatter tail.
  
  We hypothesized that
  the word effect W_x_i may fail to sufficiently affect the output values 
  if its absolute value |W_x_i| is relatively small
  compared to the Logistic noise and is squashed by the activation.
  To address this issue,
  we initialized the embedding weights by Logistic(0,1).
  While the in-depth theoretical analysis is left for future work,
  this initialization helped the training of DSAW models in empirical evaluation.
  All results reported for DSAW in other places use this Logistic initialization.
  
  Results in logistic-initialization shows that the DSAW models trained with Logistic weight initialization
  tend to outperform the DSAW trained with Gaussian weight initialization, which is the default initialization scheme
  for the embedding layers in PyTorch library.
  
  
  
  
  
   §.§ Additional model experiments: Discrete implementation of SkipGram
  
  
  In addition to the main model architecture studied in the main paper,
  we also explored two additional potential architectures: SkipGram and SkipGram-BTL.
  Word2Vec Skipgram (SG), is the other model
  architecture originally proposed by 
  along with CBOW. Instead of using a set of context word to predict a
  target word like CBOW, Skipgram reverses the task: it attempts to
  predict the set of context words from the target word. To modify
  Skipgram model to include our discrete property,
  we pass the target word through Back-To-Logit <cit.> on
  one side, and pass each context word on the other side (individually), and
  calculate the loss on both sides. Effectively, context size is now
  reduced to one word and the model loses the recurrent nature of the DSAW architecture.
  Empirically, we find SG-BTL to perform worse than DSAW,
  possibly due to the lack of the recurrence.
  overall-performance-table-sg shows the summary of the SG model
  and the SG-BTL model on the tasks we evaluated on.
  
  
  
  
  
  
  
  
  
   §.§ Additional model experiments: Hybrid discrete-continuous CBOW model
  
  
  Hybrid discrete-continuous models are the second group of additional models we implemented.
  Instead of purely training a discrete or a continuous model,
  this architecture merges the two and trains both embeddings jointly.
  We experimented with this model because we hypothesized that there
  are ambiguous, continuous concepts that are hard to capture logically (e.g., temperature, emotion)
  as well as discrete, logical concepts (e.g., apple, mathematics) within the semantic space.
  
  A hybrid model of embedding size E contains a discrete embedding of size E/2 and a
  continuous embedding of size E/2.
  Two embeddings are concatenated together before the subsequent operations.
  For example, during the training, the loss is calculated by
  concatenating the continuous-bag-of-word representation 
  and the shifted discrete output state ^i+c-0.5,
  then applying the standard Word2Vec loss logσ (·)
   between the target and predict
  embedding ,.
  Similarly, for the vector addition / subtraction operations
  in the analogy task or the word aggregation in text classification,
  the two embeddings are treated with respective methods
  separately and concatenated in the end.
  
  The evaluation results in overall-performance-table-hb shows that
  the hybrid model performs somewhere in between CBOW and
  DSAW, except for analogy top 10 category, which outperforms the best performance of DSAW.
  This could have resulted from our crude way of aggregating the hybrid
  embedding by splitting the vector into two, performing the aggregation separately, then
  concatenating the results together. Future experiments call for more strategic fusing
  of two types of models which allow meaningful and effective word
  embedding aggregation.
  
  
  
  
  
   §.§ Detailed, per-category results for the word similarity task
  
  
  
  Word similarity task is the standard benchmark for measuring the 
  attributional similarity <cit.>.
  Given a set of word pairs,
  each embedding is evaluated by
  computing the Spearman correlation between
  the similarity scores assigned by the embedding
  and those assigned by human <cit.>. 
  The scores for CBOW are obtained by the cosine similarity between two word vectors.
  For the DSAW embedding,
  the standard cosine distance is not directly applicable as each embedding consists of two binary vectors.
  We, therefore, turn the effect of a word x into
  an integer vector of tertiary values {1,0,-1} by x-x, then compute the cosine similarity.
  
  We tested our models with the baseline models on 5 different datasets
  Bruni (MEN),
  Radinsky (MT),
  Luong rare-word (RW),
  Hill Sim999 (SM),
  and WS353 (WS)
  <cit.>. 
  WS353 dataset is further separated into relatedness (WSR) and 
  similarity (WSS) <cit.>.
  To illustrate the difference between relatedness and 
  similarity, we use the example of “ice cream” and “spoon”. The two words are 
  not similar but they are releated in the sense that “spoon” is often used to 
  consume “ice cream”. 
  DSAW model outperforms CBOW model in all datasets except MT.
  The detailed, per-category results for this task can be found in word-similarity-table.
  
  
  
  
  
  
  
   §.§ Detailed, per-category results for the analogy task
  
  
  
  In addition to the overall accuracy in the analogy task, we
  break down the performance of different models into
  the sub-categories in the dataset provided by <cit.>.
  In the ADD column of analogy-best-1000-cbow-method-category,
  we show the per-category accuracy of the CBOW and DSAW models that achieved
  the best overall accuracy as a result of hyperparameter tuning.
  CBOW uses the vector addition ^*-+ for the nearest neighbor,
  and DSAW uses the STRIPS progression ^*.
  DSAW performs similarly to, if not better than CBOW, in different analogy categories. Specifically, DSAW
  performs significantly better than CBOW in “capital-world”, “gram2-opposite”, 
  “gram5-present-participle”, “gram7-past-tense”, and “gram9-plural-verbs”.  
  
  We also show the results of Ignore-A and Only-B aggregation scheme
  <cit.> compared to ADD scheme.
  Compared to the ADD column in analogy-best-1000-cbow-method-category,
  which uses all three input words for the analogy (e.g., ^*-+),
  Ignore-A does not use  (e.g., ^*+), and Only-B uses  unmodified,
  and searches for the nearest neighbor.
  The intention behind testing these variants is to see if the analogy performance
  is truly coming from the differential vector (^*-), or just from the neighborhood structure
  of the target word  and ^*.
  A good representation with nice vector-space property is deemed to have the performance ordering
  ADD > Ignore-A > Only-B.
  Our model indeed tends to have this property,
  as can be seen in the plot (different-method-plot), confirming
  the validity to our approach.
  
  
  
  
  
  
  
   §.§ Exploring the best ordering of the discrete additive operations in analogy task
  
  
  Because the proposed bit-wise operations ,  are not associative or commutable,
  we evaluated the effect of the orders of operations used while performing the analogy task.
  As seen in analogy-best-1000-cbow-3cosadd, the different order of operations
  significantly affects the results.
  The performance of different ordering was consistent across the different hyperparameters.
  In the main paper, we reported the best-performing ordering, ^*^*.
  
  
  
  
  
  
   §.§ Detailed, per-category results for the text classification task
  
  
  
  We used our embeddings for 
  the semantic text classification,
  in which the model must capture the semantic information to perform well.
  We evaluated our model on two datasets: “20 Newsgroup” <cit.>
  and “movie sentiment treebank” <cit.>.
  We created binary classification tasks 
  following the existing work <cit.>:
  For 20 Newsgroup, we picked 4 sets of 2 groups to produce 4 sets of classification problems:
  SCI (science.med vs. science.space),
  COMP (ibm.pc.hardware vs. mac.hardware),
  SPORT (baseball vs. hockey),
  RELI (alt.atheism vs. soc.religion.christian).
  For movie sentiment (MS),
  we ignored the neutral comments and set a threshold for the sentiment values:
  ≤ 0.4 as 0, and > 0.6 as 1.
  In all 20-newsgroup datasets, we split the corpus into train, 
  validation, test set by proportion 0.48, 0.12, and 0.40 
  <cit.>. The movie sentiment dataset, after removing all 
  neutral reviews (about 20% of the original data), is then split 
  into train, validation, and test sets by proportion 0.72, 0.09, and 0.19 
  <cit.>.
  
  In both the CBOW and the DSAW models, we aggregated the word embeddings (by + or ) in a
  sentence or a document to obtain the sentence / document-level embedding.
  We then classified the results with a default L2-regularized logistic regression model in Scikit-learn.
  We recorded the accuracy in the test split and compared it across the models.
  We normalize the imbalance in the number of questions between subtasks
  (SCI,…,RELI have ≈ 2000 questions each
  while MS has ≈ 9000),
  that is, the total accuracy is unweighted average of the accuracies over the 5 datasets.
  This is in order to account for the imbalance in the number of classification inputs in each dataset.
  
  As seen in text-classification-table, our method performs better than the traditional CBOW on three
  20 Newsgroup datasets, comparably on RELI, and less ideally on Movie sentiments.
  We interpreted this result as follows: This is caused by the ability of DSAW embedding to preserve
  the embedded value of the rare, key terms in the document during the aggregation.
  Imagine if a continuous embedding of a rare word x has a dimension whose absolute value is significantly large.
  However, all other words in the sentence have a varying degree of noisy values in the same dimension,
  which accumulates during the aggregation and cause the value to deviate from the original value in the rare word,
  essentially “blurring” the significance of that word.
  In contrast, discrete representations obtained by DSAW have
  the three, clear-cut modes of operations – add, delete, or no-op on specific bits.
  Therefore, the effects from unrelated words, which are frequently no-op (see effect-statistics),
  tend not to affect the value of the important bit in the rare word.
  This characteristics would be less prominent if the length of the sequence is short (MS),
  or if the important key words used for classifying the sentence are
  used frequently enough in the document that it is not obscured by other common words,
  which we subjectively observed in the RELI dataset.
  This interpretation also matches the better performance of DSAW on the
  RW (rare word) dataset in the word similarity task.
  
  
  
  
  
  
  
  
  
  
  
   §.§ Additional experiments: Word compositionality
  
  
  
  One shortcoming of continuous vector operations in CBOW is that
  the resulting embedding is easily affected by the syntactic and semantic redundancy.
  These redundancies should ideally carry no effect on logical understanding,
  and at most with diminishing effect when repetition is used for subjective emphasis.
  Consider the phrase “red red apple”.
  While the first “red” has the effect of specifying the color of the apple,
  the second “red” is logically redundant in the syntactic level.
  Phrases may also contain semantic redundancy, such as “free gift” and “regular habit”.
  However, in a continuous word embedding, simple summation or averaging
  would push the result vector toward the repeated words or meanings.
  That is, for any non-zero vectors  and ,
  cos(· n+,)→ 0, (n→∞) (fig:cosine-bad).
  Even with a more sophisticated aggregation method for a vector sequence,
  such as the recurrent neural networks <cit.>,
  the problem still remains as long as it is based on a continuous representation. 
  The model has to address it somehow, either at word embedding level or at sentence embedding level.
  
  This behavior is problematic in critical applications which require logical soundness.
  For example, one may attempt to fool the automated topic extraction or auditing system
  by repeatedly adding a certain phrase to a document in an invisible font (e.g., transparent)
  as a form of adversarial attack <cit.>.
  This issue is also related to the fact that word2vec embedding
  encodes important information in its magnitude
  <cit.>.
  While <cit.> proposed a method to
  train a vector embedding constrained to a unit sphere,
  the issue caused by the continuous operations still remains.
  
  
  
  
  In this section, we demonstrate this pathological behavior of CBOW
  and show that DSAW addresses this by visualizing the embeddings of composed words.
  We used Principal Component Analysis <cit.> to visualize
  the linear projection of the embedding space.
  Phrase embeddings are obtained by the repeated  (DSAW) or averaging (CBOW) –
  the latter choice is purely for the visualization (length does not affect the cosine distance.)
  For CBOW and DSAW, we used the models that performed the best in analogy task.
  
  
  In fig:syntactic-word-craw,
  we plotted syntactically and semantically redundant phrases
  “habit”, “regular habit”, “regular ... regular habit” (repeated 8 times).
  Continuous embeddings approach closer and closer to the embedding of “regular” as more “regular”s are added.
  On the course of additions,
  the vector tends to share the direction with irrelevant words such as “experiment” or “stunt”.
  In contrast,
  semantically redundant addition of “regular” does not seem to drastically change the direction,
  nor share the direction with irrelevant words.
  Also, repetitive additions do not affect the discrete embedding.
  
  
  
  
  Another example of such a visualization would contain “Long thin solid cylindrical pasta = spaghetti”, where 
  the left-hand-side is a compositional phrase and the right-hand-side is a target word.
  Our aim is to showcase that the given phrase
  should aggregate to the respective target word in the embedding space.
  Additionally, as more adjectives are added to the phrase,
  the resulting phrase embedding should approach the target word (i.e. “cylindrical 
  pasta” - “spaghetti” > “solid cylindrical pasta” - “spaghetti”).
  For each phrase, we added adjectives incrementally to obtain each partial phrase
  embedding through aggregating the word embeddings. We then plotted these 
  embeddings, along with a few of their neighboring words and target words, using 
  Principle Component Analysis (PCA) to show relationships in the embedding space.
  For all examples, we come up with the compositional phrase of each target word 
  inspired by the opening sentences of the corresponding Wikipedia article,
  which often contains the definition of the target word.
  
  In fig:craw-pasta, we plot compositional phrase: Long thin solid
  cylindrical pasta = spaghetti. In both CBOW and DSAW plot, we can
  clearly see two clusters of words. In CBOW, the top cluster (and the
  right cluster in DSAW) includes words related to food and cuisine, and
  the other cluster in respective plots includes words associated with the
  adjectives “long”, “thin”, “solid”, “cylindrical”. We can see
  that under bit-operation, discrete embedding kept the phrase embedding
  close to the food cluster while continuous embedding caused the phrase
  embedding to wonder around different embedding space.
  
  
  
  
  In fig:craw-cattle, we plot compositional phrase: Adult male cattle = ox.
  In the continuous embedding, the phrase is dragged by the “human” aspect of “adult” and “male”,
  resulting in the bottom cluster containing the words related to humans,
  e.g. to “white” (presumably race), “babies”, “inmates”, “girls”.
  In the discrete embedding, both vectors resides in the spread-out cluster
  containing farm (pasture, poultry), animals (chimpanzee, elephants, pig), and foods (beef, steak, patties).
  
  
  
  
  In fig:craw-sheep, we plot Quadrupedal ruminant mammal = sheep. 
  The phrase vector in both embeddings appears to roughly share the direction with “sheep”.
  
  
  
  In fig:craw-ferrari, we plot compositional phrase: Italian
  luxury sports car manufacturer = Ferrari. 
  In this case, discrete embedding fails to share the direction with the intended word “ferrari”
  while continuous embedding roughly succeeds.
  
  
  
  
  
  
  § PLANNING / PARAPHRASING EXPERIMENTS
  
  
  
  
   §.§ The archive directory 
  
  
  The accompanied data dump in 
  contains the sample domain PDDL file (<paraphrasing/domain_soft_0_4000.pddl>) for embedding size 200,
  and the problem files, log files and the plan files found in each experiment
  in <paraphrasing/target_words_examples-1-100/> directory.
  
  This data dump includes the results from other planning configurations and the embedding size.
  The secondary planning configuration uses
  , an iterative variant of planner
  <cit.> (reimplementation in Fast Downward <cit.>)
  that first performs Greedy Best First Search, then
  continues refining the solution with Weighted with decreasing weights
  10,5,3,2,1.
  
  
  
   §.§ Compilation of a net-benefit planning problem into a classical planning problem
  
  
  
  A net-benefit planning task P,A,I,G,c,u can be compiled into
  a classical planning problem with action cost P',A',I',G',c' as follows <cit.>.
  We use the slightly different notation from <cit.>
  by assuming a negative precondition extension <cit.>
  and by assuming all goals are soft:
  
  
      P'    = P ∪end-mode∪marked(p)| p ∈ G
      
       A'    = A”∪end∪collect(p),forgo(p) | p∈ G
      
       A”   = a¬end-mode,a,a| a ∈ A
      ∀ a”∈ A”; c'(a”)   =c(a)
      collect(p)   =end-mode p¬marked(p), marked(p), ∅
       
       c'(collect(p))   =0
      forgo(p)   =end-mode¬ p¬marked(p), marked(p), ∅
      
       c'(forgo(p))   =u(p)
      end   =¬end-mode, end-mode, ∅
      
       c'(end)   =0
      
       G'   =marked(p)| p ∈ G.
  
  
  Also, as mentioned in <cit.>, we add additional preconditions to collect, forgo
  that linearize the ordering between the actions, i.e., for i>0,
  collect(p_i)=end-mode p_i ¬marked(p_i) marked(p_i-1).
  (Same for forgo.)
  
  As a paraphrasing-specific enhancement, we further add the constraint that forces to avoid using the same word twice.
  That is, ∀ a”∈ A”; a”∋¬used(a”); a”∋used(a”),
  where used(a”) is added to P' for all a”.
  
  
  
  
   §.§ The list of 68 target words used in the paraphrasing experiment
  
  
  
  In the paraphrasing experiments,
  we hand-picked the words listed in fig:target-word-list
  and generate the paraphrasing planning problem.
  
  
  
  
  
  
   §.§ The statistics of the discrete effect vectors
  
  
  
   <cit.> discussed the relationship
  between the word frequency and the magnitude (length) of the continuous word embedding vectors.
  In contrast, DSAW embedding consists of two vectors, x and x,
  and each dimension in the embedding is restricted to the binary values 0, 1.
  In order to understand the behavior of our discrete embedding,
  we visualized the density of the effect presense, i.e., 1/E∑_j=1^E x_j
  and 1/E∑_j=1^E x_j.
  We plotted these statistics for each word x in the order of frequency.
  
  In fig:effect-density, we observe that rare words tend to have more effects.
  This matches our intuitive understanding of the meaning of the rare, complex words:
  Complex words tend to be explained by or constructed from the simpler, more basic words.
  This may also be suggesting why the paraphrasing task works well:
  The planner is able to compose simpler words to explain the more complex word
  because of this characteristics.
  
  
  
  
  
   §.§ Runtime statistics for the word paraphrasing experiment
  
  
  
  We visualized the runtime statistics of the paraphrasing task.
  fig:runtime (left) shows the cumulative plots
  of the number of solutions found at a certain point of time,
  over all target words / problem instances used in the experiment. 
  x-axis plots the runtime, and y-axis plots the number of solutions found.
  We plotted the results obtained by the embedding size E=200, soft-goal cost U=100 and the LAMA planner.
  The plot shows that the first solutions are obtained relatively quickly
  and more solutions are found later due to the iterative, anytime planning behavior of LAMA.
  
  Moreover, in fig:runtime (right),
  we show the “actual search time” which excludes the time for parsing, preprocessing and datastructure setup
  for the heuristic search. This shows that the majority of the time was spent on just reading the large PDDL file
  that was produced from the embedding vector of 4000 words.
  On a practical, long-running system with an appropriate caching mechanism,
  this bottleneck can be largely amortized.
  
  In fig:runtime-length2,
  we also show the cumulative plots restricted to the solutions with the length larger than 2,
  because a solution with the length 1 in the net-benefit planning problem is
  equivalent to merely finding a nearest neighbor word in L1 distance,
  rather than finding a phrase.
  
  
  
  
  
  
  
  
  
   §.§ Additional paraphrasing for a set of randomly selected 300 words
  
  
  
  Finally, we performed further experiments with an additional set of 300 words
  randomly selected from the 4000th to the 8000th most frequent words in the vocabulary.
  This additional set includes more proper nouns, whose paraphrasing tends to be meaningless.
  However, we discover even more new examples that are interesting.
  The paraphrasing examples can be found in tab:more-planning-example1tab:more-planning-example2.
  The additional data dump can be found in <paraphrasing/target_words_4000_8000-1-100/> directory.
  
  
  
  
  
  
  
  9.5pt10.5pt
  72
  
  
  urlstyle
  
  [Agirre et al.(2009)Agirre, Alfonseca, Hall, Kravalova, Pasca, and
    Soroa]agirre2009study
  Eneko Agirre, Enrique Alfonseca, Keith Hall, Jana Kravalova, Marius Pasca, and
    Aitor Soroa.
  A Study on Similarity and Relatedness Using Distributional and
    WordNet-based Approaches.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  19, 2009.
  
  [Alcázar et al.(2013)Alcázar, Borrajo, Fernández, and
    Fuentetaja]alcazar2013revisiting
  Vidal Alcázar, Daniel Borrajo, Susana Fernández, and Raquel Fuentetaja.
  Revisiting Regression in Planning.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), 2013.
  
  [Amado et al.(2018a)Amado, Pereira, Aires, Magnaguagno,
    Granada, and Meneguzzi]amado2018goal
  Leonardo Amado, Ramon Fraga Pereira, Joao Aires, Mauricio Magnaguagno, Roger
    Granada, and Felipe Meneguzzi.
  Goal Recognition in Latent Space.
  In Proc. of International Joint Conference on Neural Networks
    (IJCNN), 2018a.
  
  [Amado et al.(2018b)Amado, Pereira, Aires, Magnaguagno,
    Granada, and Meneguzzi]amado2018lstm
  Leonardo Amado, Ramon Fraga Pereira, Joao Aires, Mauricio Magnaguagno, Roger
    Granada, and Felipe Meneguzzi.
  LSTM-based Goal Recognition in Latent Space.
  arXiv preprint arXiv:1808.05249, 2018b.
  
  [Asai & Fukunaga(2018)Asai and Fukunaga]Asai2018
  Masataro Asai and Alex Fukunaga.
  Classical Planning in Deep Latent Space: Bridging the
    Subsymbolic-Symbolic Boundary.
  In Proc. of AAAI Conference on Artificial Intelligence,
    2018.
  
  [Asai & Muise(2020)Asai and Muise]Asai2020
  Masataro Asai and Christian Muise.
  Learning Neural-Symbolic Descriptive Planning Models via Cube-Space
    Priors: The Voyage Home (to STRIPS).
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), 2020.
  
  [Banarescu et al.(2013)Banarescu, Bonial, Cai, Georgescu, Griffitt,
    Hermjakob, Knight, Koehn, Palmer, and Schneider]banarescu2013abstract
  Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf
    Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider.
  Abstract Meaning Representation for Sembanking.
  In Proc. of the 7th Linguistic Annotation Workshop and
    Interoperability with Discourse, pp.  178–186, 2013.
  
  [Bolukbasi et al.(2016)Bolukbasi, Chang, Zou, Saligrama, and
    Kalai]bolukbasi2016man
  Tolga Bolukbasi, Kai-Wei Chang, James Y. Zou, Venkatesh Saligrama, and
    Adam Tauman Kalai.
  Man is to Computer Programmer as Woman is to Homemaker? Debiasing
    Word Embeddings.
  In Advances in Neural Information Processing Systems, pp.  4349–4357, 2016.
  
  [Brown et al.(2020)Brown, Mann, Ryder, Subbiah, Kaplan, Dhariwal,
    Neelakantan, Shyam, Sastry, Askell, Agarwal, Herbert-Voss, Krueger,
    Henighan, Child, Ramesh, Ziegler, Wu, Winter, Hesse, Chen, Sigler, Litwin,
    Gray, Chess, Clark, Berner, McCandlish, Radford, Sutskever, and Amodei]gpt3
  Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan,
    Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda
    Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom
    Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens
    Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott
    Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec
    Radford, Ilya Sutskever, and Dario Amodei.
  Language Models are Few-Shot Learners.
  CoRR, abs/2005.14165, 2020.
  URL <https://arxiv.org/abs/2005.14165>.
  
  [Bruni et al.(2014)Bruni, Tran, and Baroni]bruni2014multimodal
  Elia Bruni, Nam-Khanh Tran, and Marco Baroni.
  Multimodal Distributional Semantics.
  J. Artif. Intell. Res.(JAIR), 49:0 1–47, 2014.
  
  [Bylander(1994)]bylander1994
  Tom Bylander.
  The Computational Complexity of Propositional STRIPS Planning.
  Artificial Intelligence, 690 (1):0 165–204,
    1994.
  
  [Caliskan et al.(2017)Caliskan, Bryson, and
    Narayanan]caliskan2017semantics
  Aylin Caliskan, Joanna J Bryson, and Arvind Narayanan.
  Semantics derived automatically from language corpora contain
    human-like biases.
  Science, 3560 (6334):0 183–186, 2017.
  
  [Chelba et al.(2014)Chelba, Mikolov, Schuster, Ge, Brants, Koehn, and
    Robinson]chelba2014one
  Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp
    Koehn, and Tony Robinson.
  One Billion Word Benchmark for Measuring Progress in Statistical
    Language Modeling.
  In Proc. of Annual Conference of the International Speech
    Communication Association, 2014.
  
  [Chen et al.(2018)Chen, Min, and Sun]chen2018kway
  Ting Chen, Martin Renqiang Min, and Yizhou Sun.
  Learning K-way D-dimensional Discrete Codes for Compact Embedding
    Representations.
  In Proc. of the International Conference on Machine
    Learning, volume 80 of Proceedings of Machine Learning Research,
    pp.  853–862, 2018.
  
  [Cho et al.(2014)Cho, van Merrienboer, Gülçehre, Bahdanau,
    Bougares, Schwenk, and Bengio]cho2014gru
  Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry
    Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio.
  Learning Phrase Representations using RNN Encoder-Decoder for
    Statistical Machine Translation.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  1724–1734, 2014.
  
  [Cullen & Bryman(1988)Cullen and Bryman]cullen88
  J Cullen and A Bryman.
  The Knowledge Acquisition Bottleneck: Time for Reassessment?
  Expert Systems, 50 (3), 1988.
  
  [Drozd et al.(2016)Drozd, Gladkova, and Matsuoka]Drozd2016Word
  Aleksandr Drozd, Anna Gladkova, and Satoshi Matsuoka.
  Word Embeddings, Analogies, and Machine Learning: Beyond
    King-Man+Woman=Queen.
  In Proc. of the International Conference on Computational
    Linguistics, pp.  3519–3530, 2016.
  
  [Faruqui & Dyer(2014)Faruqui and Dyer]faruqui2014community
  Manaal Faruqui and Chris Dyer.
  Community Evaluation and Exchange of Word Vectors at
    Wordvectors.org.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  19–24, 2014.
  
  [Feng et al.(2018)Feng, Zhuo, and Kambhampati]feng2018extracting
  Wenfeng Feng, Hankz Hankui Zhuo, and Subbarao Kambhampati.
  Extracting Action Sequences from Texts Based on Deep Reinforcement
    Learning.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), 2018.
  
  [Fikes et al.(1972)Fikes, Hart, and Nilsson]FikesHN72
  Richard E Fikes, Peter E. Hart, and Nils J. Nilsson.
  Learning and Executing Generalized Robot Plans.
  Artificial Intelligence, 30 (1-3):0
    251–288, 1972.
  
  [Finkelstein et al.(2001)Finkelstein, Gabrilovich, Matias, Rivlin,
    Solan, Wolfman, and Ruppin]finkelstein2001placing
  Lev Finkelstein, Evgeniy Gabrilovich, Yossi Matias, Ehud Rivlin, Zach Solan,
    Gadi Wolfman, and Eytan Ruppin.
  Placing Search in Context: The Concept Revisited.
  In Proc. of the International Conference on World Wide Web,
    pp.  406–414, 2001.
  
  [Flanigan et al.(2014)Flanigan, Thomson, Carbonell, Dyer, and
    Smith]flanigan2014discriminative
  Jeffrey Flanigan, Sam Thomson, Jaime G. Carbonell, Chris Dyer, and Noah A.
    Smith.
  A Discriminative Graph-Based Parser for the Abstract Meaning
    Representation.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  1426–1436, 2014.
  
  [Geib & Steedman(2007)Geib and Steedman]geib2007on
  Christopher W. Geib and Mark Steedman.
  On Natural Language Processing and Plan Recognition.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), pp.  1612–1617, 2007.
  
  [Ghallab et al.(2004)Ghallab, Nau, and Traverso]ghallab2004automated
  Malik Ghallab, Dana Nau, and Paolo Traverso.
  Automated Planning: Theory and Practice.
  Elsevier, 2004.
  
  [Haslum et al.(2019)Haslum, Lipovetzky, Magazzeni, and Muise]pddlbook
  Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, and Christian Muise.
  An Introduction to the Planning Domain Definition Language.
  Synthesis Lectures on Artificial Intelligence and Machine
    Learning, 130 (2):0 1–187, 2019.
  
  [Helmert(2006)]Helmert2006
  Malte Helmert.
  The Fast Downward Planning System.
  J. Artif. Intell. Res.(JAIR), 26:0 191–246, 2006.
  
  [Higgins et al.(2017)Higgins, Matthey, Pal, et al.]higgins2017beta
  Irina Higgins, Loïc Matthey, Arka Pal, et al.
  β-VAE: Learning Basic Visual Concepts with a Constrained
    Variational Framework.
  In Proc. of the International Conference on Learning
    Representations, 2017.
  
  [Hill et al.(2015)Hill, Reichart, and Korhonen]hill2015simlex
  Felix Hill, Roi Reichart, and Anna Korhonen.
  Simlex-999: Evaluating Semantic Models with (Genuine) Similarity
    Estimation.
  Computational Linguistics, 410 (4):0 665–695,
    2015.
  
  [Hochreiter & Schmidhuber(1997)Hochreiter and
    Schmidhuber]hochreiter1997long
  Sepp Hochreiter and Jürgen Schmidhuber.
  Long Short-Term Memory.
  Neural Computation, 90 (8):0 1735–1780, 1997.
  
  [Hoffmann & Nebel(2001)Hoffmann and Nebel]hoffmann01
  Jörg Hoffmann and Bernhard Nebel.
  The FF Planning System: Fast Plan Generation through Heuristic
    Search.
  J. Artif. Intell. Res.(JAIR), 14:0 253–302, 2001.
  
  [Ioffe & Szegedy(2015)Ioffe and Szegedy]ioffe2015batch
  Sergey Ioffe and Christian Szegedy.
  Batch Normalization: Accelerating Deep Network Training by Reducing
    Internal Covariate Shift.
  In Proc. of the International Conference on Machine
    Learning, pp.  448–456, 2015.
  
  [Jang et al.(2017)Jang, Gu, and Poole]jang2017categorical
  Eric Jang, Shixiang Gu, and Ben Poole.
  Categorical Reparameterization with Gumbel-Softmax.
  In Proc. of the International Conference on Learning
    Representations, 2017.
  
  [Jia & Liang(2017)Jia and Liang]jia2017adversarial
  Robin Jia and Percy Liang.
  Adversarial Examples for Evaluating Reading Comprehension Systems.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  2021–2031, 2017.
  
  [Keyder & Geffner(2009)Keyder and Geffner]emil2009soft
  Emil Keyder and Hector Geffner.
  Soft goals can be compiled away.
  J. Artif. Intell. Res.(JAIR), 36:0 547–556, 2009.
  10.1613/jair.2857.
  URL <https://doi.org/10.1613/jair.2857>.
  
  [Kim et al.(2019)Kim, Dyer, and Rush]kim2019compound
  Yoon Kim, Chris Dyer, and Alexander M Rush.
  Compound Probabilistic Context-Free Grammars for Grammar Induction.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  2369–2385, 2019.
  
  [Kingma & Welling(2013)Kingma and Welling]kingma2013auto
  Diederik P Kingma and Max Welling.
  Auto-Encoding Variational Bayes.
  In Proc. of the International Conference on Learning
    Representations, 2013.
  
  [Kocmi & Bojar(2017)Kocmi and Bojar]kocmi2017initialization
  Tom Kocmi and Ondrej Bojar.
  An Exploration of Word Embedding Initialization in Deep-Learning
    Tasks.
  In Proceedings of the 14th International Conference on Natural
    Language Processing, ICON, pp.  56–64, 2017.
  
  [Kocsis & Szepesvári(2006)Kocsis and
    Szepesvári]kocsis2006bandit
  Levente Kocsis and Csaba Szepesvári.
  Bandit Based Monte-Carlo Planning.
  pp.  282–293, 2006.
  
  [Kurutach et al.(2018)Kurutach, Tamar, Yang, Russell, and
    Abbeel]kurutach2018learning
  Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart Russell, and Pieter Abbeel.
  Learning Plannable Representations with Causal InfoGAN.
  In Advances in Neural Information Processing Systems, 2018.
  
  [Lacker(2020)]gpt3-turing-test
  Kevin Lacker.
  Giving GPT-3 a Turing Test, 2020.
  URL
    <https://lacker.io/ai/2020/07/06/giving-gpt-3-a-turing-test.html>.
  
  [Lang(1995)]lang1995newsweeder
  Ken Lang.
  Newsweeder: Learning to Filter Netnews.
  In Proc. of the International Conference on Machine
    Learning, pp.  331–339, 1995.
  
  [Levy & Goldberg(2014)Levy and Goldberg]levy2014linguistic
  Omer Levy and Yoav Goldberg.
  Linguistic Regularities in Sparse and Explicit Word
    Representations.
  In Proc. of Conference on Computational Natural Language
    Learning, pp.  171–180, 2014.
  
  [Lindsay et al.(2017)Lindsay, Read, Ferreira, Hayton, Porteous, and
    Gregory]lindsay2017framer
  Alan Lindsay, Jonathon Read, Joao F Ferreira, Thomas Hayton, Julie Porteous,
    and Peter J Gregory.
  Framer: Planning Models from Natural Language Action Descriptions.
  In Proc. of the International Conference on Automated Planning
    and Scheduling(ICAPS), 2017.
  
  [Liu et al.(2019)Liu, Jiang, He, et al.]liu2019variance
  Liyuan Liu, Haoming Jiang, Pengcheng He, et al.
  On the Variance of the Adaptive Learning Rate and Beyond.
  arXiv:1908.03265, 2019.
  
  [López et al.(2015)López, Celorrio, and
    Olaya]lopez2015deterministic
  Carlos Linares López, Sergio Jiménez Celorrio, and Ángel García
    Olaya.
  The Deterministic Part of the Seventh International Planning
    Competition.
  Artificial Intelligence, 223:0 82–119, 2015.
  
  [Luong et al.(2013)Luong, Socher, and Manning]Luong2013better
  Minh-Thang Luong, Richard Socher, and Christopher D. Manning.
  Better Word Representations with Recursive Neural Networks for
    Morphology.
  In Proc. of Conference on Computational Natural Language
    Learning, 2013.
  
  [Maddison et al.(2016)Maddison, Mnih, and Teh]maddison2016concrete
  Chris J Maddison, Andriy Mnih, and Yee Whye Teh.
  The concrete distribution: A continuous relaxation of discrete random
    variables.
  arXiv preprint arXiv:1611.00712, 2016.
  
  [Maddison et al.(2017)Maddison, Mnih, and Teh]maddison2017concrete
  Chris J. Maddison, Andriy Mnih, and Yee Whye Teh.
  The Concrete Distribution: A Continuous Relaxation of Discrete
    Random Variables.
  In Proc. of the International Conference on Learning
    Representations, 2017.
  
  [Mikolov et al.(2013a)Mikolov, Chen, Corrado, and
    Dean]mikolov2013cbow
  Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.
  Efficient Estimation of Word Representations in Vector Space.
  In Proc. of the International Conference on Learning
    Representations, 2013a.
  
  [Mikolov et al.(2013b)Mikolov, Sutskever, Chen, Corrado,
    and Dean]mikolov2013distributed
  Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.
  Distributed Representations of Words and Phrases and Their
    Compositionality.
  In Advances in Neural Information Processing Systems, pp.  3111–3119, 2013b.
  
  [Mikolov et al.(2013c)Mikolov, Yih, and
    Zweig]mikolov2013linguistic
  Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig.
  Linguistic Regularities in Continuous Space Word Representations.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  746–751,
    2013c.
  
  [Miller & Charles(1991)Miller and Charles]miller1991contextual
  George A. Miller and Walter G. Charles.
  Contextual Correlates of Semantic Similarity.
  Language and Cognitive Processes, 60 (1):0
    1–28, 1991.
  
  [Myers et al.(2010)Myers, Well, and Lorch]myers2010research
  J.L. Myers, A. Well, and R.F. Lorch.
  Research Design and Statistical Analysis.
  Routledge, 2010.
  ISBN 9780805864311.
  URL <https://books.google.com/books?id=nbsOIJ_saUAC>.
  
  [Neishi et al.(2017)Neishi, Sakuma, Tohda, Ishiwatari, Yoshinaga, and
    Toyoda]neishi2017bagoftrick
  Masato Neishi, Jin Sakuma, Satoshi Tohda, Shonosuke Ishiwatari, Naoki
    Yoshinaga, and Masashi Toyoda.
  A Bag of Useful Tricks for Practical Neural Machine Translation:
    Embedding Layer Initialization and Large Batch Size.
  In Proceedings of the 4th Workshop on Asian Translation,
    pp.  99–109, 2017.
  
  [Nissim et al.(2020)Nissim, van Noord, and van der
    Goot]nissim2019fair
  Malvina Nissim, Rik van Noord, and Rob van der Goot.
  Fair is Better than Sensational: Man is to Doctor as Woman is to
    Doctor.
  Computational Linguistics, Just Accepted, 2020.
  
  [Payan(1992)]payan1992chromatic
  Charles Payan.
  On the Chromatic Number of Cube-Like Graphs.
  Discrete mathematics, 1030 (3), 1992.
  
  [Pearson(1901)]pearson1901liii
  Karl Pearson.
  LIII. On Lines and Planes of Closest Fit to Systems of Points in
    Space.
  The London, Edinburgh, and Dublin Philosophical Magazine and
    Journal of Science, 20 (11):0 559–572, 1901.
  
  [Radinsky et al.(2011)Radinsky, Agichtein, Gabrilovich, and
    Markovitch]radinsky2011word
  Kira Radinsky, Eugene Agichtein, Evgeniy Gabrilovich, and Shaul Markovitch.
  A Word at a Time: Computing Word Relatedness using Temporal Semantic
    Analysis.
  In Proc. of the International Conference on World Wide Web,
    pp.  337–346, 2011.
  
  [Resnik(1995)]resnik1995using
  Philip Resnik.
  Using Information Content to Evaluate Semantic Similarity in a
    Taxonomy.
  In Proc. of International Joint Conference on Artificial
    Intelligence (IJCAI), pp.  448–453, 1995.
  
  [Richter & Westphal(2010)Richter and Westphal]richter2010lama
  Silvia Richter and Matthias Westphal.
  The LAMA Planner: Guiding Cost-Based Anytime Planning with
    Landmarks.
  J. Artif. Intell. Res.(JAIR), 390 (1):0
    127–177, 2010.
  
  [Rieser & Lemon(2009)Rieser and Lemon]rieser2009natural
  Verena Rieser and Oliver Lemon.
  Natural Language Generation as Planning Under Uncertainty for Spoken
    Dialogue Systems.
  In Proceedings of the 12th Conference of the European
    Chapter of the ACL (EACL 2009), pp.  683–691, 2009.
  
  [Rubenstein & Goodenough(1965)Rubenstein and
    Goodenough]rubenstein1965contextual
  Herbert Rubenstein and John B Goodenough.
  Contextual Correlates of Synonymy.
  Communications of the ACM, 80 (10):0 627–633,
    1965.
  
  [Schakel & Wilson(2015)Schakel and Wilson]schakel2015measuring
  Adriaan M. J. Schakel and Benjamin J. Wilson.
  Measuring Word Significance using Distributed Representations of
    Words.
  CoRR, abs/1508.02297, 2015.
  
  [Socher et al.(2013)Socher, Perelygin, Wu, Chuang, Manning, Ng, and
    Potts]socher2013recursive
  Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning,
    Andrew Y Ng, and Christopher Potts.
  Recursive Deep Models for Semantic Compositionality over a Sentiment
    Treebank.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  1631–1642, 2013.
  
  [Towell & Shavlik(1994)Towell and Shavlik]towell1994knowledge
  Geoffrey G Towell and Jude W Shavlik.
  Knowledge-Based Artificial Neural Networks.
  Artificial Intelligence, 700 (1-2):0
    119–165, 1994.
  
  [Tsvetkov et al.(2015)Tsvetkov, Faruqui, Ling, Lample, and
    Dyer]Tsvetkov2015Evaluation
  Yulia Tsvetkov, Manaal Faruqui, Wang Ling, Guillaume Lample, and Chris Dyer.
  Evaluation of Word Vector Representations by Subspace Alignment.
  In Proc. of Conference on Empirical Methods in Natural
    Language Processing, pp.  2049–2054, 2015.
  
  [Wang et al.(2015)Wang, Xue, and Pradhan]wang2015transition
  Chuan Wang, Nianwen Xue, and Sameer Pradhan.
  A Transition-based Algorithm for AMR Parsing.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  366–375,
    2015.
  
  [Wermter & Lehnert(1989)Wermter and Lehnert]wermter1989hybrid
  Stefan Wermter and Wendy G Lehnert.
  A Hybrid Symbolic/Connectionist Model for Noun Phrase
    Understanding.
  Connection Science, 10 (3):0 255–272, 1989.
  
  [Wilson & Schakel(2015)Wilson and Schakel]wilson2015controlled
  Benjamin J. Wilson and Adriaan M. J. Schakel.
  Controlled Experiments for Word Embeddings.
  CoRR, abs/1510.02675, 2015.
  
  [Xing et al.(2015)Xing, Wang, Liu, and Lin]xing2015normalized
  Chao Xing, Dong Wang, Chao Liu, and Yiye Lin.
  Normalized Word Embedding and Orthogonal Transform for Bilingual
    Word Translation.
  In Proc. of the North American Chapter of the Association for
    Computational Linguistics: Human Language Technologies, pp.  1006–1011,
    2015.
  
  [Yogatama & Smith(2014)Yogatama and Smith]Yogatama2014Linguistic
  Dani Yogatama and Noah A Smith.
  Linguistic Structured Sparsity in Text Categorization.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  786–796, 2014.
  
  [Zhao et al.(2018)Zhao, Lee, and Eskénazi]zhao2018unsupervised
  Tiancheng Zhao, Kyusong Lee, and Maxine Eskénazi.
  Unsupervised Discrete Sentence Representation Learning for
    Interpretable Neural Dialog Generation.
  In Proc. of the Annual Meeting of the Association for
    Computational Linguistics, pp.  1098–1107, 2018.
  
  
  
  
  
  
  
  