What is AI (artificial intelligence)?

Artificial Intelligence (AI) creates intelligent machines capable of performing tasks that typically require human intellect.

There are two places that training happens, human and machine.

Human learned

Human developers are trained to produce a program. And humans write if-conditions, and assign scores to actions. Common examples are an AI player in an early chess game, and behavior of Non-player characters (NPC) in video games.

Machine learning

One meta-program, or we call it machine, including programming by examples system, Genetic programming system, and Neural networks system, reads positive examples and negative examples, and then automatically trains itself and produces a program. Internally, the meta-program can generate many programs and select the best one as output. The term “learning” is in the continuous form because such a system can adapt to an evolving environment or new inputs.

Machine learning

If a (meta-)program trains itself, it still has a function to map a candidate program to a score.
– PBE uses a ranking algorithm to establish a partial order on programs.
– In Genetic programming, the function is called fitness function.
– In Neural networks, the function is the oppsite of fitness function, called loss function.

Any kind of mapping can be thought as a bipartite graph.

All these methods suffer from over- and under-generalization in unseen test dataset.

To generate new candidates,
– programming by examples (PBE) uses the term “synthesize” rather than the generic term “generate”. The operands of synthesizing are atoms in a grammar or DSL.
– In Genetic programming, candidates with high scres are somehow crossed over. The operands of crossover are DNA.
– In Neural networks, mathematical derivatives and backprobagation help to twist values in a neural network candidate. The operands of backprobagation are decimals.

An edit script is a sequence of edit operations. Hence, an edit operation is an atom in its grammar. As a result, edit scripts can be generated (synthesized) by programming by examples.

The Flash Fill feature since Excel 2013 is a PBE system. It is few-shot learning with merely one to two positive examples. Flash Fill infers logical structures from the examples, and generates string transformation programs, or edit scripts.

Flash Fill supports conditionals and loops, and the edit scripts it produces are more likely not to be regular. Blink Fill is a fast version of Flash Fill, dropping the support of conditionals and loops.^[1]

References

1. Rishabh Singh; . BlinkFill: Semi-supervised Programming By Example for Syntactic String Transformations. Proceedings of the VLDB Endowment, Volume 9, Issue. 2016, (): [].↑