Generalization to Novel Objects using Prior Relational Knowledge
Varun Kumar Vijay Abhinav Ganesh Hanlin Tang Arjun Bansal

=1




























            





C[1]>
m#1

 
[table]skip=10pt









 
0.5em

    

    0.5em
    t]c



























Generalization to Novel Objects Using Prior Relational Knowledge
    
  Varun Kumar Vijay 

  Intel AI Lab

  Santa Clara, CA 

  
  Abhinav Ganesh 

  Intel AI Lab 

  Santa Clara, CA 

   

   Hanlin Tang 

   Intel AI Lab 

   Santa Clara, CA 

    

   Arjun K. Bansal 

   Intel AI Lab 

   Santa Clara, CA 

   

    
=============================================================================================================================================================================================================================================================





To solve tasks in new environments involving objects unseen during training, agents must reason over prior information about those objects and their relations. We introduce the Prior Knowledge Graph network, an architecture for combining prior information, structured as a knowledge graph, with a symbolic parsing of the visual scene, and demonstrate that this approach is able to apply learned relations to novel objects whereas the baseline algorithms fail. Ablation experiments show that the agents ground the knowledge graph relations to semantically-relevant behaviors. In both a Sokoban game and the more complex Pacman environment, our network is also more sample efficient than the baselines, reaching the same performance in 5-10x fewer episodes. Once the agents are trained with our approach, we can manipulate agent behavior by modifying the knowledge graph in semantically meaningful ways. These results suggest that our network provides a framework for agents to reason over structured knowledge graphs while still leveraging gradient based learning approaches.




§ INTRODUCTION



Humans have a remarkable ability to both generalize known actions to novel objects, and reason about novel objects once their relationship to known objects is understood. For example, on being told a novel object (e.g. 'bees') is to be avoided, we readily apply our prior experience avoiding known objects without needing to experience a sting. Deep Reinforcement Learning (RL) has achieved many remarkable successes in recent years including results with Atari <cit.> games and Go <cit.> that have matched or exceeded human performance. While a human playing Atari games can, with a few sentences of natural language instruction, quickly reach a decent level of performance, modern end-to-end deep reinforcement learning methods still require millions of frames of experience (for e.g. see Fig. 3 in <cit.>). Past studies have hypothesized a role for prior knowledge in addressing this gap between human performance and Deep RL <cit.>. 

While other works have studied the problem of generalizing tasks involving the same objects (and relations) to novel environments, goals, or dynamics <cit.>, here we specifically study the problem of generalizing known relationships to novel objects. Zero-shot transfer of such relations could provide a powerful mechanism for learning to solve novel tasks. We speculated that objects might serve as a useful intermediate symbolic representation to combine the visual scene with knowledge graphs encoding the objects and their relations <cit.>. 

