Managing a Portfolio of Experts

• US 20110131163A1
• Filed: 12/01/2009
• Published: 06/02/2011
• Est. Priority Date: 12/01/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Samulowitz, Horst Cornelius, Stern, David, Graepel, Thore, Herbrich, Ralf
• Granted Patent: US 8,433,660 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

Managing a portfolio of experts is described where the experts may be for example, automated experts or human experts. In an embodiment a selection engine selects an expert from a portfolio of experts and assigns the expert to a specified task. For example, the selection engine has a Bayesian machine learning system which is iteratively updated each time an experts performance on a task is observed. For example, sparsely active binary task and expert feature vectors are input to the selection engine which maps those feature vectors to a multi-dimensional trait space using a mapping learnt by the machine learning system. In examples, an inner product of the mapped vectors gives an estimate of a probability distribution over expert performance. In an embodiment the experts are automated problem solvers and the task is a hard combinatorial problem such as a constraint satisfaction problem or combinatorial auction.

Claims

1. A computer-implemented method of selecting an expert, the method comprising the steps of:

receiving at least one task feature describing a characteristic of a task to be assigned to an expert;

receiving, for each of a plurality of experts, at least one expert feature describing a characteristic of that expert;

arranging a machine learning system to access a mapping from expert features and task features to a multi-dimensional latent trait space, that mapping having been learnt by the machine learning system; and

arranging a selection engine to, for each expert, map the task features and expert features to the multi-dimensional trait space using the mapping to produce a latent task trait and a latent expert trait and to combine the latent task trait and latent expert trait using a similarity measure to obtain an estimate of a probability distribution over the expert'"'"'s performance on the task; and

arranging the selection engine to select one of the experts on the basis of the estimated probability distributions.

2. A method as claimed in claim 1 which comprises receiving the task features and expert features as binary vectors which are sparsely active.

3. A method as claimed in claim 1 wherein the selection engine is arranged to produce the latent task and expert traits as vectors of floating-point numbers.

4. A method as claimed in claim 1 wherein the machine learning system is arranged to have learnt the mapping using a Bayesian update process.

5. A method as claimed in claim 1 which comprises using an assumed density filtering process at the machine learning system.

6. A method as claimed in claim 1 which comprises receiving feedback comprising an observed performance of the selected expert on the task and wherein the method comprises using the machine learning system to update the mapping on the basis of the feedback.

7. A method as claimed in claim 1 which comprises using the machine learning system to form a plurality of probability distributions representing belief about parameters of the mapping and adding to the variance of those probability distributions at specified time intervals.

8. A method as claimed in claim 1 wherein the experts are automated problem solvers and the task is selected from any of:

an optimization problem, a combinatorial auction problem, a constraint satisfaction problem.

9. A method as claimed in claim 8 which comprises receiving feedback comprising an observed runtime of the selected automated problem solver and wherein the method comprises using the machine learning system to update the mapping on the basis of the feedback.

10. A method as claimed in claim 1 which further comprises arranging the selection engine to access a utility function and to use that utility function when selecting the selected expert.

11. A method as claimed in claim 1 which comprises arranging the machine learning system such that the multi-dimensional trait space has a maximum of three dimensions and which further comprises displaying a visual representation of the multi-dimensional trait space.

12. A selection engine comprising:

an input arranged to receive at least one task feature describing a characteristic of a task to be assigned to an expert, the task feature being a sparsely active binary vector;

the input also arranged to receive, for each of a plurality of experts, at least one expert feature describing a characteristic of that expert, the expert feature being a sparsely active binary vector;

a machine learning system comprising a mapping from expert features and task features to a multi-dimensional latent trait space, that mapping having been learnt by the machine learning system; and

a processor arranged to, for each expert, map the task features and expert features to the multi-dimensional trait space using the mapping to produce a latent task trait and a latent expert trait and to combine the latent task trait and latent expert trait using a similarity measure to obtain an estimate of a probability distribution over the expert'"'"'s performance on the task; and

the processor being arranging to select one of the experts on the basis of the estimated probability distributions.

13. A selection engine as claimed in claim 12 wherein the processor is arranged to use an inner product of the latent task trait and latent expert trait as the similarity measure.

14. A selection engine as claimed in claim 12 which comprises a feedback component arranged to receive feedback comprising an observed performance of the selected expert on the task and wherein the machine learning system is arranged to update the mapping on the basis of the feedback.

15. A selection engine as claimed in claim 14 wherein the machine learning system is arranged to form a factor graph in memory for the observed performance and to carry out message passing along edges of the factor graph using an approximate sum-product algorithm.

16. A selection engine as claimed in claim 12 wherein the machine learning system is arranged to form a plurality of probability distributions representing belief about parameters of the mapping and to add to the variance of those probability distributions at specified time intervals.

17. A selection engine as claimed in claim 12 wherein the experts are automated problem solvers and the task is selected from any of:

an optimization problem, a combinatorial auction problem, a constraint satisfaction problem.

18. A selection engine comprising:

an input arranged to receive at least one task feature describing a characteristic of a task to be assigned to an automated problem solver, the task feature being a sparsely active binary vector;

the input also arranged to receive, for each of a plurality of automated problem solvers, at least one automated problem solver feature describing a characteristic of that automated problem solver, the automated problem solver feature being a sparsely active binary vector;

a machine learning system comprising a mapping from automated problem solver features and task features to a multi-dimensional latent trait space, that mapping having been learnt by the machine learning system; and

a processor arranged to, for each expert, map the task features and automated problem solver features to the multi-dimensional trait space using the mapping to produce a latent task trait and a latent expert trait and to combine the latent task trait and latent expert trait using a similarity measure to obtain an estimate of a probability distribution over the automated problem solver'"'"'s performance on the task; and

the processor being arranging to select one of the automated problem solvers on the basis of the estimated probability distributions.

19. An apparatus as claimed in claim 18 further comprising a feedback component arranged to receive an observed performance of the selected expert with respect to the task and wherein the machine learning system is arranged to form a factor graph in memory, instantiate nodes of that factor graph according to the observed performance, and carry out inference by performing message passing over the factor graph.

20. An apparatus as claimed in claim 18 wherein the machine learning system is arranged such that the multi-dimensional trait space has only three dimensions.