Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Ensemble learning and voting

Ensemble learning combines many base learners by voting (majority, weighted or other rules) to reduce error and variance; key results include the binomial formula for majority error and the log-odds optimal weights under independent classifiers.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Ensemble learning and voting are used by engineers to improve prediction accuracy and robustness: instead of trusting one model, you combine several base learners so that their mistakes cancel out. Voting rules (majority, weighted, plurality) are simple, widely used in bagging, random forests and many practical systems where reliability matters.

Key ideas

  • Voting: a decision rule that maps base-learner outputs to a final class label. Common voting rules:

    • Majority voting (for binary/class labels): each base learner casts one equal vote; the class with more than half the votes is chosen. If n is odd, majority means strictly more than n/2 votes.
    • Plurality voting: choose the class with the highest number of votes (works for multiclass and when no majority exists).
    • Weighted voting: each base learner i has a weight w_i (often non-negative; under log-odds weighting w_i can be negative if p_i < 0.5, or equivalently flip s_i); each casts w_i votes; pick the class with maximum total weight.
    • Soft voting (probability averaging): average predicted class probabilities across base learners and choose the class with the highest averaged probability; if working in log-odds, averaging logits corresponds to multiplying odds and is equivalent to summing log-odds.
    • Borda count: for ranked outputs, assign points per position and sum points across learners.
  • Condorcet winner: a class that would beat every other class in pairwise majority contests. Not always exists (Condorcet paradox).

  • Independence assumption: many theoretical results assume base learner errors are independent across learners. Define: errors are independent if for any subset of learners, the joint probability of their error pattern is the product of individual probabilities. This is often false in practice; correlated errors reduce ensemble gains.

  • Exact theorem (Condorcet Jury Theorem, stated for classifiers):

    • Statement: Let there be n independent voters (base learners). Each voter has probability p of being correct on a given instance, with p > 1/2 and p constant across voters. Then the probability that majority voting is correct tends to 1 as n → ∞.
    • Assumptions: independence of voters, identical accuracy p > 1/2, binary decision (correct/incorrect).
    • Proof sketch (law of large numbers): The fraction of correct voters converges in probability to p. Since p > 1/2, for large n the fraction > 1/2 with probability → 1, so majority will be correct with probability → 1. Moreover, if p = 1/2, majority voting stays at chance level; if p < 1/2, the probability majority is correct tends to 0 (equivalently, flip outputs to get accuracy 1 − p > 1/2).
  • Exact finite-sample formula (binary case, identical accuracy and independence): if each base classifier has error probability p (probability it is wrong on the instance), ensemble majority error is the binomial tail probability that strictly more than n/2 base classifiers are wrong. This formula and its derivation are commonly asked in exams (see Formulas and Worked examples).

  • Bayesian/likelihood combination and optimal weights: when base classifiers are conditionally independent given the true label, and for binary labels y ∈ {+1, −1}, the log-likelihood ratio for the label given classifier outputs leads to a linear scoring rule. If each classifier i has probability p_i of matching the true label (i.e., P(s_i = y) = p_i), then the optimal additive score (log-likelihood ratio) is S = Σ_i w_i s_i + C where s_i ∈ {+1, −1} is the i-th classifier output and w_i = ln(p_i/(1 − p_i)). Choose the label by sign(S) (plus adjust for prior). Assumptions: conditional independence and known p_i. This derivation assumes symmetric errors: P(s_i=+1 | y=+1) = P(s_i=−1 | y=−1) = p_i; if class-conditional error rates differ, the optimal rule uses separate weights per classifier output based on those conditional probabilities.

  • Practical notes: in real datasets base classifiers are not independent. Diversity among base learners (different training sets, models, features) and weighting strategies (validation-based weights) help.

  • Diagrams to draw for an exam answer (describe exactly):

    1. Architecture diagram for a voting ensemble: draw n small boxes labelled h1, h2, ..., hn (base learners). Draw arrows from each box to a central box labelled "Voter". From the voter box draw an arrow to the final output ŷ. Label the voter with the rule ("majority" or "weighted sum → sign").
    2. For the binomial tail explanation: draw a bar chart (x-axis: k = number of wrong classifiers from 0..n; y-axis: probability mass P(K=k) = C(n,k) p^k (1-p)^{n-k}). Shade bars with k > n/2 to show the ensemble error as the shaded area; draw vertical line at k = n/2.

Formulas

P(majority wrong) = Σ_{k=⌈(n+1)/2⌉}^n C(n,k) p^k (1−p)^{n−k} If n is even and ties are broken at random: P(majority wrong) = Σ_{k=n/2+1}^n C(n,k) p^k (1−p)^{n−k} + 0.5·C(n,n/2) p^{n/2} (1−p)^{n/2}

  • p: error probability of each base classifier (unitless). n: odd number of classifiers. Applies when base classifiers are independent and identically distributed (i.i.d.).

P(K = k) = C(n,k) p^k (1−p)^{n−k}

  • K: number of classifiers that are wrong (unitless). C(n,k) = n!/(k!(n−k)!) is binomial coefficient.

w_i = ln(p_i / (1 − p_i))

  • w_i: weight for classifier i in the log-likelihood weighted vote (unitless). p_i: probability classifier i agrees with true label (0 < p_i < 1).

S = Σ_{i=1}^n w_i s_i + ln(π_+/π_−)

  • S: log-likelihood ratio score (unitless). s_i ∈ {+1, −1}: classifier i output. π_+, π_−: prior probabilities of labels +1 and −1. Predict +1 if S > 0.

Majority rule (binary, equal weights): ŷ = sign(Σ_{i=1}^n s_i)

  • s_i: classifier i output encoded as +1 or −1. In case of tie (sum = 0), break tie by prior or random.