To build this approach, we needed novel components to transfer information between the knowledge graph and the symbolic scene. Prior approaches <cit.> have only used one-directional transfers, and without diverse edge relation types. In this paper, we propose the Prior Knowledge Graph Network (PKGNet), which makes several key contributions:


    
  * We introduced new layer types (,  and  for sharing representations between the knowledge graph and the symbolic visual scene. 
    
  * We leveraged edge-conditioned convolution <cit.> to induce our method to learn edge-specific relations that can be applied to novel objects.
    
  * Compared to several baselines (DQN <cit.>, DQN-Prioritized Replay <cit.>, A2C <cit.>) in two environments (Sokoban, PacMan), our approach is 5-10x more sample efficient during training, and importantly, able to apply learned relations to novel objects.
    
  * We describe a mechanistic role for how the knowledge graph is leveraged in solving the tasks.


We observed agents' behavior while manipulating the knowledge graph during runtime (i.e., using a trained agent), which confirmed that those edges were grounded to the game semantics. These results demonstrate that our PKGNet framework can provide a foundation for faster learning and generalization in deep reinforcement learning.



§ RELATED WORK




 §.§ Graph Based Reinforcement Learning

Graph-based architectures for reinforcement learning have been applied in several contexts. In recent work in control problems and text-based games, the graph is used as a structured representation of the state space, either according to the anatomy of the agent <cit.> or to build a description of relations in the world during text based exploration <cit.>. We use the graph as structured prior knowledge to inject into the network. 

In Yang et al <cit.>, a knowledge graph was used to assist agents in finding novel objects in a visual search task. Our work has several key differences. Here we test methods for applying learned relations (e.g. push, avoid, chase) to novel objects. In their approach, adding those explicit relations to the graph significantly impaired performance, so relations are omitted from their knowledge graph, rendering their approach not viable in our task. Yang et al. also rely on significantly more prior knowledge, including word embeddings and object co-occurrence. Instead, here we provide arbitrary one-hot relation vectors, and agents learn to relate those vectors to actions, while achieving better relative performance gains.

Previous approaches take a one-directional approach of concatenating the knowledge graph features into the state features. We hypothesize that reasoning in both feature space and structured representations is important, and therefore introduce components to share representations between the two domains. By pooling state features into the graph and performing convolutions, our model implements a global operation similar to the self-attention layer used in the Relational RL architecture <cit.>. However, that model tackles the problem of learning relational knowledge during training, without any a priori knowledge. Our model is designed to exploit external knowledge to generalize to new objects at test time.



 §.§ Extracting symbols for Reinforcement Learning

Several studies have extracted objects from visual input using unsupervised or semi-supervised methods <cit.>.  
As the focus of our study is combining scene graphs and knowledge graphs, and not the extraction of symbols themselves, we assume that our network has object level ground truth information available from the scene. For this reason we use environments that can be programmatically generated. In comparison to approaches that operate in 3-D environments <cit.>, our approach solves fundamental problems of how and whether prior relational knowledge encoded with extremely minimal knowledge can be leveraged efficiently.
 










§ PRIOR KNOWLEDGE GRAPH NETWORK





Reinforcement learning models often use RGB features as input to a Convolutional Neural Network (CNN). We apply our algorithms to symbolically parsed visual environments by encoding each symbol into a one-hot vector, as is done for character-level CNN models in natural language processing <cit.>. In our proposed PKGNet, the input consists of a knowledge graph (representing prior information) and a scene graph. 

State. While PKGNet can handle general scene graphs, the environments in this paper are 2-D grid worlds, a specific subset of scene graphs where the vertices are the symbols, and the edges connect neighboring entities. Edge-conditioned graph convolution then reduces to regular 2D convolution. Therefore, we refer to the scene graph by its state representation 𝒮∈ℝ^h × w × d, which is the feature map. 

Knowledge Graph. The knowledge graph 𝒦=(𝒱, ℰ) is a directed graph provided as vertices for each symbol in the environment (for subjects and objects), 𝒱={v_A, v_b, v_B, v_+, …} initially encoded as one-hot vectors of length |𝒱|, and edge features ℰ={e_Ab, e_AB, e_A+, …}. The edge features (for relations) are represented as one-hot vectors. The connectivity of the graph, as well as the edge features are designed to reflect the structure of the environment. During training, the knowledge graph's structure and features are fixed. Importantly, while we provide the one-hot encoded representation of the edge relationships, the agent must learn to ground the meaning of this representation in terms of rewarding actions during training. If successfully grounded, the agent may use this representation during the test phase when it encounters novel objects connected with known relationships to entities in the knowledge graph.

Algorithms. We tested our network with the Deep-Q Network <cit.>, as well as Prioritized Experience Replay (PER) <cit.>, and the A2C algorithm <cit.>.



 §.§ Model Architecture

 The model architecture is shown in Figure <ref>. First, we apply two layers of edge-conditioned graph convolution (ECC) <cit.> to 𝒦 to enrich the node features with information from the neighborhood of each node. Those features are then encoded in the state representation 𝒮 through a  layer. The network's main trunk consists of several  layers, which serve to jointly convolve over the state and knowledge graph. The side branch (dotted blue rectangle), enables reasoning over the structured knowledge graph. In the side branch, we first update the knowledge graph with  from the state, followed by graph convolutions. Then, we update the state representation with a  layer, which incorporates the updated knowledge graph. Finally, for DQN and DQN-PER, we use a few linear layers to compute the Q-values for each action. For A2C, we also emit a value estimate. We provide below more details on the individual components.



 §.§ Model Components

We introduce several operations for transferring information between the state representation 𝒮 and the knowledge graph 𝒦. We can  the knowledge graph features into the state, or use  to gather the state features into the knowledge graph nodes. We can also update the state representation by jointly convolving over (𝒮, 𝒦), which we call . Supplemental Figure 1 shows visual depictions of these operations.



  
Graph Convolutions. In order to compute features for the entities in the knowledge graph, we use an edge-conditioned graph convolution (ECC) <cit.>. In this formulation, a multilayer perceptron network is used to generate the filters given the edge features as input. Each graph layer g computes the feature of each node v_i as:


    v_i = ∑_v_j ∈𝒩(v_i)Θ[e_ij]v_j + b


where the weight function Θ[e_ij] depends only on the edge feature and is parameterized as a neural network. 𝒩(v_i) is the set of nodes with edges into v_i. Our implementation uses graph convolution layers with d=64 features, and the weight network is a single linear layer with 8 hidden units. The output of g is a graph with nodes 𝒱∈ℝ^|𝒱| × d.



  
Broadcast. We define the function :𝒦→𝒮. For each entity i in the knowledge graph, we copy its graph representation v_i to each occurrence of i in the game map. This is used to initialize the state representation 𝒮 such that we are using a common embedding to refer to entities in both 𝒦 and 𝒮. 











  
Pooling. The reverse of , this operation is used to update the entity representations in the knowledge graph. In :𝒮→𝒦, we update the graph's representation v by averaging the features in 𝒮 over all instances of entity corresponding to v in the state.










  
KG-Conv. To update the state representation 𝒮, we augment a regular convolution layer with the knowledge graph. In addition to applying convolutional filters to the neighborhood of a location, we also add the node representation v_i of the entity i at that location, passed through linear layer to v_i to match the number of filters in the convolution. Formally, we can describe this operation as:


    Conv_3× 3 × d(𝒮) + Conv_1× 1 × d(𝙱𝚛𝚘𝚊𝚍𝚌𝚊𝚜𝚝(𝒦))


This provides a skip connection allowing deeper layers in the network to more easily make use of the global representations.



§ EXPERIMENTS



Previous environments measured generalization to more difficult levels <cit.>, modified environment dynamics <cit.>, or different solution paths <cit.>. These environments, however, do not introduce new objects at test time. To quantify the generalization ability of PKGNet to unseen objects, we needed a symbolic game with the ability to increment the difficulty in terms of the number of new objects and relationships. Therefore, we use a variation of the Sokoban environment, where the agent pushed balls into the corresponding bucket, and new ball and bucket objects and their pairing are provided at test time. We also benchmarked our model and the baseline algorithms on Pacman, after extracting a symbolic representation <cit.>.



 §.§ Sokoban


A variant of the Sokoban environment is implemented using the pycolab framework <cit.>. The set of rewarded ball-bucket pairs varies, and in the test games the agent sees balls or buckets not seen during training. For the variations, see Table <ref>. We increasingly vary the difficulty of the environment by the number of ball-bucket pairs, the complexity of the grouping, and the number of unseen objects. The buckets-repeat is a challenging environment, with complex relationships in the test environment.












 §.§ Pacman

We test the agents on the smallGrid, mediumClassic, and capsuleClassic environments from Pacman. The environments differed in the size of the map as well as the numbers of ghosts, coins, and capsules present. The agent experienced +10 points for eating a coin, +200 for eating a ghost, +500 for finishing the coins, -500 for being eaten, and -1 for each move.



 §.§ Knowledge graph construction

For both environments, we add all entities to the knowledge graph with the exception of blank spaces. We then add edges between objects to reflect relationships present in the game structure. Each entity or edge type is assigned a unique one-hot vector; note however that edges between two pairs of entities may have the same edge type if they are connected with a similar relationship. While we attach semantic meaning to these edge categories, their utility is grounded by the model during training. Additional details are in the supplement.


















§ RESULTS


Our network can be used in conjunction with a variety of RL algorithms. Here we tested PKG-DQN, PKG-A2C, and PKG-PER against the regular convolutional baselines in the Sokoban and Pacman environments. In addition, we compared the performance of different knowledge graph architectures during training. We also demonstrated the ability to manipulate agent behavior by changing the knowledge graph at test time.





 §.§ Sokoban

In the Sokoban environment, the PKG-DQN model was more sample efficient during training than the baseline Conv-DQN algorithm, as shown in Figure <ref>. For example, in the one-one environment, our model required approximately 8x fewer samples to reach the solution in the training environment. In addition, in more complex environments with an increased number of possible objects and ball-bucket pairings, the baseline Conv-DQN required increasingly more samples to solve, whereas the PKG-DQN solved in the same number of samples. 

We tested zero-shot transfer learning by placing the trained agents in environments with objects unseen during training. The PKG-DQN is able to leverage the knowledge graph to generalize, solving in > 80% of the test environments (see Figure <ref>, bottom row). The baseline DQN failed completely to generalize to these environments.

When we deleted the edges from the PKG-DQN (Figure <ref>, orange lines), the model trained slower and failed to generalize. The No Edge condition still trained faster than the baseline Conv-DQN, possibly due to additional parameters in the , however, that advantage is minimal in our most complex Sokoban environment, the buckets-repeat. We also tested baselines with significantly more parameters and different learning rates without improvement.

These observations held across all baselines tested (DQN, DQN - Prioritized Replay, and A2C), as shown in Figure <ref>. The relative performance of the Conv baselines is consistent with previous results (for e.g. Ms. Pacman in Table S3 in <cit.>). We also ran an ablation study where we removed the side branch from Figure <ref> (blue dotted rectangle), which significantly impacted sample efficiency and generalization (Figure <ref>). This demonstrates that the structured reasoning, enabled by the bi-directional flow of information from our novel layers, is important for performance.




 §.§ Knowledge graph types


In order to determine whether the results in Figure <ref> are sensitive to the choice of the knowledge graph architecture, we trained the PKG-DQN model with variants of the base knowledge graph, as shown in Figure <ref>: `Base' (graph cropped to entities present in the scene), graphs with same (`Same Edges') or no (`No Edges') edges, a fully connected graph either the same edge label (`Fully Connected') or distinct edge labels (`Fully Connected - Distinct'), and a `Complete' graph with no cropping based on presence in the scene.

When we removed the edge distinctiveness (`Same Edges'), the model still trained, but failed to generalize to novel objects. If we removed edges entirely (`No Edges'), the performance is the same as the baseline DQN. These results show that encoding the game structure into the knowledge graph is important for generalizing to the test environment but not necessary for the training environments.

Surprisingly, when the knowledge graph is fully connected (`FC' and `FC-distinct'), the model does not train, suggesting that the prior structure cannot be learned by PKG-DQN. If the complete graph is available during training, including nodes for objects that only appear in the test environments, the model generalizes to near-optimal performance (see orange lines in `Complete'). In this condition, even though the object `c' is not in the training environment, gradients still flow through the Ac edge. To avoid any contamination during training into the knowledge graph of information about ball-bucket object pairs seen during test, for the base condition we crop the knowledge graph only to entities (and corresponding edges) seen in the training environments.




 §.§ Pacman

The PKG-DQN converges significantly faster to a performing control policy than the convolution-based DQN on all three Pacman environments (Figure <ref>). Both models reach similar levels of final performance on smaller environments, which is expected, as the convolutional model should eventually be able to deduce the relations between the symbols with enough training.





 §.§ What do the agents learn?




To understand how the agents are interpreting the edge relations between objects, we observed the behavior of a trained agent running in an environment while manipulating the knowledge graph (Figure <ref>). For simplicity consider the one-one environment, with one bucket pair (bB) during training and one pair (cB) during testing. When we removed bB, the agent still pushes the ball, but does not know where to push the ball towards, suggesting that the agent has learned to ground the feature e_bB=2 as 'goal' or 'fills'. We swapped the edge features of AB and Ab, and the agent attempts to push the bucket into the ball. The knowledge graph could also be manipulated such the agent pushes a ball into another ball (Supplement). These studies show that the agent learned the 'push' and 'fills' relation and can apply these actions to objects it has never pushed before.

Similarly, in Pacman, if we remove the PlayerScared Ghost edge, the agent no longer chases the scared ghosts (Table <ref>). Without an edge to the capsule, the agent no longer eats the capsule. The agent can also be manipulated to not avoid ghosts by changing the GhostPlayer feature to the PlayerCoin edge relation.









§ DISCUSSION



We've demonstrated the efficacy of a general approach to augmenting networks with knowledge graphs that facilitate faster learning, and more critically enable algorithms to apply their learned relations to novel objects. This was substantiated with experiments across two environments and multiple algorithms. Ablation studies highlight the importance of bi-directional information exchange between the state features and knowledge graph, in contrast to previous work with one-directional feature concatenation <cit.>. Moreover, the use of edge-conditioned convolution allows the agent to ground and leverage edge relations, as well as generalize to changing knowledge graphs. Previous approaches <cit.> are most similar to our `Same Edges` case (Figure <ref>), which was significantly worse performing.




Our approach is complementary to other approaches in RL that strive to improve sample efficiency and generalization such as hierarchical RL <cit.>, metalearning <cit.>, or better exploration policies <cit.> and can be combined as such with these approaches to build better overall systems. Interestingly, attempts to learn the knowledge graph during training were not successful (see 'fully connected' in Figure <ref>), and we speculate that graph attention models <cit.> could help prune the graph to only the useful relations. We used simple one-hot edge features throughout, whereas one could use word embeddings <cit.> to seed the knowledge graph with semantic information.

The field has long debated the importance of reasoning with symbols and its compatibility with gradient based learning. Our architecture provides one framework to bridge these seemingly disparate approaches <cit.>.




unsrt






