Granted Patent B2

US 11,009,836 · App. 15/457,743 · Granted May 18, 2021

Inventors: Henry Hoffmann (Chicago, IL); John Lafferty (Evanston, IL); Nikita Mishra (Chicago, IL)

Assignee: University of Chicago

G05B13/0265G06N7/005

Abstract

Claims (89)

1. A system, comprising:

an apparatus having at least one constrained property and at least one other property to be optimized, the apparatus including

a plurality of components, which are configurable in real-time, such that the apparatus can be configured in a plurality of configurations, and

detection circuitry configured to detect values of the at least one constrained property and values of the at least one other property when the apparatus is configured in each of a first subset of configurations of the plurality of configurations;

learning circuitry configured to

learn, using a machine learning method and based on the detected values of the at least one constrained property and the detected values of the at least one other property, which were detected for the first subset, a model that predicts values of the at least one constrained property and the at least one other property when the apparatus is configured in each configuration of the plurality of configurations; and

control circuitry configured to

select, using the learned model, a particular configuration of the plurality of configurations that optimizes the at least one other property, subject to a constraint of the at least one constrained property compared to other configurations of the plurality of configurations,

wherein the learning circuitry is further configured to learn the model by comparing the detected values of the at least one constrained property and the at least one other property for the first subset of the plurality of configurations to a database of measurements of other apparatuses also having the at least one constrained property and the at least one other property, the measurements of the other apparatuses representing values of the at least one constrained property and values of the at least one other property of respective other apparatuses when components of the other apparatuses are configured in a plurality of other-apparatus configurations.

2. The system according to claim 1 , wherein the learning circuitry is further configured to encode the learned model as a data structure storing configurations of the apparatus that optimize the at least one other property subject to the constraint of the at least one constrained property.

3. The system according to claim 1 , wherein the learning circuitry is further configured to learn the model using a hierarchical Bayesian method.

4. The system according to claim 1 , wherein

the apparatus is a mobile computing device executing an application,

the plurality of configurations include computational configurations of the mobile computing device,

the control circuitry is included on the mobile computing device, and

the learning circuitry is included on a server, which transmits and receives communications to and from the mobile computing device, and the server stores the database of measurements of other mobile computing devices on a non-transitory computer readable medium, wherein

the database includes measurements of the at least one constrained property and the at least one other property for the other mobile computing devices when the other mobile computing devices are configured in various computational configurations, and

the database is used to learn the model by inference using similarities between the measurements of other mobile computing devices when configured in the various computational configurations and the detected values of the apparatus when configured in the first subset of the plurality of configurations.

5. The system according to claim 1 , wherein

the learning circuitry is further configured to learn the model, wherein the model is represented using performance-frontier configurations of the plurality of configurations, and the performance-frontier configurations correspond to values of the at least one constrained property and values of the at least one other property that are on a convex hull of a tradeoff space between the at least one constrained property and the at least one other property, and

the control circuitry is further configured to select a configuration of the performance-frontier configurations or a combination of configurations of the performance-frontier configurations to be the particular configuration of the plurality of configurations that optimizes the at least one other property.

6. The system according to claim 1 , wherein the control circuitry is further configured to

update the constraint of the at least one constrained property to minimize an error value, wherein the error value represents a difference between a desired value and an observed value of the apparatus, and

update, using the model, the particular configuration of the plurality of configurations that optimizes the at least one other property subject to the updated constraint of the at least one constrained property.

7. The system according to claim 6 , wherein the control circuitry is further configured to

detect updated values of the at least one constrained property and updated values of the at least one other property when the apparatus is configured in the particular configuration of the plurality of configurations;

update the model based on the particular configuration of the plurality of configurations and on the updated values of the at least one constrained property and the updated values of the at least one other property, and

perform the updating of the configuration of the plurality of configurations using the updated model together with the updated constraint of the at least one constrained property.

8. The system according to claim 4 , wherein the control circuitry is further configured to select the particular configuration of the plurality of configurations, wherein

the at least one other property includes one of an energy-consumption rate and a computational-performance rate,

when the at least one other property includes the computational-performance rate, the at least one constrained property includes the energy-consumption rate,

when the at least one other property includes the energy-consumption rate, the at least one constrained property includes the computational-performance rate, and

the energy-consumption rate is a rate at which the mobile computing device consumes energy while executing the application, and the computational-performance rate is a rate at which the mobile computing device performs computational tasks of the application.

9. The system according to claim 8 , wherein, when the at least one constrained property includes the computational-performance rate, the control circuitry is further configured to select the configuration of the plurality of configurations to be a schedule that minimizes the energy consumed over a predefined time period subject to a constraint that a predefined number of the computational tasks of the application are completed within the predefined time period, wherein

the schedule includes that

the apparatus is configured in a first configuration of the plurality of configurations during a period corresponding to a duty cycle of the schedule,

the apparatus is configured in a second configuration of the plurality of configurations, which is different from the first configuration, for a period corresponding to a complement of the duty cycle, and

