Statistical Conformity: Feedback¹

Introduction

The Feedback indexer applies an algorithm of my own devising called "statistical feedback"² to ensure that each index value receives its fair share of usage over the extent of a sequence. The number of index values, along with the relative frequency with which each value should appear, is controlled by a set of weights {W₀, W₁, …, W_N-1}, where W_j is the weight accorded to index value j and N is the supply size.

The Feedback indexer is the discrete counterpart to the Balance driver, to the extent that both rely upon statistical feedback. The difference is that Balance produces continuous uniform distributions which must be adapted to non-uniform distributions using a separate Transform unit. Feedback, by contrast, accepts a discrete distribution parametrically.

What "fair share" means depends upon the weights. When the weights are uniform (all equal), then "fair share" means equal share. The Feedback algorithm maintains a set of running statistics {S₀, S₁, …, S_N-1}, where S_j reflects how often index value j has been selected up to the current sequence element. Favor is given to whichever index value has fallen farthest behind the others. When two or more index values have fallen equally behind, the choice between them is random.

When W_j = m×W_n, then index value j should occur m times as often in the sequence as index value n. This is accomplished by advancing the statistic for value j (when selected) as follows:

Here u_j is calculated using Random.nextDouble(), while the parameter H (for heterogeneity) modulates the influence of (u_j −0.5).

Table 1 emulates how the algorithm works with N=2, W₀=1., W₁=2., A=1., and H=0.1:

• For the first sequence element (k=0):
  Index 0 yields decider θ₀=1.012, reflecting S₀ + (A/W₀) + (H×(u₀-0.25)/W₀) = 0.0 + (1.0/1.0) + (0.1×0.12/1.0) = 0.0 + 1.0 + 0.012.
  Index 1 yields decider θ₁=0.416, reflecting S₁ + (A/W₁) + (H×(u₁-0.25)/W₁) = 0.0 + (1.0/2.0) + (0.1×−0.08/2.0) = 0.0 + 0.5 − 0.004.
  θ₁=0.416, being smaller, is formatted in green to indicate that 1 is the chosen index.
  θ₀=1.012, being larger, is formatted in red to indicate that 0 is not the chosen index.
  Δ₁=0.500, being associated with the chosen index 1, is formatted in green to indicate that statistic S₁ will be incremented by this amount.
  Randomness does not contribute to this decision.
• For the second sequence element (k=1):
  Index 0 yields decider θ₀=0.971, reflecting S₀ + (A/W₀) + (H×(u₀-0.25)/W₀) = 0.0 + (1.0/1.0) + (0.1×−0.29/1.0) = 0.0 + 1.0 − 0.019.
  Index 1 yields decider θ₁=0.992, reflecting S₁ + (A/W₁) + (H×(u₁-0.25)/W₁) = 0.5 + (1.0/2.0) + (0.1×−0.16/2.0) = 0.5 + 0.5 + -0.008.
  θ₀=0.971, being smaller, is formatted in green to indicate that 0 is the chosen index.
  θ₁=0.992, being larger, is formatted in red to indicate that 1 is not the chosen index.
  Δ₀=1.000, being associated with the chosen index, is formatted in green to indicate that statistic S₀ will be incremented by this amount.
  Both S₀ + (A/W₀) and S₁ + (A/W₁) evaluate to 1.000 in this situation, making the choice hinge on the small random components.

With H small relative to A, this mostly determinate algorithm maintains conformity over the very short term indeed. The first three rows (0-2) select indices 1, 0, 1; the next three rows (3-5) select indices 1, 1, 0; the three rows after that (6-8) select indices 1, 0, 1, and the final three rows (9-11) select indices 1, 1, 0. In each instance two sequence elements have index value 1 while the remaining element has value 0. This is exactly what the weights prescribed.

The Feedback algorithm takes an additional step not reflected in Table 1; that step is to offset the running statistics so that

As explained in "Statistics and Compositional Balance"³, this step is needed to cope with situations where W_n falls to zero for some index value n. When that happens the increment Δ_n = 1/W_n becomes undefined. Since the decider value θ_n cannot be calculated, the value is simply skipped over. S_j keeps advancing for each j still active, but S_n stays fixed. If after some number of samples W_n becomes positive again, there's a whole lot of catching up to do. Keeping the running statistics centered around zero remedies this situation.

Profile

Figure 1 illustrates four examples of Feedback output with sequences of 200 samples.

Figure 1: Sample output from Feedback.next() with different weightings and heterogeneity settings. The left graph in each row displays samples in time-series while the right graph in the same row presents a histogram analyzed from the same samples.

The vertical x axes for the two graphs in each row represent the index domain from zero to N; the horizontal j axis of the time-series graph (left) plots ordinal sequence numbers; the horizontal f(x) axis of the histogram (right) plots the relative concentration of samples at each point in the driver domain.

The top two sequences illustrate scenarios with uniform weights. More specifically, the array of weights was {1., 1., 1., 1., 1.}.

