Title: RECOGNIZING PLANS BY LEARNING EMBEDDINGS FROM OBSERVED ACTION DISTRIBUTIONS HANDLING UNCERTAINTY IN VISUAL PERCEPTION FOR PLAN RECOGNITION Anonymous authors Paper under double-blind review

Abstract: Plan recognition aims to look for target plans to best explain the observed actions based on plan libraries and/or domain models. Despite the success of previous approaches on plan recognition, they mostly rely on correct action observations. Recent advances in visual activity recognition have the potential of enabling applications such as automated video surveillance. Effective approaches for such problems would require the ability to recognize the plans of agents from video information. Traditional plan recognition algorithms rely on access to detailed planning domain models. One recent promising direction involves learning approximate (or shallow) domain models directly from the observed activity sequences. Such plan recognition approaches expect observed action sequences as inputs. However, visual inference results are often noisy and uncertain, typically represented as a distribution over possible actions. In this work, we develop a visual plan recognition framework that recognizes plans with an approximate domain model learned from uncertain visual data.

1. INTRODUCTION:

Plan recognition aims to look for target plans to best explain the observed actions based on plan libraries (Kautz and Allen (1986) ) and/or domain models (Ramírez and Geffner (2009) ; Zhuo, Yang, and Kambhampati (2012) ). Despite the success of previous approaches proposed to handle plan recognition problems, they generally rely on the assumption that the observed actions are correct and try to discover missing actions (c.f. Tian, Zhuo, and Kambhampati (2016) ). Even though there have been previous works on noisy observations, they only consider the case that the observed actions (c.f. Zhuo and Kambhampati (2013) ) or states (c.f. Mourão et al. (2012) ) have a probability to be incorrect, instead of considering full distribution of actions (or states). In many real-world applications, such as video surveillance ( c.f. Collins et al. (2000) ), a full distribution of actions, which can be directly estimated by off-the-shelf approaches (e.g., Zhong, Shi, and Visontai (2004) ), is however available and can be explored to help recognize plans.

Consider the example in Figure 1 , where a surveillance system attempts to recognize plans from captured video clips of salad-making activities. In the first two frames, the activity recognition module may generate a distribution over three activities, and determine that the human grasps a pestle with the highest confidence (probability), a cucumber and a pen with lower confidences. In such a case there is a perceptual error (PE), assuming the ground-truth activity of picking up a cucumber. If the plan recognition module only takes the most likely activity (i.e. grasping a pestle), only erroneous information is used by the plan recognition module, leading to a poor performance. Hence the plan recognition module should consider the information of less likely activities as well.

In this work, we consider the problem of recognizing plans from videos, namely visual plan recognition, based on the distribution of actions at each step of the underlying plan to be discovered. Visual plan recognition is challenging due to the complex affinities of candidate actions among multiple steps of the underlying plan based on distributions of actions. In this paper we propose to learn action embeddings to capture affinities according to the distributions of actions, and then exploit the action embeddings to recognize plans. Specifically, to learn action embeddings from distributions of actions, we propose three candidate approaches. The first one is to greedily take the most probable action from each distribution, namely B ). The number '18', '24', and '36' means the 18-th, 24-th, and 36-th action in action vocabulary Ā (explained in Section 3) GM (Greedy Model). GM may suffer from noisy observations because of greedy sampling. The second, in order to use more information from uncertain observations, is to sample action sequences from each sequence of action distributions, and then build a Word2Vec model, namely RS2Vec ( Resampling-to-Vector Model). RS2Vec can be quite inefficient in that it will have to generate many samples to capture the distribution. The required sample size increases with the length of the sequence and the number of actions in the distribution of each step. We thus propose the third way, which is to directly handle distributions of actions, namely Distr2Vec (Distribution-to-Vector model). Distr2Vec requires a revision to the Word2Vec to let it learn embeddings for distributions over words as opposed to single words. To train the Distr2Vec affinity model, we introduce a loss function based on combining Kullback-Leibler (KL) divergence and (Hierarchical-Softmax) H-Softmax Mikolov et al. (2013) .

The framework, namely VPR (visual plan recognition), is shown in Figure 1 . A pretrained action recognition module converts a sequence of video clips from a camera, to a sequence of observed action distributions (i.e., observed plans). Then we could do plan recognition by using one of the three affinity models, GM, RS2Vec, or Distr2Vec. Those affinity models serve as approximated planning domain models and generate affinity scores for plan recognition. An affinity score represents how likely an action is going to happen given observed actions.

To the best of our knowledge, we are the first to learn approximated domain (action affinities) models from sequences of action distributions that are gathered from an activity recognition model trained on real-world videos. Further, the potential of Distr2Vec and RS2Vec is not restricted to visual plan recognition. They may also be useful in any categorical data sequence learning scenario where there is uncertainty at each step of the input data such as in speech recognition.

2. RELATED WORK:

In the planning literature, there has been a long history of leveraging models for plan recognition but without considering connections to low-level perception. In Sohrabi, Riabov, and Udrea (2016) and Ramírez and Geffner (2009) , solving a plan recognition problem is transformed to solving a planning problem. These two plan recognition works assume that a planning domain model is given, whose description strictly follows certain rules or syntaxes, like those in PDDL McDermott et al. (1998) . Recently an interesting direction that has emerged, is to learn an approximated planning model. These models could be flexibly represented in various formats, to do plan recognition, as in Tian, Zhuo, and Kambhampati (2016) , which exploits Word2Vec to learn approximated planning models from plan corpora. In contrast to these works, our VPR can handle uncertain information in action recognition from a visual processing model. Our work is also different from existing works of probabilistic plan recognition ( Bui (2003) ; Ramírez and Geffner (2010) ; Geib and Goldman (2009) ). These works require a predefined set of rules or a domain model, which is instead approximately learned from plan traces in our VPR.