(Units: all quantities above are unitless; they are probabilities or dimensionless scores.)

Worked examples

Example 1 — numerical binomial computation (university exam style)

Question (model answer): Suppose you have n = 11 independent base classifiers. Each classifier has error probability p = 0.30 (i.e., each is correct with probability 0.70). Using majority voting (odd n), compute the ensemble error probability (probability that majority vote is wrong). Show steps and final answer.

Solution:

  1. Number of classifiers wrong K ∼ Binomial(n=11, p=0.30).
  2. Majority is wrong when K ≥ 6. Use binomial tail: P(majority wrong) = Σ_{k=6}^{11} C(11,k) (0.30)^k (0.70)^{11−k}
  3. Compute each term (show main intermediate multiplications):
    • k=6: C(11,6)=462; term ≈ 462·0.000729·0.16807 ≈ 0.05660
    • k=7: C(11,7)=330; term ≈ 330·0.0002187·0.2401 ≈ 0.01732
    • k=8: C(11,8)=165; term ≈ 165·0.00006561·0.343 ≈ 0.00372
    • k=9: C(11,9)=55; term ≈ 55·0.000019683·0.49 ≈ 0.00053
    • k=10: C(11,10)=11; term ≈ 11·0.0000059049·0.7 ≈ 0.0000455
    • k=11: C(11,11)=1; term ≈ 1·0.00000177147·1 ≈ 0.00000177
  4. Sum terms: P ≈ 0.05660 + 0.01732 + 0.00372 + 0.00053 + 0.0000455 + 0.00000177 ≈ 0.07822.

Final answer: Ensemble majority-vote error ≈ 0.0782 (unitless probability).

Interpretation: Single classifier error 0.30 reduced to ensemble error ≈ 0.0782 by majority voting under independence.

Example 2 — derivation of optimal weights and a numerical decision

Question (model answer): Derive the weighted voting rule (weights in log-odds) for independent binary classifiers with known accuracies p_i, and apply it to a numerical example where p1 = 0.70, p2 = 0.60, p3 = 0.80 and classifier outputs s = [+1, −1, +1]. Show final decision.

Solution (derivation):

  1. Let true label y ∈ {+1, −1}. For classifier i define p_i = P(s_i = y). Under conditional independence: P(s | y) = Π_i P(s_i | y).
  2. Compute likelihood ratio Λ(s) = P(s | y=+1) / P(s | y=−1).
  3. For each i, if s_i = +1 then factor = p_i / (1 − p_i); if s_i = −1 factor = (1 − p_i) / p_i. Combine: Λ(s) = Π_i (p_i / (1 − p_i))^{s_i} where s_i mapped to exponent +1 for +1 and −1 for −1.
  4. Take log: ln Λ(s) = Σ_i s_i ln(p_i / (1 − p_i)). Add prior term ln(π_+/π_−) if needed.
  5. Decision: predict +1 if ln Λ(s) + ln(π_+/π_−) > 0. So define weights w_i = ln(p_i/(1 − p_i)) and compute S = Σ w_i s_i + ln(π_+/π_−).

Numerical application (assume equal priors so prior term 0):

  • p1 = 0.70 ⇒ w1 = ln(0.70/0.30) ≈ ln(2.3333) ≈ 0.8473
  • p2 = 0.60 ⇒ w2 = ln(0.60/0.40) ≈ ln(1.5) ≈ 0.405465
  • p3 = 0.80 ⇒ w3 = ln(0.80/0.20) ≈ ln(4) ≈ 1.386294

Classifier outputs s = [+1, −1, +1], so S = w1·(+1) + w2·(−1) + w3·(+1) ≈ 0.8473 − 0.405465 + 1.386294 ≈ 1.828129

Final decision: sign(S) = +1, so predict +1.

Common mistakes

  • Using average accuracy p in the binomial formula when classifiers have different accuracies p_i — the identical-p assumption must be stated.
  • Confusing a classifier that agrees with the true label with one that predicts a specific class; when applying weighted sums be consistent in encoding outputs as +1/−1.
  • Not adjusting for class priors when combining via log-likelihoods; the prior term ln(π_+/π_−) matters with class imbalance.

For your exam

Typical question types: definitions (define ensemble, majority voting, weighted voting), short notes (advantages/disadvantages of voting, independence assumption), derivations (derive binomial formula for majority error, derive log-odds weights), numericals (compute ensemble error for given n and p), and diagrams (draw ensemble architecture and binomial-bar chart).

What a full-marks answer includes:

  • Clear definitions with bolded terms (e.g., Ensemble, Majority voting).
  • Statement of assumptions (independence, identical accuracies) before using formulas.
  • Correct derivation steps: for binomial tail show probability of k wrong is C(n,k) p^k (1−p)^{n−k} and sum from k = ⌈(n+1)/2⌉ to n; for log-odds weights show likelihood ratio steps and taking log.
  • A labelled diagram when asked (boxes for base learners, arrows to voter, label rule), and clear tie-breaking policy.
  • Numerical calculations with intermediate steps and final bold answer.

Quick check

  1. If 5 independent classifiers each have error p = 0.4, is majority voting expected to help? (Yes/No)
  2. Write the decision rule (score) when classifiers have known accuracies p_i and outputs s_i ∈ {+1, −1}.
  3. What assumption is critical for the binomial majority error formula to be correct?

Answers: 1. Yes (because p < 0.5, majority voting improves as n increases); 2. S = Σ_i ln(p_i/(1−p_i))·s_i + ln(π_+/π_−), predict +1 if S > 0; 3. Independence (and identical distribution if using single p).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?