Learning geofence models directly

• US 9,349,104 B2
• Filed: 09/25/2013
• Issued: 05/24/2016
• Est. Priority Date: 09/25/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: O'Neill, Thomas Germano, Williams, Brian Patrick
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US14/037,332
• Publication Number:
  US 20150088792A1
• Time in Patent Office: 972 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

Methods and apparatus are directed to geofencing applications that utilize machine learning. A computing device can receive a plurality of geofence-status indications, where a geofence-status indication includes training data associated with a geofence at a first location. The geofence is associated with a geographical area. The computing device trains a geofence-status classifier to determine a geofence status by providing the training data as input to the geofence-status classifier. The training data includes data for a plurality of training features. After the geofence-status classifier is trained, the computing device receives query data associated with a second location. The query data includes data for a plurality of query features. The query features include a query feature that corresponds to a training feature. The query data is input to the geofence-status classifier. After providing the query data, the trained geofence-status classifier indicates the geofence status.

Claims

1. A method, comprising:

receiving, at a computing device, a plurality of geofence-status indications, wherein at least one geofence-status indication of the plurality of geofence-status indications comprises training data associated with a geofence at a first location, wherein the training data comprises signal strength information from one or more networks at the first location, and wherein the geofence is associated with a geographical area;

training a geofence-status classifier of the computing device to determine a status of the geofence by providing the training data as input to the geofence-status classifier, wherein the training data comprises data for each of a plurality of training features, wherein the plurality of training features comprise a training feature associated with the signal strength information from one or more networks at the first location, and wherein the geofence-status classifier comprises a plurality of decision trees;

after the geofence-status classifier is trained, receiving query data associated with a second location at the computing device, wherein the query data comprises data for each of a plurality of query features, wherein the query data comprises signal strength information from one or more networks at the second location, and wherein the plurality of query features comprises at least one query feature associated with the signal strength information from one or more networks at the second location;

providing the query data as input to the trained geofence-status classifier; and

after providing the query data as input, indicating the status of the geofence using the trained geofence-status classifier by at least;

providing the query data to at least a subset of the plurality of decision trees;

after providing the query data, determining one or more output values from the at least the subset of the plurality of decision trees; and

determining the status of the geofence by at least aggregating the one or more output values.

2. The method of claim 1, wherein the status of the geofence is selected from at least:

(a) a status of being inside the geographical area associated with the geofence and (b) a status of being outside the geographical area associated with the geofence.

3. The method of claim 1, wherein aggregating the one or more output values comprises determining an average of the one or more output values.

4. The method of claim 1, wherein indicating the status of the geofence comprises indicating the status of the geofence without determining the second location.

5. The method of claim 1, wherein the plurality of decision trees comprises a first decision tree, and wherein indicating the status of the geofence using the trained geofence-status classifier comprises:

arriving at a first node of the first decision tree, wherein the first node is not a terminal node, wherein the first node is associated with a first question, and wherein the first question has two possible answers;

determining an answer to the first question based on one or more inputs;

determining whether the answer to the first question is a first answer of the two possible answers; and

after determining that the answer to the first question is the first answer, traversing to a second node of the first decision tree, wherein the second node differs from the first node.

6. The method of claim 5, further comprising:

after determining that the answer to the first question is not the first answer, traversing to a third node of the first decision tree, wherein the first node, second node, and third node are all different nodes of the first decision tree.

7. The method of claim 6, wherein the second node and third node are each terminal nodes, and wherein the second node is labeled with a status of the geofence that differs from a status of the geofence labeling the third node.

8. The method of claim 1, wherein the query data comprises data related to one or more devices operating according to an IEEE 802.11 (“

Wi-Fi”

) standard.

9. The method of claim 1, wherein the query data does not include data specifying the second location.

10. The method of claim 1, wherein the geofence is further associated with a stationary object.

11. The method of claim 1, wherein the geofence is further associated with a moving object.

12. A computing device, comprising:

a plurality of sensors;

a processor; and

a non-transitory computer-readable storage medium having stored thereon program instructions that, upon execution by the processor, cause the computing device to perform functions comprising;

receiving a plurality of geofence-status indications, wherein at least one geofence-status indication of the plurality of geofence-status indications comprises training data associated with a geofence at a first location, wherein the training data comprises signal strength information from one or more networks at the first location, and wherein the geofence is associated with a geographical area;

training a geofence-status classifier to determine a status of the geofence by providing the training data as input to the geofence-status classifier, wherein the training data comprises data for each of a plurality of training features, wherein the plurality of training features comprise a training feature associated with the signal strength information from one or more networks at the first location, and wherein the geofence-status classifier comprises a plurality of decision trees;

after the geofence-status classifier is trained, receiving query data associated with a second location, wherein the query data comprises signal strength information from one or more networks at the second location, wherein the query data comprises data for each of a plurality of query features, and wherein the plurality of query features comprises at least one query feature associated with the signal strength information from one or more networks at the second location;

providing the query data as input to the trained geofence-status classifier; and

after providing the query data as input, indicating the status of the geofence using the trained geofence-status classifier by at least;

providing the query data to at least a subset of the plurality of decision trees;

after providing the query data, determining one or more output values from the at least the subset of the plurality of decision trees; and

determining the status of the geofence by at least aggregating the one or more output values.

13. The computing device of claim 12, wherein the status of the geofence is selected from at least (a) a status of being inside the geographical area associated with the geofence and (b) a status of being outside the geographical area associated with the geofence.

14. The computing device of claim 12, wherein aggregating the one or more output values comprises determining an average of the one or more output values.

15. The computing device of claim 12, wherein indicating the status of the geofence comprises indicating the status of the geofence without determining the second location.

16. The computing device of claim 12, wherein the query data comprises data related to one or more devices operating according to an IEEE 802.11 (“

Wi-Fi”

) standard.

17. The computing device of claim 12, wherein the query data does not include data specifying the second location.

18. An apparatus, including a non-transitory computer-readable storage medium having stored thereon program instructions that, upon execution by a computing device, cause the apparatus to perform functions comprising:

receiving a plurality of geofence-status indications, wherein at least one geofence-status indication of the plurality of geofence-status indications comprises training data associated with a geofence at a first location, wherein the training data comprises signal strength information from one or more networks at the first location, and wherein the geofence is associated with a geographical area;

training a geofence-status classifier to determine a status of the geofence by providing the training data as input to the geofence-status classifier, wherein the training data comprises data for each of a plurality of training features, wherein the plurality of training features comprise a training feature associated with the signal strength information from one or more networks at the first location, and wherein the geofence-status classifier comprises a plurality of decision trees;

after the geofence-status classifier is trained, receiving query data associated with a second location, wherein the query data comprises data for each of a plurality of query features, wherein the query data comprises signal strength information from one or more networks at the second location, and wherein the plurality of query features comprises at least one query feature associated with the signal strength information from one or more networks at the second location;

providing the query data as input to the trained geofence-status classifier; and

after providing the query data as input, indicating the status of the geofence using the trained geofence-status classifier by at least;

providing the query data to at least a subset of the plurality of decision trees;

after providing the query data, determining one or more output values from the at least the subset of the plurality of decision trees; and

determining the status of the geofence by at least aggregating the one or more output values.

19. The apparatus of claim 18, wherein the status of the geofence is selected from at least (a) a status of being inside the geographical area associated with the geofence and (b) a status of being outside the geographical area associated with the geofence.

20. The apparatus of claim 18, wherein indicating the status of the geofence comprises indicating the status of the geofence without determining the second location.