Another relevant body of research is intention recognition from visual observations (Xie et al. (2018b) ; Kitani et al. (2012) ; Holtzen et al. (2016) ). The intention recognition modules in these works remove observation uncertainty by taking only the most likely observed (or demonstrated) trajectories and object states from a tracking module in a similar sense of our GM. They will therefore lose the information in the distribution-style observation sequences. Our work may be used to Observation: augment these and similar visual intention recognition works because our approach preserves the information from the uncertainty in the data.

[ 𝑎𝑑𝑑-𝑝𝑒𝑝𝑝𝑒𝑟-𝑝𝑟𝑒𝑝 0.7 𝑎𝑑𝑑-𝑐𝑢𝑐𝑢𝑚𝑏𝑒𝑟-𝑝𝑟𝑒𝑝 0.2 𝑎𝑑𝑑-𝑠𝑎𝑙𝑡-𝑝𝑟𝑒𝑝 0.1 ] 𝟇 𝟇 [ 𝑎𝑑𝑑-𝑣𝑖𝑛𝑒𝑔𝑎𝑟-𝑐𝑜𝑟𝑒 0.6 𝑎𝑑𝑑-𝑜𝑖𝑙-𝑐𝑜𝑟𝑒 0.3 𝑎𝑑𝑑-𝑤𝑎𝑡𝑒𝑟-𝑐𝑜𝑟𝑒 0.1 ] [ 𝑎𝑑𝑑-𝑠𝑎𝑙𝑡-𝑝𝑟𝑒𝑝 0.5 𝑎𝑑𝑑-𝑣𝑖𝑛𝑒𝑔𝑎𝑟-𝑝𝑟𝑒𝑝 0.3 𝑎𝑑𝑑-𝑜𝑖𝑙-𝑝𝑟𝑒𝑝 0.2 ] Completed Plan: [ 𝑎𝑑𝑑-𝑝𝑒𝑝𝑝𝑒𝑟-𝑝𝑟𝑒𝑝 0.7 𝑎𝑑𝑑-𝑐𝑢𝑐𝑢𝑚𝑏𝑒𝑟-𝑝𝑟𝑒𝑝 0.2 𝑎𝑑𝑑-𝑠𝑎𝑙𝑡-𝑝𝑟𝑒𝑝 0.1 ] 𝑎𝑑𝑑-𝑝𝑒𝑝𝑝𝑒𝑟-𝑐𝑜𝑟𝑒 𝑎𝑑𝑑-𝑣𝑖𝑛𝑒𝑔𝑎𝑟-𝑝𝑟𝑒𝑝 [ 𝑎𝑑𝑑-𝑣𝑖𝑛𝑒𝑔𝑎𝑟-𝑐𝑜𝑟𝑒 0.6 𝑎𝑑𝑑-𝑜𝑖𝑙-𝑐𝑜𝑟𝑒 0.3 𝑎𝑑𝑑-𝑤𝑎𝑡𝑒𝑟-𝑐𝑜𝑟𝑒 0.1 ] [ 𝑎𝑑𝑑-𝑠𝑎𝑙𝑡-𝑝𝑟𝑒𝑝 0.5 𝑎𝑑𝑑-𝑣𝑖𝑛𝑒𝑔𝑎𝑟-𝑝𝑟𝑒𝑝 0.3 𝑎𝑑𝑑-𝑜𝑖𝑙-𝑝𝑟𝑒𝑝 0.2 ]

Using sensor data as input, Hodges and Pollack designed machine learning-based systems Hodges and Pollack (2007) for identifying individuals as they perform routine daily activities such as making coffee. 

3. VISUAL PLAN RECOGNITION:

Definition 1. (Action Space) We define the action space as A = Ā ∪ φ. The action set A consists of all possible grounded action symbols (in action vocabulary Ā), and a symbol φ which denotes a step with missing observation (action distribution).

Definition 2. (Action Distribution) An observed action distribution of size K at time step t is denoted as Distr(a t ) which equals to (a 1 t , c 1 t ), (a 2 t , c 2 t ), ..., (a K t , c K t ) . Note that each action a has a corresponding confidence value c. c is a probability given by a visual recognition module, and

K k c k = 1. Definition 3. (Uncertain Plan)

We use p to define an observed plan with uncertainty, and T to denote its length or number of steps. A plan p with T steps would be a sequence of T action distributions, defined as the matrix below.

Actions          Time ---------------------------------→       a 1 1 , c 1 T . . . . . . . . . . . . • • • a K 1 , c K 1 a K 2 , c K 2 a K 3 , c K 3 • • • a K T , c K T       Definition 4. (Visual Plan Recognition)

The visual plan recognition problem is defined as R = (L, O, A). L is a library of uncertain plan traces p (Figure 2 ). A denotes the action space as explained. O is an observed plan captured by running visual activity recognition modules on video 3 ). To recognize a plan we need to search for proper actions to fill them in those steps. The searching requires using action affinity models, whose training will be explained later. Action affinity model works as a subroutine in VPR. The solution R, as illustrated in Figure 4 , could be either a completed plan with all missing actions filled in (plan completion), or a plan that includes future actions of an agent (plan recognition). Note that plan completion is a more general version of plan recognition problem such that missing observation can be at any step in a plan. For plan recognition, missing observations are only at the end of a plan. In some earlier plan recognition works Ramírez and Geffner (2009) ; Zhuo, Yang, and Kambhampati (2012) they did solve plan completion problems as well, as pointed out by Tian, Zhuo, and Kambhampati (2016) . Similar to their works, we also mean to solve the more general problem of plan completion and assume that the missing observations can be at any plan step.

3.1. FORMULATION OF LEARNING ACTION AFFINITY MODELS:

We can now formulate the learning of action affinity model, as maximizing the mean of log probability of distributions over the steps of plans in L:

