hotchpotch/wikipedia-multilingual-ir-pairs huggingface dataset:
グループテスト 基本的な説明と用語
The items that cause a group to test positive are generally called defective items (these are the broken lightbulbs, syphilitic men, etc.). Often, the total number of items is denoted as  and  represents the number of defectives if it is assumed to be known.
There are two independent classifications for group-testing problems; every group-testing problem is either adaptive or non-adaptive, and either probabilistic or combinatorial.
グループテスト 基本的な説明と用語
In probabilistic models, the defective items are assumed to follow some probability distribution and the aim is to minimise the expected number of tests needed to identify the defectiveness of every item. On the other hand, with combinatorial group testing, the goal is to minimise the number of tests needed in a 'worst-case scenario' – that is, create a minmax algorithm – and no knowledge of the distribution of defectives is assumed.
グループテスト 基本的な説明と用語
The other classification, adaptivity, concerns what information can be used when choosing which items to group into a test. In general, the choice of which items to test can depend on the results of previous tests, as in the above lightbulb problem. An algorithm that proceeds by performing a test, and then using the result (and all past results) to decide which next test to perform, is called adaptive. Conversely, in non-adaptive algorithms, all tests are decided in advance. This idea can be generalised to multistage algorithms, where tests are divided into stages, and every test in the next stage must be decided in advance, with only the knowledge of the results of tests in previous stages.
グループテスト 基本的な説明と用語
Although adaptive algorithms offer much more freedom in design, it is known that adaptive group-testing algorithms do not improve upon non-adaptive ones by more than a constant factor in the number of tests required to identify the set of defective items. In addition to this, non-adaptive methods are often useful in practice because one can proceed with successive tests without first analysing the results of all previous tests, allowing for the effective distribution of the testing process.
グループテスト 基本的な説明と用語
There are many ways to extend the problem of group testing. One of the most important is called noisy group testing, and deals with a big assumption of the original problem: that testing is error-free. A group-testing problem is called noisy when there is some chance that the result of a group test is erroneous (e.g. comes out positive when the test contained no defectives). The Bernoulli noise model assumes this probability is some constant, , but in general it can depend on the true number of defectives in the test and the number of items tested. For example, the effect of dilution can be modelled by saying a positive result is more likely when there are more defectives (or more defectives as a fraction of the number tested), present in the test. A noisy algorithm will always have a non-zero probability of making an error (that is, mislabeling an item).
グループテスト 基本的な説明と用語
Group testing can be extended by considering scenarios in which there are more than two possible outcomes of a test. For example, a test may have the outcomes  and , corresponding to there being no defectives, a single defective, or an unknown number of defectives larger than one. More generally, it is possible to consider the outcome-set of a test to be  for some .
グループテスト 基本的な説明と用語
Another extension is to consider geometric restrictions on which sets can be tested. The above lightbulb problem is an example of this kind of restriction: only bulbs that appear consecutively can be tested. Similarly, the items may be arranged in a circle, or in general, a net, where the tests are available paths on the graph. Another kind of geometric restriction would be on the maximum number of items that can be tested in a group, or the group sizes might have to be even and so on. In a similar way, it may be useful to consider the restriction that any given item can only appear in a certain number of tests.
グループテスト 基本的な説明と用語
There are endless ways to continue remixing the basic formula of group testing. The following elaborations will give an idea of some of the more exotic variants. In the 'good–mediocre–bad' model, each item is one of 'good', 'mediocre' or 'bad', and the result of a test is the type of the 'worst' item in the group. In threshold group testing, the result of a test is positive if the number of defective items in the group is greater than some threshold value or proportion. Group testing with inhibitors is a variant with applications in molecular biology. Here, there is a third class of items called inhibitors, and the result of a test is positive if it contains at least one defective and no inhibitors.
グループテスト History and development
The concept of group testing was first introduced by Robert Dorfman in 1943 in a short report published in the Notes section of Annals of Mathematical Statistics. Dorfman's report – as with all the early work on group testing – focused on the probabilistic problem, and aimed to use the novel idea of group testing to reduce the expected number of tests needed to weed out all syphilitic men in a given pool of soldiers. The method was simple: put the soldiers into groups of a given size, and use individual testing (testing items in groups of size one) on the positive groups to find which were infected. Dorfman tabulated the optimum group sizes for this strategy against the prevalence rate of defectiveness in the population.
グループテスト History and development
After 1943, group testing remained largely untouched for a number of years. Then in 1957, Sterrett produced an improvement on Dorfman's procedure. This newer process starts by again performing individual testing on the positive groups, but stopping as soon as a defective is identified. Then, the remaining items in the group are tested together, since it is very likely that none of them are defective.
グループテスト History and development
The first thorough treatment of group testing was given by Sobel and Groll in their formative 1959 paper on the subject. They described five new procedures – in addition to generalisations for when the prevalence rate is unknown – and for the most optimal one, they provided an explicit formula for the expected number of tests it would use. The paper also made the connection between group testing and information theory for the first time, as well as discussing several generalisations of the group-testing problem and providing some new applications of the theory.
グループテスト History and development
Group testing was first studied in the combinatorial context by Li in 1962, with the introduction of Li’s -stage algorithm. Li proposed an extension of
Dorfman's '2-stage algorithm' to an arbitrary number of stages that required no more
than  tests to be guaranteed to find  or fewer defectives among  items.
The idea was to remove all the items in negative tests, and divide the remaining items into groups as was done with the initial pool. This was to be done  times before performing individual testing.
グループテスト History and development
Combinatorial group testing in general was later studied more fully by Katona in 1973. Katona introduced the matrix representation of non-adaptive group-testing and produced a procedure for finding the defective in the non-adaptive 1-defective case in no more than tests, which he also proved to be optimal.
グループテスト History and development
In general, finding optimal algorithms for adaptive combinatorial group testing is difficult, and although the computational complexity of group testing has not been determined, it is suspected to be hard in some complexity class. However, an important breakthrough occurred in 1972, with the introduction of the generalised binary-splitting algorithm. The generalised binary-splitting algorithm works by performing a binary search on groups that test positive, and is a simple algorithm that finds a single defective in no more than the information-lower-bound number of tests.
グループテスト History and development
In scenarios where there are two or more defectives, the generalised binary-splitting algorithm still produces near-optimal results, requiring at most  tests above the information lower bound where  is the number of defectives. Considerable improvements to this were made in 2013 by Allemann, getting the required number of tests to less than  above the information lower bound when  and . This was achieved by changing the binary search in the binary-splitting algorithm to a complex set of sub-algorithms with overlapping test groups. As such, the problem of adaptive combinatorial group testing – with a known number or upper bound on the number of defectives – has essentially been solved, with little room for further improvement.
グループテスト History and development
There is an open question as to when individual testing is minmax. Hu, Hwang and Wang showed in 1981 that individual testing is minmax when , and that it is not minmax when . It is currently conjectured that this bound is sharp: that is, individual testing is minmax if and only if . Some progress was made in 2000 by Ricccio and Colbourn, who showed that for large , individual testing is minmax when .
グループテスト History and development
One of the key insights in non-adaptive group testing is that significant gains can be made by eliminating the requirement that the group-testing procedure be certain to succeed (the "combinatorial" problem), but rather permit it to have some low but non-zero probability of mis-labelling each item (the "probabilistic" problem). It is known that as the number of defective items approaches the total number of items, exact combinatorial solutions require significantly more tests than probabilistic solutions — even probabilistic solutions permitting only an asymptotically small probability of error.
グループテスト History and development
In this vein, Chan et al. (2011) introduced COMP, a probabilistic algorithm that requires no more than  tests to find up to  defectives in  items with a probability of error no more than . This is within a constant factor of the  lower bound.
Chan et al. (2011) also provided a generalisation of COMP to a simple noisy model, and similarly produced an explicit performance bound, which was again only a constant (dependent on the likelihood of a failed test) above the corresponding lower bound. In general, the number of tests required in the Bernoulli noise case is a constant factor larger than in the noiseless case.
Aldridge, Baldassini and Johnson (2014) produced an extension of the COMP algorithm that added additional post-processing steps. They showed that the performance of this new algorithm, called DD, strictly exceeds that of COMP, and that DD is 'essentially optimal' in scenarios where , by comparing it to a hypothetical algorithm that defines a reasonable optimum. The performance of this hypothetical algorithm suggests that there is room for improvement when , as well as suggesting how much improvement this might be.
グループテスト Formalisation of combinatorial group testing
This section formally defines the notions and terms relating to group testing.
The input vector, , is defined to be a binary vector of length  (that is, ), with the j-th item being called defective if and only if . Further, any non-defective item is referred called a 'good' item.
is intended to describe the (unknown) set of defective items. The key property of  is that it is an implicit input. That is to say, there is no direct knowledge of what the entries of  are, other than that which can be inferred via some series of 'tests'. This leads on to the next definition.
グループテスト Formalisation of combinatorial group testing
Therefore, the goal of group testing is to come up with a method for choosing a 'short' series of tests that allow  to be determined, either exactly or with a high degree of certainty.
A group-testing algorithm is said to make an error if it incorrectly labels an item (that is, labels any defective item as non-defective or vice versa). This is not the same thing as the result of a group test being incorrect. An algorithm is called zero-error if the probability that it makes an error is zero.
グループテスト Formalisation of combinatorial group testing
denotes the minimum number of tests required to always find  defectives among  items with zero probability of error by any group-testing algorithm. For the same quantity but with the restriction that the algorithm is non-adaptive, the notation  is used.
グループテスト Formalisation of combinatorial group testing
Since it is always possible to resort to individual testing by setting  for each , it must be that that . Also, since any non-adaptive testing procedure can be written as an adaptive algorithm by simply performing all the tests without regard to their outcome, . Finally, when , there is at least one item whose defectiveness must be determined (by at least one test), and so .
In summary (when assuming ), .
グループテスト Formalisation of combinatorial group testing
A lower bound on the number of tests needed can be described using the notion of sample space, denoted , which is simply the set of possible placements of defectives. For any group testing problem with sample space  and any group-testing algorithm, it can be shown that , where  is the minimum number of tests required to identify all defectives with a zero probability of error. This is called the information lower bound. This bound is derived from the fact that after each test,  is split into two disjoint subsets, each corresponding to one of the two possible outcomes of the test.
グループテスト Formalisation of combinatorial group testing
However, the information lower bound itself is usually unachievable, even for small problems. This is because the splitting of  is not arbitrary, since it must be realisable by some test.
In fact, the information lower bound can be generalised to the case where there is a non-zero probability that the algorithm makes an error. In this form, the theorem gives us an upper bound on the probability of success based on the number of tests. For any group-testing algorithm that performs  tests, the probability of success, , satisfies . This can be strengthened to: .
グループテスト Formalisation of combinatorial group testing
Algorithms for non-adaptive group testing consist of two distinct phases. First, it is decided how many tests to perform and which items to include in each test.  In the second phase, often called the decoding step, the results of each group test are analysed to determine which items are likely to be defective. The first phase is usually encoded in a matrix as follows.
Suppose a non-adaptive group testing procedure for  items consists of the tests  for some . The testing matrix for this scheme is the  binary matrix, , where  if and only if  (and is zero otherwise).
グループテスト Formalisation of combinatorial group testing
Thus each column of  represents an item and each row represents a test, with a  in the  entry indicating that the  test included the  item and a  indicating otherwise.
As well as the vector  (of length ) that describes the unknown defective set, it is common to introduce the result vector, which describes the results of each test.
Let  be the number of tests performed by a non-adaptive algorithm. The result vector, , is a binary vector of length  (that is, ) such that  if and only if the result of the  test was positive (i.e. contained at least one defective).
グループテスト Formalisation of combinatorial group testing
With these definitions, the non-adaptive problem can be reframed as follows: first a testing matrix is chosen, , after which the vector  is returned. Then the problem is to analyse  to find some estimate for .
グループテスト Formalisation of combinatorial group testing
In the simplest noisy case, where there is a constant probability, , that a group test will have an erroneous result, one considers a random binary vector, , where each entry has a probability  of being , and is  otherwise. The vector that is returned is then , with the usual addition on  (equivalently this is the element-wise XOR operation). A noisy algorithm must estimate  using  (that is, without direct knowledge of ).
グループテスト Formalisation of combinatorial group testing
The matrix representation makes it possible to prove some bounds on non-adaptive group testing. The approach mirrors that of many deterministic designs, where -separable matrices are considered, as defined below.
A binary matrix, , is called -separable if every Boolean sum (logical OR) of any  of its columns is distinct. Additionally, the notation -separable indicates that every sum of any of up to  of 's columns is distinct. (This is not the same as  being -separable for every .)
When  is a testing matrix, the property of being -separable (-separable) is equivalent to being able to distinguish between (up to)  defectives. However, it does not guarantee that this will be straightforward. A stronger property, called -disjunctness does.
A binary matrix,  is called -disjunct if the Boolean sum of any  columns does not contain any other column. (In this context, a column A is said to contain a column B if for every index where B has a 1, A also has a 1.)
A useful property of -disjunct testing matrices is that, with up to  defectives, every non-defective item will appear in at least one test whose outcome is negative. This means there is a simple procedure for finding the defectives: just remove every item that appears in a negative test.
Using the properties of -separable and -disjunct matrices the following can be shown for the problem of identifying  defectives among  total items.
グループテスト Generalised binary-splitting algorithm
The generalised binary-splitting algorithm is an essentially-optimal adaptive group-testing algorithm that finds  or fewer defectives among  items as follows:
Test a group of size . If the outcome is negative, every item in the group is declared to be non-defective; set  and go to step 1. Otherwise, use a binary search to identify one defective and an unspecified number, called , of non-defective items; set  and . Go to step 1.
グループテスト Generalised binary-splitting algorithm
The generalised binary-splitting algorithm requires no more than  tests where
.
For  large, it can be shown that , which compares favorably to the  tests required for Li's -stage algorithm. In fact, the generalised binary-splitting algorithm is close to optimal in the following sense. When  it can be shown that , where  is the information lower bound.
グループテスト Non-adaptive algorithms
Non-adaptive group-testing algorithms tend to assume that the number of defectives, or at least a good upper bound on them, is known. This quantity is denoted  in this section. If no bounds are known, there are non-adaptive algorithms with low query complexity that can help estimate .
Combinatorial Orthogonal Matching Pursuit, or COMP, is a simple non-adaptive group-testing algorithm that forms the basis for the more complicated algorithms that follow in this section.
First, each entry of the testing matrix is chosen i.i.d. to be  with probability  and  otherwise.
グループテスト Non-adaptive algorithms
The decoding step proceeds column-wise (i.e. by item). If every test in which an item appears is positive, then the item is declared defective; otherwise the item is assumed to be non-defective. Or equivalently, if an item appears in any test whose outcome is negative, the item is declared non-defective; otherwise the item is assumed to be defective. An important property of this algorithm is that it never creates false negatives, though a false positive occurs when all locations with ones in the j-th column of  (corresponding to a non-defective item j) are "hidden" by the ones of other columns corresponding to defective items.
グループテスト Non-adaptive algorithms
The COMP algorithm requires no more than  tests to have an error probability less than or equal to . This is within a constant factor of the lower bound for the average probability of error above.
グループテスト Non-adaptive algorithms
In the noisy case, one relaxes the requirement in the original COMP algorithm that the set of locations of ones in any column of  corresponding to a positive item be entirely contained in the set of locations of ones in the result vector. Instead, one allows for a certain number of “mismatches” – this number of mismatches depends on both the number of ones in each column, and also the noise parameter, . This noisy COMP algorithm requires no more than  tests to achieve an error probability at most .
グループテスト Non-adaptive algorithms
The definite defectives method (DD) is an extension of the COMP algorithm that attempts to remove any false positives. Performance guarantees for DD have been shown to strictly exceed those of COMP.
The decoding step uses a useful property of the COMP algorithm: that every item that COMP declares non-defective is certainly non-defective (that is, there are no false negatives). It proceeds as follows.
Next the algorithm looks at all the positive tests. If an item appears as the only "possible defective" in a test, then it must be defective, so the algorithm declares it to be defective.
グループテスト Non-adaptive algorithms
All other items are assumed to be non-defective. The justification for this last step comes from the assumption that the number of defectives is much smaller than the total number of items.
Note that steps 1 and 2 never make a mistake, so the algorithm can only make a mistake if it declares a defective item to be non-defective. Thus the DD algorithm can only create false negatives.
グループテスト Non-adaptive algorithms
SCOMP (Sequential COMP) is an algorithm that makes use of the fact that DD makes no mistakes until the last step, where it is assumed that the remaining items are non-defective. Let the set of declared defectives be . A positive test is called explained by  if it contains at least one item in . The key observation with SCOMP is that the set of defectives found by DD may not explain every positive test, and that every unexplained test must contain a hidden defective.
The algorithm proceeds as follows.
If there are any unexplained tests, find the "possible defective" that appears in the largest number of unexplained tests, and declare it to be defective (that is, add it to the set ). Go to step 2.
In simulations, SCOMP has been shown to perform close to optimally.
グループテスト Example applications
The generality of the theory of group testing lends it to many diverse applications, including clone screening, locating electrical shorts; high speed computer networks; medical examination, quantity searching, statistics; machine learning, DNA sequencing; cryptography; and data forensics. This section provides a brief overview of a small selection of these applications.
グループテスト Example applications
A multiaccess channel is a communication channel that connects many users at once. Every user can listen and transmit on the channel, but if more than one user transmits at the same time, the signals collide, and are reduced to unintelligible noise. Multiaccess channels are important for various real-world applications, notably wireless computer networks and phone networks.
グループテスト Example applications
A prominent problem with multiaccess channels is how to assign transmission times to the users so that their messages do not collide. A simple method is to give each user their own time slot in which to transmit, requiring  slots. (This is called time division multiplexing, or TDM.) However, this is very inefficient, since it will assign transmission slots to users that may not have a message, and it is usually assumed that only a few users will want to transmit at any given time – otherwise a multiaccess channel is not practical in the first place.