
Structural Extension to Logistic Regression (Auxiliary Material)
This webpage presents a number of results related to the paper "Structural Extension to Logistic Regression: Discriminative Parameter Learning of Belief Net Classifiers" (ps; pdf), which appears in the Machine Learning Journal special issue on Probabilistic Graphical Models for Classification -- MLJ 59(3), June 2005, p. 297--322.
The bulk of the material in this website also appears in ps and pdf formats.
Slides - from 2008: here
EXPERIMENTAL RESULTS
We used the
for most of our experimental studies.
(25 UCI BENCHMARK DATABASES) with "missing at random" at 0.25, MCAR [LR87, J.A. Little and D.B. Rubin, Statistical Analysis with Missing Data, Wiley, New York, 1987]
25 UCI benchmark datasets
We evaluated various algorithms over the standard 25 benchmark datasets used by Friedman et al. [FGG97]: 23 from UCI repository [BM00], plus �mofn-3-7-10� and �corral�, which were developed by [KJ97] to study feature selection. Also the same 5-fold cross validation and Train/Test learning schemas are followed (see following Table). As part of data preparation, continuous data are always discretized using the supervised entropy-based approach.
(You can download the discretized data here.)
Description of data sets used in the experiments; see also [FGG97: N. Friedman, D. Geiger and M. Goldszmidt. Bayesian Network Classifiers. Machine Learning 29:131-163, 1997 ]

Empirical accuracy of classifiers learned from complete data (25 UCI benchmark datasets)

Empirical accuracy of classifiers learned from incomplete data (25 UCI benchmark datasets with "missing completely at random" at 0.25)

Based on the generalization error plots, we see that ELR should stop after {2, 1, 1, 4, 5} iterations, for these 5 cross validation runs. Of course, ELR will not know these "optimal iteration numbers" as they are based on the hold-out data, which is NOT available at training time.
Fortunately, ELR estimates these numbers from the available training data, using a standard method we call "cross-tuning", described on pages 9-10 of the manuscript, to try to identify the number of climbs (iterations) that is appropriate for each specific dataset. Cross-tuning first splits the training set into n parts (folds), then successively trains on n-1 folds and evaluates on the remaining one. In particular, for each instance, it runs the ELR algorithm on n-1 folds for a large number of iterations, and measures the quality of the resulting classifier on the other fold. For each run, it determines which iteration produces the smallest generalization error. Cross-tuning then picks the median value m over these runs. Later, when running on the full dataset (all n folds), it will run for m iterations before stopping.
The paired t-tests of ELR results on the UCI benchmark datasets shows that cross-tuning is essential in ELR learning:
-
NB+ELR(+xt) <-- NB+ELR(-xt) (p < 0.3) (slightly better), while
-
TAN+ELR(+xt) <-- TAN+ELR(-xt) (p < 0.05) (statistically better).
(Recall 'x <- y' means 'x is better than y'.)
Here NB+ELR(-xt) is comparable to TAN+ELR(-xt), whose performance was significantly degraded by overfitting. This shows cross-tuning can be effective to prevent overfitting especially when learning parameters of complex BN structures.
The obvious downside of cross-tuning, of course, is computation expense; see timing information.
To demonstrate how cross-tuning works to help avoid overfitting, we revisit the experiments on the cleve dataset. For the first cross validation run, we split the training data from folds {F1,F2, F3, F4} into another 5 folds for cross-tuning; call them 1CT = {1CT1, 1CT2, ..., 1CT5}. (Note: F1 + F2 + F3 + F4 = 1CT1 + 1CT2 + ... + 1CT5.) We then ran 5 fold cross-tuning on 1CT, here by using 4 folds of 1CT for training and the remaining 1CT fold for testing, over 20 iterations. Each cross-tuning run determined an iteration number that produced the smallest testing error on the hold-out 1CT fold. After 5-fold cross-tuning runs, we took the median value of the 5 estimates and used it as the iteration number in the training on the full 1CT set.
For this first cross-validation run, this produced an estimate of 2, which we see (from the "cleve fold 1/5" graph below) is correct. We similarly computed this quantity for the other four cross-validation scenarios, producing {2, 1, 1, 3, 5} respectively for the 5 cross validation runs. Notice cross-tuning identified the correct stopping number in 4 of the 5 cross validation run. The only exception is the fourth one, where it returned 3, not 4.
Experiments with "Cross Tuning"
Gradient based learners have to determine when to stop climbing. A naive implementation would climb for a fixed pre-set number of iterations, or would continue climbing as long as the empirical accuracy is increasing. Our empirical studies (on both ELR and APN) show that these approaches are problematic, as these systems will typically overfit or underfit. To demonstrate this, we present 5-fold cross validation learning curves from TAN+ELR training results on the cleve dataset. For each cross validation run, we used a performed 20 iterations over the training data; and we plotted the 'Resubstitution Error' and 'Generalization Error' after each gradient descent iteration (See graphs below.) The 'Generalization Error' is the testing error of the resulting system on the hold-out fold after each training iteration. (I.e., we divided all cleve data into 5 fold: {F1, F2, F3, F4, F5}; in each iteration of the first cross validation run, we used F1+F2+F3+F4 for training, then evaluated the resulting system against the F5 hold-out testing data to produce the 'Generalization Error'). Many of the plots show that ELR's gradient ascent starts overfitting significantly only after a few training iterations.

