From: Kevin Murphy (murphyk@cs.berkeley.edu)
Date: Wed 25 Jul 2001 - 08:11:31 EST
Message-id: <3B5DF293.B81098EA@cs.berkeley.edu>
Has anyone implemented AIC for trees? I realise that the tree growing
procedure does variable selection automatically - my goal is to learn
belief net structure where the local conditional probability
distributions (CPDs) are represented by trees (as in e.g., Nir
Friedman, 1996 - ref below). For this, I need to properly penalize each
CPD. This is my current implementation for the tree class (I have
similar code for the rpart class - I am assuming this is a
classification tree for now.)
logLik.tree <- function(tr) {
k <- length(attr(tr, "ylevels"))
nparams.leaves <- (k-1)*num.leaves(tr)
# specify the params of the multinomials at the leaves
nparams.struct <- 0 # ignore params needed to specify splits
df <- nparams.leaves + nparams.struct # degrees of freedom
structure(-2*deviance(tr), df=df, class="logLik")
}
num.leaves.tree <- function(tr) sum(as.numeric(tr$frame$var ==
"<leaf>"))
num.leaves <- function(tr) UseMethod("num.leaves")
To compute the num. parameters used to specify the tree structure, one
can use the recursive encoding proposed by Quinlan and Rivest. To do
this, I need a way to map a function down a tree and to return a list of
the values.
I could then write something like
n <- num.inputs(tr)
f <- function(x) {
if (is.leaf(x)) 1
else 1 + log2(n-depth(x)) + sum(tree.apply(f, children(x)))
}
nparams.struct <- tree.apply(f, tr)
How can I implement tree.apply, children, is.leaf and depth?
Kevin
@inproceedings{Friedman96,
author = "N. Friedman and M. Goldszmidt",
title = "Learning {B}ayesian Networks with Local Structure",
booktitle = uai,
year = 1996
}
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !) To: r-help-request@stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._
This archive was generated by hypermail 2.1.3 : Wed 10 Mar 2004 - 08:18:21 EST