The heterogeneity setting for the topmost sequence was 0.1. Upon close examination you can verify that the first five samples are {2, 0, 4, 3, 1}, the next five samples are {0, 2, 4, 3, 1}, the next five samples are {2, 4, 1, 0, 3}, and so fourth: each successive frame of five samples presents all five indices. The histogram on the right is absolutely flat, reflecting the fact that each index value appears exactly 40 times over the length of the sequence.

The heterogeneity setting for the second-from-top sequence was 4.0. It is no longer true that successive frames of five samples present all five indices. However, any 10 consecutive samples will contain approximately 2 instances of each index value. The histogram for this second sequence, taken as a whole, only shows the very slightest aberration from perfect uniformity.

The bottom two sequences illustrate scenarios with non-uniform weights. In these examples the array of weights was {1., 1./2., 1./3., 1./4., 1./5.}.

The heterogeneity setting for the second-from-bottom sequence was 0.1. This means that any 27 consecutive samples should contain 12 instances of index 0, 6 instances of index 1, 4 instances of index 2, 3 instances of index 3, and 2 instances of index 4. The histogram on the right confirms that the actual counts of index values conforms to the prescribed weights.

The heterogeneity setting for the bottommost sequence was 4.0. Short-term conformity is less evident, but here any 54 consecutive samples should contain nearly 24 instances of index 0, 12 instances of index 1, 8 instances of index 2, 6 instances of index 3, and 4 instances of index 4. The histogram for this bottommost sequence is not readily distinguishable from the histogram for the non-uniform sequence with heterogeneity 0.1.

Stress

Consider this abstract scenario: there is a collection of entities, the objective is to select an attribute for each entity from a supply in such a matter that each supply element is emphasized equally. A musical version of this scenario has notes as entities and scale degrees as attributes. A graphic version has shapes as entities and colors as attributes. The Feedback indexer offers one way of addressing these analogous scenarios. Equal emphasis will result if the weights associated with supply elements are all the same.

Except, what happens when the note durations are unequal, or when the shapes have different areas? Does a whole-note E balance with a sixteenth-note F? Does a large pink shape balance with a small red shape?

Othodox serialism maintains that a whole-note E does indeed balance with a sixteenth-note F. Yet serialism provides a carve out: row elements can be repeated if done so in a decorative way; for example, as a tremolo.

Suppose you believe in equal balance, but unlike an orthodox serialist you believe that 16 sixteenth notes are required to balance one whole note. If so, the Feedback indexer can accomodate you. If you're about to select a degree for a sixteenth note, set A = 1. If you're about to select a degree for a whole note, set A = 16.

Suppose you believe that duration counts for something but that just showing up also counts for something, and familiarity breeds contempt. A comprimise might be to set A to the square root of the duration. If you're about to select a degree for a sixteenth note, set A = √1 = 1. If you're about to select a degree for a whole note, set A = √16 = 4.

Considerations become even more murky when some weights are much smaller than others. The mere fact that an attribute is rare means that when that attribute is selected for an entity, the attribute itself imparts stress to the entity. Thus a yellow life vest can be easily discernable amongst a sea of blue.

/**
 * The {@link Feedback} class implements selection using statistical feedback.
 * @author Charles Ames
 */
