extfieldsofstudy:
Computer Science
Medicine
Physics

text:
Competing neural networks: Finding a strategy for the game of matching pennies

The ability of a deterministic, plastic system to learn to imitate stochastic behavior is analyzed. Two neural networks -actually, two perceptrons- are put to play a zero-sum game one against the other. The competition, by acting as a kind of mutually supervised learning, drives the networks to produce an approximation to the optimal strategy, that is to say, a random signal.

I. INTRODUCTION
Since the connection between disordered spin systems and symmetric binary neural networks was drawn [1] intensive theoretical, numerical and experimental research has been devoted to this field within physics, and in the boundary of physics with biology and information theory, among others [2,3]. From the viewpoint of the study of dynamical systems, neural networks are a special kind of distributed active systems [4], which in their most impressive realization -the brain-are able to display extremely sophisticated collective behavior. Actual models have of course much more modest scopes but, in spite of their simplicity, they have been able to imitate some basic features of cognitive processes. These models have also been extended to perform specific tasks, such as for instance process control and forecasting [5].
A basic capability of a wide class of neural-network models is that of learning, i.e. the possibility of modifying the internal architecture of the network to adapt its dynamics to an expected response. This process can take a variety of forms, to be chosen according to the aims of the model. Pattern storing and recognition -the so-called associative memory-is perhaps the best known [6]. Another well known instance is learning by generalization. In this case, the network is exposed to some input information and the output is compared with the expected response. Errors are usually backpropagated to modify the network dynamics through a change in its architecture. The network thus learns from experience. It is expected that after a certain learning transient the network is able to produce the correct output even from inputs not included in the learning sample. This kind of learning can be carried on under supervision, or the system can be designed to learn in an unsupervised manner, by means of a selforganization mechanism [2][3][4].
In this paper, we explore a neural-network model of the learning that takes place during a competitive game. Competitive games have recently attracted a great deal of attention among physicists as simple models of adaptive evolution and selforganization in biological, social, and economical systems [7]. Neural networks have been designed and trained to play some highly complex games such as chess and backgammon [8]. The complexity of these games, however, does not allow a systematic analysis of the learning process or a statistical evaluation of the performance accomplished. On the other hand, too simple games -such as those that admit a pure optimal strategy [9]-should be readily solved by a suitably designed neural network. In fact, finding a pure strategy can be associated with a maximization problem.
Here, we focus the attention at an intermediate level, choosing a competitive zero-sum game with very simple rules but lacking a pure optimal strategy, v.g. the game of matching pennies. Two neural networks are left to repeatedly play the game against each other. The successive game results are used on-line to feed the learning mechanism of the two players. As in the case of human players, each network tries to guess the strategy of its opponent and, thus, competition becomes a kind of mutual supervision. The optimal strategy for the game of matching pennies is a purely stochastic one. Thus, the challenge for the networks, whose dynamics is fully deterministic, consists in approximating as close as possible a random evolution. Our analysis of the time series generated during the game shows that even small networks with simple architectures do quite well -probably better than any human being (not using a randomizing device) [10].
In the next section we describe in detail the game of matching pennies, and specify the architecture and learning dynamics of the competing neural networks. Section III is devoted to the study of the model as a timediscrete dynamical system -a mapping-with emphasis in its phase-space evolution. In Sect. IV, we analyze statistical properties of the dynamics during the game, evaluating the performance of the networks within an information-theory approach. Finally, we discuss our results and consider some possible extensions.

II. THE GAME AND THE PLAYERS
In the game of matching pennies, player I chooses among two possible instances, say "heads" or "tails." Player II, not knowing player I's choice, also chooses either "heads" or "tails." Then, the two choices are disclosed -for example, each player showing a penny-and, if they are the same, player I pays one cent to player II. If, on the contrary, the choices have been different, II pays one cent to I. The procedure is then repeated a large number of rounds, which has for instance been defined by a previous agreement between the players. In a less symmetric but very well-known realization of the same game, player II must guess in which hand has player I hidden a coin or any other small object. The pay-off rules are the same as for the game of matching pennies. Since at each round player I's loss (or gain) equals player II's gain (or loss), this is a zero-sum game. In game theory, a two-player zero-sum game is said to be a "strictly competitive" game [9].
As the game proceeds, we expect the two players trying to outguess each other, keeping their own strategies secret. Due to the high symmetry of the game of matching pennies, however, there is no optimal pure strategy for either player. Of course, it would be a most poor strategy for any player to choose the same instance at every time step. But, moreover, any deterministic way of deciding which instance should be chosen at a given time step could be disclosed by the opponent in the long run. On the other hand, trying to guess the opponent's strategy could lead an unsolvable, infinitely involved problem. As illustrated in [9], we may picture player I as thinking: "People usually choose heads; hence II will expect me to choose heads and choose heads himself, and so I should choose tails. But perhaps II is reasoning along the same line: he'll expect me to choose tails, and so I'd better choose heads. But perhaps that is II's reasoning, so..." In this way, it becomes impossible to determine a strategy in which either player could be confident. It follows that it is necessary for both players to introduce a mixed stochastic strategy where, at each time step, each player chooses an instance at random, with a certain probability distribution. The symmetry of the present game indicates clearly that the best strategy for both players is to choose heads or tails with equal probability. In the long run, this insures a zero average gain, whereas any other strategy implies a net gain for the opponent.
Our aim here is to study, as a dynamical system, a pair of competing neural networks playing the game of matching pennies. In particular, we are interested at analyzing whether the dynamics implies learning of an efficient strategy "on-line," i.e. as the game proceeds. Since the network dynamics and the learning algorithm considered in the following are deterministic, it cannot be expected that the networks will find the optimal (stochastic) strategy. However, it could be possible that the networks were able to approximate it by means of a complex determin- istic dynamics over a sufficiently long period. The basic idea in the learning process is that the playing strategy of each network should emerge from trying to guess the opponent's strategy. This is in fact the mechanism expected to drive the game between human players: though a general analysis of the game shows that the best way of playing is at random, each player tries to outguess the other assuming a deterministic strategy, at least, in the short term. The way of playing derives therefore from a (somewhat paradoxical) cooperative mechanism during the contest, where each player "supervises" the learning of the other.
As for the architecture of each neural network, we take the simplest model, namely, the perceptron, introduced in [11,12] and reviewed in standard books on neural networks (see, for example, [2,3,13]). It consists of a collection of N inputs s i (t) and of N synaptic weights w i (t) (i = 1, . . . , N ) which define, at each time step, a single output σ(t) as Here S is a step-shaped function, that we choose to be S(x) = sign(x). Thus, σ = ±1. We associate each of this two possible values of the output with the instance chosen by the network at a given time step, say, σ(t) = +1 for heads and σ(t) = −1 for tails.
We consider now two of these perceptrons (see Fig. 1), both with N inputs. At each time step, the output of one of the perceptrons should be determined by the outputs of the other at the precedent steps. Indeed, this is the information available to each player on the strategy of the opponent. We associate therefore the inputs s 1 i of perceptron I with the previous outputs σ 2 of perceptron II and vice versa, as i = 1, . . . , N . Time steps are of unitary length.
Learning is a consequence of the comparison of the outputs of the two perceptrons at each time. If the outputs are identical perceptron II wins, and the synaptic weights w 1 i of perceptron I are modified to produce a better prediction of the opponent's output at the next round. Meanwhile, the synaptic weights w 2 i of perceptron II can be left invariant, as they have led this perceptron to win the round. If, on the other hand, the outputs have been different, w 2 i are modified and w 1 i are maintained. A suitable algorithm for implementing this mechanism is the standard perceptron learning rule [2,3,13], which in our case implies and The Heaviside function Θ -where Θ(x) = 1 for x ≥ 0 and Θ(x) = 0 for x < 0-acts here as a mask, by selecting the perceptron whose synaptic weights are to be modified.
Suppose that the successive outputs of perceptron I are replaced by a periodic series of ±1 [14]. From the viewpoint of perceptron II, this is interpreted as the opponent's choice of a trivial strategy. As a matter of fact, the perceptron convergence theorem [2,11,15] insures that if N is large enough, i.e. if perceptron II's memory is sufficiently long-ranged, the learning procedure stops and, from then on, perceptron II wins all rounds. When the period of the output series of perceptron I is lower than N , in fact, it can be straightforwardly shown that there is at least one set of synaptic weights w 2 i that make perceptron II able to win at every round. The number of steps needed to compute these synaptic weights is of order N 3 [13], and can be tested numerically in our system. It is therefore not expected that when two large perceptrons are left to play freely one of them will adopt a shortperiod strategy.

