Source-linked AI summary
End-to-End Goal-Driven Web Navigation
Rodrigo Nogueira, Kyunghyun Cho
TL;DR
Text-based games offer limited vocabulary and mostly scene-level descriptions, motivating a benchmark that tests natural-language understanding and planning in a richer setting. The paper introduces WebNav, which turns websites into partially observed navigation tasks, and builds WikiNav from Wikipedia. Neural agents perform better as models become more sophisticated, and on Jeopardy!-based queries they outperform search-based strategies; the authors present the task as a benchmark and a potential proxy for question-answering and focused crawling.
Problem
Text-based games have limited vocabularies and usually describe only the current scene, limiting the natural-language complexity represented in these tasks.
Source: §1 · p. 1Method
WebNav converts websites into partially observed graph-navigation tasks in which agents follow hyperlinks to find pages containing queries, with WikiNav built from Wikipedia.
Source: §1 · pp. 1–2, §2 · p. 2Results
Takeaways & Limitations
The authors conclude that goal-driven web navigation is suited to evaluating progress in natural-language understanding and planning, with potential as a proxy for question-answering and focused crawling.
Source: §1 · p. 2, §9 · p. 8The authors find WebNav suitable for benchmarking machine intelligence but not for comparison with humans, who were not trained on Wikipedia and became exhausted by reading multiple articles.
Source: §8.1 · p. 7
Abstract
from arXiv · showhide
We propose a goal-driven web navigation as a benchmark task for evaluating an agent with abilities to understand natural language and plan on partially observed environments. In this challenging task, an agent navigates through a website, which is represented as a graph consisting of web pages as nodes and hyperlinks as directed edges, to find a web page in which a query appears. The agent is required to have sophisticated high-level reasoning based on natural languages and efficient sequential decision-making capability to succeed. We release a software tool, called WebNav, that automatically transforms a website into this goal-driven web navigation task, and as an example, we make WikiNav, a dataset constructed from the English Wikipedia. We extensively evaluate different variants of neural net based artificial agents on WikiNav and observe that the proposed goal-driven web navigation well reflects the advances in models, making it a suitable benchmark for evaluating future progress. Furthermore, we extend the WikiNav with question-answer pairs from Jeopardy! and test the proposed agent based on recurrent neural networks against strong inverted index based search engines. The artificial agents trained on WikiNav outperforms the engined based approaches, demonstrating the capability of the proposed goal-driven navigation as a good proxy for measuring the progress in real-world tasks such as focused crawling and question-answering.
1 Introduction
The paper proposes goal-driven web navigation as a large-scale benchmark for natural-language understanding and planning, addressing the limited vocabulary and scene-level descriptions of text-based games. WebNav generates tasks from websites, and results on WikiNav-Jeopardy show NeuAgents outperforming search-based strategies.
1 Introduction
- Goal-driven web navigation evaluates natural-language understanding and planning by asking an agent to find a page containing a query while navigating a website graph.Pages are nodes, hyperlinks are directed edges, and the query comes from a randomly selected page.Source: §1 · pp. 1–2
- Unlike text-based games, the task uses existing website text and has an action space that changes with the current page.The authors note that text-based games tested had vocabularies of 1,340 and 2,258 unique words and generally described only the current scene.Source: §1 · pp. 1–2
- WebNav converts websites into tasks, with WikiNav as an English Wikipedia example; task difficulty is controlled by maximum hop distance Nh and query length Nq.The paper evaluates neural-network agents and human volunteers on the benchmark.Source: §1 · p. 2
- On WikiNav-Jeopardy, NeuAgents outperform SimpleSearch, Apache Lucene, and Google Search API in document recall, supporting the task as a proxy for question-answering and focused crawling.The paper extends WikiNav with queries constructed from Jeopardy! questions.Source: §1 · p. 2
2 Goal-driven Web Navigation
Goal-driven web navigation models a website as a partially observed graph in which an agent searches for a page containing a query. At each page, it chooses among outgoing links or stops, under constraints intended to prevent degenerate search policies.
2 Goal-driven Web Navigation
- A website is a directed graph of pages and hyperlinks; a target page is one whose text contains the query, and multiple target pages may exist.The agent begins at a designated start page.Source: §2 · p. 2
- The task is partially observed: the agent reads the current page, while the full website and its graph structure remain hidden.Available actions are the current page’s outgoing links plus a stop action, so the action space depends on the page.Source: §2 · p. 2
- Stopping receives a binary reward based on whether the current page contains the query.Source: §2 · p. 2
- Four constraints limit search: outgoing edges per page, agent memory, hop distance, and query distance from the start; they are intended to prevent breadth-first search and test-time or training-time graph reconstruction.The query-distance condition is included because the agent may read the next page’s content.Source: §2 · pp. 2–3
3 WebNav: Software
WebNav converts a website into a graph-based navigation task and generates examples by selecting queries from pages reached along paths through that graph. It separates target pages across training, validation, and test sets, while retaining target and path information for training.
3 WebNav: Software
- WebNav builds a website graph from a starting URL, using cleaned page text as node content and intra-site hyperlinks as directed edges.Source: §3 · p. 3
- WebNav assigns each target page to only one of the training, validation, or test sets to prevent overlap among the sets.Source: §3 · p. 3
- Examples include a query, its target page, and a path from the start; the target and path can support training but are not used to evaluate a trained agent.Source: §3 · p. 3
- For each example, WebNav random-walks from a start page for Nh/2 steps, selects a query from the reached target page, and chooses among its top five candidates by average TF-IDF.This query selection is intended to discourage trivial queries.Source: §3 · p. 3
4 WikiNav: A Benchmark Task
WikiNav applies goal-driven navigation to a large English Wikipedia graph and varies task difficulty through hop limits and query size. The paper frames this task as a more challenging reworking of Wikispeedia, with less informative queries and potentially multiple target pages.
4 WikiNav: A Benchmark Task
- WikiNav tasks vary the maximum allowed hops (Nh ∈ {4, 8, 16}) and query size (Nq ∈ {1, 2, 4}).Examples come from pages half as many hops from the starting page as the maximum allowed; the authors chose this limit for computational reasons.Source: §4 · p. 3
- Wikipedia’s per-page statistics characterize the cleaned WikiNav world as large and complicated.The benchmark uses the September 2015 English Wikipedia dump, containing more than five million pages.Source: §4 · p. 4, Table 2 · p. 4
- The dataset is fairly small for WikiNav-4-* but large for WikiNav-8-* and WikiNav-16-*.Source: §4 · p. 4
4.1 Related Work: Wikispeedia
- Wikispeedia uses a Wikipedia graph with about 4,000 articles and asks agents to navigate from a start article to a specified target article.Agents can access the current and immediately neighboring nodes’ text.Source: §4.1 · p. 4
- Unlike Wikispeedia’s single whole-article target, WikiNav can have multiple target nodes and gives the agent a less informative query.Source: §4.1 · p. 4
- The paper’s focus differs from Wikispeedia’s human-navigation research: it proposes an automatic tool for building challenging tasks to evaluate artificial agents.Source: §4.1 · p. 4
5 WikiNav-Jeopardy: Jeopardy! on WikiNav
WikiNav-Jeopardy extends WikiNav with Jeopardy! question-answer pairs whose answers are Wikipedia article titles. The authors use the resulting pairs to train navigation agents on paths to target articles.
5 WikiNav-Jeopardy: Jeopardy! on WikiNav
- The authors retain 133k of more than 300k Jeopardy! question-answer pairs by keeping only answers that are Wikipedia article titles.Source: §5 · p. 4
- The 133k pairs are split into 113k training, 10k validation, and 10k test examples, with no article crossing partitions and no shuffling across episodes.Source: §5 · pp. 4–5
- For supervised learning, each training pair is assigned a path from Main Topic Classification to its target, averaging 5.8 hops (standard deviation 1.2; range 2–10).Source: §5 · p. 5
6 NeuAgent: Neural Network based Agent
NeuAgent combines the current page and query to form a hidden state, then selects a navigation action. It supports beam-search inference and is trained from example traces with a differentiable cost.
6.1 Model Description
- NeuAgent uses the current node and query to compute a hidden state, then scores outgoing edges and a stop action to choose its next action.The feedforward and recurrent variants use different hidden-state implementations; the recurrent variant conditions action probabilities on the action history.Source: §6.1 · p. 5
- Node content uses continuous bag-of-words vectors, while queries can use either bag-of-words or attention-based context vectors.Attention scores query words using the previous hidden state and combines them into a time-specific query representation.Source: §6.1 · pp. 5–6
6.2 Inference: Beam Search
- Forward-only beam search retains the Nn most likely traces at each step, improving on greedy selection by exploring multiple outgoing edges.The beam width is capped at Nn.Source: §6.2 · p. 6
6.3 Training: Supervised Learning
- Supervised training follows an example trace and minimizes a differentiable per-example cost with stochastic gradient descent.Backpropagation trains the model end-to-end, directly optimizing query-to-target performance.Source: §6.3 · p. 6
7 Human Evaluation
The human evaluation tested volunteers on WikiNav queries and compared their average reward with the NeuAgents. The section also describes why navigating the information network is difficult for an untrained person.
7 Human Evaluation
- Untrained people face difficulty from needing graph familiarity, broad topic knowledge, and careful reading of each visited page.The paper notes that acquiring graph familiarity can require many months or years of training.Source: §7 · p. 6
- Five volunteers attempted up to 20 four-sentence queries from WikiNav-{4, 8, 16}-4 test sets, with up to two hours and an option to give up.Volunteers could explore up to the same maximum of four edges per node as the NeuAgents.Source: §7 · pp. 6–7
- Table 4 reports average reward for NeuAgent-FF, NeuAgent-Rec, and humans on the test sets of all nine WikiNav configurations.The reported reward is the fraction of correct trials.Source: Table 4 · p. 7, §7 · p. 7
8 Results and Analysis
On WikiNav, task difficulty rises with more allowed hops and falls with longer queries, while recurrent history, larger models, and attention-based query representations help on harder navigation tasks. On WikiNav-Jeopardy, WikiNav-pretrained agents outperform search strategies, though the authors caution that WebNav is not suited to comparing machine and human intelligence.
8.1 WikiNav
- Task difficulty is positively correlated with maximum allowed hops Nh and negatively correlated with query length Nq.The authors suggest that shorter queries require more language understanding and planning to find a path to the target.Source: §8.1 · p. 7
- NeuAgent-FF and NeuAgent-Rec perform similarly at Nh = 4, but NeuAgent-Rec does better at higher Nh; a larger, deeper recurrent model does better when targets are farther away.The authors interpret the recurrent model’s higher-hop performance as evidence that access to history helps with long-term planning.Source: §8.1 · p. 7
- The best-performing model uses an attention-based query representation, especially as Nq decreases and Nh increases.The paper illustrates attention weights changing over query words as the model navigates toward a target.Source: §8.1 · p. 7
- Human participants generally perform worse than NeuAgents, but the authors caution that WebNav is suitable for machine-intelligence evaluation, not comparison with human intelligence.They attribute the difference partly to agents’ Wikipedia-specific training and volunteers’ exhaustion from reading multiple articles.Source: §8.1 · p. 7
8.2 WikiNav-Jeopardy
- The WikiNav-Jeopardy evaluation tests the best recurrent model with and without WikiNav-16-4 pretraining against SimpleSearch, Lucene, and Google Search API using Recall@K.NeuAgent uses beam search with width K to return K final nodes; the evaluation varies K across 1, 4, and 40.Source: §8.2 · p. 8
- The pretrained NeuAgent outperforms all three search strategies on WikiNav-Jeopardy, with a larger advantage when fewer candidate documents are allowed.Without pretraining, the NeuAgent performs comparably to the search strategies; the authors say pretraining on the larger WikiNav is beneficial.Source: Table 5 · p. 8, §8.2 · p. 8
- The WikiNav-Jeopardy comparison pits agents observing pages only as they visit against search strategies that can access all nodes for each query.The authors connect the pretrained agent’s result to potential use in focused crawling, where some Internet content is hidden or dynamically generated.Source: §8.2 · p. 8
9 Conclusion
The paper presents goal-driven web navigation as a test bed for natural-language understanding and planning, with WebNav for task creation and WikiNav and WikiNav-Jeopardy as datasets. Results show stronger performance from more sophisticated agents and that WikiNav-pretrained agents outperform inverted-index search engines on WikiNav-Jeopardy.
9 Conclusion
- The paper concludes that more sophisticated agents perform better on WikiNav and WikiNav-Jeopardy, supporting the task’s use to evaluate natural-language understanding and planning.The authors describe goal-driven web navigation as a large-scale test bed and release WebNav to compile websites into tasks.Source: §9 · p. 8
- On WikiNav-Jeopardy, the agent pretrained on WikiNav outperforms two strong inverted-index search engines.Source: §9 · p. 8
- The authors say these results support the usefulness of the task and agents for challenging applications such as focused crawling and question-answering.Source: §9 · p. 8