Show Me More Details: Discovering Hierarchies of Procedures from Semi-structured Web Data (2022)

Abstract: Procedures are inherently hierarchical. To “make videos”, one may need to “purchase a camera”, which in turn may require one to “set a budget”. While such hierarchical knowledge is critical for reasoning about complex procedures, most existing work has treated procedures as shallow structures without modeling the parent-child relation. In this work, we attempt to construct an open-domain hierarchical knowledge-base (KB) of procedures based on wikiHow, a website containing more than 110k instructional articles, each documenting the steps to carry out a complex procedure. To this end, we develop a simple and efficient method that links steps (e.g., “purchase a camera”) in an article to other articles with similar goals (e.g., “how to choose a camera”), recursively constructing the KB. Our method significantly outperforms several strong baselines according to automatic evaluation, human judgment, and application to downstream tasks such as instructional video retrieval.

## introduction a procedure includes some steps needed to achieve a particular goal @xcite . procedures are inherently hierarchical: a high-level procedure is composed of many lower-level procedures. for example, a procedure with the goal make videos consists of steps like purchase a camera, set up lighting, edit the video, and so on, where each step itself is a procedure as well. such hierarchical relations between procedures are recursive: the lower-level procedures can be further decomposed into even more fine-grained steps: one may need to arrange the footage in order to edit the video. relatively little attention has been paid to hierarchical relations in complex procedures in the field of nlp. some work performed a shallow one-level decomposition and often required costly resources such as human expert task-specific annotation @xcite @xcite . more attention has been paid in fields adjacent to nlp. for example, @xcite and @xcite both create hierarchical structures in how-to documents by linking action phrases in one procedure to another procedure or by linking steps in howto articles to resources like dbpedia @xcite . this kind of linking is helpful for explaining complex steps to readers who do not have prior knowledge of the topic being explained. in this paper, we revisit this important but understudied task to develop a simple and effective algorithm (figure 1 ) to construct a hierarchical knowledge-base (kb) for over 110k complex procedures spanning a wide range of topics from wiki-how, a large-scale how-to website that has recently become a widely-used resource in nlp @xcite @xcite ). 2 from each wikihow article which represents a procedure, we follow @xcite and extract the title as the goal (e.g., g 1 in figure 1 ), and the paragraph headlines as steps (e.g., s 1 . . . s n ). next, we decompose the steps by linking them to articles with the same or a similar goal (e.g., s 1 to g 2 ). the steps of the linked article are treated as the finergrained steps (s i to s j ) of the linked step (s1). in this way, the procedural hierarchies go from shallow (b1) to deep (b4). to link steps and article goals, we employ a retrieve-then-rerank approach, a well-established paradigm in related tasks @xcite . our hierarchy discovery model ( §3) first independently encodes each step and goal in wikihow and searches the k nearest goals of similar meaning for each step (b2). then, it applies a dedicated joint encoder to calculate the similarity score between the step and each candidate goal, : make videos g 1 : purchase a camera s 1 : set up equipment s 2 :choose a camera g 2 : consider use case s j : set a budget s i … b1: input : record the video s 3 : practice editing your videos application 1 ( §4&5) enrich wikihow step-goal hyperlinks s: step collection purchase a camera set up equipment consider use case g: goal collection make videos choose a camera edit videos b2: candidate retrieval ( §3.1) b3: reranking ( §3.2) make videos purchase a camera set up equipment consider use case set a budget g n s j … … s i b4: output thus reranking the goals (b3). this pipeline can efficiently search over a large candidate pool while accurately measuring the similarity between steps and goals. with each step linked to an article goal, a hierarchical kb of procedures is thus constructed. we evaluate our kb both intrinsically and extrinsically. intrinsically, the discovered links can be directly used to complete missing step-goal hyperlinks in wikihow, which have been manually curated (b5). our proposed method outperforms strong baselines (e.g., @xcite ) according to both automatic and human evaluation, in terms of recall and usefulness respectively ( §4, §5). extrinsically, we consider the task of retrieving instructional videos given textual queries. we observe that queries that encode deeper hierarchies are better than those that do not ( §6). this provides evidence that our kb can bridge the high-level instructions and the low-level executions of procedures, which is important for applications such as robotic planning. ## problem formulation we represent a procedure as a tree where the root node n represents a goal and its children nodes ch(n) represent the steps of n. we formulate the hierarchy discovery task as identifying the steps among ch(n) that can themselves be a goal of some other finer-grained steps (sub-steps), which are inserted into the tree. while this formulation could potentially be used on any large collection of procedures, we specifically focus on wikihow. as shown in b1 of fig-ure 1, each article comprises a goal (g), and a series of steps (ch(g)). therefore, each article forms a procedure tree of depth one. we denote the collection of all goals and steps in wikihow as g and s respectively. our hierarchy discovery algorithm aims to link a step s @xmath0. it then treats ch(g) as ch(s i ). given that g and s i are both represented by textual descriptions, the discovery process can be framed as a paraphrase detection task. this discovery process can be applied recursively on the leaf nodes until the resulting leaf nodes reach the desired granularity, effectively growing a hierarchical procedure tree (b4 of figure 1 ). ## hierarchy discovery model for each of the 1.5 million steps in the wikihow corpus, we aim to select one goal that expresses the same procedure as the step from over 110k goals. we propose a simple and efficient method to deal with such a large search space through a two-stage process. first, we perform retrieval, encoding each step and goal separately in an unsupervised fashion and select the k most similar goals for each step s. this process is fast at the expense of accuracy. second, we perform reranking, jointly encoding a step with each of its candidate goals in a supervised fashion to allow for more expressive contextualized embeddings. this process is more accurate at the expense of speed, since calculating each similarity score requires a forward pass in the neural network. the goal with the highest similarity score is se-lected and the step is expanded accordingly, as in b4 of figure 1 . ## automatic step prediction evaluation to train our models and evaluate how well our hierarchy discovery model can link steps to goals, we leverage existing annotated step-goal links. ## manual step prediction evaluation the automatic evaluation strongly indicates the effectiveness of our proposed hierarchy discovery model. however, it is not comprehensive because the annotated hyperlinks are not exhaustive. we complement our evaluation with crowdsourced human judgments via amazon mechanical turk (mturk). each example of annotating is a tuple of a step, its original goal from wikihow, and the top-ranked goal predicted by one of our models. for each example, we ask three mturk workers to judge whether the steps in the article of the linked goal are exact, helpful, related, or unhelpful with regard to accomplishing the queried step. details about the task design, task requirements, worker pay, example sampling, etc. are in a. we select sp, deberta, and deberta with unlinkable prediction and λ = 0 (deberta-ul) for comparison. we attempt to answer the following questions. first, does the performance trend shown in automatic evaluation hold in human evaluation? second, can the unlinkable predictions help avoid providing users with misleading information @xcite ? for the purpose of the second question, we separate the examples into two groups. one contains linkable examples. namely, those whose top-1 prediction is not predicted as unlinkable by the deberta-ul model. ideally, the linked articles from these examples should be helpful. the other group contains unlinkable examples. for these, we evaluate the second-highest ranked prediction of the deberta-ul model. ideally, the linked articles from these examples should be unhelpful. the corresponding crowd judgment is shown in figure 2 . comparing the models, the deberta model and the deberta-ul model have similar performance, while greatly outperforming the sp model. this shows that our proposed model decomposes much more helpful finer-grained steps to assist users with tasks, similar to the trend observed in our automatic evaluation. comparing the two graphs, it is apparent that when the deberta-ul model predicts unlinkable for a step, the suggested decompositions of all models are more likely to be unhelpful. this implies the high precision of the unlinkable prediction, effectively avoiding misleading predictions. note that our study does not explicitly require subjects to carry out the task, but only annotates whether they find the instructions helpful. ## application to video retrieval in addition to intrinsic evaluation, we take a further step to study the usefulness of our open-domain hierarchical kb to downstream tasks. we select video retrieval as the extrinsic evaluation task, which aims at retrieving relevant how-to videos for a textual goal to visually aid users. more formally, given a textual goal g, the task is to retrieve its relevant videos v g from the set of all videos, with a textual query q. intuitively, our kb can be useful because videos usually contain finer-grained steps and verbal descriptions to accomplish a task. therefore, the extra information presented in decomposed steps could benefit retrieving relevant videos. ## decomposition analysis in this section, we study the properties of the hierarchies. first, what kind of steps are likely to be linked to another goal and are thus decomposed? second, what do the decomposed steps look like? we group steps into two clusters. the first contains the immediate steps of a goal (@xmath1. the second contains the decomposed steps of the steps in the first cluster (@xmath2. we use spacy @xcite to extract and lemmatize the verb in each step and rank the verbs by their frequency in each cluster. next, the top-100 most frequent verbs in each cluster are selected and we measure the rank difference of these verbs in the two clusters. figure 3 plots the verbs with largest rank difference and the full figure is in figure 4 . we observe that verbs that convey complex actions and intuitively consist of many other actions become less frequent after the decomposition (e.g., decorate). on the other hand, verbs that describe the action itself gain in frequency after the decomposition (e.g., push, hold, press). this observation follows our assumption that the decomposition would lead to more fine-grained realizations of a complex procedure. some other more abstract actions such as "learn" and "decide" also increase in frequency, as some low-level goals are explained with more complex steps. ## related work linking procedural events to the best of our knowledge, two other pieces of work @xcite ; @xcite tackled the task of linking steps in procedures to other procedures. both of them also drew the procedures from wik-ihow. while we share the same task formulation, our work makes several additional contributions: ## conclusion we propose a search-then-rerank algorithm to effectively construct a hierarchical knowledge-base of procedures based on wikihow. our hierarchies are shown to help users accomplish tasks by accurately providing decomposition of a step and improve the performance of downstream tasks such as retrieving instructional videos. one interesting extension is to further study and improve the robustness of our two-stage method to tackle more complex linguistic structures of steps and goals (e.g., negation, conjunction). another direction is to enrich the resulting knowledge-base by applying our method to other web resources, 12 or to other modalities (e.g., video clips). future work could also explore other usages such as comparing and clustering procedures based on their deep hierarchies; or applying the procedural knowledge to control robots in the situated environments.