METHOD AND APPARATUS FOR AUTOMATED DECISION MAKING
1. A method for operating a first electronic device, the method comprising:
- generating a decision-making data structure using a machine learning data structure;
transmitting, to a second electronic device, the decision-making data structure;
receiving, from the electronic device, result data regarding a result of performing a selected action selected from the decision-making data structure; and
updating the machine learning data structure using the result data.
A method for a first electronic device comprises generating a decision-making data structure using a machine learning data structure; transmitting, to a second electronic device, the decision-making data structure; receiving, from the electronic device, result data regarding a result of performing a selected action selected from the decision-making data structure; and updating the machine learning data structure using the result data.
- 1. A method for operating a first electronic device, the method comprising:
generating a decision-making data structure using a machine learning data structure; transmitting, to a second electronic device, the decision-making data structure; receiving, from the electronic device, result data regarding a result of performing a selected action selected from the decision-making data structure; and updating the machine learning data structure using the result data.
- View Dependent Claims (2, 3, 4, 5)
- 6. An apparatus of a first electronic device, the apparatus comprising:
a memory storing a machine learning data structure; a transceiver; and at least one processor, wherein the at least one processor is configured to; generate a decision-making data structure using the machine learning data structure, control the transceiver to transmit, to a second electronic device, the decision-making data structure, control the transceiver to receive, from the second electronic device, result data regarding a result of performing a selected action selected from the decision-making data structure, and update the machine learning data structure stored in the memory using the result data.
- View Dependent Claims (7, 8, 9, 10)
- 11. An apparatus of a second electronic device, the apparatus comprising:
a memory; at least one sensor; a transceiver; and at least one processor, wherein the at least one processor is configured to; control the transceiver to receive, from a first electronic device, a decision-making data structure, control the at least one sensor to obtain state information on a current state of the second electronic device, select an action from the decision-making data structure using the state information, perform the selected action, and control the transceiver to transmit, to the first electronic device, result data regarding a result of the performing the selected action, wherein the decision-making data structure is generated using a machine learning data structure.
- View Dependent Claims (12, 13, 14, 15)
The present disclosure relates to artificial intelligence technologies, more particularly to method and apparatus for automated decision making.
Artificial Intelligence (AI) system is a computer system that implements human-level intelligence. Unlike conventional Rule-based smart system, AI is a system that learns, judges and becomes smart. As the use of artificial intelligence improves recognition rate and understanding of user'"'"'s taste more accurately, existing rule-based smart systems are gradually being replaced by deep-based artificial intelligence systems.
Artificial intelligence technology consists of machine learning (deep learning) and element technology that utilizes machine learning.
Machine Learning (ML) is an algorithm technology that classifies/learns the characteristics of input data by itself. Element technology is a technology that simulates functions of human brain such as recognition and judgment using machine learning algorithms such as deep learning, and consists of technical fields such as linguistic understanding, visual understanding, reasoning/prediction, knowledge representation, and motion control.
The various fields in which artificial intelligence technology is applied are as follows. Linguistic understanding is a technology for recognizing, applying/processing human language/characters, and includes natural language processing, machine translation, dialogue system, query response, speech recognition/synthesis, and the like. Visual understanding is a technology for recognizing and processing objects as human vision, and includes object recognition, object tracking, image search, human recognition, scene understanding, spatial understanding, and image enhancement. Reasoning/prediction is a technology for judging information, logically inferring and predicting, and includes knowledge/probability based reasoning, optimization prediction, preference base planning, and recommendation. Knowledge representation is a technology for automating human experience information into knowledge data, and includes knowledge building (data generation/classification) and knowledge management (data utilization). Motion control is a technology for controlling the autonomous travel of the vehicle and the motion of the robot, and includes motion control (navigation, collision, traveling), operation control (behavior control), and the like.
The present disclosure provides method and apparatus for automated decision making
According to an aspect of the present disclosure, a method for a first electronic device comprises: generating a decision-making data structure using a machine learning data structure; transmitting, to a second electronic device, the decision-making data structure; receiving, from the electronic device, result data regarding a result of performing a selected action selected from the decision-making data structure; and updating the machine learning data structure using the result data.
According to another aspect of the present disclosure, an apparatus of a first electronic device, the apparatus comprises: a memory storing a machine learning data structure; a transceiver; and at least one processor, wherein the at least one processor is configured to: generate a decision-making data structure using the machine learning data structure, control the transceiver to transmit, to a second electronic device, the decision-making data structure, control the transceiver to receive, from the second electronic device, result data regarding a result of performing a selected action selected from the decision-making data structure, and update the machine learning data structure stored in the memory using the result data.
According to another aspect of the present disclosure, an apparatus of a second electronic device, the apparatus comprises: a memory; at least one sensor; a transceiver; and at least one processor, wherein the at least one processor is configured to: control the transceiver to receive, from a first electronic device, a decision-making data structure, control the at least one sensor to obtain state information on a current state of the second electronic device, select an action from the decision-making data structure using the state information, perform the selected action, and control the transceiver to transmit, to the first electronic device, result data regarding a result of the performing the selected action, wherein the decision-making data structure is generated using a machine learning data structure.
Various embodiments of the present disclosure provide an improved system performance.
Hereinafter, in various embodiments of the present disclosure, hardware approaches will be described as an example. However, various embodiments of the present disclosure include a technology that uses both hardware and software and thus, the various embodiments of the present disclosure may not exclude the perspective of software.
Machine Learning (ML) is a type of Artificial Intelligence (AI) that gives computers the ability to learn correct decisions without being explicitly programmed. ML algorithms typically make data driven decisions using a model built from sample inputs. ML is employed in a wide range of fields, such as image/video processing, text/speech recognition, search engines, security, robotics, autonomous vehicles, and many others.
A known type of ML, which is used in applications including Google DeepMind™, Advanced Robotics, etc, is Q-Learning (see, for example, Christopher JCH Watkins and Peter Dayan. Q-Learning. Machine Learning, 8(3-4): 279-292, 1992). Q-Learning is based on adaptive ML heuristics and learns based on experience as well as trial and error. A benefit of Q-Learning is that it does not require previously created training data; it is a “decision making” and “updating” ML algorithm that can be used in scenarios requiring a system to automatically learn and self-adjust without a previously generated training set.
Q-Learning takes decisions or “actions” based on previous experiences and selects the best decision in order to reach or get closer to a specific goal. Actions lead to changes in system “states”. When there are no experiences, a randomly-selected action is performed. High “rewards” are given to good actions, whilst zero or low value rewards are given to bad actions. Experiences are stored in a data structure called the “Q-Table”. The Q-Table is updated when new experiences are gained from the environment. This feedback loop, with rewards and actions, allows the system to “learn”.
Unlike other ML heuristics, such as Neural Networks, which are static, Q-Learning can adapt in real time. It also typically uses low CPU resources because updates and decision making are relatively trivial operations.
However, ML algorithms, such as Q-Learning, can be slow and time consuming in some cases. In particular, the learning rate is dependent on the rate at it which it is fed input and on the number of variables involved. ML can be ineffective in some cases because it makes random (or incorrect) decisions when it has low learning or when it is starting out. Further, the learned information data structures/Q-Tables generated can be very large. Learning time is linear to the amount of states in the Q-Table, whilst memory usage is linear to the amount of states in the Q-Table. It is not always feasible to simplify or reduce the Q-Table size (states or actions). Further, if deployed in several independent devices, learning information is not shared.
Distributed Q-Learning is a known variation that solves some of the drawbacks of conventional Q-Learning. Distributed Q-Learning addresses slow learning by using multiple “clients” and learning in parallel. Each client updates a centrally-stored Q-Table asynchronously, thereby decreasing the learning time linearly by the number of clients. Thus, the algorithm learns faster, typically proportional to the number of clients.
However, distributed Q-Learning requires constant communication with a central server that stores the Q-Table in order to function because no Q-Learning is performed by the clients themselves. Therefore, network dropout can cause client devices to become unresponsive. Further, increases in network latency can slow down the client devices'"'"' decision making (in some scenarios where decisions are needed in just 10 ms timeframes, a system may even make invalid decisions), and constant network access can be expensive in terms of money, power, etc.
Embodiments of the present disclosure can provide a Cloud-based ML heuristic that learns from multiple, e.g. millions, of devices/sources and can optimize itself and the devices under it. Embodiments can be based on the widely accepted Q-Learning (Reinforcement Learning) Heuristic, or other types of ML. Embodiments may be designed to be lightweight and optimized for Cloud operation, and can also minimize network usage and dependency. Embodiments may be particularly suitable for mobile devices or low power devices.
In example embodiments client devices no longer directly update a full ML data structure, such as a full Q-table, which is stored remotely, e.g. on a server or in the Cloud. Client devices can make decisions using a locally-stored read-only Decision Look-up Table (DLUT), which is a simplified version of the total ML learnt information (i.e. the Q-Table) provided by a remote source, such as the server. In typical embodiments, the client devices do not update the DLUT themselves. Occasionally, e.g. when a network connection is available, the client device may be updated to the latest DLUT version. The server can therefore create the DLUT for the client devices, and also process and add data transferred from the clients into the server'"'"'s full ML system (Q-Table). The client devices may save the results of executing at least some decisions in a local file/table. When a network connection is available the client devices can transfer at least some of that data to the server/Cloud. These operations can be performed asynchronously while serving an old DLUT version to the clients. DLUT access does not have latency limitations, resulting in faster operation than standard distributed Q-Learning.
Embodiments can reduce training time in a manner that is proportional to the number of client devices. Embodiments may address the large data size problem with ML by storing the full learnt data (Q-Table) remotely (e.g. in a server or the Cloud), and only a device specific “simplified” table may be stored locally in the client device. Embodiments can offer a Cloud based solution that allows for more complex Q-Learning solutions due to fast training time. Training specific to each situation, e.g. power optimisation whilst running a particular software application/game, is possible.
Example embodiments can be applied to power management in mobile devices. Further, embodiments, which can include a Cloud-based self learning infrastructure, may be used to operate many other complex applications, including mobile device applications.
In the example embodiment, the server 110 is a computer that functions as part of a Cloud service. However, any step described herein as being performed by the server (or any data stored/processed by it) could be performed/stored by other devices via the Cloud. The example embodiment is not a definite limitation and many variations are possible, e.g. the server 110 may comprise a server in connection with one or more (same or different types of) laptop or desktop computers over a wired communications network. Common components of the computers, e.g. user input/output units, etc, are well-known to the skilled person and are not shown or described herein in detail.
The client device 120 may be a terminal, a user equipment (UE), a mobile station, a subscriber station, a remote terminal, a wireless terminal, a terminal, or a user device or other term having equivalent technical meaning. In some cases, the client device 120 is a device that performs machine type communication (MTC) and may not be carried by the user. For brevity, the operations performed by one of the client devices only will sometimes be described below; however, it should be understood that such operations can be performed by any number of client devices and that they can all exchange data with the server.
According to an embodiment, the memory 230 stores a machine learning data structure, and the at least one processor 220 is configured to: generate a decision-making data structure using the machine learning data structure, control the transceiver 210 to transmit, to a client device 120, the decision-making data structure, control the transceiver 210 to receive, from the client device 120, result data regarding a result of performing a selected action selected from the decision-making data structure, and update the machine learning data structure stored in the memory 230 using the result data.
According to an embodiment, at least one processor is configured to: control the transceiver 310 to receive, from a server 110, a decision-making data structure, control the at least one sensor 340 to obtain state information on a current state of the client device 120, select an action from the decision-making data structure using the state information, perform the selected action, and control the transceiver 330 to transmit, to the server 110, result data regarding a result of the performing the selected action. And, the decision-making data structure is generated using a machine learning data structure.
According to an embodiment, the operation of the server 110 may comprises: generating 401 a decision-making data structure using a machine learning data structure; transmitting 403, to a second electronic device, the decision-making data structure; receiving 405, from the electronic device, result data regarding a result of performing a selected action selected from the decision-making data structure; and updating 407 the machine learning data structure using the result data.
According to an embodiment, the operation of the client device 120 may comprises: receiving 501, from a first electronic device, a decision-making data structure; obtaining 503 state information on a current state of the second electronic device; selecting 505 an action from the decision-making data structure using the state information; performing 507 the selected action; and transmitting 509, to the first electronic device, result data regarding a result of the performing the selected action, wherein the decision-making data structure is generated using a machine learning data structure.
As with embodiments of the present disclosure, the “states” and “actions” of the Q-Learning process can vary greatly and should be construed broadly. For instance, a state may relate to the condition of a hardware or software component (which can be internal or external to the agent), e.g. the temperature of a component or outside environment; load of a processor; a value (e.g. a variable used by an application) stored in a register or other data store, and so on. The state may be obtained/computed directly by the agent (e.g. by reading/processing data from its storage), or it may involve use of at least one sensor, network connection, etc. An action may also relate to a hardware or software component, which may be internal or external to the agent. For example, an action may switch on/off a component or device; change a value (e.g. a variable used by an application) stored in a register or other data store; change a device setting (e.g. screen brightness, GPS on/off); move a robot in a particular direction, and so on.
The format of each line/entry in a simple example Q-Table can be as follows:
(State, Action) Q-Value
The Q-Learning process selects the best action based on the current state of the environment with the aim of reaching or getting closer to a specific goal. The action to be selected for a given state may be determined in various ways, e.g. using the known Algorithmic Temperature Function or Boltzmann Probability:
When there are no relevant experiences stored in the Q-Table, a randomly-selected action may be performed.
Performing actions leads to changes in system/environment states. The new state of the system is directly or indirectly the result of the action taken. The Q-Table 606 is updated when new experiences are gained from the environment. A reward value can be calculated for each state based on a satisfaction formula 608. These rewards in effect are determined by the results of a given action. High rewards are given to good results, whilst zero or low rewards are given to bad results. For example, in an AI car driver application, a reward can be based on fuel usage, smooth drive, etc. The satisfaction formula represents the ideal results to be obtained by the system. The update formula 610 updates Q-Values with new data obtained from the satisfaction formula.
Requirements for setting up a Q-Learning system normally include:
1. Define Actions (a)
(1) Actions are what the agent does in the environment
(2) Example: Move, sell, buy, update a particular device or application setting, etc.
2. Define Satisfaction or Reward formula (r)
(1) Rewards indicate if the results are good or bad
(2) Rewards tell the learning algorithm the outcome of the actions
(3) Example: Giving a robot positive reward for moving in straight line and a negative reward for hitting the wall; the robot will learn to move in straight line, and avoid walls
3. Define States (s)
(1) States represent the status of the system at any given time (t)
(2) Example: Current position in space for a robot, speed of a driving car, etc
(3) States can also be calculated values; for example average speed of a car, fuel average fuel consumption in a car, battery level of a robot, etc.
4. Define Learning Rate (α) and Discount Factor (γ)
(1) Learning rate (α) will define how quickly an agent learns (longer learning could be more accurate and vice-versa)
(2) Discount Factor (γ) defines the importance given to future rewards—Should the agent look for Future high reward or short-term smaller rewards?
An example function for updating the Q-Table is:
The skilled person will appreciate that the above formula is orientative and that alternative Q-Learning implementations can have multiple different variations of the formula. Provided that the Q-Value of the action gets updated by a suitable formula that uses the reward value obtained, it can still be a Q-Learning implementation.
Embodiments of the present disclosure can be based on modifying the conventional Q-Learning process. However, the skilled person will appreciate that alternative embodiments may be based on other ML techniques, such as Neural Networks, where the inputs can be defined in finite states and there is a limited set of output actions.
In known distributed Q-Learning the client devices 120 would communicate with the server 110 in order to obtain Q-Learning decisions based on their current states, and also to transfer result information for updating the Q-Table after taking action. However, in contrast to such conventional Q-Learning systems, in embodiments of the present disclosure the client devices do not directly update the full Q-Table maintained by the server. Rather, the client devices make decisions using a locally-stored decision-making data structure that is derived by the server from the full Q-Table. In some embodiments, this local data structure can comprise a read-only Decision look-up Table (DLUT). Further, the client devices can save result data in a local store (e.g. as a file or table) and at an appropriate juncture, e.g. when a cheap network connection is available (e.g. WiFi™), may transfer the result data to the server in order for it to update its full Q-Table and use that to generate an updated DLUT.
As shown in
The DLUT 705 represents a substantial reduction in size compared to the corresponding full Q-Table 703. The size of the full Q-Table is: Nstates*NActions*QValueSize, with typically the Q-Value size being an integer or floating point value (4 Bytes). In contrast, the size of the corresponding DLUT is:
Thus, the DLUT is,
Advantages can be seen when the DLUT is calculated for a sample Q-Table with 4 Byte Q-Values and 5 Actions: 32× reduction in size; 5 bits/state for Local Look-up Table and 160 bits/state for Full Q-Table.
It will be understood that alternative embodiments can use (one or more) data structures other than look-up tables, preferably simple ones (e.g. arrays or lists) that require little storage and a small amount of processing power in order to obtain/output an action based on (input representing) the current state of a client device 120. For example, in cases where memory might be a problem other structures such as decisions trees can be an in-place replacement to a look-up table. Also, an equivalent mathematical formula, which may cost more computing power but save memory storage, could be used.
The client device 120 uses the DLUT 705′ to make a decision by selecting/looking-up the action from the DLUT that corresponds to its current state. Executing that action results in a change in the state/environment 714 of the client device. In some embodiments data relating to the result 716 of executing (all or some) actions may be stored locally by the client device. The result data may comprise, for example, an updated state of the client device that resulted from performing the action, as well as data representing the performed action. In some embodiments, the client device may transfer (all or some of) the result data to the server 110 at an appropriate juncture. For example, if there is a functional network connection between the server and the client device or only when there is no cost to perform the transfer (network cost, battery cost, etc.), then the result data may be transferred immediately/soon after the result data has been generated. Additionally or alternatively, the result data may be transferred periodically, in batches (e.g. after X number of results have been generated), and/or on an event-basis, such as when the server requests it; after a functional network connection has been re-established following a disconnection or power off event, etc. The result data transferred may include additional information, such as an identifier of the client device; a version identifier and/or time/date stamp for the DLUT used to generate the results, and so on. The result data may be in any suitable format and may be modified after receipt by the server for further processing.
In some embodiments the server 110 stores a copy 716′ of the received result data. The server can use this saved result data to update the full Q-Table, e.g. by means of a software component 708 that executes the satisfaction formula/formula update, at an appropriate juncture. This can be done, for example, immediately upon receipt of the result data; in batches (e.g. after X number of results have been received); periodically; on an event-basis, such as when a user of the server requests it, and so on. In some embodiments the updating software component 708 may be remote from the server, e.g. accessed via a Cloud service.
At an appropriate juncture, the system (e.g. the server 110 and/or other computing devices) may re-generate/update the DLUT 705. For example, this may be done after each update of the full Q-Table 703; periodically; after a certain number of updates to the full Q-Table have been completed; upon request by a software/hardware component, and so on. Thus, the server takes care of creating the DLUT for the client devices, as well as processing and adding the result data from the clients into the server-stored full Q-Table. All of this can be computed asynchronously whilst the client devices can continue to operate using their currently-stored version of the DLUT.
In some cases, there may not be enough data for a given state to take a decision as to which action is best. In conventional Q-Learning there is no information regarding whether a state is learned or not. However, some advanced ML techniques can differentiate between unlearned states and learned states by having a counter of how many times a state is visited, as well as recognising empty states by setting all empty states to an empty value. Embodiments can address this shortcoming of conventional Q-Learning by using additional information that indicates whether the data regarding a state is “complete” and/or whether “more data” is needed in order to improve results.
Embodiments can therefore process four “levels” of data completeness/certainty for at least some of the states, including:
1) There is no data for the state (e.g. see row 924 of DLUT 905)
2) There is data, but it is not complete (e.g. row 923)—the ML system is not sure at all whether the action that is considered the best one so far is the real best action possible.
3) There is complete data, but more data is needed (e.g. row 922)—the ML system is quite sure that the best action so far is the overall best action, but more data should be collected to confirm.
4) There is complete data, and more data is not needed (e.g. row 921)
Embodiments can use two additional bits/values in the DLUT 905 in order to indicate which of the above cases 1)-4) apply to the corresponding row of the original full Q-Table 903. An extra action value (“?” in the second column 909 in the example DLUT of
The use of the extra action value can make the table slightly larger, but still small in comparison to the full Q-Table:
Based on the previous calculation, this still means that the example alternative DLUT is 22.8× smaller.
In general, the client device 120 is intended to make the “best” decisions 1002, according to its local DLUT 705 based on its current state/environment 1004, and can also decide 1006 whether or not to store 1008 the result data (typically results relating to new experiences), as will be detailed below. In some embodiments, the “Complete” and “More data” bits in the DLUT can be used to decide whether or not a randomly-selected action is to be taken instead of any action specified in the DLUT for the current state. When a random action is performed it selected from amongst all the possible actions that the system can perform; this data is known a priori by the client as it has to know what the actions mean and how many there are. Thus, the data in the DLUT can affect the randomness of the decision making process. A user/designer of the system can select/modify levels (e.g. X %, Y % probability levels) in order to reduce/minimize the user/system impact of performing random actions, whilst still allowing the system to learn the results of performing new actions when more data is needed.
There are typically four possible client device scenarios that will determine which action to take/decision to make:
Local DLUT 705 has no data for the current state:
- Perform a random action
- Save the result of performing the random action, e.g. State+Action=Updated state
Local DLUT 705 has data for the current state, but it is not complete:
- Based on specified X % (e.g. 60%) probability level: perform a random action; otherwise, perform the action stored in the DLUT for the state
- Save the result of performing the selected action, e.g. State+Action=Updated state
Local DLUT 705 has data for the current state, but more data is needed by the server 110:
- Based on specified Y % (typically lower than X %, e.g. 5%) probability level: perform a random action; otherwise, perform the action stored in the DLUT for the state
- Save the result of performing the selected action, e.g. State+Action=Updated state
Local DLUT has data for the current state, and more data is not needed:
- Perform the action specified in the DLUT for the state
- Do not save the result of performing the action
As discussed above, the client device 120 may transfer the saved result data to the server 110 at an appropriate juncture. The server 110 can then use the result data received by one or more of the client devices to update its full Q-Table. This updating can be done in various ways, e.g. immediately after receiving new result data from any client device; in batches based on all/some client devices; periodically; upon user command/request, etc.
Some embodiments may be adapted to address a “cold-start” problem. Cold-start is when the system has no experience or learning data and needs to learn before making any decisions. Typically during cold-boot, when a client device 120 runs for the first time, there is no existing data. In some embodiments, the client device may use an auxiliary data structure, e.g. a “default” look-up table 1010, to address this problem. The default table can be computed using a handmade function that decides the best action for a given state or from another source of knowledge. A table can be generated according to a mathematical formula that is known to address some level of the problem the ML has to address; for example, if/else conditions that perform actions based on states. A table can also be generated by reusing data collected for other applications, conditions or devices. When enough data has been collected by the server 110, the default table can also be computed using extrapolation. It is supposed that most of the states in a system will never be explored and therefore it is logical solution to extrapolate the most common data to fill up the table. For example, if the best action when a temperature state of a device is 70° C. is to reduce performance, then the action of reducing performance can be extrapolated to 72° C., 74° C. and all other upper temperature states. A default table is not typically customized for individual applications/situations that are the subject of the ML process.
A default table can only be provided if one is available and so is typically used in cases where the learning system is to specialize. For example, the system may be intended to learn how to play each of several games installed in a phone very well. It could start with a general default table that has training for all games and the system will then train on top of that in order to generate tables that are specialized for each game. However, a default table is not applicable in a case where there is zero training.
As mentioned above, a formula can be used to generate a default table to be used as a solution for cold-start. For example, for a phone client device, formulas can be written to: increase frequency if the processor load is at 100% and decrease otherwise; reduce maximum processor frequency if the temperature is greater than X°, etc. Such formulas will create an initial data set for the server to train and produce a first DLUT. However, the formula must also be used to guide learning; otherwise, the system will never explore past the boundaries of the formula.
Formulas can be written in many different ways. The server may adjust formulas at periodic intervals. For example, an initial formula could be: don'"'"'t allow increase in processor frequency if temperature is greater than a limit. At a later stage this limit can be changed. This limit can also be different for each device, e.g. for most of the devices the formula may never allow temperature beyond X. However, if that is the case then the system will never beyond temperature X as it never visits states beyond X, and so for a few devices (e.g. 1 in every 1000) it may increase X limit to X+10 (say).
In some embodiments devices are “volunteered” for training, e.g. bits in a DLUT transferred to the devices from the server can indicate whether or not the devices are enabled for unbounded training (for one or more states) or only enabled to run based on formulas. There can also be many variables for these volunteer devices. For example, a device always runs based on formula, but explores for a specific game and only for 10 minutes per day; when its processing load is below a given threshold, and so on. Some embodiments may set and adjust these variables from the server side.
In some embodiments the server may provide specific instructions for training. For example, if an agent/device finds itself in a specific state, taking a specific set of actions, or repeating the same action for a certain time period (e.g. 1) minute before reverting back to formula based control. Based on this, it is possible to expand cold-start to cover more ground.
In use, the client device 120 may be configured to decide when to use the default table 1010 instead of the local DLUT 705, e.g. use the default table for at least one initial iteration of the decision-making process; use the default table when the DLUT contains less than a particular amount of data, e.g. no actions for less a certain number of states; fewer than a certain number of states stored in the DLUT, use the default DLUT when enough random actions have been done lately, and so on.
During a cold-start, or during a new scenario/state not previously encountered, there is a need to reduce the number of sub-optimal actions taken by the client device 120. For example, when a client device encounters unknown states, e.g. when executing a new application, it may perform many random actions. The resulting random behavior can degrade performance, e.g. slow execution of the application itself and/or other software/network issues.
Therefore, some embodiments can set an upper threshold on the number of random decisions to be taken. For example, embodiments may set a maximum, N, number of random decisions during a certain time period (e.g. 100 decisions per hour). In some embodiments random actions are not taken until the number of actions being performed is below a (e.g. user-set) threshold. It will be understood that the selection of random actions may be based on other factors. For instance, the number of random actions may be limited when specific applications/events are being executed by the client device; based on the current load of the client device; and so on. Data containing rules for controlling the number of random actions to be taken can be stored locally by each client device 120. This data may be received from/updated by the server 110 at an appropriate juncture, e.g. at the same time as a DLUT data update; when a new application is installed on the client device; periodically, etc.
Briefly, the known IPM method of
The IPM logic of
In the known method of
The governing equations for some version of the IPM of
where P represents power, T represents Temperature, F represents FPS, Gload represents load, and w represents configurable “weight” parameters to give more or less importance to the parameters.
Example reward formulas include:
However, there are limitations associated with the known IPM method illustrated in
Each of a plurality of client devices 120 decides on an Action 1202 (e.g. in the form of setting a processor frequency) based on its current state (e.g. its current CPU/GPU load, FPS, temperature, etc) using a locally-stored DLUT 705. The DLUT contains the best action for all given states as determined by a Q-Learning processed performed by the server 110 in a similar manner to the embodiments described above. Information regarding the current state of the mobile device may be derived from information provided by temperature sensors, etc. Taking the selected Action will result in a new mobile device state 1204 that can have changed performance, power, temperature 1206, etc. These steps can be repeated as appropriate. In some embodiments, each client device can record the result (e.g. the change in performance, temperature, etc) of taking the selected action in a local data store/database 1208. As discussed above, the client device 120 may transfer/upload 1210 the saved result data to the server 110 at an appropriate juncture.
Operations performed by the server 110 include collecting result data 1220 from the client devices 120. The server also recalculates 1222 its full Q-Table based on the received result data at an appropriate juncture, e.g. after a certain amount of result data has been received; periodically; upon request by a software/hardware component, and so on. As discussed above, the server can create a DLUT 705 for each client device and transfer 1224 copies to the client devices. In some example embodiments, the Q-Table recalculation and DLUT creation can be once per day initially, and then once every couple of days/weeks.
In some embodiments the server/cloud side processing can produce individual Q-Tables for different users/client devices rather than a single Q-Table for use by all users/devices. Training information can be collected from various types of users/client devices and the data processed to find patterns associated with different geographical regions, devices (e.g. phones), applications (e.g. games), etc. For example, there might be different needs depending on the device country; devices in hot countries might learn differently from those located in cold countries. Also, embodiments can support many different devices and so may separate the client devices into categories, even if they all use the same actions/states; the learning might be different due to different behaviour that is learnt by devices having different configurations, locations, user types, etc. Embodiments may use techniques such as the known K-means clustering method to generate common clusters for multidimensional data.
Thus, in some embodiments, different ML data structures, such as Q-Tables, and simplified decision-making data structures, e.g. DLUTs, derived from these can be generated and tailored for different uses/situations. Embodiments can identify clusters of client devices based on having data patterns in common. These data patterns may be based on a wide variety of factors, such as location, identify of user, hardware and/or software features and so on. For example, Q-Tables may be generated for different geographical regions. In some embodiments, Q-Tables tailored for individual devices and/or location, OS, application/game and profile can be created and be deployed to all devices/phones when there is a functional internet connection. This level of fine-tuning is not possible/practical with known solutions. If a device, e.g. phone, is not connected to the internet then it can operate using default tables (it may only lack the fine-tuned tables).
In some embodiments, each (or at least some) client device will have different State-Action mappings in its local DLUT. For example, a newer version of a mobile device may have better thermal management and so 600 Mhz frequency GPU runs cooler compared to an older version. The server can produce different Q-Tables and derived DLUTs for each version/release of the device.
In some embodiments, the same client device can have different performance attributes depending on Operating System version. For example, one particular version of Android™ may have fewer background programs and hence require lower frequencies for an application/game compared to another version. Therefore, for the same model of client device the server can produce different Q-Tables and derived DLUTs for different (or even every) Android™ OS versions. As embodiments can provide extremely fast training, such combinations are possible.
In some embodiments, Q-Tables and derived DLUTs tailored to individual applications can be generated, particularly for applications having high processing demands, such as games. This can increase the accuracy of decisions and improve power/performance values. Training data sent to the server can be tagged with specific application/game/package name. This will allow the server to produce one Q-Table/DLUT per application.
Devices are naturally colder in cold countries compared to hot countries. Therefore, embodiments can generate IPM tables specifically to be sent to client devices located in cold countries that allow for higher FPS (as they are cooler devices), whilst a more aggressive FPS throttle may be specified in tables sent to devices in warmer countries.
Due to fast training speed, some embodiments configured to perform IPM can offer more profiles (e.g. 10) than the total number of conventionally supported IPM profiles (e.g. 4—Ultra, High, Mid and Low). Each profile may require training for its own specific FPS, temperature, power target, etc, which can be achieved using embodiments of the present disclosure.
Embodiments can provide layered Q-Learning where a first level comprises a cloud server (that collects the data from users/client devices and creates the Q-Table(s) and DLUT(s)) and a second level comprises user/client devices (which can upload learning to server, downloads new DLUT(s) and operates even offline with already known experience).
Alternative embodiments can operate using generic Q-Learning-like algorithms that operate on a table or similar data structure. Other embodiments can operate using Neural Networks (NN) algorithms or the like, which can be optimized in a similar way. For example, embodiments may use a NN with quantized input levels and quantized output levels as a blackbox equivalent to a Q-Table, so that upon input of states, the NN outputs best actions. For instance, a server device may use a Neural Network/derived data structure (instead of a table) that can provide an output value and a confidence value. A low confidence value can be used to determine that new result data should be recorded and sent to the server. The server can use received result data to re-compute a full neural network data structure and, in some embodiments, generate a neural network derived data structure that is transferred for use by client devices. Embodiments may operate using other types of ML based on graphs/formulas/tables (any type can be converted from one to the other). Embodiments can be produced that provide benefits for any decision-making application/system where ML can be used, including, but not limited to: image/video processing, text/speech recognition, search engines, security, robotics, autonomous vehicles, and so on.
Methods according to embodiments stated in claims and/or specifications of the present disclosure may be implemented in hardware, software, or a combination of hardware and software.
When the methods are implemented by software, a computer-readable storage medium for storing one or more programs (software modules) may be provided. The one or more programs stored in the computer-readable storage medium may be configured for execution by one or more processors within the electronic device. The at least one program may include instructions that cause the electronic device to perform the methods according to various embodiments of the present disclosure as defined by the appended claims and/or disclosed herein.
The programs (software modules or software) may be stored in non-volatile memories including a random access memory and a flash memory, a read only memory (ROM), an electrically erasable programmable read only memory (EEPROM), a magnetic disc storage device, a compact disc-ROM (CD-ROM), digital versatile discs (DVDs), or other type optical storage devices, or a magnetic cassette. Alternatively, any combination of some or all of the may form a memory in which the program is stored. Further, a plurality of such memories may be included in the electronic device.
In addition, the programs may be stored in an attachable storage device which is accessible through communication networks such as the Internet, Intranet, local area network (LAN), wide area network (WAN), and storage area network (SAN), or a combination thereof. Such a storage device may access the electronic device via an external port. Further, a separate storage device on the communication network may access a portable electronic device.
In the above-described detailed embodiments of the present disclosure, a component included in the present disclosure is expressed in the singular or the plural according to a presented detailed embodiment. However, the singular form or plural form is selected for convenience of description suitable for the presented situation, and various embodiments of the present disclosure are not limited to a single element or multiple elements thereof. Further, either multiple elements expressed in the description may be configured into a single element or a single element in the description may be configured into multiple elements.
While the present disclosure has been shown and described with reference to certain embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the present disclosure. Therefore, the scope of the present disclosure should not be defined as being limited to the embodiments, but should be defined by the appended claims and equivalents thereof.
Although the present disclosure has been described with an exemplary embodiment, various changes and modifications may be suggested to one skilled in the art. It is intended that the present disclosure encompass such changes and modifications as fall within the scope of the appended claims.