the first configuration and the second configuration respectively correspond to the values of the at least one constrained property and the values of the at least one other property of the model that are on a convex hull of a trade-off space between the at least one constrained property and the at least one other property.

10. The system according to claim 2 , wherein

the learning circuitry is further configured to

learn the model using the machine learning method, which is one of a hierarchical Bayesian model method, a matrix completion method, a low rank matrix completion with noise method, a high rank matrix completion method, a collaborative filtering method, a recommender system method, a matrix completion with side information method, a Bayesian matrix completion method, a nonparametric matrix completion method, a multi-tasking algorithm method, a transfer learning based algorithm method, a regression algorithm method, a random forest algorithm method, a polynomial regression method, a gradient boosting method, a Bandit-based learning method, a multi-armed bandit learner method, a multi-armed bandit learner with correlated arms method, a genetic algorithm method, and an evolutionary algorithm method,

encode the learned model as the data structure, the data structure being one of a hash table, a sorted list, a list, a binary search tree, a binary heap, a btree, and a skip list, and

the control circuitry is further configured to select the particular configuration of the plurality of configurations that optimizes the at least one other property using a control method that is one of a proportional-integral control method, a proportional control method, an integral control method, a proportional integral derivative control method, a state-space control method, a stochastic control method, an adaptive control method, an optimal control method, a model predictive control method, a switching control method, a gain scheduling method, a self-tuning regulator method, a minimum variance control method, and a fuzzy control method.

11. The system according to claim 1 , wherein the learning circuitry is located remotely from the apparatus and communicates with the apparatus via a communication channel, and the learning circuitry is configured to learn the model by

determining similarities between the apparatus and the other apparatuses by comparing the database of measurements of the other apparatuses with the detected values of the at least one constrained property and the detected values of the at least one other property when the apparatus is configured in the first subset of the plurality of configurations,

learning, for all configurations of the apparatus, a complete model including estimates of the at least one other property, uncertainties of the estimates of the at least one other property, estimates of the at least one constrained property, and uncertainties of the estimates of the at least one constrained property, wherein the complete model is learned using the similarities between the apparatus and the other apparatuses, and the complete model represents the values of the at least one other property and the values of the at least one constrained property for all configurations of the apparatus,

learning, using the complete model, a convex-hull model, wherein the convex-hull model represents a second subset of the plurality of configurations having values of the at least one other property and values of the at least one constrained property that are on a convex hull of a tradeoff space between the at least one other property and the at least one constrained property, and the convex-hull model represents the estimates of the at least one other property and the estimates of the at least one constrained property corresponding the second subset of the plurality of configurations, and

transmitting, over the communication channel, the learned convex-hull model from the learning circuitry to the apparatus.

12. The system according to claim 1 , wherein learning circuitry is further configured to estimate uncertainties of the learned model to generate uncertainty estimates, wherein the learned model includes the uncertainty estimates.

13. An apparatus having at least one constrained property and at least one other property to be optimized, the apparatus communicating over a communication channel with learning circuitry, the apparatus comprising:

a plurality of components, which are configurable in real-time, such that the apparatus can be configured in a plurality of configurations;

detection circuitry configured to detect values of the at least one constrained property and values of the at least one other property when the apparatus is configured in a first subset of the plurality of configurations;

a transmitter configured to transmit the detected values of the at least one constrained property and values of the at least one other property corresponding to the first subset of the plurality of configurations to the learning circuitry;

a receiver configured to receive, from the learning circuitry, a model representing values of the at least one constrained property and values of the at least one other property, when the apparatus is configured in respective configurations of the plurality of configurations, the learning circuitry learning the model by comparing the detected values of the at least one constrained property and the at least one other property corresponding to the first subset of the plurality of configurations to a database of measurements of other apparatuses also having the at least one constrained property and the at least one other property, the measurements of the other apparatuses representing values of the at least one constrained property and values of the at least one other property of respective other apparatuses when components of the other apparatuses are configured in a plurality of other-apparatus configurations; and

control circuitry configured to select, using the received model, a particular configuration of the plurality of configurations that optimizes the at least one other property subject to a constraint of the at least one constrained property.

14. A server communicating with an apparatus, wherein the apparatus has at least one constrained property and at least one other property to be optimized, and the apparatus can be configured in a plurality of configurations, the server comprising:

a receiver configured to receive, from the apparatus, values of the at least one constrained property and values of the at least one other property, which are detected when the apparatus is in each of a first subset of configurations of the plurality of configurations,

learning circuitry configured to learn, using a machine learning method and based on the received values of the at least one constrained property and the detected values of the at least one other property, which were detected for the first subset, a model that predicts values of the at least one constrained property and the at least one other property when the apparatus is configured in each configuration of the plurality of configurations; and

a transmitter configured to transmit, to the apparatus, the determined model, wherein the learned model is learned by

comparing the received values of the at least one constrained property and the received values of the at least one other property with measurements of the at least one constrained property and the at least one other property for other apparatuses when the other apparatuses are configured in a plurality of other-apparatus configurations to determine similarities between the apparatus and the other apparatuses, and

