Ldim

Why SOA Keeps a Version Space

The Standard Optimal Algorithm, abbreviated SOA, makes each prediction by examining the hypotheses that are still consistent with the labels observed so far. It begins with V_1 = H, meaning that the initial consistent class is the full hypothesis class H. As examples arrive, hypotheses that disagree with the true labels are removed. The remaining class is the current version space used for the next prediction.

One Round of SOA

At round t, SOA receives an input x_t and starts with the current class V_t. It divides V_t into two subclasses. V_t^(0) contains the hypotheses that assign label 0 to x_t, while V_t^(1) contains the hypotheses that assign label 1 to x_t. SOA compares the Ldim of these two subclasses and predicts the label belonging to the subclass with the larger Ldim. If the two Ldim values are equal, SOA predicts 1.

1. Initialize the process with V_1 = H.
2. At round t, divide V_t into V_t^(0) and V_t^(1) according to the labels assigned to x_t.
3. Compare the Ldim of the two candidate subclasses.
4. Predict the label whose subclass has larger Ldim; predict 1 if the values are equal.
5. After the true label y_t arrives, keep only the hypotheses in V_t that agree with y_t to form V_(t+1).

Comparing Candidate Labels

Updating the Consistent Class

The current class V_t represents the hypotheses that have survived all previously observed labels. Once the true label y_t is revealed, SOA removes every hypothesis in V_t that disagrees with y_t on x_t. The survivors form V_(t+1). This means that the version space can become smaller as observations rule out hypotheses, but the rule for removal is always agreement with the true label.

Tie-Breaking Rule

When V_t^(0) and V_t^(1) have equal Ldim, neither candidate has a larger value. SOA resolves this tie by predicting 1. The tie rule is part of the prediction procedure, so a trace that predicts 0 in this situation does not follow SOA, even if its later update uses the true label correctly.

Checking a Prediction Trace

To check whether a prediction trace follows SOA, inspect the events in order. First verify that the trace starts with V_1 = H. Then check that it divides the current class according to the two labels assigned to the current input. Next verify the Ldim comparison and the resulting prediction, including the rule that a tie produces 1. Finally check that the update uses y_t, the true label, rather than p_t, the prediction. The first mismatch in this sequence is where the trace diverges from SOA.

• Updating with the prediction instead of the true label

  The update is defined by y_t, not p_t.

  Fix: Keep only the hypotheses that agree with the observed true label 1.

• Choosing the smaller-Ldim subclass

  SOA predicts using the candidate class with larger Ldim.

  Fix: Compare both candidate values and select the label associated with the larger value.

• Breaking an Ldim tie in favor of 0

  SOA's specified tie-breaking rule is to predict 1.

  Fix: Predict 1 whenever the two candidate Ldim values are equal.

• Treating prediction and update as one event

  The selected subclass reflects the prediction, while the true label determines the update.

  Fix: Record p_t first, observe y_t separately, and then construct V_(t+1) using y_t.

Mistake Bound

The formal guarantee stated for SOA is that the number of mistakes it makes on hypothesis class H is at most Ldim(H). Thus, Ldim has two roles in the procedure: the current candidate Ldim values guide each prediction, and the Ldim of the original class gives the upper bound on the total number of mistakes.

Practice Check

1. SOA starts with V_1 = H and maintains the hypotheses consistent with the true labels observed so far. At each round, it divides V_t into the two candidate subclasses V_t^(0) and V_t^(1), compares their Ldim values, and predicts the label associated with the larger value. Equal values are resolved by predicting 1. After the true label arrives, SOA forms V_(t+1) using that true label, not the prediction. Its total number of mistakes on H is at most Ldim(H).