III. THE SYSTEM AS A MAPPING: PHASE-SPACE DYNAMICS
Equations (1) to (4) define the dynamics of our system. They can be resumed in a 4N -dimensional recursive mapping for the perceptron inputs and the synaptic weights only. The recursion equations are The phase space corresponding to this mapping is discrete. In fact, the inputs s 1,2 i can adopt the two values ±1 only. Moreover, w 1,2 i can have real values but they vary on a discrete set, since according to Eqs. (3) and (4) the variation of the synaptic weights has always the same modulus, ∆w 1,2 = η. Once the initial synaptic weights have been fixed, the discrete set of their possible future values is completely determined.
During the evolution, the synaptic weights can in principle run over an infinite set. However, though the synaptic weights are not expected to converge to fixed values but to continuously evolve as the game proceeds, it is reasonable to conjecture that they will not perform arbitrarily long excursions in phase space. To prove this conjecture, let us consider in detail the evolution of the synaptic weights, given by the two last equations in (5) or, equivalently, by Eqs. (3) and (4). These two equations can be written, respectively, as and We now select one of the perceptrons and restrict the dynamics of its synaptic weights to the time steps where they are effectively modified, by simply ignoring the steps where no changes occur. The evolution equations can be written in vectorial form as where the components of w and s are the synaptic weights and the inputs of the selected perceptron, respectively. We recall that S(x) is the sign function. The scalar product w · s is defined in the usual way, cf. Eq.
Let us now consider for a moment that, in Eq. (8), the vector s is independent of time. Under this assumption it is possible to reduce the system (8) to two equations for the quantities p(t) = s · w(t) and q(t) = |w(t)| 2 , namely, It can be easily seen from the first equation that p(t) converges, after a certain transient, to a period-2 cycle. The two values of p on this cycle, p 1 and p 2 , satisfy the relation p 2 = p 1 − 1 + η. They depend on the initial conditions, but are always restricted to the intervals 0 < p 1 < 1 − η and η − 1 < p 2 < 0. Accordingly, q(t) oscillates between two values, q 1 and q 2 , defined by the initial conditions and related by q 2 = q 1 −2ηp 1 +η(1−η). After the transient, the modulus of the vector w is therefore restricted to vary within the interval In summary, for fixed s the evolution given by Eq. (8) drives the synaptic weights towards a bounded domain whose size depends on the initial condition but which is always finite. We stress that this is valid for any choice of s. Coming now back to the case of variable inputs, we note that the number of possible values for s(t) is also finite, and equals 2 N . Equation (8) can therefore be thought of as the application, at each time step, of one of the 2 N transformations just studied. Since each of them contracts the space of synaptic weights towards a bounded region, after the transient w(t) will always evolve within the union of all those regions. Disregarding transient effects, the space of synaptic weights is then finite. Hence, the accessible phase space of mapping (5) is finite and discrete.
As an illustration of the evolution of synaptic weights, we show in Fig. 2 with w = w/|w|. This recursion equation is analogous to the second of Eqs. (9). It can be seen that, for sufficiently large N , the average of | w(t) · s(t)| over time -or, equivalently, over random realizations of the vectors w and s-becomes independent of N and approaches the limit | w · s| = 2/π ≈ 0.798. From Eq. (10), this implies that for large N : cf. [16]. A better approximation for finite N is |w| = πN (N − 1)/8(N + 1) 2 . For N = 10 this gives |w| ≈ 0.540, which is the value plotted in Fig. 2. The average value of |w| provides an estimate for the size of the domain of phase space where the synaptic weights evolve after transients have elapsed. Note that the fact that |w| approaches a constant for large N implies that, in average, the synaptic weights are w 1,2 i ∼ 1/ √ N . The main byproduct of the fact that for our system phase space is finite and discrete is that, after the transient has elapsed, the orbits will be periodic. It becomes therefore relevant to determine the length of the periods. In fact, if it resulted that orbits get typically trapped in short cycles, the problem would at once get uninteresting. We have measured the periods numerically, carrying out extensive series of 100 to 1000 realizations 6.4 × 10 5 steps long, with N ranging from 2 to 10. Initial conditions were chosen at random, with the synaptic weights uniformly distributed in (−0.2, 0.2). The system has always been found to reach a periodic orbit for N < 7. For a fixed value of N , periods show typically a broad distribution. The average period has been found to increase exponentially with N , as shown in Fig. 3. For N ≥ 7, not all the realizations displayed periodicity, indicating the occurrence of periods longer than our numerical realizations. Some test realizations for N = 10 suggest that periods could grow beyond 10 8 steps.
The system thus seems to have two well-differentiated time scales. On the one hand, there should be a time scale associated with learning, of order N 3 . As stated above, in the case of a single perceptron being trained to predict a periodic series this is in fact the number of steps needed to compute all the synaptic weights. For the competing perceptrons, the length of the initial transient during which the system explores phase space to find the bounded region where it will evolve later, should be of the same order. On the other hand, we have a much longer "recursion" time scale, of order A N (A ≈ 5.05, Fig. 3), associated with the periods of orbits inside that region. Though the two-perceptron dynamics is dissipative, it resembles in this aspect that of Hamiltonian systems with many degrees of freedom. Indeed, according to Poincaré's theorem [17], Hamiltonian systems are recurrent and, at sufficiently long times, they visit an arbitrarily small neighborhood of their initial state. However, in a statistical description of their evolution, it is possible to identify much shorter time scales, related to the relaxation of fast variables [18].
At the level of recursion time scales, the dynamics of the two-perceptron system is in a sense trivial. Orbits are in fact periodic at long times, and the results of successive game rounds will be repeated ad infinitum. When, during a whole period, one of the perceptrons is able to gain even the smallest advantage over the other, this small difference will continuously accumulate producing, in the long run, an arbitrarily large bias in the result of the game. As in the case of large Hamiltonian systems, however, recursion times are far beyond the reach of our (numerical) experience as the size of the perceptrons increases. Therefore, most of the realizations of the two-perceptron game analyzed bellow will always be restricted to the transient period, previous to the appearance of periodicity. In this stage, the relevant time scale is the learning time, of order N 3 . Within such times we expect the system to reach a kind of stationary playing regime where, if the learning algorithm is efficient, the outputs of the two perceptrons should imitate a random series of ±1. In the next section we study the statistical properties of these output series.