EQUATION

where W denotes the window size. Distr(a t ) denotes the input observation distribution (input) at the current step. Distr(a t+j ) denotes the target observation distribution (target, which is the expected output) at step t+j, which provides training signals. P r(Distr(a t+j )|Distr(a t )) represents the similarity between Distr(a t+j ) and Distr(a t ), computed by an affinity model.

Also, when using a Distr(a t ), the affinity model encodes Distr(a t ) into a vector enc(Distr(a t )) = u 1 , ..., u Ā. The size of Ā equals to the number of nodes in input layer. Distr(a t ) is encoded into a vector by having a unique index i associated to each action in Ā. The value u i at each index i in the input vector, is the confidence value associated to the matching action in Distr(a t ). The rest of the units in input layer, whose corresponding actions are not in Distr(a t ), have zero probability values.

3.2. RECOGNIZING PLANS WITH A LEARNED AFFINITY MODEL:

For an observed plan O (Definition 4.), if there are totally M steps or observations (o 1 , ..., o M ), the length of O is M . If there are x steps in O with missing observed action distributions, there are x φ symbols in O (Definition 1.). To recognize the plan O we try different actions within Ā to fill in each of the x steps, and select the actions that maximize overall affinities. Note that x is a variable that may vary plan by plan.

For example, consider when x = 1 that there is only one missing observation (at step j) in the observed plan O. All observations at other steps are known (action distributions). To determine the action for a step of missing observation, we calculate Ā × 2W pairwise affinities for all possible actions that could complete O. W is the context window size (a hyperparameter) assumed to be set to one in this example. Each candidate plan completion is denoted as p. p is also a M -step plan but with symbols φ replaced by actions in Ā. To score p with one filled-in action in our example, we need to compute the pairwise affinities between all possible actions in Ā, and an observed action distribution within -W ≤ j ≤ W. The selected action would have the highest pairwise affinity to observations in the window. As a result, because the plan only has one step with missing observation, the selected action completes the p and we obtain a recognized plan. for steps in -W ≤ i ≤ W do 3:

if any step j has the value φ then 4:

for each action a from Ā do end for 11: end for 12: Select actions with maximum affinity values to form p 13: return p the weights in this layer are not trainable. This way, we are able to do summarization over all pixel regions, and across all SPMs, which is identical to Equation 3.

EQUATION

)

where Z is a normalization number, and we set it to one in our experiments. In h l=5 , there are M × K SPMs, because there are M plans of length K, and each AMP leads to a SPM. Each SPM has N × N values. Generating a PRDA map requires calculating statistics over all of them. In addition, here c denotes the c-th channel or SPM in h l=5 , t denotes the current time step, and each pixel location in a PRDA map is identified by i and j.

3.5.. Joint Event Recognition and Frame Prediction with PDN:

Because of the difficulty of collecting ground-truth attention maps, neural network based attention models are usually put in a larger model for specific tasks like action recognition [5] . In order to train our PDN, we design a system, ER-PDN, that takes the advantage of PDN to jointly recognize events and predict the next video frame. Thus, the training signal comes from ground-truth event labels, and the next-step input frame. 

4.. Deeper Analysis of PDN:



4.1.. Connection to Belief Upd Models:

We start from providing the bel the observation model, in partially cision process (POMDP) framewo model could handle observation u the evolution of states. POMDP fr uncertainty, and treats actions as (the essential difference to belief u tion models, e.g., HMMs). The b POMDP is described in Equation 45

The score of a plan completion p, denoted as F( p), is calculated using the sum of log probabilities P r(target|input) (measuring a pairwise affinity) over all M steps:

F( p) = M t=1 -W≤j≤W,j =0 log P r(target|input) (2)

where both input and target are encodings of either a single action (a one-hot vector), enumerated from the action vocabulary, that could be put in a step with missing observation, or an observed action distribution (e.g., enc(Distr(a t ))) in the window W. Note that target action or action distribution is the expected output. Each p (has length M ) is a candidate plan completion, in which x actions would be filled in the x steps with missing observations in an observed plan O (Definition 4.). j is the index inside context window W. The plan completion for p that has the highest score, is treated as the solution R for visual plan recognition. The general procedure is described in Algorithm. 1.

4. ACTION AFFINITY MODELS:

In this section, we formally introduce our action affinity models, Distr2Vec and RS2Vec, that could be used in VPR framework for visual plan recognition. We train Distr2Vec by minimizing the KL-divergence between the target distribution Distr(a t+j ), and the predicted output distribution Distr(a t+j ). KL-divergence is an often-used measure of the distance between two distributions. So, if we use it as the loss function we can keep the input data as is (no resampling). Using KL-divergence as the loss function, Distr2Vec is trained by minimizing:

EQUATION

where D KL represents the KL divergence. enc(Distr(a t )) are defined in Section. 3. KL-divergence D KL is calculated in Equation 4.

KL(p||q) K k=1 p k log p k q k = K k=1 p k log p k - K k=1 p k log q k (4)

where q is the output probability distribution of our Distr2Vec model. q is also an approximation of p, the target distribution Distr(a t+j ) in the plan trace. Equation 4 allows us to avoid computing the derivative of the entropy of p when taking partial derivative of KL(p||q) with respect to model parameters. This is because the probability values for p (which is Distr(a t+j )), are constants with respect to the model parameters. Using this information, we can obtain Equation 5.

EQUATION

where Z(Distr(a t+j )) = K k=1 c k t+j log(c k t+j ) is a constant, and h(Distr(a t )) is the embedding computed by multiplying the embedding matrix W E and the action-distribution input vector enc(Distr(a t )) = u 1 , u 2 , ..., u Ā = 0...0, c1 t , 0, ..., 0, c 2 t , 0, ...0, c K t , 0... encoded from Distr(a t ), as done in Equation 6. u, Ā,c t , and K are defined in Section. 3.

