Learning Geofence Models Directly

• US 20150088792A1
• Filed: 09/25/2013
• Published: 03/26/2015
• 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
• Granted Patent: US 9,349,104 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• 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 locations comprises training data associated with a geofence at a 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;

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, and wherein the plurality of query features comprises at least one query feature that corresponds to at least one training feature;

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.

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 the geofence-status classifier comprises a decision tree.

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 3, wherein indicating the status of the geofence using the trained geofence-status classifier comprises:

arriving at a first node of the 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 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 decision tree, wherein the first node, second node, and third node are all different nodes of the 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 training data comprises data related to the first location, and wherein the query data does not include data related to either the first location or 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 locations comprises training data associated with a geofence at a 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;

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, and wherein the plurality of query features comprises at least one query feature that corresponds to at least one training feature;

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.

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 the geofence-status classifier comprises a decision tree.

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 training data comprises data related to the first location, and wherein the query data does not include data related to either the first location or the second location.

18. An apparatus, including a 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 locations comprises training data associated with a geofence at a 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;

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, and wherein the plurality of query features comprises at least one query feature that corresponds to at least one training feature;

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.

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.