IV. STATISTICAL ANALYSIS OF THE GAME DYNAMICS
Random properties in time series can be characterized in a variety of ways. In our case, where the relevant series are arrays of ±1, a suitable measure of time correlations is an information-like quantity [19]. As shown below, this quantity can be used to characterize the correlation between different series and, consequently, the correlation of a series with itself. It has the advantage of being additive, and is therefore appropriate when comparing numerical results. We thus begin by defining the mutual information of two time series.
Consider two dichotomic stochastic processes S 1 and S 2 that, at each time step, can adopt the values ±1 with certain probability distributions. Let P (S 1 , S 2 ) be the joint probability for the processes, and P 1 (S 1 ) = S2 P (S 1 , S 2 ) and P 2 (S 2 ) = S1 P (S 1 , S 2 ) their individual (marginal [20]) probabilities. A measure of the correlation between the two processes is given by the mutual information [19], defined as .
In practice, for a finite realization of the stochastic processes, the probabilities involved in Eqs. (12) and (13) are approximated by the corresponding frequencies, which can be computed by simple counting of the relevant occurrences. This approximation implies that in the case of uncorrelated processes the information can differ from zero, due to fluctuations in the finite sample under consideration. It can be shown that for a T -step realization of uncorrelated stochastic processes where the individual probabilities of the two possible values ±1 are equal, P (+1) = P (−1) = 1/2, the probability distribution for the information to have a value I is for small I. The resulting mean value of the information is values for the information computed from finite samples of size T and its average are to be respectively compared with p T (I) and I in order to detect the presence of correlations.
We now consider two playing perceptrons with N = 10, and apply the definition of autoinformation (13) to any of the two series of outputs, S(t) ≡ σ 1,2 (t). The outputs are recorded after the first 10 4 steps have elapsed, in order to avoid nonstationary transient effects during the first stage of learning (of order N 3 [13]). The recorded series are T = 10 4 steps long, and the results presented below correspond to averages over 5 × 10 4 realizations. Figure 4 shows the measured average autoinformation as a function of τ . The horizontal line corresponds to the average autoinformation (15) expected for an uncorrelated series with the present value of T , i.e. I ≈ 7.2×10 −5 . We first note that, except for τ = 2 and 4, the autoinformation of the output signal is always less that twice the value of I for a random series. This implies that each perceptron exhibits a quite good performance in generating a random sequence. There are however certain regular patterns that suggest the presence of small but nontrivial correlations. Indeed, the average autoinformation oscillates strongly for small τ , reaching high levels for even values of τ and dropping abruptly for odd values of τ . On average, these oscillations decrease as τ grows, but they reappear near τ = 20 and 30. Realizations for other values of N indicate that the oscillation amplitude decreases as N grows, and that the "bursts" at which oscillations reappear occur when τ approaches integer multiples of N . The amplitude of these bursts decreases for larger multiples. . For τ = 1 practically no correlations are detected by the autoinformation. We note only a slight overpopulation for large I. On the other hand, for τ = 2, which corresponds to the largest deviation in the average autoinformation (see Fig. 4), the distribution is qualitatively different. It exhibits a maximum at a rather large value of the autoinformation (I ≈ 2 × 10 −3 ) and, except for small values of I, it is systematically much larger than the distribution expected for a random series. At τ = 10, the distribution has a profile similar to that observed for τ = 1, but the overpopulation at the tail is noticeably larger. This overpopulation grows further during the bursts where oscillations reappear. The plot for τ = 20 shows the distribution at the first of these bursts. In contrast, for the intermediate values at which the average autoinformation plotted in Fig. 4 reaches the information of a random series, the corresponding distribution cannot be distinguished from p T (I).
We have found that the oscillations of the average autoinformation shown in Fig. 4 are essentially a byproduct of the internal dynamics of each perceptron. In fact, if instead of using the opponent's output, a perceptron is fed with a random series of ±1, the autoinformation of its own output oscillates as well. A detailed analysis of the output series reveals that, for even τ , the product σ(t)σ(t+τ ) is more frequently negative than positive. For instance, for τ = 2, the respective frequencies are about 0.52 and 0.48. We remark in passing that this small relative difference -of the order of a few percent-produces an increment larger than one order of magnitude in the autoinformation, which evidences the sensibility of this quantity as a measure of correlations. For larger values of τ , the difference is even smaller. On the other hand, for odd τ no differences are detected.
In order to trace the origin of the correlations observed for even τ , a careful analysis of the learning algorithm has to be carried out. We consider first the case of τ = 2. After two time steps, the vector of synaptic weights can be written as where θ(t) = 1 if the weights have been modified at time t, and θ(t) = 0 otherwise [cf. Eq. (8)]. When the perceptron if fed with a random signal, θ(t) can be seen as a stochastic process with equal probabilities for its two values. The product of the outputs two steps apart is Numerical measurements of the right-hand side (r.h.s.) of this equation show that the first two terms in the argument of the sign function have zero mean and do not produce a net contribution to the sign of σ(t)σ(t + 2). The only contribution to the correlation is originated in the third term. To verify this fact analytically, we first note that The first of these identities results from the fact that, as shown in the previous section, w i ∼ 1/ √ N whereas, according to Eq. (5), its variation in one time step is given by η ∼ 1/N . The second identity can be readily proven from the evolution of s i (t), also given in Eq. (5). Consequently, neglecting terms of order 1/ √ N , the sign of the product σ(t)σ(t+ 1)s(t+ 1)·s(t+ 2) can be approximated as follows: Note that the argument of the sign function in the r.h.s. of this equation is likely to be positive, since it is given by the product of the projections of two vectors, s(t) and s(t + 1), along the direction of w(t) times their mutual scalar product. More explicitly, with s w = w · s and s ′ = s − s w w. The first term in the r.h.s. of this equation is always positive, whereas the second term is not expected to have a definite sign on average. Note moreover that the first term is of the order of unity, whereas the second term is of order √ N . This implies that the relative importance of the positive contribution decreases as N grows. Coming now back to Eq. (17) through Eq (19) it is clear that, when the synaptic weights are modified at time t+1 (i.e. θ(t+1) = 1), there is in average a negative contribution to σ(t)σ(t+ 2), in agreement with numerical results. According to the above analysis, this correlation should become less important as N grows. In fact, the autoinformation peak at τ = 2 is observed to decrease in the simulations.
For arbitrary τ , the analysis can be repeated mutatis mutandis. We have Taking now into account that the sign of the product σ(t)σ(t + t ′ )s(t + t ′ ) · s(t + τ ) in the sum of Eq. (21) can be approximately written as The argument of the sign function in the r.h.s. of this equation has a positive contribution of the same type as in Eq. (19) when t + t ′ = t + τ − t ′ , i.e. for τ = 2t ′ . Therefore, in the realizations where θ(t + τ /2) = 1 a negative contribution to σ(t)σ(t + τ ) appears. This of course requires τ to be even. Since other contributions have no definite sign, peaks in the average autoinformation are expected for even values of τ , as observed. Note moreover that the order t ′ /N of the terms neglected in Eq.
(23) increases with t ′ , i.e. with τ . This explains why the height of the peaks decreases as τ grows. Along the same line of analysis, it is possible to explain the bursts where the autoinformation peaks reappear. Now, however, it is necessary to take into account both perceptrons. In fact, the output of a single perceptron fed with a random signal does not exhibit such bursts. They are rather a consequence of the interaction between the two perceptrons during the game. The analysis, whose details we omit here, shows that bursts are originated by a kind of bouncing effect in the transmission of information between the opponents. This bouncing effects is attenuated as τ grows, and decreases for larger perceptrons, as observed in the numerical simulations.
In summary, the statistical analysis of perceptron outputs at time scales larger than the learning stage but much shorter than the recursion times, reveals that the perceptrons are quite efficient players of the game of matching pennies. Even with a relatively small number of inputs, i.e. with a relatively short-ranged memory, their dynamics is able to generate quasi-random mixed strategies. We recall that this behavior originates spontaneously from the deterministic learning algorithm with which each player is endowed to outguess its opponent. Remaining correlations, which could in principle be exploited by a "smarter" opponent to obtain a net gain during the game, are overall small and can in fact be reduced systematically by increasing the memory range.

