Factorized conditional log-likelihood

Supplementary material

Alexandra M. Carvalho, Teemu Roos, Arlindo L. Oliveira, and Petri Myllymäki

This webpage makes available some auxiliary material related to the paper Factorized Conditional Log-Likelihood, including:

Theoretical insights
Datasets
Download
Running
Results
Further information

Get a preprint: pdf

If you use aCLL or fCLL in your research, please cite:

Alexandra M. Carvalho, Teemu Roos, Arlindo L. Oliveira and Petri Myllymäki, Discriminative learning of Bayesian networks via factorized conditional log-likelihood, Journal of Machine Learning Research, 12(Jul):2181-2210, 2011.

Theoretical insights

Dirichlet vs Uniform distribution: A pictorial study of Dirichlet versus Uniform distribution for a typical dataset.
Bad behavior of âCLL under OFE: Understanding the âCLL problem with typical datasets.

Datasets

Dataset used in the experiments:

Original data from the UCI repository.
Original discretized data, in .arff format, obtained using the Fayyad and Irani (1993) method implemented in WEKA package. Default parameters were used.

Datasets description:

Dataset		Features	Classes	Train	Test
1	australian	15	2	690	CV-5
2	breast	10	2	683	CV-5
3	chess	37	2	2130	1066
4	cleve	14	2	296	CV-5
5	corral	7	2	128	CV-5
6	crx	16	2	653	CV-5
7	diabetes	9	2	768	CV-5
8	flare	11	2	1066	CV-5
9	german	21	2	1000	CV-5
10	glass	10	7	214	CV-5
11	glass2	10	2	163	CV-5
12	heart	14	2	270	CV-5
13	hepatitis	20	2	80	CV-5
14	iris	5	3	150	CV-5
15	letter	17	26	15000	5000
16	lymphography	19	4	148	CV-5
17	mofn-3-7-10	11	2	300	1024
18	pima	9	2	768	CV-5
19	satimage	37	6	4435	2000
20	segment	20	7	1540	770
21	shuttle-small	10	7	3866	1934
22	soybean-large	36	19	562	CV-5
23	vehicle	19	4	846	CV-5
24	vote	17	2	435	CV-5
25	waveform-21	22	3	300	4700

Download

The WEKA package extended with fCLL-based learning of Bayesian network classifiers can be found here. We call into attention that:

The fCLL scoring criterion works with all local learning methods of Bayesian network classifiers provided in the original WEKA package.
The original WEKA package was updated to do not perform shuffling of the received input data (for comparison purposes among different implementations). This is achieved by the -ns option. See Running extended WEKA package for details.

The Combinatorica package extended with âCLL-based learning of TAN classifiers is available under request and includes:

Chow-Liu tree learning algorithm (1968) and its extensions for finding optimal branchings.
Edmond's algorithm (1967), non-recursive version.
Algorithm to learn TAN classifiers proposed by Friedman, Geiger and Goldszmidt (1997).

Running extended WEKA package

To run the available extended WEKA package:

Use the shell (or command prompt) to run your tests. No graphical user interface is made available with the fCLL implementation.
Use the same options as the ones described in Bayesian network classifiers in WEKA. The only differences are:
- To use the fCLL within local search methods use the -S fCLL option.
- To ensure that no shuffling of the input data is performed use the -ns option.

For instance, to run TAN classifier with fCLL scoring criterion over some data.csv, not supposed to be shuffled, with the observed frequency estimator smoothed with 0.5 pseudo-counts, in a 10-fold cross validation test, just use the command:


			java weka.classifiers.bayes.BayesNet -i -t data.csv -c last -ns -x 10 -D -Q weka.classifiers.bayes.net.search.local.TAN -- -S fCLL -E weka.classifiers.bayes.net.estimate.SimpleEstimator -- -A 0.5

Results

Empirical accuracy of classifiers, annotated with standard deviation, learned from complete data:

Classifier		GHC2	GHC2	TAN	TAN	TAN	TAN	C4.5	1-NN	3-NN	5-NN	SVM	SVM2	SVMG	LogR
Struct. Learning		LL	fCLL	LL	LL	âCLL	fCLL
Param. Learning		OFE	OFE	OFE	ELR	OFE	OFE
Dataset
1	australian	85.22 ± 1.35	85.51 ± 1.34	84.93 ± 1.36	84.35 ± 1.38	85.51 ± 1.34	85.36 ± 1.35	85.94 ± 1.32	82.46 ± 1.45	85.36 ± 1.35	85.94 ± 1.32	84.78 ± 1.37	75.80 ± 1.63	82.61 ± 1.44	83.62 ± 1.41
2	breast	96.19 ± 0.73	97.36 ± 0.61	96.19 ± 0.73	96.19 ± 0.73	97.66 ± 0.58	97.66 ± 0.58	95.90 ± 0.76	97.07 ± 0.65	96.93 ± 0.66	96.93 ± 0.66	97.51 ± 0.60	96.05 ± 0.75	96.63 ± 0.69	96.63 ± 0.69
3	chess	91.72 ± 0.84	92.92 ± 0.79	92.36 ± 0.81	97.09 ± 0.51	91.84 ± 0.84	93.01 ± 0.78	99.45 ± 0.23	94.85 ± 0.68	95.22 ± 0.65	94.20 ± 0.72	96.87 ± 0.53	99.26 ± 0.26	99.17 ± 0.28	97.24 ± 0.50
4	cleve	81.42 ± 2.26	82.77 ± 2.19	81.76 ± 2.24	80.79 ± 2.29	84.12 ± 2.12	82.77 ± 2.19	76.69 ± 2.46	78.38 ± 2.39	80.41 ± 2.31	82.77 ± 2.19	82.09 ± 2.23	72.97 ± 2.58	78.38 ± 2.39	81.42 ± 2.26
5	corral	98.44 ± 1.10	99.22 ± 0.78	100.00 ± 0.00	100.00 ± 0.00	99.22 ± 0.78	100.00 ± 0.00	92.19 ± 2.37	92.19 ± 2.37	92.19 ± 2.37	92.19 ± 2.37	89.06 ± 2.76	100.00 ± 0.00	100.00 ± 0.00	88.28 ± 2.84
6	crx	84.99 ± 1.40	86.06 ± 1.36	85.45 ± 1.38	85.44 ± 1.38	86.22 ± 1.35	87.14 ± 1.31	85.91 ± 1.36	82.70 ± 1.48	85.15 ± 1.39	86.22 ± 1.35	86.98 ± 1.32	79.94 ± 1.57	82.54 ± 1.49	86.37 ± 1.34
7	diabetes	78.91 ± 1.47	79.17 ± 1.47	79.04 ± 1.47	78.77 ± 1.48	78.12 ± 1.49	78.91 ± 1.47	77.60 ± 1.50	78.12 ± 1.49	77.86 ± 1.50	77.73 ± 1.50	77.47 ± 1.51	76.56 ± 1.53	77.86 ± 1.50	78.65 ± 1.48
8	flare	82.74 ± 1.16	82.93 ± 1.15	82.55 ± 1.16	81.71 ± 1.18	80.30 ± 1.22	82.55 ± 1.16	82.27 ± 1.17	80.11 ± 1.22	81.24 ± 1.20	82.65 ± 1.16	82.46 ± 1.16	82.27 ± 1.17	80.49 ± 1.21	82.55 ± 1.16
9	german	73.30 ± 1.40	73.90 ± 1.39	73.30 ± 1.40	73.90 ± 1.39	75.80 ± 1.35	74.20 ± 1.38	73.00 ± 1.40	69.80 ± 1.45	70.40 ± 1.44	73.20 ± 1.40	75.60 ± 1.36	66.60 ± 1.49	71.40 ± 1.43	75.80 ± 1.35
10	glass	77.10 ± 2.87	78.97 ± 2.79	76.64 ± 2.89	75.27 ± 2.95	73.83 ± 3.00	78.97 ± 2.79	75.70 ± 2.93	79.44 ± 2.76	77.10 ± 2.87	73.83 ± 3.00	75.70 ± 2.93	77.10 ± 2.87	78.04 ± 2.83	73.83 ± 3.00
11	glass2	85.89 ± 2.73	85.89 ± 2.73	85.89 ± 2.73	86.46 ± 2.68	85.28 ± 2.78	85.89 ± 2.73	82.82 ± 2.95	86.50 ± 2.68	83.44 ± 2.91	80.37 ± 3.11	86.50 ± 2.68	87.73 ± 2.57	88.34 ± 2.51	86.50 ± 2.68
12	heart	82.59 ± 2.31	83.70 ± 2.25	81.85 ± 2.35	82.22 ± 2.33	85.93 ± 2.12	83.70 ± 2.25	82.96 ± 2.29	83.33 ± 2.27	82.59 ± 2.31	83.70 ± 2.25	84.81 ± 2.18	78.52 ± 2.50	83.70 ± 2.25	84.81 ± 2.18
13	hepatitis	86.25 ± 3.85	88.75 ± 3.53	86.25 ± 3.85	88.75 ± 3.53	85.00 ± 3.99	90.00 ± 3.35	85.00 ± 3.99	87.50 ± 3.70	91.25 ± 3.16	92.50 ± 2.94	83.75 ± 4.12	87.50 ± 3.70	87.50 ± 3.70	78.75 ± 4.57
14	iris	93.33 ± 2.04	94.67 ± 1.83	93.33 ± 2.04	93.33 ± 2.04	94.00 ± 1.94	94.00 ± 1.94	93.33 ± 2.04	94.00 ± 1.94	94.67 ± 1.83	94.67 ± 1.83	94.00 ± 1.94	92.67 ± 2.13	92.67 ± 2.13	92.67 ± 2.13
15	letter	86.14 ± 0.49	86.44 ± 0.48	86.06 ± 0.49	88.96 ± 0.44	86.14 ± 0.49	86.40 ± 0.48	77.50 ± 0.59	90.92 ± 0.41	89.60 ± 0.43	89.04 ± 0.44	89.00 ± 0.44	94.20 ± 0.33	94.16 ± 0.33	86.10 ± 0.49
16	lymphography	81.76 ± 3.17	85.14 ± 2.92	83.11 ± 3.08	86.46 ± 2.81	83.78 ± 3.03	83.11 ± 3.08	78.38 ± 3.38	83.11 ± 3.08	83.11 ± 3.08	81.76 ± 3.17	82.43 ± 3.13	81.76 ± 3.17	82.43 ± 3.13	69.59 ± 3.78
17	mofn	90.61 ± 1.68	90.61 ± 1.68	90.90 ± 1.66	100.00 ± 0.00	90.04 ± 1.73	90.90 ± 1.66	85.58 ± 2.03	89.06 ± 1.80	86.35 ± 1.98	85.48 ± 2.03	100.00 ± 0.00	99.90 ± 0.18	100.00 ± 0.00	100.00 ± 0.00
18	pima	78.26 ± 1.49	78.39 ± 1.49	78.52 ± 1.48	77.74 ± 1.50	78.39 ± 1.49	78.52 ± 1.48	77.21 ± 1.51	76.95 ± 1.52	76.82 ± 1.52	76.69 ± 1.53	78.91 ± 1.47	76.95 ± 1.52	77.08 ± 1.52	78.26 ± 1.49
19	satimage	88.54 ± 0.71	88.25 ± 0.72	87.86 ± 0.73	87.60 ± 0.74	88.20 ± 0.72	88.20 ± 0.72	82.33 ± 0.85	87.86 ± 0.73	87.96 ± 0.73	87.82 ± 0.73	85.19 ± 0.79	88.69 ± 0.71	88.25 ± 0.72	83.54 ± 0.83
20	segment	95.29 ± 0.76	92.49 ± 0.95	95.29 ± 0.76	95.58 ± 0.74	91.17 ± 1.02	92.24 ± 0.96	94.15 ± 0.85	94.02 ± 0.85	93.38 ± 0.90	91.48 ± 1.01	94.66 ± 0.81	97.33 ± 0.58	97.46 ± 0.57	94.53 ± 0.82
21	shuttle	99.85 ± 0.09	100.00 ± 0.00	99.85 ± 0.09	99.84 ± 0.09	100.00 ± 0.00	100.00 ± 0.00	99.70 ± 0.13	99.90 ± 0.07	99.75 ± 0.11	99.64 ± 0.14	99.95 ± 0.05	100.00 ± 0.00	100.00 ± 0.00	99.95 ± 0.05
22	soybean	93.42 ± 1.05	93.42 ± 1.05	92.35 ± 1.12	93.24 ± 1.06	91.99 ± 1.14	93.42 ± 1.05	91.28 ± 1.19	90.21 ± 1.25	89.86 ± 1.27	89.32 ± 1.30	91.46 ± 1.18	91.46 ± 1.18	91.99 ± 1.14	89.15 ± 1.31
23	vehicle	73.17 ± 1.52	72.10 ± 1.54	72.58 ± 1.53	72.93 ± 1.53	70.33 ± 1.57	72.10 ± 1.54	67.73 ± 1.61	71.04 ± 1.56	71.16 ± 1.56	71.39 ± 1.55	71.75 ± 1.54	74.00 ± 1.51	64.54 ± 1.64	70.80 ± 1.56
24	vote	94.48 ± 1.09	91.03 ± 1.37	94.25 ± 1.12	94.94 ± 1.05	93.33 ± 1.20	91.49 ± 1.34	95.17 ± 1.03	92.87 ± 1.23	93.56 ± 1.18	93.33 ± 1.20	93.33 ± 1.20	94.02 ± 1.14	95.17 ± 1.03	92.64 ± 1.25
25	waveform	75.28 ± 0.63	78.19 ± 0.60	75.30 ± 0.63	75.34 ± 0.63	78.26 ± 0.60	77.72 ± 0.61	65.49 ± 0.69	70.79 ± 0.66	73.19 ± 0.65	74.68 ± 0.63	77.66 ± 0.61	80.51 ± 0.58	81.89 ± 0.56	71.36 ± 0.66

