Processing queries using reinforcement learning
Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for processing a user query, comprising receiving a user query corresponding to a primary node in the computational graph; processing the user query to determine one or more listing nodes in the computational graph, providing, to the user device, data associated with one or more listing nodes. The processing comprises: determining a first set of random walks starting at the primary node according to a policy, determining a second set of random walks starting at one or more secondary nodes according to the policy, determining a final score for each of a first set of listing nodes reached by the first set of random walks, and determining the one or more listing nodes from the first set of listing nodes based on the final scores.
1 . A method, comprising:
receiving, from a user device, a user query corresponding to a primary node in a computational graph;
processing the received user query to determine one or more listing nodes in the computational graph for the user query, the processing comprising:
determining a first set of random walks starting at the primary node according to a policy trained using reinforcement learning, wherein the primary node is determined based on text of the user query,
determining a second set of random walks starting at one or more secondary nodes in the computational graph according to the policy, wherein each of the one or more secondary nodes is determined based on context information associated with one or more user activities and is different from the primary node,
generating a final score for each of a first set of listing nodes in the computational graph reached by the first set of random walks based on outputs of the first set of random walks and the second set of random walks, and
identifying the one or more listing nodes from the first set of listing nodes based on the final scores; and
providing, to the user device, data associated with one or more listing nodes that correspond to the user query.
2 . The method of claim 1 , wherein generating the final score for each of the first set of listing nodes in the computational graph comprises:
determining the first set of listing nodes in the computational graph reached by the first set of random walks from the primary node according to the policy;
determining a second set of listing nodes in the computational graph reached by the second set of random walks from the one or more secondary nodes according to the policy; and
generating the final score for each of the first set of listing nodes by updating a score for one or more listing nodes in the first set of listing nodes according to the second set of listing nodes.
3 . The method of claim 1 , wherein updating the score for the one or more listing nodes in the first set of listing nodes comprises:
for each listing node in the first set of listing nodes that is also in the second set of listing nodes, updating the score for the listing node in the first set of listing nodes by adding a modification value.
4 . The method of claim 3 , wherein the modification value is computed based on (i) a value proportional to a total count of reaches at the listing node in the second set of random walks and (ii) a boost value.
5 . The method of claim 4 , wherein the boost value includes a range from zero to one.
6 . The method of claim 3 , wherein the modification value is computed using an exponentiation function with a base proportional to a total count of reaches at the listing node in the second set of random walks and a pre-determined power value.
7 . The method of claim 1 , wherein the first set of random walks and the second set of random walks are performed in parallel using two or more threads using respective random seeds.
8 . A system, comprising:
one or more memory devices storing instructions; and
one or more data processing apparatus that are configured to interact with the one or more memory devices, and upon execution of the instructions, perform operations including:
receiving, from a user device, a user query corresponding to a primary node in a computational graph;
processing the received user query to determine one or more listing nodes in the computational graph for the user query, the processing comprising:
determining a first set of random walks starting at the primary node according to a policy trained using reinforcement learning, wherein the primary node is determined based on text of the user query,
determining a second set of random walks starting at one or more secondary nodes in the computational graph according to the policy, wherein each of the one or more secondary nodes is determined based on context information associated with one or more user activities and is different from the primary node,
generating a final score for each of a first set of listing nodes in the computational graph reached by the first set of random walks based on outputs of the first set of random walks and the second set of random walks, and
identifying the one or more listing nodes from the first set of listing nodes based on the final scores; and
providing, to the user device, data associated with one or more listing nodes that correspond to the user query.
9 . The system of claim 8 , wherein generating the final score for each of the first set of listing nodes in the computational graph comprises:
determining the first set of listing nodes in the computational graph reached by the first set of random walks from the primary node according to the policy;
determining a second set of listing nodes in the computational graph reached by the second set of random walks from the one or more secondary nodes according to the policy; and
generating the final score for each of the first set of listing nodes by updating a score for one or more listing nodes in the first set of listing nodes according to the second set of listing nodes.
10 . The system of claim 8 , wherein updating the score for the one or more listing nodes in the first set of listing nodes comprises:
for each listing node in the first set of listing nodes that is also in the second set of listing nodes, updating the score for the listing node in the first set of listing nodes by adding a modification value.
11 . The system of claim 10 , wherein the modification value is computed based on (i) a value proportional to a total count of reaches at the listing node in the second set of random walks and (ii) a boost value.
12 . The system of claim 11 , wherein the boost value includes a range from zero to one.
13 . The system of claim 10 , wherein the modification value is computed using an exponentiation function with a base proportional to a total count of reaches at the listing node in the second set of random walks and a pre-determined power value.
14 . The system of claim 8 , wherein the first set of random walks and the second set of random walks are performed in parallel using two or more threads using respective random seeds.
15 . One or more non-transitory computer-readable media storing instructions that, when executed by one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising:
receiving, from a user device, a user query corresponding to a primary node in a computational graph;
processing the received user query to determine one or more listing nodes in the computational graph for the user query, the processing comprising:
determining a first set of random walks starting at the primary node according to a policy trained using reinforcement learning, wherein the primary node is determined based on text of the user query,
determining a second set of random walks starting at one or more secondary nodes in the computational graph according to the policy, wherein each of the one or more secondary nodes is determined based on context information associated with one or more user activities and is different from the primary node,
generating a final score for each of a first set of listing nodes in the computational graph reached by the first set of random walks based on outputs of the first set of random walks and the second set of random walks, and
identifying the one or more listing nodes from the first set of listing nodes based on the final scores; and
providing, to the user device, data associated with one or more listing nodes that correspond to the user query.
16 . The one or more non-transitory computer-readable media of claim 15 , wherein generating the final score for each of the first set of listing nodes in the computational graph comprises:
determining the first set of listing nodes in the computational graph reached by the first set of random walks from the primary node according to the policy;
determining a second set of listing nodes in the computational graph reached by the second set of random walks from the one or more secondary nodes according to the policy; and
generating the final score for each of the first set of listing nodes by updating a score for one or more listing nodes in the first set of listing nodes according to the second set of listing nodes.
17 . The one or more non-transitory computer-readable media of claim 15 , wherein updating the score for the one or more listing nodes in the first set of listing nodes comprises:
for each listing node in the first set of listing nodes that is also in the second set of listing nodes, updating the score for the listing node in the first set of listing nodes by adding a modification value.
18 . The one or more non-transitory computer-readable media of claim 17 , wherein the modification value is computed based on (i) a value proportional to a total count of reaches at the listing node in the second set of random walks and (ii) a boost value.
19 . The one or more non-transitory computer-readable media of claim 18 , wherein the boost value includes a range from zero to one.
20 . The one or more non-transitory computer-readable media of claim 17 , wherein the modification value is computed using an exponentiation function with a base proportional to a total count of reaches at the listing node in the second set of random walks and a pre-determined power value.
21 . The one or more non-transitory computer-readable media of claim 15 , wherein the first set of random walks and the second set of random walks are performed in parallel using two or more threads using respective random seeds.