V. DISCUSSION
We have here considered an example of a fully deterministic learning system and explored its ability to behave stochastically. Concretely, we have coupled two deterministic perceptrons in such a way that they imitate two players of the game of matching pennies, trying to outguess each other. Since the optimal strategy for this game is a purely stochastic sequence of outputs, the learning process should lead the network dynamics to approach a random signal.
In the first place, we have observed that a perceptron producing a periodic signal can always be defeated by a sufficiently "smart" opponent, i.e. by a perceptron with a sufficiently large number of neurons. This kind of "dummy" player provides in fact a linearly separable set of examples for the learning of its opponent [2]. The learning task is thus to find a plane in the input space that separates the input states into two groups, namely those whose expected outputs are either +1 or −1. On the other hand, when the two competing perceptrons are allowed to learn the situation is pretty much different. Since both networks are looking for the best performance, they both change their strategies on line and, thus, they may well provide not only a nonlinearly separable set of examples, but also an inconsistent one. That is to say, at two different times any perceptron can give two different outputs from the same input state. This is the reason why the learning process does, in fact, not converge, and why the system is expected to spontaneously develop stochastic-like dynamics.
Our main conclusion is that, despite the fact that the overall dynamics is in the long run periodic, the perceptrons do learn to behave quasi-stochastically over moderately long time intervals. An information-theoretical statistical analysis of the output signals shows slight time correlations, to be ascribed to the deterministic coupling between the learning mechanism and the outputs themselves, which act as the inputs of the respective opponents. The effect of these correlations is observed to decrease gradually as the number of neurons in each per-ceptron grows. Two seemingly paradoxical aspects of this learning process deserve to be pointed out, because of their suggestive similarity with learning in humans (or other animals) entrained in a systematic activity such as a repetitive competition game. In the first place, the mutual search for regularity in the opponent's behavior leads the whole system to develop highly irregular evolution over long times, which can hardly be distinguished from purely random dynamics. In the second place, we stress that competition can here be interpreted as a form of mutually supervised learning and, thus, results in a kind of collaboration between the opponents.
Some natural extensions of the present model are worth considering for future work. An important question to be addressed regards the case where the entangled perceptrons are not equal in size, i.e. they have different numbers of neurons. In such a situation, in fact, the above quoted correspondence of competition and collaboration could fail to hold. Preliminary results along this line (not presented in this paper) suggest however that the advantage of a larger perceptron is relatively small. Only very small networks (N ∼ 2) are systematically defeated by larger opponents, as they typically fall in short-period cyclic orbits.
The perceptron-like structure of our networks is probably the simplest instance among a large class of possible architectures. Fully connected networks and multilayer structures have been shown to exhibit very high performance in learning tasks [2,3,19]. It would therefore be interesting to study how these more complex networks respond to mutually supervised learning. Finally, from the viewpoint of game theory, it would be relevant to analyze the dynamics of competing networks engaged in other games, especially, when ordinary optimization procedures do not lead to the optimal playing strategy. We mention, in particular, the iterated prisoner's dilemma [21], which is attracting a great deal of attention as a paradigm of competition-collaboration interplay, and multiplayer minority games, recently studied by means of ensembles of globally coupled perceptrons [22]. Competing neural networks could contribute to a better understanding of the complex learning mechanisms involved in such kind of social interactions.