public class Feedback
extends WriteableEntity implements Indexer {
   private DiscreteDistribution distribution;
   private double stress;
   private double heterogeneity;
   private double balance[];
   private int position;
   private Random random;
   /**
    * Constructor for {@link Feedback} instances.
    * @param container A {@link WriteableEntity} which contains this instance.
    */
   public Feedback(WriteableEntity container) {
      super(container);
      setIDQuality(AttributeQuality.MODIFIABLE);
      setNameQuality(AttributeQuality.MODIFIABLE);
      this.balance = null;
      this.random = SharedRandomGenerator.getSingleton().getRandom();
      this.distribution = new DiscreteDistribution(this);
      this.distribution.setIDQuality(AttributeQuality.UNUSED);
      this.distribution.setNameQuality(AttributeQuality.UNUSED);
      this.stress = Double.NaN;
      this.heterogeneity = Double.NaN;
      this.position = Integer.MIN_VALUE;
   }
   /**
    * Set the count of index choices.
    * @param limit The intended length of the {@link balance} array.
    * @return True if the length has changed; false otherwise.
    */
   private boolean allocateBalances(int limit) {
      if (0 >= limit) throw new IllegalArgumentException("Argument not positive");
      if (null != balance) {
         if (balance.length == limit) return false;
      }
      balance = new double[limit];
      resetBalances();
      makeDirty();
      return true;
   }
   private void resetBalances() {
      int limit = getLimit();
      for (position = 0; position < limit; position++) {
         balance[position] = 0.;
      }
   }
   /**
    * Get the count of index choices.
    * @return The allocated length of the {@link #balance} array.
    */
   public int getLimit() {
      if (null == balance) throw new UninitializedException("Balance array not dimensioned");
      return balance.length;
   }
   /**
    * Set the weights data.
    * @param weights An array of non-negative double-precision numbers.
    * @throws IllegalArgumentException when the argument is null.
    * @throws IllegalArgumentException when any weight is negative.
    */
   public void setWeights(double[] weights) {
      if (null == weights)
         throw new IllegalArgumentException("Null argument");
      allocateBalances(weights.length);
      distribution.initialize();
      int items = weights.length;
      for (int index = 0; index < items; index++) {
         distribution.addItem(index, weights[index]);
      }
      distribution.normalize();
      makeDirty();
   }
   /**
    * Getter for {@link #stress}.
    * @return The assigned {@link #stress} value.
    * @throws UninitializedException when the {@link #stress} value is uninitialized.
    */
   public double getStress() {
      if (Double.isNaN(stress)) throw new UninitializedException("Stress not initialized");
      return stress;
   }
   /**
    * Setter for {@link #stress}.
    * @param stress The intended {@link #stress} value.
    * @return True if {@link #stress} has changed; false otherwise.
    * @throws IllegalArgumentException when the argument is not positive.
    */
   public boolean setStress(double stress) {
      if (stress < MathMethods.TINY)
         throw new IllegalArgumentException("Stress must be positive");
      if (this.stress != stress) {
         this.stress = stress;
         makeDirty();
         return true;
      }
      return false;
   }
   /**
    * Getter for {@link #heterogeneity}.
    * @return The assigned {@link #heterogeneity} value.
    * @throws UninitializedException when the {@link #heterogeneity} value is uninitialized.
    */
   public double getHeterogeneity() {
      if (Double.isNaN(heterogeneity)) throw new UninitializedException("Heterogeneity not initialized");
      return heterogeneity;
   }
   /**
    * Setter for {@link #heterogeneity}.
    * @param heterogeneity The intended {@link #heterogeneity} value.
    * @return True if {@link #heterogeneity} has changed; false otherwise.
    * @throws IllegalArgumentException when the argument is not positive.
    */
   public boolean setHeterogeneity(double heterogeneity) {
      if (heterogeneity < MathMethods.TINY)
         throw new IllegalArgumentException("Heterogeneity must be positive");
      if (this.heterogeneity != heterogeneity) {
         this.heterogeneity = heterogeneity;
         makeDirty();
         return true;
      }
      return false;
   }
   /**
    * Update usage statistics in the event that the indicated index has been selected.
    * @param usedIndex The indicated index.
    */
   public void useIndex(int usedIndex) {
      double usedWeight = Double.NaN;
      int index = 0;
      int count = 0;
      double stress = getStress();
      Iterator<DiscreteDistributionItem> iterator = distribution.iterateItems();
      while (iterator.hasNext()) {
         DiscreteDistributionItem item = iterator.next();
         double weight = item.getWeight();
         if (weight > MathMethods.TINY) {
            count++;
            if (usedIndex == index) usedWeight = weight;
         }
         index++;
      }
      double increment = stress / usedWeight;
      balance[usedIndex] += increment;
      double decrement = increment / count;
      index = 0;
      iterator = distribution.iterateItems();
      while (iterator.hasNext()) {
         DiscreteDistributionItem item = iterator.next();
         double weight = item.getWeight();
         if (weight > MathMethods.TINY) {
            balance[index] -= decrement;
         }
         index++;
      }
   }
   public Integer next() {
      double bestScore = Double.MAX_VALUE;
      int bestIndex = Integer.MAX_VALUE;
      int index = 0;
      double heterogeneity = getHeterogeneity();
      double stress = getStress();
      Iterator<DiscreteDistributionItem> iterator = distribution.iterateItems();
      while (iterator.hasNext()) {
         DiscreteDistributionItem item = iterator.next();
         double weight = item.getWeight();
         if (weight > MathMethods.TINY) {
            double score = balance[index] + ((stress + (heterogeneity * (random.nextDouble()-0.5))) / weight);
            if (score < bestScore) {
               bestScore = score;
               bestIndex = index;
            }
         }
         index++;
      }
      if (Integer.MAX_VALUE == bestIndex)
         throw new RuntimeException("No nonzero weights");
      useIndex(bestIndex);
      return bestIndex;
   }
   @Override
   public boolean hasNext() {
      return true;
   }
   @Override
   public boolean hasReset() {
      return true;
   }
   @Override
   public void reset() {
      resetBalances();
   }
   @Override
   public double minGraphValue() {
      if (0 == distribution.itemCount()) throw new UnsupportedOperationException("Distribution has no values");
      return distribution.getMaxValue();
   }
   @Override
   public double maxGraphValue() {
      if (0 == distribution.itemCount()) throw new UnsupportedOperationException("Distribution has no values");
      return distribution.getMinValue();
   }
}

Comments

1. The present text is adapted from my Leonardo Music Journal article from 1992, "A Catalog of Sequence Generators". The heading is "Statistical Feedback", p. 69.
2. Statistical feedback is explained in my Perspectives of New Music article from 1990, "Statistics and Compositional Balance".
3. The topic heading is "Statistical Exclusion" on page 100.