PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing F-measure: A Tale of Two Approaches

Ye Nan, Kian Ming Chai, Wee Sun Lee, Hai Leong Chieu

arXiv:1206.4625v1cs.LG

TL;DR

The paper examines the theoretical basis of EUM and DTA for F-measure optimization and when each approach is preferable. It finds asymptotic equivalence under stated conditions, alongside different empirical strengths across settings.

  • Problem

    The paper asks when EUM or DTA is preferable for F-measure optimization, a metric popular for imbalanced tasks.

    Source: §1 · pp. 1–2

  • Method

    The paper develops theories and algorithms for comparing EUM and DTA, evaluating them on synthetic and real datasets.

    Source: §1 · p. 2

  • Results

    With accurate models and large training and test sets, EUM and DTA are asymptotically equivalent; empirically, EUM is more robust to misspecification, while DTA handles rare classes and domain adaptation better given a good model.

    Source: §1 · p. 2, §2.3 · p. 4

  • Takeaways & Limitations

    The observed strengths differ by setting: model misspecification favors EUM, while a good model favors DTA for rare classes and domain adaptation.

    Source: §1 · p. 2, §5 · p. 8

    The results hold only for large datasets, leaving their applicability to small samples unresolved.

    Source: §5 · p. 8

Abstract

from arXiv · show

F-measures are popular performance metrics, particularly for tasks with imbalanced data sets. Algorithms for learning to maximize F-measures follow two approaches: the empirical utility maximization (EUM) approach learns a classifier having optimal performance on training data, while the decision-theoretic approach learns a probabilistic model and then predicts labels with maximum expected F-measure. In this paper, we investigate the theoretical justifications and connections for these two approaches, and we study the conditions under which one approach is preferable to the other using synthetic and real datasets. Given accurate models, our results suggest that the two approaches are asymptotically equivalent given large training and test sets. Nevertheless, empirically, the EUM approach appears to be more robust against model misspecification, and given a good model, the decision-theoretic approach appears to be better for handling rare classes and a common domain adaptation scenario.

1. Introduction

The paper compares empirical utility maximization (EUM), which optimizes training-set F-measure, with decision-theoretic optimization (DTA), which predicts to maximize expected F-measure. It develops theoretical connections between them and compares their behavior on synthetic and real datasets.

1. Introduction

  • EUM and DTA define optimality differently: EUM optimizes an instance classifier's F-measure on a large test set, whereas DTA optimizes expected F-measure over set classifiers.The approaches also use different learning objectives.Source: §1 · p. 2
  • The paper establishes EUM consistency and convergence-rate bounds, with the bounds suggesting that rare classes require more data for performance guarantees.It focuses on binary classification with independently and identically distributed data.Source: §1 · p. 2
  • For large i.i.d. training and test sets, an EUM-optimal classifier and a DTA-optimal classifier are asymptotically equivalent under a condition on instances with equal relevance probabilities.The paper also shows that thresholding the true conditional distribution on a large i.i.d. test set can perform as well as the best instance classifier.Source: §1 · p. 2
  • An O(n^2)-time algorithm computes DTA-optimal predictions for tens of thousands of instances within seconds, versus hours or more for previous algorithms.The algorithm assumes independence of labels.Source: §1 · p. 2
  • EUM appears more robust to model misspecification, while DTA with a good model appears better for rare classes and a common domain-adaptation scenario.The empirical comparison uses a synthetic dataset, Reuters-21578, and four multilabel datasets.Source: §1 · p. 2

2. Theoretical Analysis

The analysis concerns binary classification with i.i.d. data and studies consistency, thresholding, and the relationship between EUM and DTA. Its results give conditions for EUM convergence and for asymptotic equivalence between threshold-based and decision-theoretic predictions.

2.1. Uniform Convergence and Consistency for EUM

  • Using VC-dimension to quantify classifier-class complexity, the analysis shows empirical Fβ maximization is consistent; its bound indicates smaller π1 and β may require more samples for convergence to begin.Source: §2.1 · p. 3

2.2. Optimality of Thresholding in EUM

  • With the true conditional distribution, empirical optimization over probability thresholds is consistent and can attain the optimal classifier; rank preservation is sufficient, but not necessary, for a score function to be optimal.An optimal score function may reorder instances above the optimal threshold.Source: §2.2 · p. 3

2.3. An Asymptotic Equivalence Result

  • For large i.i.d. test sets, a classifier's expected Fβ approaches its classifier-level Fβ, with the approximation holding uniformly across probability thresholds.This gives a basis for comparing the threshold-based and expected-Fβ objectives.Source: §2.3 · p. 4
  • When no conditional-probability value has positive probability mass, optimal probability-threshold and constrained set predictions are asymptotically equivalent in expected and realized Fβ on large i.i.d. test sets.The constraint groups instances with the same probability of being positive into the same predicted class.Source: §2.3 · p. 4