EQUATION

4.2 COMBINING WITH HIERARCHICAL SOFT-MAX We adopted the H-Softmax introduced in Mikolov et al. ( 2013), which has been shown to have advantages over the non-hierarchical counterpart in both the accuracy, and computational efficiency 1 . H-Softmax decomposes the logits computation of each word to computing a sequence of nodes (logit values) in a tree data structure.

If we combine Equation 5 with H-Softmax, with distribution input Distr(a t ), we obtain the probability of an action a k t+j in the target observed action distribution Distr(a t+j ):

P r(a k t+j |h(Distr(a t ))) = L(a k t+j )-1 i=1 σ(I(n(a k t+j , i + 1) (7) = child(n(a k t+j , i))) • v n(a k t+j ,i) • h(Distr(a t )

)) where I(x) is an identity function. L(a k t+j ) is the length of path from root to the leaf node, i.e., an action, in a H-Softmax tree. v n(a k t+j ,i) is the weights vector of ith node along the path in the tree, and h is the embedding computed using Equation 6. We encourage readers to read a brief review of the Word2Vec and H-Softmax in the Section D of appendix, to understand Equation 7 better.

And if we substitute Equation 7 into Equation 5, we obtain the error function in Equation 8. This is the error function as we are trying to minimize the KL divergence of Equation 5.

EQUATION

Note that we also use Equation 8to calculate the logarithmic posterior probability of obtaining target encoding given input encoding, log P r(target|input), as in Equation 2. Readers should refer to the Section E in appendix for detailed derivation of gradient descent for Equation 8.

4.3. RESAMPLING-TO-VECTOR (RS2VEC):

In RS2Vec, we first perform a beam search sampling on each uncertain plan p from library L, to obtain a set of deterministic samples (plans). Each sample includes a sequence of actions, and a probability value calculated by multiplying the confidence values of all actions along a sequence. This probability value could be used to represent the overall uncertainty or score of a sampled plan. After doing beam search sampling in which the beam size is set to S, the top S samples (action sequences) with their scores are selected. We then resample them by using the roulette wheel resampling approach of Lipowski and Lipowska (2012) , which lets us drop some samples that have low scores, and increase the amount of samples with high scores. After doing resampling we use the action sequences in all stored samples after performing beam search, to train a Word2Vec model as an action affinity model for plan recognition.

That said, the potential problem for RS2Vec are the following. First, the resampling would make the algorithm more computationally expensive, and the training time would be closely related to the number of samples and length of the training data. This makes it hard to apply RS2Vec to a real-time plan recognition system. Secondly, the resampling approach could lose some information, whereas Distr2Vec directly uses the entire distribution sequence.

5. EVALUATION:

We evaluate Distr2Vec and RS2Vec in VPR by observing training time and the plan recognition performance of VPR. VPR takes Distr2Vec, RS2Vec, and the baseline model GM. In GM, we take sequences of most likely actions from distributions across each plan to build a plan corpus. With the corpus we train an action affinity (Word2Vec) model. This is as opposed to the RS2Vec model which takes more samples per sequence for training. We ran our experiments on a machine with a Quad-Core CPU (Intel Xeon 3.4GHz), a 64GB RAM, a GeForce GTX 1080 GPU, and Ubuntu 16.04 OS.

5.1. DATASET COLLECTION AND EXPERIMENT DESIGN:

We collected two plan corpora based on processing the 50 Salads Dataset Stein and McKenna (2013) . One is from real world videos (visually grounded corpus), for evaluating the real world value of our model in connecting high-level plan recognition and low-level perception. The other corpus is a controlled synthetic plan corpus. In order to fully assess the validity and effectiveness of our approaches, we need to test with different types of distributions in input data. Thus we generated synthetic plans (distribution sequences), as they would allow us to maximally evaluate the approach by testing the effects of various factors. We evaluate the effect of factors like distribution entropies, perception error rates (PER), and the length of observation sequences. Note that we simulate the perceptual error (PE) in an action distribution by exchanging the highest confidence action with another action in that distribution. A specified PER is achieved by simulating PE in a proportion of the action distributions in each plan trace. For experiments on synthetic data we evaluate affinity models with H-Softmax. We also explore the performance difference from using their counterparts without H-Softmax in terms of training time and accuracy in Section 5.3. We set the size of window W to one, embedding size to 100 and train each model for 60 epochs. For each position of missing observation, we ask models to predict top-three actions in all experiments except for Figure . 8. The prediction is counted as correct if at least one of the three is correct. We denote the number of candidate predictions as top-k-prediction. For details of dataset collection and experiment settings, readers should refer to section B and C in the appendix.

We evaluate different approximated domain models (Distr2Vec, RS2Vec, and GM) as used in VPR using 6-fold cross validation. For each test, we randomly remove some distributions at some steps. Then we compare the performance by the average accuracy. We define the accuracy following the work Tian, Zhuo, and Kambhampati (2016), using Equation 9.

acc = 1 Z Z i=1 # CorrectRecognition i x i (9)

Where Z is the total number of plan traces in testing set, and x i is the number of steps with missing actions for the plan i. # CorrectRecognition i is the number of correct predicted actions in i-th uncertain plan in testing set. three RS2Vec instances trained on three levels of samples (small, medium, and large). We set the sample numbers of small, medium, and large levels to 3, 9, and 27 respectively. In the rightmost sub-plot, we show a comparison of training time required by GM, Distr2Vec, and RS2Vec with respect to increasing number of samples that an RS2Vec instance takes, when sequence length is 20. We did training time experiments for length 10, 20, and 30 of sequences, but because the three training time results are very similar to each other, we only report the length 20 results. We observe that the training time of RS2Vec increases linearly with the number of samples per plan. This is easily explained by the fact that increasing the number of samples, is increasing the training cost. In contrast, the training time for Distr2Vec and GM stay constant as there is no sampling step.