Many uses, many annotations for large speech corpora: Switchboard and TDT as case studies

This paper discusses the challenges that arise when large speech corpora receive an ever-broadening range of diverse and distinct annotations. Two case studies of this process are presented: the Switchboard Corpus of telephone conversations and the TDT2 corpus of broadcast news. Switchboard has undergone two independent transcriptions and various types of additional annotation, all carried out as separate projects that were dispersed both geographically and chronologically. The TDT2 corpus has also received a variety of annotations, but all directly created or managed by a core group. In both cases, issues arise involving the propagation of repairs, consistency of references, and the ability to integrate annotations having different formats and levels of detail. We describe a general framework whereby these issues can be addressed successfully.

Introduction
Any well-constructed corpus of speech data can provide a valuable resource for a wide variety of uses in language research and technology development, especially if the corpus is centered on common and naturally-occurring speech events. Both the potential and the motivation for re-use increase with the size of the corpus: larger corpora provide a better representation of linguistic diversity and variability, and so are richer objects of study for any research goal; also, the expense and effort that go into the creation of a large corpus, typically on behalf of a particular research program, can provide powerful leverage for researchers involved in other projects or areas of study.
It is often the case that a new use of a corpus will require a new annotation that was not part of the initial corpus creation effort. But for large corpora, it often happens that the new annotations can be applied only to subsets of the collection, depending on the difficulty of the new task and the resources available to carry it out. In this case, it becomes increasingly important, and increasingly difficult, to maintain the coherence of shared resources.
The Linguistic Data Consortium (LDC) has been involved in managing multiple annotations of two large speech corpora: the Switchboard Corpus of conversational telephone speech (SWB), and the Topic Detection and Tracking corpus of broadcast news (TDT). In the case of SWB, the original corpus creation and all subsequent annotations have been done by others outside the LDC, and we have acted simply as the central point of contact and access for all users and annotators; in the case of TDT, LDC personnel have been responsible for most forms of annotation done so far.
The following sections will review these corpora in terms of their overall content, the particular types of annotations that have been applied to them so far, and the relative coverage of those annotations (including the overlap that exists among them). We then discuss some of the problems that arose due to localized data repairs that were applied in some annotations, and measure the extent of referential consistency among the diverse annotations. Finally, we describe how the application of annotation graph structure to the various derivative data sets provides a powerful and flexible means for comparing and integrating their contents.

The Switchboard Corpus
Switchboard-1, the first large collection of spontaneous conversational speech over the telephone, was collected in 1990 by Texas Instruments (TI) (Godfrey et al., 1992). The current published corpus comprises 2438 calls involving 520 native speakers of American English, recruited from all over the United States. The calls range between five and ten minutes in length, and each call contains a unique pairing of speakers. Individual speakers are designated by identification numbers, and information is provided as to their gender, age, education and dialect region. On average, each speaker appears in about nine calls (the range of calls per speaker varies between 1 and 32).
The speech data for each call is provided in the form of a two channel interleaved sample file; the two channels, designated "A" and "B", represent the mu-law encoded signal received from the telephone handsets of the two speakers participating in the call.

Initial transcription
TI created an initial set of manual transcripts, employing professionally trained transcribers equipped with analog tape copies of the sample files. These transcripts were then submitted to an automatic speech recognition (ASR) process to establish approximate time alignments at the word level.
The initial publication of the corpus in 1993 contained 2288 calls on 25 CD-ROMS (additional calls were being held in reserve at that time for future use as test data). A separate CD-ROM provided the transcripts in two forms (two files per call): (1) the original text files as created by transcribers, including a generic header with information about the call, and speaker designations ("A" or "B") for each turn in the dialog, but no time annotations; (2) the time-aligned version of the text, with one word token per line, accompanied by the speaker designation, and the beginning time and duration of the word. The transcript release also included documentation and tables describing the corpus content.
Given the size, complexity and novelty of this effort, a variety of problems affected the first release of the corpus by the LDC: In about 200 calls, the transcribers had made mistakes in assigning the speaker labels ("A" or "B") to some or all of the turns in the transcripts. Because the speaker label is intended to represent the signal channel in the speech file, an error in the speaker label would direct the corpus user to the wrong channel when retrieving the audio data for a given turn in the dialog.
Other more typical kinds of errors, involving misperceptions by transcribers about what was said, presumably affected nearly all files, but only to a very small degree.
The ASR word alignment was applied to a singlechannel (combined) version of the speech data, and so was not affected by speaker label errors, but it was relatively ineffective in regions where turns overlapped in time, and where the transcript contained omissions, additions or substitutions of words relative to what had been spoken.
In about 30 calls, the two forms of transcript data did not match up in terms of the number of speaker turns present in the dialog.
For about 30 additional calls, some or all of the transcript data were absent from the publication, because the text files were missing, incomplete or corrupted due to errors in preparing the publication.
In 1994, the LDC released an "interim" version of the transcripts, fixing all cases of the last two types of problems, and about one quarter of the files containing known speaker-label errors (particularly, those files where the label errors were limited to small portions of the transcript). The remaining speaker-label problems were documented as well as possible, but were not fixed, nor was any attempt made to correct other transcription or time-alignment errors.

Subsequent annotations
Since the initial release of SWB transcripts, a number of research sites have used this data, either with or without reference to the speech, as input to a range of divergent annotation projects. These are briefly described below, in roughly chronological order. Some of the resulting annotations are displayed in Figure 1.

Phrase-level time stamps (BBN)
The first application of SWB data for research in large vocabulary conversational speech recognition was in conjunction with the DARPA LVCSR project. In preparation for initial training on SWB, researchers at BBN created a modified version of the original TI transcripts, and circulated this among the LVCSR participants. The modification involved forming time-stamped "phrasal" regions from the word-level time-aligned transcripts, and assigning a unique identifier to each region. This produced a segmentation of the dialogs that differed from the turn units created by the original transcribers: a single time-stamped phrase might encompass parts of two consecutive turns, if the original transcriber had broken up the phrase in order to insert an interruption by the other speaker; also, multiple time-stamped phrases might be derived from a single turn, if that turn was considered too long for reliable ASR processing. The speaker-label errors mentioned above were not repaired in this process (though a list of affected files was circulated among LVCSR participants). This form of the transcripts has never been made available through the LDC.

Disfluency annotation (Penn Treebank Project)
As a preliminary step to prepare for Treebank annotation, 650 transcript files were selected from the LDC "interim" release and annotated for various types of disfluency that occurred in the spontaneous speech. This annotation was essentially text-based, relying entirely on the representation of disfluencies in the (non-time-aligned) transcripts (see Figure 1). The objective was to tag hesitations, stutters, word fragments, restarts, and a limited class of discourse markers, since these elements in the transcripts would constitute exceptions or barriers to syntactic analysis. These annotations are included in the current "Treebank 3" corpus, available from the LDC.

