PROGRAM BOOSTING INCLUDING USING CROWDSOURCING FOR CORRECTNESS

• US 20150262079A1
• Filed: 03/14/2014
• Published: 09/17/2015
• Est. Priority Date: 03/14/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Livshits, Benjamin, Cochran, Robert A.
• Granted Patent: US 9,753,696 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 8/20 Software design
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The subject disclosure is directed towards crowd-based approach to boosting the correctness of a computer program. Results from candidate programs obtained from a first crowd and which may be blended with one another into synthesized programs are sent to a second crowd for evaluation. Based upon the results, a training set evolves and programs are filtered based upon fitness. The process of blending and fitness evaluation with an evolved training set may be iteratively repeated to find a most fit program.

Claims

1. In a computing environment, a method, comprising, obtaining candidate programs related to a programming task, synthesizing the candidate programs by combining initial programs, generating results from synthesized programs by using training data as input, providing information corresponding to the results to a crowd to obtain feedback, determining fitness measures comprising a fitness measure for each program based upon on the training set and the feedback, and selecting a most fit program based upon the fitness measure.

2. The method of claim 1 wherein determining the fitness measures for program suitability comprises evolving the training set by combining data of an initial training set and feedback-related data into an evolved training set.

3. The method of claim 1 wherein combining the data of the initial training set and the feedback-related data into the evolved training set comprises weighing the data of the initial training set differently from the feedback-related data.

4. The method of claim 1 wherein obtaining the candidate programs comprises receiving the initial programs from a first crowd that is different from the crowd from which the feedback is obtained.

5. The method of claim 1 wherein obtaining the candidate programs comprising receiving programs corresponding to regular expressions.

6. The method of claim 5 wherein synthesizing the candidate programs comprises using a crossover function.

7. The method of claim 6 wherein using the crossover function comprises using a first component of a first program in a second program and using a second component of a second program in a first program.

8. The method of claim 7 further comprising collapsing strongly connected components into the first component.

9. The method of claim 7 further comprising collapsing a stretch into the first component

10. The method of claim 7 further comprising detecting a set of single-entry, single-exit components as an independent part of a program and using the independent part as the first component.

11. The method of claim 1 wherein synthesizing the candidate programs comprises using a mutation function.

12. The method of claim 1 wherein receiving initial programs comprising receiving programs corresponding to regular expressions, in which the regular expressions are represented with symbolic finite automata.

13. The method of claim 1 wherein providing the information corresponding to the results to the crowd comprises generating strings

14. The method of claim 13 wherein generating the strings comprises using at least one of:

string edit distance, character insertion, character deletion or character replacement.

15. In a computing environment, a system comprising;

memory configured with a program selection mechanism;

at least one processor coupled to the memory to execute the program selection mechanism, and

the program selection mechanism configured to;

a) obtain initial candidate programs received from a first crowd source;

b) generate results from the candidate programs, or from blended programs synthesized from the candidate programs, or both;

c) provide information corresponding to the results to a second crowd source;

d) process feedback from the second crowd into evaluation data;

e) determine fitness data for each of the programs based at least in part on the evaluation data; and

f) output at least one selected program based upon the fitness data.

16. The system of claim 15 wherein the program selection mechanism is further configured to iteratively select and further blend programs based upon the fitness data before outputting the at least one selected program.

17. One or more machine-readable storage media or logic having machine-executable instructions, which when executed perform steps, comprising:

a) blending a set of programs into synthesized programs;

b) generating results from the synthesized programs using training data in a current state;

c) providing information corresponding to the results to a second crowd source;

d) processing feedback from the second source crowd to evolve the training data into a new current state;

e) determining fitness data for each of the synthesized programs, and associating each program with its fitness data;

f) filtering the programs based on each program'"'"'s associated fitness data to obtain a new set of programs;

g) returning to step a) until the fitness data associated with a program achieves a desired fitness level or another stopping criterion is met; and

h) selecting a selected program based upon the fitness data associated with that program.

18. The one or more machine-readable storage media or hardware logic of claim 17 having further instructions comprising obtaining programs corresponding to regular expressions as at least part of the set of programs.

19. The one or more machine-readable storage media or hardware logic of claim 18 wherein blending the set of programs into the synthesized programs comprises using a crossover function or a mutation function, or both a crossover function and a mutation function.

20. The one or more machine-readable storage media or logic of claim 17 wherein the evolved training set comprises positive and negative examples and wherein determining fitness data for each of the synthesized programs comprises using the evolved training set.