5.2. EXPERIMENTS AND ANALYSIS ON SYNTHETIC PLANS:

For accuracy performances under all PER settings, Distr2Vec generally gets better performances for longer training sequences. As the length of plan increases, RS2Vec requires more samples from the distribution sequence to match or outperform the Distr2Vec (this is more obvious when PER is high). For RS2Vec, increasing the number of samples could be beneficial when PER is higher. Higher PER means more observed action distributions in a plan would have lower probabilities for correct actions (assuming each distribution must have one action that matches the ground-truth). Thus, taking more samples would give RS2Vec more accesses to correct information. We can observe clearly in sub-plots of 100% and 75% PER, that RS2Vec could get better performance by training on more samples. As for the GM model, its accuracy for 100% PER across all lengths is 0%. This matches our expectation sicne the training data for the GM model does not have the ground-truth action in any step for 100% PER. Therefore, the GM would not capture any relevant information. For lower PER cases the GM performance is higher. This matches our expectations since the GM gets more of the correct information from highest-probability sampling of low PER plans.

As for data with high and low entropies, the experimental results are shown in Figure . 7. We set PER to zero, and sample numbers of RS2Vec-S, RS2Vec-M, and RS2Vec-L, to 7, 11, and 15 respectively. Then the actions which match ground-truth ones are most probable ones in all distributions. As expected, GM performs the best when entropy of distributions in training distribution sequences (plan corpus) is high, since it gets the correct plan when PER is zero. The performance of Distr2Vec is expectedly lower than GM, yet it gets appreciably bet-ter than RS2Vec. In low entropy cases all models perform comparably well.

We also evaluated Algorithm 1 in VPR (Section 3.2) by comparing it with the Long-shot Term Memory networks (LSTM) approach Graves (2013). Our LSTM based approach is essentially a generative model, implemented based on2 . It first learns action representations based on Distr2Vec and then uses the learnt representations to train the LSTM for predicting an action. Different from Algorithm 1, LSTM can do plan recognition by approximating an optimal prediction, which may require a slower training time but do faster in testing (plan recognition) phase. We would like to investigate the differences in accuracy and running time between the two approaches. The accuracy result is shown in Figure . 8 and we used the synthetic data of 30% PER. The VPR with Algorithm. 1 and VPR with LSTM performs comparably well with top-k-prediction value increases. In addition, VPR with LSTM requires 29.5 Secs to train and 0.02 Secs to recognize one action in testing phase.

VPR with Algorithm 1 requires 8.0 Secs and 0.80 Secs respectively. Hence VPR with Algorithm 1 overall has a less running cost.

5.3. EXPERIMENTS AND ANALYSIS ON VISUALLY GROUNDED PLANS:

In Figure 9 , the left sub-plot shows how Distr2Vec, GM, and RS2Vec which takes 9 (as RS2Vec-S) and 27 (as RS2Vec-L) samples would perform, when PER is high (69%) and low (8%), meanwhile setting distribution size to 5. The right sub-plot shows how sizes of distributions per step influence the accuracy (setting RS2Vec to takes 15 samples). We observe that, when PER is high, VPR with Distr2Vec clearly performs the best, whereas when PER is low, all models perform comparably well. This is consistent to results of synthetic data evaluation. We also observe that, overall the distribution size is not a key factor for deciding model performance. The left two subplots in Figure 10 show that the H-Softmax in Distr2Vec slightly decreases the training time, and vice versa for GM. This is probably because our action space is small (52). H-Softmax is faster for corpora with larger vocabularies as the tree traversal way of updating weights will eventually take less time than updating the entire hidden-output matrix. The accuracy advantage of using H-Softmax is obvious for RS2Vec with more samples. The reason is RS2Vecnohs with more samples tends to sample more incorrect data. RS2Vec tends to be more robust to this noise.

From the right two subplots we observe that the optimal window size is one, and 50% of missing observations per plan is the lower bound for Distr2Vec to maintain its advantage over other models.

6. CONCLUSION AND FUTURE WORK:

Our work aims to make plan recognition more practically useful in scenarios with observational error in action recognition. We introduce our VPR framework that uses Distr2Vec and RS2Vec as action affinity models, to do visual plan recognition which may suffer from perceptual uncertainty. Distr2Vec and RS2Vec learn embeddings for distributions over actions to preserve the information from the visual recognition module. Our VPR framework can thus handle the uncertainty in visual data and perform plan recognition. We evaluated our models (Distr2Vec and RS2Vec) as well as a baseline GM model in the context of plan recognition in the VPR framework. We evaluated models with/without H-Softmax on plans in which action distributions are generated from realworld videos. We also evaluated the H-Softmax version of models on synthetic plans with different types of action distributions. We conclude that when there is a higher PER, VPR with Distr2Vec outperforms other models. When PER is lower, and sequence length is longer, all models perform comparably well. Another advantage of using Distr2Vec to handle distributions within the VPR framework is that the training time is shorter as compared to the RS2Vec model in which we have to sample more action sequences for comparable performance. For future work we would be interested in exploring other domains that provide uncertain observations, like speech recognition.

A APPENDIX B DATASET COLLECTION B.1 COLLECTION OF VISUALLY GROUNDED PLAN CORPUS

The procedure for making the visually grounded corpus is illustrated in Figure 1 . First, we converted all videos into video clips, and each clip matches a ground-truth action. Secondly, we applied a video processing model, Video2Vec Hu, Li, and Li (2016) , on those video clips, to output action distribution sequences. For each clip it outputs a distribution over all actions. We concatenate distribution sequences together for each video to make plan corpora that correspond to real-world videos. We trained two visual recognition models. The first is trained on 90% of video clips with 450 epochs.

