A learning augmented algorithm is an algorithm that can make use of a prediction to improve its performance.[1] Whereas in regular algorithms just the problem instance is inputted, learning augmented algorithms accept an extra parameter. This extra parameter often is a prediction of some property of the solution. This prediction is then used by the algorithm to improve its running time or the quality of its output.
A learning augmented algorithm typically takes an input [math]\displaystyle{ (\mathcal{I}, \mathcal{A}) }[/math]. Here [math]\displaystyle{ \mathcal{I} }[/math] is a problem instance and [math]\displaystyle{ \mathcal{A} }[/math] is the advice: a prediction about a certain property of the optimal solution. The type of the problem instance and the prediction depend on the algorithm. Learning augmented algorithms usually satisfy the following two properties:
Learning augmented algorithms generally do not prescribe how the prediction should be done. For this purpose machine learning can be used.[citation needed]
The binary search algorithm is an algorithm for finding elements of a sorted list [math]\displaystyle{ x_1,\ldots,x_n }[/math]. It needs [math]\displaystyle{ O(\log(n)) }[/math] steps to find an element with some known value [math]\displaystyle{ x }[/math] in a list of length [math]\displaystyle{ n }[/math]. With a prediction [math]\displaystyle{ i }[/math] for the position of [math]\displaystyle{ x }[/math], the following learning augmented algorithm can be used.[1]
The error is defined to be [math]\displaystyle{ \eta=|i-i^*| }[/math], where [math]\displaystyle{ i^* }[/math] is the real index of [math]\displaystyle{ y }[/math]. In the learning augmented algorithm, probing the positions [math]\displaystyle{ i+1,i+2,i+4,\ldots }[/math] takes [math]\displaystyle{ \log_2(\eta) }[/math] steps. Then a binary search is performed on a list of size at most [math]\displaystyle{ 2\eta }[/math], which takes [math]\displaystyle{ \log_2(\eta) }[/math] steps. This makes the total running time of the algorithm [math]\displaystyle{ 2\log_2(\eta) }[/math]. So, when the error is small, the algorithm is faster than a normal binary search. This shows that the algorithm is consistent. Even in the worst case, the error will be at most [math]\displaystyle{ n }[/math]. Then the algorithm takes at most [math]\displaystyle{ O(\log(n)) }[/math] steps, so the algorithm is robust.
Learning augmented algorithms are known for:
Original source: https://en.wikipedia.org/wiki/Learning augmented algorithm.
Read more |