POS-tagging, parsing (Penn Treebank Project)
Building on the output of the disfluency annotations, the Penn Treebank Project applied part-of-speech tagging and syntactic parsing to the 650 files that had been selected (see Figure 1). In the course of this annotation, a small number of corrections were made to the text data, consisting mostly of repairs to punctuation and replacements of some incorrect words. Again, this annotation was done without reference to the audio data. It is currently available as the "Treebank 3" corpus.

Discourse annotation (Univ. of Colorado, SRI)
This annotation project set out to "model the speech act type of each utterance" and "model sociolinguistic facts about conversation structure..."  It builds on the disfluency annotation mentioned above, using the same conceptual basis for segmenting dialog turns into phrases ("utterances") that are cohesive in terms of the speech acts being performed. An exhaustive segmentation of such utterances was carried out on 1155 conversations, and each utterance was categorized as to speech act or discourse function. All 650 files covered by the Treebank Project are included in this set. The data is available directly from the University of Colorado (Jurafsky, 1997).

Phonetic transcription (ICSI)
The International Computer Science Institute (ICSI) at the University of California, Berkeley, began a project in
The initial stage of the project assigned time marks at the level of segmental boundaries, as well as syllable and word boundaries. In the second phase, time boundaries were applied at the word and syllable levels. Throughout the project, the labels assigned to phonetic segments (whether time marked individually or at the syllable level) were intended to accurately reflect the actual pronunciation in the signal, to a much finer level of detail than in previous corpora (e.g. TIMIT or the Boston University Radio corpus).

Complete resegmentation (ISIP)
In view of the importance of SWB as a multi-functional corpus, and the difficulties that have accompanied the original transcripts, an important effort was launched at the Institute for Signal and Information Processing (ISIP) at Mississippi State University, to conduct a complete review of the transcription data, applying a new speech transcription tool developed at ISIP with particular attention to locating known types of problems and avoiding known pitfalls in this type of annotation effort. By the time this project began, the SWB calls that had previously been held back as test data had been used over the course of several benchmark tests in the LVCSR project, and were now available for publication. The current release of SWB speech and transcript data now comprises 2438 calls. By agreement with the LDC, ISIP has made the complete set of SWB transcripts freely available on their web site (Mantha, 2000).

Rectification and Integration
With the completion of the ISIP review of SWB transcripts, it is now possible to assess the impact of transcription errors on the various divergent annotations. As an initial step to check for the magnitude of errors involving lexical content, we treated the LDC "interim" transcripts as a test set to be measured for error rates, using the ISIP transcripts as the reference text. Comparable versions of the two data sets were constructed by aligning the phrase-level ISIP time marks with the original TI word-level time marks, and the NIST scoring tool "SCLite" was used to calculate insertions, deletions and substitutions. The results are summarized in table 1. 1 It should be noted that word fragments and non-lexical tokens (e.g. "uh-hum" vs. "uh-huh") accounted for roughly 30% (over 19,000) of the substitution errors, and about 21% (nearly 34,000) of the insertion and deletion errors. The comparison of ICSI annotations to the other versions of SWB transcripts is somewhat more problematic. ICSI transcribers made corrections to the lexical content in accordance with their more detailed attention to the actual pronunciation of phrases, but they used different conventions regarding word hyphenation and disfluencies, and occasionally inserted annotations for non-linguistic events (e.g. "breath", "mouthnoise", etc.) without the intended markup to distinguish these from lexical tokens. Still, we can estimate the upper bound on the number of corrections imposed by ICSI, again using the NIST SCLite scoring method. In this case, the LDC transcripts contained 96% of the words in the 3.5 hours of ICSI word-level data -there were, at most, 2% omissions and 2% substitutions in the LDC transcripts.
ICSI's use of the BBN phrasal time marks as the basis of phrase selection creates some additional difficulties: Correlation with original TI word-level time marks is imperfect at best; insertion errors predominated in scoring the LDC transcripts (6.2%, three times more than deletions or substitutions), yielding an overall word accuracy of 89.2%. This was due mostly to discrepancies at phrase boundaries.
Some of the BBN "phrase boundaries" occur at impractical positions within syllables, causing some boundary tokens to be interpreted differently. Until a reliable word-level time marking is done for the ISIP transcripts, there will be no reasonable way to align the ICSI and ISIP annotations, due to significant differences in phrase segmentation.
Overall, these tabulations indicate that the lexical accuracy of the original TI transcripts was quite high, and the impact of word errors on downstream annotations, particularly the Treebank and discourse data, may be considered negligible.
A major challenge remains, however, in terms of integrating the various annotations. All three versions of timemarked transcripts (LDC "interim", ICSI and ISIP) assign unique identifiers to each turn or phrase unit, but each set has a distinct inventory of units that cannot, as yet, be crossreferenced to the other two sets in any reliable way. The only stable point of reference is the audio data, and the use of time offsets into the speech files.

The TDT Corpora
The design and content of the TDT corpora are described in other presentations at LREC-2000 (Wayne, 2000;Cieri et al., 2000). The present discussion will focus on the range of distinct annotations applied to the data, the relationships among them, and the problems involved in coordinating them.

Multiple data streams from audio and text sources
The audio recordings of broadcast (video and radio) sources in TDT were used to create a variety of textual data streams. For video sources (which have all been in English), the broadcast signal included closed-caption text data, which was converted to computer-readable form while the audio was being digitized; also, one video source (ABC News) provided full transcripts of its daily broadcasts to the public through a commercial transcription service. It is well known that closed-caption text tends to be incomplete relative to what is actually spoken during a broadcast, because the maximum practical display rate, in words per minute, is slower than typical rates of speech. The full transcripts produced by commercial services, which are intended for use as a standard public record of broadcast content, are lexically correct to a high degree of accuracy, though they typically avoid the inclusion of any disfluencies -the text represents only what the speaker intended to say, and omits filled pauses, false starts, stutters, and the like. On the basis of this one source, then, it is possible to estimate a baseline of "word error rate" for closed-caption text, which can be useful when assessing other sources for which only the closed-captions are available.
The radio sources in TDT did not have publicly available transcripts, and four different transcription services were enlisted to transcribe these programs as part of the corpus creation effort (one for all TDT Mandarin data, one for TDT3 English, and two others for TDT2 English). The services varied in terms of the quality of transcripts delivered, with one of the TDT2 English services having been poorest.
In addition to manual transcription, all audio sources were submitted to unguided ASR, to establish a benchmark of TDT system performance given this quality of text as input. The TDT2 English data was submitted to two different English-based ASR systems; of course, in the absence of fully accurate manual transcriptions for most of this material, it remains difficult to compare their performance in terms of word error rate.
For all Mandarin sources, both newswire text and radio transcripts, additional data streams were produced by running the data through a Chinese-to-English machine translation system (SYSTRAN), with no manual guidance or revision of the system output. For audio data, both the manual and ASR transcriptions were translated in this way. Again, this was intended to set a benchmark for cross-lingual TDT performance given this quality of input.
As a result, most data sources were represented by at least two parallel, independent data streams -a couple of sources had three or four streams -each with its own peculiar properties and token sequence. The stable points of reference across all streams were the boundaries between news stories, and in the case of audio sources, the time offsets of those boundaries in the speech data.

