グループテスト
Example applications > Machine learning and compressed sensing

Machine learning is a field of computer science that has many software applications such as DNA classification, fraud detection and targeted advertising. One of the main subfields of machine learning is the 'learning by examples' problem, where the task is to approximate some unknown function when given its value at a number of specific points. As outlined in this section, this function learning problem can be tackled with a group-testing approach.
In a simple version of the problem, there is some unknown function,  f:\{0,1\}^{N}\to \{0,1\} where  f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}, and  {\textbf {a}}\in \{0,1\}^{N} (using logical arithmetic: addition is logical OR and multiplication is logical AND). Here  {\textbf {a}} is ' d sparse', which means that at most  d\ll N of its entries are  1. The aim is to construct an approximation to  f using  t point evaluations, where  t is as small as possible. (Exactly recovering  f corresponds to zero-error algorithms, whereas  f is approximated by algorithms that have a non-zero probability of error.)
In this problem, recovering  f is equivalent to finding  {\textbf {a}}. Moreover,  f({\textbf {p}})=1 if and only if there is some index,  n, where  {\textbf {a}}_{n}={\textbf {p}}_{n}=1. Thus this problem is analogous to a group-testing problem with  d defectives and  n total items. The entries of  {\textbf {a}} are the items, which are defective if they are  1,  {\textbf {p}} specifies a test, and a test is positive if and only if  f({\textbf {p}})=1.
In reality, one will often be interested in functions that are more complicated, such as  f:\mathbb {C} ^{N}\to \mathbb {C} , again where  f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}. Compressed sensing, which is closely related to group testing, can be used to solve this problem.
In compressed sensing, the goal is to reconstruct a signal,  {\textbf {v}}\in \mathbb {C} ^{N}, by taking a number of measurements. These measurements are modelled as taking the dot product of  {\textbf {v}} with a chosen vector. The aim is to use a small number of measurements, though this is typically not possible unless something is assumed about the signal. One such assumption (which is common) is that only a small number of entries of  {\textbf {v}} are significant, meaning that they have a large magnitude. Since the measurements are dot products of  {\textbf {v}}, the equation  M{\textbf {v}}={\textbf {q}} holds, where  M is a  t\times N matrix that describes the set of measurements that have been chosen and  \mathbf {q}  is the set of measurement results. This construction shows that compressed sensing is a kind of 'continuous' group testing.
The primary difficulty in compressed sensing is identifying which entries are significant. Once that is done, there are a variety of methods to estimate the actual values of the entries. This task of identification can be approached with a simple application of group testing. Here a group test produces a complex number: the sum of the entries that are tested. The outcome of a test is called  positive if it produces a complex number with a large magnitude, which, given the assumption that the significant entries are sparse, indicates that at least one significant entry is contained in the test.
There are explicit deterministic constructions for this type of combinatorial search algorithm, requiring  d2^{(\log _{2}\log _{2}N)^{O(1)}} measurements. However, as with group-testing, these are sub-optimal, and random constructions (such as COMP) can often recover  f sub-linearly in  N.