The second one is trained on 70% of video clips with 100 epochs. With the two visual models trained by Video2Vec, we obtain two plan corpora. We found the PER for plan corpora collected by running the first visual model, is (8%), and the PER for plans collected by running the second visual model is 79%.

B.2 COLLECTION OF SYNTHETIC PLAN CORPUS:

We also augmented the ground-truth sequences in 50 Salads Dataset Stein and McKenna (2013) to create a synthetic plan corpus of action distribution sequences. There are totally 54 ground-truth, low-level action sequences, a * 1:T (T is sequence length). We synthesize a distribution per action step, by adding actions to each step and assigning a probability distribution over the actions. We add K -1 additional actions to each observation and assign a probability distribution such that the ground truth has the highest confidence (probability).

In order to generate the K -1 additional actions, we search for the K -1 most similar actions by using a Word2Vec model that is pretrained on Google News corpus3 . We use the semantic correlation of actions in this model, to simulate their visual correlation. As for assigning confidence values for each of the K -1 additional actions, we followed the Equation 10.

c(a k t ) = s k 1 + w entropy + K-1 i=1 s i (10)

where a k t is the k th additional action in a distribution at step t. We search for a k t in the Word2Vec model based on the ground truth action a * t . s k is the similarity between a * t , and a k t , which can be computed by using the pretrained Word2Vec of gensim library Reh u rek and Sojka (2010). These similarity values are used as in the Equation 10. The +1 in the denominator denotes the similarity between the ground-truth action and itself. We also use a parameter w entropy which we can use to increase or decrease probability differences between actions. Thus it could be used to adjust the entropy of each action distribution. We set up w entropy for the computation of each c(a k t ) to either zero or one, to slightly increase the variance of confidences at each step. The confidence for groundtruth action a * t is initially the highest and is equal to Equation 11.

EQUATION

where c(a k t ) is the confidence of one of the K -1 additional actions in the distribution at a step. Thus far, the synthetic data generated will have the ground truth as the action with the highest confidence. We would like to vary this, and simulate perception errors. We define a perception error (PE) as when the action a t that has the highest confidence in Distr(a t ) does not match the groundtruth action a * t . The perception error rate (PER) is the percentage of action distributions that have perception errors. We simulate the PE in a particular action distribution by exchanging the highest confident action with another action in that distribution. A specified PER is achieved by simulating PE in a proportion of the action distributions in each plan trace. The action distributions in which we simulate PE are randomly chosen. In this way, data of different distribution types is generated for testing the effectiveness of our model.

C EXPERIMENTS SETTINGS:

All of our experiments have the following hyperparameters (thus fair to all models): We set the window W to one, embedding size to 100 and train each model for 60 epochs. We considered other training epochs from 20 to 80, and decide to use 60 in our experiments. The number of missing actions is one in synthetic evaluation and 10% in video based evaluation, the number of recommendations for each missing action is three, and the number of threads when running the experiment is eight. Specifically, in accuracy evaluation on synthetic dataset, we evaluate the data under two categories: 1) Fixed entropy but varying PERs between (25%, 50%, 75%, and 100%); 2) Zero PER but test with both high entropy (all confidence values each time step are uniformly distributed) and low entropy. We set PER to zero in order to evaluate with only the influence of entropy. For low entropy, we set the confidence for a * t to 0.9, and the two simulated actions to 0.05. And on real world dataset (consists of whole distribution sequences with varying lengths), we also evaluate the data under two categories: 1) Fixed sequence length (30) but varying number of samples; 2) Fixed number of samples (15) but varying sizes of distributions.

We also look at the effect of the number of sampled paths on the training time, on the synthetic dataset. Please note that in results where the number of samples are varied, it only affects the RS2Vec model. The other models are unaffected by resampling and thus only have their average value plotted as a line.

D WORD2VEC AND HIERARCHICAL SOFTMAX:

In this section we make a brief review about how the Skip-gram Word2Vec works, based on Mikolov et al. (2013) , and how it could be used for plan recognition as introduced in Tian, Zhuo, and Kambhampati (2016) . To be consistent with the whole paper, we use the term "action" and treat it an equivalence to the term "word" in other papers which introduces Word2Vec.

Given a corpora which contains action (word) sequences, a Skip-gram model is trained by maximizing the average log probability:

EQUATION

)

where T is the length of a sequence, W is the context window size, a t is fed as the model input, a I , and a t+j is used as the target action (word), a O . The probability p(a O |a I ) is computed as:

EQUATION

which is essentially a softmax function. A denotes a vocabulary of all possible actions. Other symbols follows the definition in Equation 12. We can use this equation that computes p(a O |a I ) to compute p(a t+j |a t ) in Equation 12.

The p(a t+j |a t ) in the Word2Vec with hierarchical softmax is calculated in the following manner.

The output layer's weight matrix of the regular Word2Vec is replaced by a binary tree whose leaf nodes are words in the trained vocabulary. Every node on the path from the root node until the leaf node has a vector, excluding the leaf node. The input action a i is converted into an embedding h which is the input into the binary tree component. The probability of this input vector h that could go to a particular leaf node is calculated by following the path from the root node to the target leaf node, using the following formula: 

where I(x) is a function that returns 1 if the next node on the path to the target leaf node is on the left of the current node, and -1 if the next node is to the right. L(a t+j ) is the length of path from root to the leaf node a t+j , v n(at+j ,i) is the vector of the ith node along the path. h is the embedding obtained by multiplying the embedding matrix and vector of the input action a t . h is the vector that represents the input action in the embedding space. In order to maximize the probability, the vectors of the intermediary nodes are updated with each training sample which has the target action a t and an action in its context a t+j . We back-propagate the error E as shown in Figure 11 , where the dashed lines show the path of back-propagation. For this derivation, we shorten h(Distr(a t )) as h. We start by computing the derivative of E with respect to (v n(a k t+j ,i) * h) as in Equation 15. We also shorten our notation of v n(a k t+j ,i) as v k,i , which is the vector of i-th node in the tree path to the leaf node of the k-th action in the vocabulary as illustrated in Figure 11 . where t i = 1 if I(.) = 1 and t i = 0 if I(.) = -1. Recall that I(.) is the identity function defined in Equation 14.