Creating and tracking multiple annotations
A relational database was used to track the main stages of data creation and TDT-specific annotations. The basic units of the corpus are the sample file and the topical story unit. For audio sources, an entry was created each time a recording process was scheduled; the entry was updated at the conclusion of the recording, updated again after manual inspection to determine whether the recording was successful, and again after manual segmentation of the 30-or 60minute file into story and non-news segments. This done, each story was assigned a unique identifier, which included the source, date, broadcast start time, and time offset within the file at the start of the story, and these identifiers were entered into the database to guide the topic annotation. (The equivalent stages for newswire data were fully automated to prepare the stream or bulk archive text data for topic annotation.) During the main topic annotation phase, in which every story had to be read some minimum number of times to assess it against all selected TDT topics, annotators also had to decide whether a given story was flawed in any of four ways, making it unsuitable for topic labeling. In the newswire data, a reported flaw would typically result in the removal of a story from the corpus, but for broadcast data, a flaw would generally be the result of a mistake during the manual story segmentation phase. Broadcast stories could not simply be discarded, as this would create gaps in the coverage of the continuous audio signal -segmentation errors needed to be fixed, and this would affect the inventory of news stories in the file, and/or the locations of boundaries (hence the identification numbers assigned to the stories would change, as well).
A further complication was the need in TDT3 to support alternative methods of topic annotation while the main annotation was still in progress. These alternative forms of labeling -first-story detection and story-link detection -were not actively tied into the database management of the main topic annotation; rather, they used a snap-shot of the corpus, taken as late and as carefully as possible during the main annotation. Fortunately, they would involve only a subset of the full TDT3 corpus, so it was possible to avoid particular files or stories where problems had been observed, and still provide an adequate sample. Despite our best efforts, some of the results of these alternate annotations could not be used in the final delivery of the corpus, because the stories to which they applied had been altered or removed in the course of repairs prompted by the main annotation; in particular, 0.5% of the 21,600 story link annotations were discarded because a number of stories had been eliminated from the corpus.
Additional uses of TDT data have already begun, spurring new annotations that were not part of the original corpus design. In order to establish a better estimate of ASR performance on this data set, NIST selected a random sample of 530 individual news stories from the TDT2 English corpus, totaling 10 hours of speech. The LDC adapted the text for these stories to the Hub-4 transcription specifications for broadcast news, and carefully went over each story, adding in the missing words and disfluencies, correcting spelling errors (common in closed-caption text), and adding time stamps to break long turns by news announcers into manageable phrases. This 10-hour set of careful transcription is now available from the LDC.
Other directions for annotation of TDT have included the identification of named entities, in support of the TREC project and related research, and the identification of new information across a sequence of stories on a given topic.
In a sense, each of these various annotations could be said to stand on its own as a sample for modeling a particular characteristic of language behavior or information flow. But research tasks moving along these various lines will tend to intersect, and it will be important to know to what extent their respective annotations intersect as well. The same crew may be handling the annotations for, e.g., first story detection, marking of new information, and named entity extraction, but these tasks might not be carried out in unison (indeed they typically will not), they might be applied to discrete subsets of the corpus, and even if they do overlap on some sampling of the data, it might not be immediately obvious how to integrate these different annotations. Needless to say, it would not seem improbable that

Annotation Graphs as a Means of Integration
Annotation graphs were introduced by Bird and Liberman (Bird & Liberman, 1999a) as a convenient data model which abstracts away from the many contingent details of corpus file formats. An important consequence of this move, explored by Bird and Liberman (Bird & Liberman, 1999b), is that multiple independent annotations of a single corpus can be accessed and analyzed simultaneously. In this section we discuss the case of SWB, and the data shown in Figure 1. Figure 2 shows the annotation graph for this SWB data, corresponding to the interval [21.86, 26.10]. In this graph, word arcs have type W/, Treebank arcs have T/ and disfluency arcs have DISF/ type. Types for the part-of-speech arcs have been omitted for sake of clarity (i.e. Pos/metric/JJ is written as just metric/JJ). For readability, the graph is represented in two pieces; the lower piece should be interpolated into the upper piece at the position of the dotted arc labeled X. Observe that the equivocation about the tokenization of punctation from Figure 1 is preserved in the annotation graph.
The ability to merge diverse layers of independent annotations into a single graph derives from the definition of nodes for connecting the arcs. The nodes are anchored at specific points along a time line representing the signal being annotated. In SWB, the LDC interim transcripts, the ICSI phonetic transcripts, and the ISIP revised transcripts each represent a distinct segmentation of the time lines for the corresponding signals. The migration of these data sets into annotation graphs provides a stable, timeanchored basis for cross-reference; owing to the divergent turn-or phrase-level segmentations provided by each data set, the time line is in fact the only practical basis for crossreference.
Even though the phonetic transcripts cover only sparse portions of most calls, these partial annotations for any one file can be mapped coherently onto a single complete graph that includes the other transcripts in their entirety, providing a well-defined algorithmic approach for locating and resolving discrepancies in lexical content, phrasal segmentation, and word-level time alignments. The disfluency, discourse and Treebank annotations are derived from the LDC transcripts, and as demonstrated above, they can also be incorporated into the one graph, making it quite simple to identify the particular elements in those annotations that will be affected by corrections to the underlying transcripts. It follows that the propagation of transcription repairs through all levels of annotation becomes a well-behaved and accountable process.
Apart from the obvious benefits to corpus maintenance, this approach to handling annotations provides an important capability for integrating the results of diverse annotation efforts in new research. If and when a prosodic annotation of SWB becomes available, we can readily envision the ability to study interactions among intonational focus, discourse function, syntactic structure, and phonological processes, simply by adding the one new layer to the existing network of other annotations.
The application of annotation graphs to TDT is equally fruitful. The stability of reference to the basic units of TDT corpora (sample files, news stories, word tokens) is already well established, owing to the fact that the corpus creation effort has been tightly centralized. But due to the overall bulk of the data, most new annotations, especially those requiring human judgment, are likely to be limited to cover only portions of the collection. Again, these partial annotations can form coherent annotation graphs on their own, and can be treated atomically or integrated with other graph structures as needed.
The issue of data formatting for creation, storage, distribution and research use of annotations is an independent concern, orthogonal to the use of annotation graphs as a framework for handling corpora. The arc-and-node structure can be rendered into (and retrieved from) a very simple XML data stream, and it is equally possible to create filters that can populate an annotation graph by reading any chosen data format, without loss of information. Filters could also be made to create a chosen data format from an annotation graph, though it's possible that some information in the graph would not be preserved in the process.