Statistical significance of the previous results. If the row is:
- significantly better than the column the cell is in orange.
- better than the column, without significance, the cell is in yellow.
- worse than the column, without significance, the cell is in blue.

Classifier	GHC2	TAN	GHC2	TAN	TAN	C4.5	1-NN	3-NN	5-NN	SVM	SVM2	SVMG	LogR
Struct. Learning	fCLL	âCLL	LL	LL	LL
Param. Learning	OFE	OFE	OFE	OFE	ELR
Competitor
TAN-fCLL-OFE	0.3702 0.3556	1.4447 0.0743	2.1265 0.0167	2.1328 0.0165	0.3143 0.3766	3.0001 0.0013	2.2507 0.0122	2.1595 0.0154	2.0682 0.0193	0.4286 0.3341	0.6083 0.2715	0.2110 0.4164	1.8000 0.0359
GHC2-fLL-OFE	--	1.4946 0.0675	2.2564 0.0120	2.2143 0.0134	0.0608 0.4758	3.0001 0.0013	2.3544 0.0093	2.2000 0.0139	2.1914 0.0142	0.3902 0.3482	0.7429 0.2288	0.1136 0.4548	1.6548 0.0490
TAN-âCLL-OFE	--	--	0.0429 0.4829	-0.3363 0.3683	-1.3050 0.0959	2.2571 0.0120	1.3383 0.0904	1.1705 0.1209	1.3149 0.0943	-0.3954 0.3463	-0.2857 0.3876	-0.5475 0.2920	1.3687 0.0855