3. Algorithms

The section compares approximations to empirical F-measure optimization with decision-theoretic prediction, then develops an efficient algorithm for maximizing expected F-measure. For rational β², the prediction computation takes O(n²) time.

3.1. Approximations to the EUM Approach

  • The MLδ approximation estimates conditional probabilities by maximum likelihood, then optimizes the F-measure threshold; it is asymptotically optimal when the model family is well specified.The stated convergence-rate result does not apply to this combined approximation.Source: §3.1 · p. 4
  • The Fδ approximation replaces binary decisions with predictive probabilities when optimizing empirical Fβ, then optimizes the decision threshold on training data.A direct smoothed optimization of model and threshold parameters overfit easily and rarely outperformed MLδ or Fδ in preliminary experiments.Source: §3.1 · p. 4

3.2. Maximizing Expected F-measure

  • The MLE approach estimates the distribution before choosing predictions that maximize expected utility, and is asymptotically optimal with sufficient data from a well-specified family.Even with misspecification, it can yield results indistinguishable from optimal when the family contains a reasonable approximation to the true distribution.Source: §3.2 · p. 4
  • For F-measure, the probability ranking principle restricts optimal predictions to the top k instances by positive-class probability, reducing candidates from 2^n to n+1.This characterization enables the efficient prediction algorithm.Source: §3.2 · p. 5

3.2.1. A Quadratic Time Algorithm

  • For rational β², optimal expected-F predictions can be computed in O(n²) time and O(n) space, improving on the O(n³) algorithm.The algorithm exploits shared intermediate values across candidate predictions.Source: §3.2.1 · p. 5
  • Expected Fβ for each top-k prediction is computed from the positive-label counts among selected and unselected instances; computing all candidates takes O(n³) time before the rational-β² improvement.The count probabilities are obtained from polynomial coefficients.Source: §3.2.1 · p. 5

4. Experiments

Across synthetic and real datasets, EUM appears more robust to model misspecification, while DTA can better handle rare classes and a common domain-adaptation setting. The experiments examine how these patterns depend on model quality and data conditions.

4. Experiments

  • EUM appears more robust to model misspecification, while DTA can better handle rare classes on small datasets and a common domain-adaptation scenario.The experiments compare synthetic and real datasets.Source: §4 · p. 5

4.1. Mixtures of Gaussians

  • Table 1 finds scores generally near optimal, but well-specified R2 often scores below simpler R0 and R1 under several settings.The authors attribute this pattern to the higher complexity of R2 requiring more samples for convergence.Source: Table 1 · p. 6, §4.1 · p. 6

4.1.1. Effect of Model Quality

  • DTA performance is roughly positively correlated with model quality, and is more sensitive to model quality when the true positive ratio is small.Figure 1 compares 1 − F1 with KL across assumed π1 values.Source: Figure 1 · p. 7, §4.1.1 · p. 7

4.1.2. Domain Adaptation

  • With a shifted test distribution where P(X) changes but P(Y|X) does not, DTA is more robust than EUM.In the described Gaussian setting, F1 scores for Truthδ, TruthE, MLδ, and MLE are 21%, 38%, 11%, and 36%, respectively.Source: §4.1.2 · p. 7

4.2. Text Classification

  • On Reuters-21578, MLE is at least comparable to thresholding methods with naїve Bayes, and a few percentage points better with logistic regression for rare classes.Table 3 reports macro-F1 for topics meeting the stated positive-instance threshold.Source: Table 3 · p. 7, §4.2 · p. 7

4.3. Multilabel Datasets

  • On four multilabel datasets, MLE performs better than MLδ and Fδ, especially for smaller C, while models closer to the true distribution perform better for both MLE and MLδ.Table 4 reports macro-F1 for labels meeting the stated positive-instance threshold.Source: Table 4 · p. 8, §4.3 · p. 8

5. Conclusion

The paper develops theoretical justifications and connections for EUM and DTA, while its experiments suggest different advantages under model misspecification and good-model conditions. The results are stated to hold for large datasets, with small-sample behavior still an open question.

  • The paper provides theoretical justifications and connections for optimizing F-measures with EUM and DTA.Source: §5 · p. 8
  • Empirically, EUM seems more robust to model misspecification, while DTA can better handle rare classes and a common domain-adaptation scenario given a good model.Source: §5 · p. 8
  • The results hold for large datasets; behavior with small numbers of instances remains important to examine.The authors also identify method selection for a dataset and the effects of inaccurate models as unanswered questions.Source: §5 · p. 8
Loading 1206.4625v1…