Conclusion
We have presented an overview of two large speech corpora, both of which have received a wide range of divergent and independent annotations. For Switchboard, we have discussed some details about the comparability and compatibility of the various annotations, and have presented an analysis framework that will enable a high degree of integration among them, in terms of both maintenance and research use. The case of TDT demonstrates that even with a centralized corpus creation effort, there can still be problems with handling data repairs and consistency when distinct sets of annotation must be carried out simultaneously. Both corpora present the need to accommodate sparse annotations in a manner that does not sacrifice the overall coherence of the larger corpus. Annotation graphs provide an effective framework for meeting this need.


s2fieldsofstudy:
Computer Science
Mathematics

text:
Search for Three Forged Coins

Suppose we are given a set of t coins which look identical, but a known number s of them are counterfeit, with a known weight different from the others. Our problem is to locate the counterfeits by weighing subsets of the t coins, with as few weighings as possible. Despite a large literature on this problem, it remains wide open for s>2. In this paper, we give an efficient sequential weighing algorithm for the case s=3, with an average of 1.75 weighings per bit of t, as t approaches infinity. (It is known that any algorithm must have more than 1.5 weighings per bit.) We use our algorithm to give an efficient channel coding for the three-sender multiple-access adder channel with feedback.

Problem
Let T be a set of t coins which are either genuine or forged. Genuine coins have normalized weight 0, forged coins have normalized weight 1, so that for any subset W of T , the weight of W , written by wt(W ), is the number of forged coins in W . Since one weighing can determine the number of forged coins in T , we assume that the number of the forged coins in T is known and denoted by s. We want to identify all the forged coins in T by weighing some subsets of T , with as few weighings as possible.
In a static weighing algorithm, all the subsets chosen to weigh are determined in advance; in a sequential weighing algorithm, each subset depends on all the previous weighing results.
In this paper, we give a sequential weighing algorithm for s = 3 forged coins, which is efficient when the total number of coins t is large. For convenience, we assume that t = 2 m for some m. If t is not a power of 2, we can add "dummy" genuine coins to make up the number without affecting the asymptotic efficiency of an algorithm.

The Algorithm: Three Stages
Stage 0. We reduce T to three disjoint subsets, T 1 , T 2 , T 3 , with exactly one forged coin in each set and with |T 1 | = |T 2 | = |T 3 | = 2 n for some n. First, we bisect T and weigh one of the halves. If the weighing result is 0 or 3, we bisect the half with 3 forged coins and weigh one of the quarters. We continue these bisections until the weighing result is 1 or 2. Suppose l 1 steps are needed and the resulting subsets are T ′ and T ′′ , containing one and two forged coins, respectively. Next, we bisect T ′′ until the weighing result is 1. Suppose l 2 steps are needed and the resulting subsets are denoted by T 1 and T 2 . Finally, we do l 2 bisections on T ′ and denote the resulting subset with one forged coin by T 3 .
Stage 0 takes l 1 + 2l 2 weighings and n = m − l 1 − l 2 . Label each coin in T i by a distinct binary sequence of length n. Let c indicate the label of a coin; c (i) the i-th digit of c; and c 1 , c 2 , c 3 the labels of the three forged coins in T 1 , T 2 , T 3 respectively. Stage 1. We do n static weighings. The i-th weighing is the subset W i of all coins in T 1 , T 2 , and T 3 whose i-th digit is 1: = 0 (resp. = 1). If wt(W i ) = 1 or 2, then the ith digit of c 1 , c 2 and c 3 is not completely determined, and we call such a position an ambiguity. If wt(W i ) = 1, exactly one of c 3 is 0. Suppose there are l 3 weighings with result 1 or 2.
The results of Stage 1 and Stage 2 are illustrated in the following table.
Lemma. The mean number N of weighings in the algorithm is Proof. In Stage 0, l 1 is the number of weighings for the first occurrence of a weighing result of 1 or 2 to appear. Consider the first occurrence of a weighing result 1 or 2 to be a geometric random variable, then the probability to have l 1 weighings is 3 4 ( 1 4 ) l 1 −1 , since the probability of getting weighing result 1 or 2 is 3 4 . Similarly, the probability to have l 2 weighings is 2 −l 2 , since the probability of getting weighing result 1 is 1 2 . In Stage 1, the number of weighings is n = m − l 1 − l 2 . In Stage 2, the probability of having l 3 ambiguities is n l 3 ( 3 4 ) l 3 ( 1 4 ) n−l 3 , and l 3 weighings is needed to resolve the l 3 ambiguities. • Simplifying the formula in the Lemma, we get . We use the asymptotic rate R to measure the efficiency of an algorithm when t goes to infinity. Then the rate of this weighing algorithm is The best known weighing algorithm is Lindström's [1] static algorithm which gives R = 0.46. The theoretical rate bound for static weighing algorithm is 0.6 [2]. The theoretical rate bound for sequential weighing algorithm is unknown.

Corresponding code for three-user Adder
Channel with noiseless feedback The three-user Multiple Access Adder Channel takes three independent binary inputs and outputs a ternary symbol which is the sum of the three inputs. The communication system of this channel with noiseless feedback is illustrated in Fig. 1. , the encoders send their binary codewords symbol by symbol simultaneously. The output of each transmission is the sum of all the three input symbols. With the noiseless feedback channel, each encoder knows all the previous output symbols, and then decides its next input symbol, depending on the message itself and all the previous outputs.
We derive a simple and efficient zero-error code from the algorithm in Section 2 for this channel. Let can not be completely determined, since we only know that exactly one of them is 1 when y k = 1, and exactly one of them is 0 when y k = 2, such a position is called an ambiguity. Suppose that there are a such ambiguities after the first l transmissions. In Stage 2, we will resolve these a ambiguous positions.