We also compared the empirical accuracy of fCLL-based classifiers with:
- Global methods (only indirect comparison, that is, results were taken from the original papers):
  - BNC-2P and BNC-MDL classifiers obtained from the paper of Grossman and Domingos (2004).
  - TAN-EAR-OFE and MULTINET-EAR-OFE classifiers obtained from the paper of Pernkopf and Bilmes (2005).
- Local methods (direct comparison, that is, with the same test-split tests as the proposed scoring criteria):
  - TAN classifiers induced by the local interaction information (LII) scoring criterion (which is the sum for all nodes of the interaction information between the node, its parents and the class variable). Recall that fCLL is a weighted balance between LL and LII, that is, fCLL(G|D) = 0.322 LL(G|D) + 0.557 LII(G|D) + const (see Eq. (39) and footnote at page 20 in the manuscript), and so we wanted to evaluate if LII per se was an acceptable scoring criterion for learning augmented naive Bayes networks from complete data.

Classifier		GHC2	TAN	TAN	TAN	BNC-2P	BNC-MDL	TAN	MULTINET
Struct. Learning		fCLL	âCLL	fCLL	LII	CLL	CLL	EAR	EAR
Param. Learning		OFE	OFE	OFE	OFE	OFE	OFE	OFE	OFE
Dataset		The proposed scoring criteria			Just an heuristic!	Grossman and Domingos (2004)		Pernkopf and Bilmes (2005)
1	australian	85.51±1.38	85.51±1.34	85.36±1.35	85.51	87.04	85.95	85.92±1.52	84.47±1.48
2	breast	97.36±0.61	97.66±0.58	97.66±0.58	97.66	95.75	94.82	97.39±0.59	97.39±0.59
3	chess	92.92±0.79	91.84±0.84	93.01±0.78	86.94	95.78	95.50	94.18±0.72	91.93±0.83
4	cleve	82.77±2.19	84.12±2.12	82.77±2.19	83.11	80.03	74.37	81.07±3.51	80.06±2.32
5	corral	99.22±0.78	99.22±0.78	100.00±0.00	92.19	98.81	100.00	99.20±0.80	99.20±0.80
6	crx	86.06±1.36	86.22±1.35	87.14±1.31	86.22	84.20	86.03	85.75±1.61	84.22±1.37
7	diabetes	79.17±1.47	78.12±1.49	78.91±1.47	77.99	73.44	74.31	72.80±1.19	74.86±1.72
8	flare	82.93±1.15	80.30±1.22	82.55±1.16	79.64	81.96	82.24	83.11±0.51	80.58±2.32
9	german	73.90±1.39	75.80±1.35	74.20±1.38	76.10	73.57	70.23	69.70±0.43	73.40±1.86
10	glass	78.97±2.79	73.83±3.00	78.97±2.79	73.36	58.27	31.16	66.72±2.17	70.33±2.72
11	glass2	85.89±2.73	85.28±2.78	85.89±2.73	84.66	73.09	52.99	80.38±2.50	81.52±2.10
12	heart	83.70±2.25	85.93±2.12	83.70±2.25	84.44	81.26	53.65	81.48±2.49	84.07±2.24
13	hepatitis	88.75±3.53	85.00±3.99	90.00±3.35	87.50	83.82	81.23	84.33±3.14	85.67±3.64
14	iris	94.67±1.83	94.00±1.94	94.00±1.94	94.00	95.80	94.37	93.33±0.00	93.33±0.00
15	letter	86.44±0.48	86.14±0.49	86.40±0.48	74.58	81.70	64.70	85.72±0.49	86.72±0.48
16	lymphography	85.14±2.92	83.78±3.03	83.11±3.08	84.46	83.65	72.06	81.24±4.75	83.01±4.35
17	mofn-3-7-10	90.61±0.91	90.04±0.94	90.90±0.90	88.38	91.41	86.72	91.70±0.86	91.21±0.88
18	pima	78.39±1.49	78.39±1.49	78.52±1.48	77.86	73.34	74.31	70.71±1.40	75.13±0.74
19	satimage	88.25±0.72	88.20±0.72	88.20±0.72	84.76	82.55	77.80	81.75±0.86	85.40±0.79
20	segment	92.49±0.95	91.17±1.02	92.24±0.96	90.59	94.29	86.36	92.60±0.94	92.99±0.92
21	shuttle-small	100.00±0.00	100.00±0.00	100.00±0.00	99.70	99.53	98.14	98.97±0.23	99.53±0.16
22	soybean-large	93.42±1.05	91.99±1.14	93.42±1.05	91.81	92.46	66.27	92.18±0.85	92.67±0.53
23	vehicle	72.10±1.54	70.33±1.57	72.10±1.54	62.41	70.78	55.22	62.00±2.19	63.46±1.99
24	vote	91.03±1.37	93.33±1.20	91.49±1.34	90.57	95.83	95.80	92.65±0.86	91.48±0.46
25	waveform-21	78.19±0.60	78.26±0.60	77.72±0.61	80.36	73.30	67.19	75.30±0.63	76.83±0.62

Statistical significance involving fCLL vs LL and LII:

Classifier	TAN	TAN
Struct. Learning	LL	LII
Param. Learning	OFE	OFE
Competitor
TAN-fCLL-OFE	2.1328 0.0165	3.0680 0.0011

Further information

For any help please contact Alexandra M. Carvalho at .