E DERIVATION OF GRADIENT UPDATE EQUATIONS:

Then we calculate the derivative with respect to each v k,i along the path to a specific action, at the time step t + j:

EQUATION

With this, we update each v k,i as follows:

EQUATION

Note that each node's vector v k,i could get updated more than once, as each node could be on the path to more than one action as show in the right side of Figure 11 .

Then we compute the back-propagated error δ h by substituting Equation 15 as follows:

EQUATION

We can understand this equation by imagining that there are multiple channels coming back from each leaf node, passing thorough a sequence of child nodes in the hierarchical softmax tree, towards the output of the embedding matrix W E . So doing the back-propagation means summing errors of these channels together, and that is why v k,i could get updated more than once.

We derive the Equation 18 leveraging Equation 15. However, we could also go directly from the original error function (Equation 8). Thus here we provide another derivation of δ h which is equally valid: Finally, we update the weights in the embedding matrix W E :

EQUATION

EQUATION

)

where v t a = c 1 t , c 2 t , ..., c K t is the confidence values from Distr(a t ), and ∂E ∂W E can be used to update the values in W E as follows:

EQUATION

:

The first version that tried to improve Word2Vec with H-Softmax inMorin and Bengio (2005), reports that the new model requires less training time, but also results in a degraded accuracy. However, the workMnih and Hinton (2009) introduces an approach to automatically grow a tree to organize words, for H-Softmax, which outperforms non-hierarchical Word2Vec. In the recent workMikolov et al. (2013), the advantage is confirmed and it selects the binary Huffman tree as the basic tree data structure.

https://github.com/pytorch/examples/tree/master/word language model

https://drive.google.com/file/d/0B7XkCwpI5KDYNlNUTTlSS21pQmM/edit

Figures and Tables:

Figure 1: This figure illustrates the framework of VPR, which does plan recognition on uncertain observations. Those uncertain observations come from a visual recognition model, Video2Vec, whose training is explained in the appendix (Section B). The number '18', '24', and '36' means the 18-th, 24-th, and 36-th action in action vocabulary Ā (explained in Section 3)

Figure 3: An observed plan O, that has two steps of missing observations (action distributions) marked with symbol φ.

Figure5: Our Distr2Vec for learning action embeddings (approximated planning domain models) directly from distribution sequences. The embedding matrix W E has the size of action vocabulary Ā times embedding size. The hidden-Output Matrix has the shape of embedding length times size of Ā, whose output is a vector of size Ā.

Figure 5 illustrates our Distr2Vec model, that takes a pair of action distribution encodings to update its embeddings. The pair of distributions are enumerated within the context window. Distr2Vec takes one as input and treats the other as the target. Each row in W E is the embedding of an action symbol.

Figure6shows accuracy results for synthetic plans of length 10, 20 and 30, with varying PER and fixed entropy, in the four sub-plots on the left. The RS2Vec-S, RS2Vec-M, and RS2Vec-L are

Figure 7: Accuracy results of GM, Distr2Vec, and three RS2Vec instances on synthetic data of different entropies. The RS2Vec-S, RS2Vec-M, and RS2Vec-L are explained in the description of Figure 6.

Figure 8: Algorithm. 1 and LSTM comparison in VPR framework for plan recognition.

Figure10: The left two subplots show a comparison between using H-Softmax or not with respect to training time and accuracy for affinity models on the visually grounded corpus of 8% PER. The suffix "-nohs" denotes models without H-Softmax. The right two subplots show accuracy with respect to the percentage of missing observations and window sizes on the visually grounded corpus of 69% PER.

p(a t+j |a t ) = L(at+j )-1 i=1 σ(I(n(a t+j , i + 1) = child(n(a t+j , i))) • v n(at+j ,i) • h) ,

Figure 11: Details of Distr2Vec model for Error Propagation.