Experiments on UCI Irvine Database with missing data
classification errors for 20 UCI incomplete datasets.
Paired T-tests ('x <- y' means 'x is better than y'):
NB+ELR <- NB+EM (p < 0.00559)
NB+ELR <- NB+APN (p < 0.026125)
TAN+ELR <- TAN+EM (p < 0.083164)
TAN+ELR <- TAN+APN (p < 0.077631)
Note: All datasets have >200 instances.


ELR vs other Learning Algorithms
The page summarizes all the results on complete data experiments from various papers. In short, we found that x+ELR performed comparably to C4.5 and SNB.
The following table summarizes our results when comparing ELR vs SVM-light. (Note that we only ran over the datasets with BINARY class labels.) The page presents further details on these SVM experiments.

* We tried many settings, and found this specific setting, [c=0.05, poly 2 (t=1, d=2)] produced the best average for SVM. (As this is based on ALL data, this does give svm-light a slight advantage.)
Paried T-tests ('x <-- y' means 'x is better than y'):
NB+ELR <-- SVM-light[best_ave] (p< 0.023)
TAN+ELR <-- SVM-light[best_ave] (p< 0.036)
GBN+ELR <-- SVM-light[best_ave] (p< 0.0078)
See here for the 'training time' data for various algorithms.
Compare to the work in [GGS97]
Finally, our companion paper [GGS97] also considers learning the parameters of a given structure towards optimizing performance on a distribution of queries. Our results here differ, as we are considering a different learning model: [GGS97] tries to minimize the squared-error score, a variant of Equation 9 that is based on two different types of samples --- one over tuples, to estimate P(C | E), and the other over queries, to estimate the probability of seeing each ``What is P(C | E = e)?'' query. By contrast, the current paper tries to minimize classification error (Equation 3) by seeking the optimal ``conditional likelihood'' score (Equation 4), wrt a single sample of labeled instances. Moreover, our current paper includes new theoretical results, a different algorithm, and completely new empirical data.
Recall from the paper:

Earlier Publications
The current paper significantly extends the earlier short papers
-
Structural Extension to Logistic Regression: Discriminant Parameter Learning of Belief Net Classifiers
Russell Greiner and Wei Zhou
Proceedings of the Eighteenth Annual National Conference on Artificial Intelligence (AAAI-02), p. 167-173, Edmonton, Aug 2002. -
Discriminative Parameter Learning of General Bayesian Network Classifiers
Bin Shen, Xiaoyuan Su, Russell Greiner, Petr Musilek, Corrine Chen
Proceedings of the Fifteenth IEEE International Conference on Tools with Artificial Intelligence (ICTAI-03), Sacramento, Nov 2003.
as it provides:
-
PROOFS of the claims (Article 1 above simply stated the claims; n.b., the proofs are non-trivial)
-
many more EXPERIMENTS --
-
complete series of results on G<T, G~T, G>T (which is completely new),
for both complete and incomplete data,
comparison not only within different BN structures (NB/TAN/GBN), but also
with other parameter learning algorithms OFE/EM/APN, etc.
-
-
a deeper ANALYSIS of the results.
It also assembles the various pieces into a single coherent story.
For problems or questions regarding this web page, contact [Bin Shen]
GSSZ04 Greiner et al. (2004)
GZ02 Greiner and Zhou (2002)
GD04 Domingos et all (2004)
FGG97 Friedman et all. (1997)
Note: Here, x+ELR performed comparably to C4.5 and SNB.
Check out the training time information for ELR with and without cross-tuning.