determining estimates of the at least one other property and estimates of the at least one constrained property using the similarities between the apparatus and the other apparatuses to generate a complete model of the apparatus representing the at least one other property and the at least one constrained property for all configurations of the apparatus, and the learned model is based on the complete model.

15. The server according to claim 14 , wherein

the learning circuitry is further configured to learn a convex-hull model representing estimates of the at least one other property and estimates of the at least one constrained property of a second subset of the plurality of configurations corresponding to the estimates of the at least one other property and the estimates of the at least one constrained property of the complete model located on a convex hull of a tradeoff space between the at least one other property and the at least one constrained property; and

the learned model transmitted to the apparatus is the convex-hull model.

16. A method of optimizing an apparatus, the apparatus having at least one constrained property, at least one other property to be optimized, and a plurality of components, which are configurable in real-time, such that the apparatus can be configured in a plurality of configurations, the method comprising:

detecting values of the at least one constrained property and values of the at least one other property when the apparatus is configured in each of a first subset of configurations of the plurality of configurations;

learning, using a machine learning method and based on the detected values of the at least one constrained property and the detected values of the at least one other property, which were detected for the first subset, a model that predicts values of the at least one constrained property and the at least one other property when the apparatus is configured in each configuration of the plurality of configurations; and

selecting, using the learned model, a particular configuration of the plurality of configurations that optimizes the at least one other property, subject to a constraint of the at least one constrained property compared to other configurations of the plurality of configurations,

wherein the learning step further includes learning the model by comparing the detected values of the at least one constrained property and the at least one other property for the first subset of the plurality of configurations to a database of measurements of other apparatuses also having the at least one constrained property and the at least one other property, the measurements of the other apparatuses representing values of the at least one constrained property and values of the at least one other property of respective other apparatuses when components of the other apparatuses are configured in a plurality of other-apparatus configurations.

17. The method according to claim 16 , further comprising;

estimating uncertainties of the values of the at least one constrained property and the values of the at least one other property of the learned model to generate uncertainty estimates, and including the uncertainty estimates in the learned model; and

encoding the model as a data structure to lookup configurations of the apparatus to optimize the at least one other property subject to the constraint of the at least one constrained property.

18. The method according to claim 17 , wherein

the learning of the model is performed using the machine learning method, which is one of a hierarchical Bayesian model method, a matrix completion method, a low rank matrix completion with noise method, a high rank matrix completion method, a collaborative filtering method, a recommender system method, a matrix completion with side information method, a Bayesian matrix completion method, a nonparametric matrix completion method, a multi-tasking algorithm method, a transfer learning based algorithm method, a regression algorithm method, a random forest algorithm method, a polynomial regression method, a gradient boosting method, a Bandit-based learning method, a multi-armed bandit learner method, a multi-armed bandit learner with correlated arms method, a genetic algorithm method, and an evolutionary algorithm method,

the encoding of the learned model is performed, wherein the data structure is one of a hash table, a sorted list, a list, a binary search tree, a binary heap, a btree, and a skip list, and

the selecting of the particular configuration of the plurality of configurations to optimize the at least one other property is performed using a control method that is one of a proportional-integral control method, a proportional control method, an integral control method, a proportional integral derivative control method, a state-space control method, a stochastic control method, an adaptive control method, an optimal control method, a model predictive control method, a switching control method, a gain scheduling method, a self-tuning regulator method, a minimum variance control method, and a fuzzy control method.

19. The method according to claim 16 , further comprising:

detecting values of the at least one constrained property and values of the at least one other property when the apparatus is configured in the particular configuration of the plurality of configurations;

updating the learned model using the detected values of the at least one constrained property and the detected values of the at least one other property when the apparatus is configured in the particular configuration of the plurality of configurations;

updating the constraint of the at least one constrained property to minimize an error value, wherein the error value represents a difference between a desired value and an observed value of the apparatus, which is determined from values detected when the apparatus is configured in the particular configuration of the plurality of configurations; and

updating, using the updated model, the particular configuration of the plurality of configurations to optimize the at least one other property subject to the updated constraint of the at least one constrained property.

20. The method according to claim 16 , wherein

the apparatus is a mobile computing device executing an application, and the mobile computing device performs the detecting of the values and the selecting of the particular configuration of the plurality of configurations to optimize the at least one other property,

the learning of the model is performed by a server that communicates with the mobile computing device using a communication channel,

the at least one other property includes one of an energy-consumption rate at which the mobile computing device consumes energy while executing the application and a computational-performance rate at which the mobile computing device performs computational tasks of the application,

the at least one constrained property includes another of the energy-consumption rate application and the computational-performance rate, and

the method includes

updating a speed-up factor to minimize a difference between a desired latency and a measured latency of the mobile computing device when executing the application, and

updating the constraint of the at least one constrained property according to the updated speed-up factor.

Assignments (2)

Continuity (2)

Cited By (11)

US 12,207,433 US 12,307,224 US 12,437,348 US 12,437,349 US 12,443,444 US 12,462,312 US 12,470,292 US 12,483,475 US 12,488,573 US 12,519,542 US 12,639,650