.)v k,i h)(1σ(I(.)v k,i h)I(.) σ(I(.)v k,i h) = c k t+j (σ(I(.)v k,i h) -1)I(.) = c k t+j (σ(I(.)v k,i h) -1), (I(.) = 1) c k t+j (σ(I(.)v k,i h), (I(.) = -1)

log σ(I(.)v n(a k t+j ,i) •h) ∂h has already been derived as a part of Equation 15.

The overall framework is shown in Figure.4. The solid paths are differentiable, and dashed ones are not.At each step, a video frame X t , is filtered by bottomup attention model, to get a BUA map V BU

Table content: <table><tr><td>Training</td><td/><td colspan="2">PDN</td><td/><td/></tr><tr><td>R G B Mask Location</td><td>𝒗𝒗 𝒕𝒕 𝝁𝝁</td><td>PR PR 𝒑𝒑𝒕𝒕 𝟐𝟐 𝒑𝒑𝒕𝒕 𝟏𝟏</td><td>…</td><td>PR 𝒑𝒑 𝒕𝒕 𝑴𝑴𝒕𝒕</td><td>R G B Mask Location</td></tr><tr><td colspan="2">…</td><td/><td/><td/><td/></tr><tr><td>𝑨𝑨𝑷𝑷𝑷𝑷𝑨𝑨𝒕𝒕-𝟏𝟏</td><td/><td>𝒈𝒈𝒕𝒕 𝟏𝟏 𝒈𝒈𝒕𝒕 𝟐𝟐</td><td>…</td><td>𝒈𝒈 𝒕𝒕 𝑴𝑴𝒕𝒕</td><td>𝑨𝑨𝑷𝑷𝑷𝑷𝑨𝑨𝒕𝒕</td></tr><tr><td>Plan</td><td/><td/><td/><td/><td/></tr><tr><td>Recognition</td><td/><td colspan="2">Segmentation</td><td/><td/></tr><tr><td>Memory Working 𝑨𝑨𝑴𝑴𝑨𝑨𝟏𝟏:𝒕𝒕 𝒎𝒎</td><td/><td colspan="2">B R G and Masking 𝒗𝒗𝒕𝒕</td><td colspan="2">Intuitive Recognition</td></tr><tr><td>𝑨𝑨𝑴𝑴𝑨𝑨𝒕𝒕 𝒎𝒎</td><td/><td colspan="2">𝒗𝒗𝒕𝒕 𝑩𝑩𝑩𝑩</td><td>� 𝒆𝒆 𝑰𝑰</td><td>𝒕𝒕</td></tr><tr><td>AMP</td><td/><td/><td/><td/><td/></tr><tr><td>Extractor</td><td/><td colspan="2">Bottom-up</td><td/><td/></tr><tr><td/><td/><td colspan="2">Attention</td><td/><td/></tr><tr><td/><td/><td>𝒙𝒙𝒕𝒕</td><td/><td/><td/></tr><tr><td colspan="6">Figure 4. The event recognition system</td></tr><tr><td>work.</td><td/><td/><td/><td/><td/></tr><tr><td colspan="6">component then extracts M t glim nected highlighted areas in V t . Fo a minimal bounding box by using on the boundary of that glimpse. I bounding box to future K frames, w described in Section. 3.1 to extract fed into the plan recognition modu one or more predicted AMPs as a r</td></tr><tr><td colspan="6">The segmentation and masking c ditional channels as explained in S of M t recognized plans that is ind lighted region in V µ t . Consequently has a mask code m. The PDN takes the masked V µ t , to generate the PR Both event recognition (the main tion help train the model. For even helps in using the output P RDA t frame. Then a LSTM layer served module to generate an event index task, we have the state offset featu 1) used as frame-level motion repre current frame. It is like an action c tion task [16].</td></tr><tr><td>t then combined with a PRDA map from the previous step, to . The V BU t is get a highlighted frame V t . The segmentation and masking</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper addresses the problem of visual plan completion in the presence of noisy observations. The heart of the authors* approach is to learn embeddings of actions given distributions over actions (which correspond to steps in an uncertain plan), using various proposed *affinity models.* These affinity models are used to generate affinity scores (roughly, given a set of previous distributions over actions, how likely is each possible next action?). I think that the problem being studied is well-motivated by the authors, and I especially appreciated the introductory material on the importance of a system that reasons about distributions over actions, rather than simply assuming maximum likelihood ones. --Main Comments-- My main concern with the current version of the paper is the lack of clarity as to what is being done, and what (formally) the core contribution is. Even after reading through a couple of times, I only have a vague understanding of exactly what a *affinity model* is, mathematically. From what I gather, it seems an affinity model is a distribution P(Distr(a_{t+j}) | Distr(a_t))? How do the encodings *enc* factor into this definition? Is computing an encoding a necessary characteristic of any affinity model? Without these details, I am unable to understand precisely how the methods proposed in Section 4 (Distr2Vec and RS2Vec) fit into the problem formulation described in Section 3.1. I believe the text could be strongly improved with a clear mathematical definition of what an affinity model is, since this term is used so frequently, and a reframing of Section 4 around this definition. My other major concerns lie in the experimental results. The experiments as a whole are rather opaque (some sort of visualization would have been very nice to see; for instance, could you maybe show a plan completion found by your method in one of the domains you experimented in?) Looking at the results in Section 5.3, I found Figure 9 rather unconvincing. The authors state that when PER is high, Distr2Vec *clearly performs the best,* when in fact the improved accuracy is only around 5%. I fully appreciate that in some benchmarks, 5% can be a major improvement, but I am unable to place the experimental results provided in this paper in comparison to other state-of-the-art plan recognition methods; only a naive affinity-model-based baseline (GM) is compared against. On a similar note, Figure 10 seems to show little to no accuracy gains by using the proposed methods over GM, especially in light of the increase in training times. Finally, Figure 8 seems to suggest that LSTM and Algorithm 1 perform similarly. In the text, the authors state that *LSTM requires 29.5 Secs to train and 0.02 Secs to recognize one action in testing phase* while *Algorithm 1 requires 8.0 Secs and 0.80 Secs respectively* -- this, to me, indicates a tradeoff of faster training and slower inference vs. slower training and faster inference; it*s not quite clear that one should be preferred over the other, and in fact it probably depends on the application in general. Due to the issues of clarity as to what is being done, and the unclear experimental significance of the work, I cannot recommend acceptance at this time, but I look forward to hearing the authors* responses in the rebuttal phase. --Other Comments-- - Could you give some intuition on why anything useful should be learned when PER is 100%? My intuition would be that your proposed methods will not *rule out* the correct actions like GM does; is this correct? - The experimental results suggest that Distr2Vec performs mostly comparably to RS2Vec, while only requiring a tiny fraction of the training time. Is there any practical reason to ever prefer RS2Vec? - There are also other places where the exposition are unclear. For instance, in the Introduction, Distr2Vec is written to seem like an improvement over RS2Vec, but counter-intuitively, Distr2Vec is described before RS2Vec in Section 4. Making the story and relationship between the two consistent throughout the document would help improve the clarity. --Minor Points-- - Make colors in plots consistent, e.g. in Figure 6 the colors for RS2Vec and Distr2Vec are swapped in the rightmost plot compared to the other three. - The colors in Figure 10 (left) are too similar, I cannot tell the data apart.