help for tree

Facility for creating, managing, and evaluating decision trees

This suite of commands enables you to...

specify the structure and payoff variables for one or more decision trees;

specify values for payoff variables in terminal nodes;

specify probability values in all nodes;

propagate payoff values toward the roots;

extract payoff values at a specified node;

take differences in payoff values between a specified pair of nodes.

Preliminary Disucssion

This facility provides the capability to construct a representation of decision trees,
or, more generally, directed, rooted trees. These are
abstract structures that can be used for modeling decision processes or hierarchical relationships.
While this facility was initially developed for use with decision processes,
it may also find use in modeling hierarchical relationships.
See Raw Sums and Means for details on this matter.

The following discussion relies on an understanding of certain concepts:

Graph and Tree (in the topological sense)

Connected graph

Cycles in a graph

Forest

Node (or point or vertex)

Link (or edge or connection)

Directed link

To follow a link in the forward or reverse direction

Rooted tree

Root node

Interior node

Terminal node

Parent node

Child node (or branch)

Sibling nodes and sibling set

Path

Directed (forward) path, or path of descendancy

Reverse path, or path of parentage

Directed Acyclic Graph (DAG)

If you need clarification on these concepts, you should see
About Trees, below.

You can click here to jump to the section on syntax.

The trees are constructed in the current dataset, which must be empty
prior to the start of the construction phase. Such trees will contain user-defined "payoff" variables,
which carry numeric quantities that are of interest to the analyst,
and a probability variable, which contains values of a discrete distribution function,
as will be explained below.

Trees can model decision processes in that each interior node (or root) corresponds to a
juncture in a decision process; the forward links and the nodes that they lead to
(the children) correspond to the choices that one might take as one passes through that juncture.
That is, a decision juncture corresponds to an interior node or root; the possible choices are the
children. There are other places in the decision process where there are no more
choices to be made; those correspond to terminal nodes. (There may be places where there
is a next step in the decisions process, but where there is only one available "choice".
In the corresponding tree, such a node is not terminal; it is an interior node with
just one child. You can, optionally, reduce the parent and child to one node, or you may elect to keep them
as separate nodes, to model the various stages of the decision process.)

Another way to view the decision process is that there is a starting
population which divides into several sub-populations according to some particular characteristic,
and the sub-populations divide further, and so on, until they stop dividing.
The root corresponds to the point at which the initial population divides.
An interior node corresponds to a point at which a sub-population divides.

The probability value can be considered as...

the probability of
taking a particular choice at a given juncture in a decision process;

the proportion
of instances of the decision process that take the specified choice at that juncture;

the proportion of a population (at a parent node) that has the characteristic represented by the
particular child node.

The probability values ostensibly belong to the links. But each link leads to a
unique child node, so we can associate the probability with the child node.
(That is, in a directed, rooted tree, there is a one-to-one correspondence between links and
child nodes; this does not hold in a DAG.)

Payoff variables are assigned values in the terminal nodes; probability values are
assigned to all nodes, though usually not the roots. (See Superroot
for an exception.) The purpose of the
tree facility is to facilitate the propagation of payoff values toward the roots of the
trees, according to the probability values encountered along the way as the
reverse path to the roots is traced. Typically, analysts are interested in the
resulting payoff values at the roots or at one link away from the roots. Also,
typically, analysts are interested in the difference between payoff values
at two selected nodes.

The tree facility is capable of modeling a multitude of trees taken together,
that is, a forest.

In this facility, there are two types of names that you will be concerned with:
node names and variable names; we will discuss node names first. Every node is
given a name, which is a sequence of characters that adheres to the Stata convention on names:

A name is a sequence of letters, digits, or underscore characters; it begins with
a letter or underscore, and may contain digits thereafter.
It is contiguous, in that it does not contain spaces.
There is a maximal length of 32 characters. Certain names are reserved and cannot be used:
if, in, using, with.
(These are names that are syntactically significant in Stata commands, which
comprise a proper subset of the Stata reserved names.
Thus, node names are slightly less restrictive than variable names.)

Presumably, one may use non-plain-ASCII Unicode characters such as é, however
this has not been tested.

Node names are case-sensitive, and are "locally unique", which will be explained below.
Also, the name superroot is not allowed as a root name.
(It is allowed in other nodes, though there is probably no need for such a node name, and
may prove confusing to the user. See Superroot for more on
this matter.)

We may sometimes speak of the "tree name", which is the name of the root node.

Every node is designated as root, interior or terminal, a distinction known as
the node type, which is a fixed attribute of every node.
A root is a distinct node type, but, aside from its role as the entry point
of a tree, functions like an interior node.
A root or an interior node may have forward connections to other nodes - interior or
terminal, but never to a root. For a given node, the set of other nodes that it
directly connects to in the forward direction is known as its children. You can also
follow connections in the reverse direction, leading to the parent of a given
node, which may be an interior node or a root. The parent relation is unique; a node may have
many children, but only one parent; a root has no parent; every non-root node has a parent.
Since the parent relation
is unique, you can trace a unique path of parentage (backward) from any non-root node to a root.
If you trace that path in the opposite direction (which is forward), you get the
unique forward path from a root to any given node. Call this a path of descendancy;
every node has its own unique path of descendancy.

Technical note:
We just noted that a root has no parent. This statement is correct in the study
of topological trees, however, in the implementation of trees in the present program,
root nodes do have a parent: the superroot. But it is true that
the superroot has no parent.

A child node, especially an interior child node, may also be referred to as a branch,
as it potentially leads to more nodes, which can be considered as a tree in itself -
a "sub-tree".

In the case of multiple trees, every node belongs to a unique tree,
identified by the root that its parentage path leads to. Thus, we may speak of the
root that a given node belongs to.

While we define a tree as a graph with certain properties, it is helpful to think
of a tree in terms of constructing it from the roots outward, by attaching child nodes
as you go. Each node that is added must be new - distinct from any existing node.

The locally unique property states that the names of the children of any
given node are unique within that set of children (a sibling set).
Similarly, the names of roots are unique among the set of root names. This implies that the
path of descendancy from a root to any descendant node is has a corresponding unique
sequence of node names. Therefore, every node can be uniquely identified by the sequence
of node names along its path of descendancy. This will be a useful property in
many of the tree commands, as will be described below.

In terms of Stata data, the nodes are observations, and the payoff and probability variables
are Stata data variables. Therefore, all nodes carry the same set of payoff
variables plus a probability variable. (There may be a multitude of payoff variables,
but just one probability variable.) The names of the payoff variables are
user-specified (in tree init); the name of the probabilty variable is fixed
as prob.

When we speak of payoff variables, as well as prob, each of these is actually
a family of variables with a common "basename". There are always at least two
manifestations of each such variable:

a textual (string-type) variable, to hold expressions;

a numeric variable to receive the evaluation of those expressions.

For each payoff variable, plus prob,...

The textual variables use the basenames as their names;

the corresponding numeric variables are
named R_basename, that is they acquire an R_ prefix.

There may be additional manifestations of payoff variables, depending on commands that the
user may issue; see Raw Sums and Means.

The basenames are subject to the usual restrictions
on variable names (see naming conventions), but they also are limited to a length of 30 characters.
Certain other restrictions apply, as will be explained under Further Remarks.

The length should be <=29 if you intend to call tree eval with the
rawsum or means option(s), followed by tree diffs,
tree a_minus_b, or tree values with a prefix longer than 1.

The contents of the textual variables are expected to be valid numeric expressions, in that they can be evaluated
as numeric values - not necessarily immediately, but at the time that tree eval
is called. This will be explained further under Further Remarks.

The numeric variables may be considered as internal to the tree program, but
there may be occasions to reference them, as will be shown in Further Remarks.

In what follows, "payoff variable" may refer to the textual or numeric
manifestation of the variable, or the basename, or to the family of variables, depending on the context.

You specify expressions for the payoff variables in the terminal nodes, and for prob
in any type of node; these expressions are stored in the textual manifestation of these variables.
Later, when you call tree eval,

these expressions get evaluated, and the values are stored
in the corresponding numeric variables (R_basename and R_prob);

the payoff values are propagated from the terminal nodes into
parent interior nodes and toward the roots in accordance with R_prob values.
Think of this as having payoff values flow from terminal nodes
backwards toward the roots.

Optionally, other variants on the payoff variables may be generated and
propagated toward the roots. See Raw Sums and Means.

Payoff variable
names are independent of node names. That is, a node and a payoff variable may have the same name;
you probably don't want to do this, as it may confuse people, but won't confuse the tree program.

Syntax

Some of these syntax descriptions include various namelists, which are
space-separated sequences of node names - nodes to be created.

Some of these syntax descriptions include treepath, which serves to identify
a tree root or any node. It is a space-separated sequence of existing node names,
starting with a root name, followed by 0 or more interior node names, tracing
the path of descendancy to a given node; it is the unique node-name sequence that corresponds
to the node's path of descendancy. It may or may not end at a terminal node, depending on the
context.

Some of the options to these commands will be explained below.

Initialize the current (empty) dataset to hold decision trees

tree init payoffvarlist [verbose]

where payoffvarlist establishes the basenames of payoff variables to be included
in the trees.

Create one or more decision trees

tree create treenamelist [, verbose]

Where treenamelist is a list of root names of trees to be created.

Establish one or more nodes to be attached at a specified tree or interior node

tree node, at(treepath) [interior(intnodenamelist) terminal(termnodenamelist)
verbose]

Alternative syntax

tree node treepath [, interior(intnodenamelist) terminal(termnodenamelist)
verbose]

Where treepath (described above) identifies an existing tree or interior node.

intnodenamelist and termnodenamelist are names of interior and terminal
nodes to be established as children of the node identified in treepath.

Draw a textual diagram of the tree structure

tree draw [varlist]

Draw an image of the tree using Stata graphics capabilities

tree plot [varlist] [, superlabel(superlabeltext)
numbers
gphsaving(gphfilename)
gphasis gphreplace
dosave(dofilename) doreplace prob_places(#) noprob
]

Due to the way this is programmed, you can also write

tree_plot ...

Either way, this is not to be confused with treeplot, a separate user-generated program,
which does a much different task.

varlist specifies variables to be displayed in the plot. The plot can become crowded if
too many variables are specified.

List the payoff variables and trees

tree des

Set the values of payoff variables and/or probabilities for a given node

tree setvals, at(treepath) [v1(v1exp) v2(v2exp)
... vn(vnexp) prob(probexp)
check nosub verbose]

Alternative syntax

tree setvals treepath [, v1(v1exp) v2(v2exp)
... vn(vnexp) prob(probexp)
check nosub verbose]

Where treepath (described above) identifies a tree or an interior node.

v1, v2, etc. are basenames of payoff variables, as specified in tree init.
That is, the basenames of the payoff variables become options in tree setvals.
So does prob.

v1exp, v2exp, etc. and probexp are expressions that can be evaluated
as numeric values, or rather, they can be evaluated when tree eval is called.

The setting of
payoff values is allowed only on terminal nodes. Thus, for an interior node, you may
set prob only:

tree setvals treepath [, prob(probexp) check nosub verbose]

or alternatively:

tree setvals, at(treepath) [prob(probexp) check nosub verbose]

These expressions may include references to global macros to be evaluated later,
when tree eval is called. However, you must use @ rather than $ to indicate
global-macro dereferencing.

probexp may also take the special value * to indicate a residual probability.

For a given node, you may set all the payoff variables and prob in one command,
or spread these actions over several commands. You may also change the values by issuing additional
tree setvals commands for the same node and payoff variables and/or prob.

Evaluate the payoff and probability values; propagate payoff values toward the roots;
optionally compute raw sums or means

tree eval [weight] [, rawsum(rawsumvars) means(meansvars)
retain verbose]

The weight feature applies to the means option only.

Check that the expressions for payoff variables and prob are valid
numeric expressions. (Missing values count as valid in this context.)

tree check [, verbose]

Take differences of payoff values between two nodes

tree diffs, minuend(treepath1) subtrahend(treepath2) [prefix(pref)]

Alternative command and syntax for differences

tree a_minus_b, a(treepath1) b(treepath2) [prefix(pref)]

Extract payoff values at a particular node

tree values, at(treepath) [prefix(pref)]

Preserve the probability settings

tree preserveprob [, channel(#) replace verbose]

Restore the probability settings

tree restoreprob [, channel(#) verbose]

Preserve the payoff value settings

tree preservepayoff [, channel(#) replace verbose]

Restore the payoff value settings

tree restorepayoff [, channel(#) verbose]

Preserve the probability and payoff value settings

tree preserveall [, channel(#) replace verbose]

Restore the probability and payoff value settings

tree restoreall [, channel(#) verbose]

Verify proper tree structure in the dataset

tree verify

Options not explained above

verbose: additional information is displayed as the command is executed.

channel(#) for the preserve and restore commands:
specify which, of possibly many "channels", the
preserve or restore operation is to use. The channel value may be any integer
from 0 to 99, with 0 being the default.

replace for the preserve subcommands: specify that the preserved
values may overwrite existing values in the indicated channel.

nosub for the setvals subcommand: prevent the substitution of $
for @.

check for the setvals subcommand: check that the expressions for payoff variables and prob are valid
numeric expressions. (Missing values count as valid in this context.)
This is meaningful only if all the components of the expressions are defined at
the time that setvals is called.

Note that there is also a tree check command. The check option in
tree setvals performs the check for the specific node indicated and for only the
variables specified; the tree check command performs the check for all nodes
and all payoff variables and prob.

prefix(pref) for tree diffs, tree a_minus_b, and tree values:
set a prefix for
the names of scalars that are to be defined. The defaults are
d_ for tree diffs and tree a_minus_b, and v_ for tree values.

rawsum(rawsumvars) for tree eval: specify variables for which to propagate
raw sums toward the roots. See Raw Sums and Means, below.

means(meansvars) for tree eval: specify variables for which to propagate
weighted sums and means toward the roots. See Raw Sums and Means, below.

retain for tree eval: specify that variables pertaining to rawsums or means
from an earlier invocation of tree eval are to be retained. The default action
is to drop them. See Raw Sums and Means, below.

superlabel(superlabeltext) for the plot subcommand: specify alternative
text to be written for labeling the superroot in the plot; the default is superroot.

numbers for the plot subcommand: specify that node numbers are to be
displayed in the plot.

gphsaving(gphfilename) for the plot subcommand: save the plot as a
Stata graphics (.gph) file.

As with the graph save command, if gphfilename is specified without an extension,
.gph is assumed.

gphasis for the plot subcommand: employ the asis option in saving
the plot. See graph save.

gphreplace for the plot subcommand: employ the replace option in saving
the plot; the file may be replaced if it already exists.

dosave(dofilename) for the plot subcommand: save the generated do-file
under the specified name. If dofilename is specified without an extension,
.do is assumed.

To create a plot, a do-file is generated containing Stata graphing commands.
By default, this is a tempfile; thus, it is deleted after is is run.
With this option, you can, instead, save the file.

doreplace used with dosave(dofilename), specifies that dofilename
may be replaced if it already exists.

prob_places(#) for the plot subcommand: specify the number of decimal places
to report probability values. The default is 3.

The plot will include probability values after the node names, in parentheses. Note that
this is R_prob, that is, the numeric value, rather than the prob expression. Therefore,
you will not get values unless you have already called tree eval.
(You will not get updated values unless you have called tree eval since any
changes to prob values (via tree setvals) have occurred.)

noprob for the plot subcommand: suppress the reporting of probability
values.

How to use the tree commands - overview

The tree suite of commands is designed to facilitate the creation and evaluation of decision trees.
For a discussion about trees, see About Trees, below.
Another benefit is that it can utilize payoff and probability values that you develop
in Stata, Thus, if the payoff and probability value development process is done in Stata
(or if the values can be imported into Stata), then these values can be automatically
conveyed into the tree(s). See Practical Considerations.

tree is used in several phases and sub-phases:

(1) Construction; defining the shape of the tree or forest:

Establish the tree (or forest) structure; call tree init (once).

Establish roots and nodes; call tree create and tree node
(typically many times).

(2) Populating the payoff and probability values:

Call tree setvals to populate the payoff values in terminal nodes,
and the probability values in all nodes.

(3) Analysis:

Call tree eval to propagate payoff values toward the roots.

Call tree diffs to calculate differences in payoff values, or
tree values to obtain payoff values.

Optionally, use the results of tree diffs and/or tree values in
your choice of calculations.

How to use the tree commands - details

tree init initializes the dataset to model a set of decision trees.
The current dataset must be empty prior to calling this; it is called just once
in a tree-analysis session, whereas, any other tree command may be called
multiple times.

As there may be a multitude of trees, tree init actually enables you to
establish a forest.

You must specify payoffvarlist, a set of basenames for the payoff variables.
These names are limited to a length of 30, with certain other restrictions;
see Further Remarks.

Each name in payoffvarlist will establish a string and a numeric (double)
variable, as noted above, which are common to all nodes in all trees. More on this below, under
Further Remarks.

tree create will create one or more directed rooted trees.
More accurately, it establishes root nodes, on which you may
subsequently build trees. Thus, "tree" may refer to either a whole tree or just
its root node, depending on the context.

treenamelist is a list of names for the trees.

tree create may be called as many times as you like; each call just adds more roots
on which you may grow trees.
Thus,

tree create abc xyz

is equivalent to

tree create abc

tree create xyz

You can create a multitude of trees, or just one, according to your design and preference.
That is, you may be modeling the relative benefits of two courses of action.
Each of these courses may be modeled by a tree, or they may be branches
located on a master tree. You can do it either way. (See Superroot for more on
this matter.)

If there are multiple trees, they all share the same set of payoff variables.

Once one or more trees are established, you can add nodes by using the tree node
command. Typically, you call it multiple times, building up trees from the roots
outward, adding node upon (interior or root) node, and also establishing terminal nodes.
Thus, while the root may be considered as an "entry point" for tracing a path
through an existing directed, rooted tree, it also may be viewed as the "starting point" for
building a tree.

The first calls to tree node would have just a tree root name in treepath;
later calls would cite a path to an interior node. Thus, for example, you could
code:

tree init qaly cost

tree create a

tree node, at(a) int(b c)

tree node, at(a b) term(d e)

tree node, at(a c) term(f g)

Once an interior node is created, it is allowed to have children;

once a terminal node is created, it is prohibited from having children.

Notice that tree node performs two actions:

creates one or more new nodes;

attaches these nodes to a specified tree or interior node, which becomes the parent of
the new node(s).

Thus, it can attach only new nodes, thereby preventing cycles (directed or non-directed).

Once the tree structure is established, you can call tree setvals to set the
payoff and probability values. Each payoff variable becomes an option in the syntax
of tree setvals; so is prob. But note that the setting of payoff values
is allowed only in terminal nodes, while prob may be specified in interior
or terminal nodes. Thus, if you have cost and qaly
as payoff variables, then you can specify

tree setvals treepath, cost(costexp) qaly(qalyexp) prob(probexp)

in a terminal node, but only

tree setvals treepath, prob(probexp)

in an interior node.

Also note that the contents of these options are expressions, which are more encompassing
than literal numeric values. Thus, you may specify cost(12000*2), rather than cost(24000).
This possiblity can be useful, as will be explained later.

The contents of these options are stored for later evaluation; they are not evaluated
at the time they are specified, unless you specify the check option, in which case
they must be valid expressions. Therefore, with the check option, any references to
data variables, scalars, or global macros must refer to entities that exist at that time, though the
values at that time are irrelevant.

You can refer to global macros, but you use the @ character in place of $. Thus, you may
specify

tree setvals treepath, cost(@cost_lr_mm70)

assuming that cost_lr_mm70 is a global macro containing a number or a numeric expression.

As the expression is captured and stored, @ characters will be converted to $.
Then at eval time, the $ will trigger the evaluation of a global macro.
This is done to enable that deferred evaluation. If you were to specify

tree setvals treepath, cost($cost_lr_mm70)

then, $cost_lr_mm70 would be evaluated at the time that this tree setvals command
is executed, and the resulting value, rather than $cost_lr_mm70, would be stored.
As this would be a constant, this stored expression would not be sensitive to subsequent changes
to the value of the macro cost_lr_mm70.

In case you need the @ to remain as-is, specify the nosub option.

There is one special value allowed for probexp: *. Thus, you may specify
prob(*). This signifies a residual probability value:

1 - (sum of sibling prob values that are not *)

If there are multiple instances of prob(*) among a sibling set, then the
residual probability is distributed equally among them.

tree eval will invoke the evaluation process. Probability expression are evaluated
in all nodes; payoff expression are evaluated in terminal nodes.
Then, for each payoff variable, values are propagated toward the roots by taking, at each
interior node and root, the product of the value and probability in each child, and summing them across all child nodes.
(This can be considered as an inner product, a weighted sum, or an expected value.) This is done iteratively from the terminal
nodes toward the roots.

Optionally, raw sums and means may be generated and
propagated toward the roots. See Raw Sums and Means.

After tree eval has been called, you can call tree diffs, which will,
for each payoff variable, take the difference between the numeric values at the two specified nodes,
yielding

(value at treepath1) - (value at treepath2)

The results are stored in scalars named prefbasename
(pref and basename are separate entities, but they runtogether, lexically);
The default pref is d_, yielding d_basename.
Subsequently, you can refer to these scalars for other calculations.
Thus, with the example of cost and qaly, using the default pref,
you get scalars d_cost and d_qaly.

pref must not be longer than 32-(maximal length of payoff basenames).
It is not possible to specify a null pref.

tree a_minus_b, is a synonym for tree diffs. It is provided as a convenience,
as the syntax and semantics may be easier to remember.

Another possibility is to use tree values, which is similar to tree diffs, but it extracts the values of
payoff variables at a single specified node, rather than the differences at a pair
of nodes. Its default pref is v_.

For tree diffs, tree a_minus_b, or tree values, any pre-existing
scalars of the name prefbasename would be overwritten. Therefore, if you use both
tree diffs (or a_minus_b) and tree values in the
same analysis, then the use of distinct pref values is wise, so as to keep the resulting
scalar names distinct. You might also run alternative analyses on the same setup,
or extract values from a different pair of nodes (or single node),
using distinct pref values to preserve the results under distinct scalar names.

The various preserve and restore subcommands will preserve and restore
payoff or probability expressions, or both. These may be used to facilitate
the running of alternative scenarios and sensitivity analyses.
You might establish a set of probabilities and terminal-node payoff expressions that you
regard as a base-case scenario. After running analyses on this base case, you may
then want to adjust certain probabilities and/or payoff expressions, and rerun
the analysis. (You would rerun tree eval, tree diffs, and any necessary further
calculations.)

The benefit of the preserve and restore subcommands occurs when you want to run
a multitude of alternative scenarios and sensitivity analyses.
Typically, each such analysis deviates from the base case in a different way, and
you would want to return the values to the base case before making the adjustments
that pertain to the next analysis. For example, if one analysis changes cost (in a
multitude of terminal nodes}, and another analysis changes qaly, then you would
want to return cost to its base-case value before doing the second scenario.
The restore subcommands conveniently take care of this.

Any of the preserve subcommands (tree preserveprob or tree preservepayoff or tree preserveall)
may be issued at any time; they will save the present state of the probability or payoff (or all) expressions.
It is appropriate to do this after the base-case values are established, but before any
adjustments are made for scenario/sensitivity analyses.

Whether you use tree preserveprob or tree preservepayoff or tree preserveall
would depend on which of the settings (probability or payoff variables or both)
you expect to alter and need to be restored later.

A corresponding restore subcommand (tree restoreprob or tree restorepayoff or tree restoreall)
should be issued prior to making adjustments for a subsequent scenario/sensitivity analysis.

As noted above, the preserve and restore subcommands have an optional
channel(#) option, allowing you to specify which, of possibly many "channels", that the
preserve or restore operation is to use. The channel value may be any integer
from 0 to 99, with 0 being the default. Thus, you may establish a multitude of base cases,
in case that is useful. If you have only one base case, then you can ignore this option.

The preserve subcommands have a replace option. This is used if you nave already
done a preserve (using the same channel), and want to overwrite the previously-preserved values.

At any point, you may view the tree structure in a textual graphic form by calling
tree draw. It will display one line for each node, with
connecting lines and indentation to indicate the hirearchical relations, similar
to the output of the tree command in the Windows command prompt.
Integers will be displayed on the left side; these are the Stata observation numbers,
which may help you in diagnosing data problems that may arise.
(You can list a given observation, though tree draw can give you the
same information. You can use the observation number to index a variable to retrieve
a value from a specific observation, though tree values can also do that.)
Terminal nodes are marked with an asterisk to the right of the node name.

The observation numbers will not necessarily be in sequential order.
The order diplayed reflects the tree structure, whereas the observation
numbers reflect the order in which the tree was built (the order in which nodes
were added).

The optional varlist is a set of variables that will be displayed
in the output. It is best not to specify too many variables, as the display will
get crowded.

Note that there are two methods of obtaining a visual representation of the tree:
tree draw and tree plot. The latter gives a more natural image of the
tree, while tree draw may be better for viewing values of selected variables.

Further Remarks

As noted previously, node types are permanently set when a node is created. This
can potentially create a discrepancy with the graph-theoretic idea of node type,
which is determined by the connectedness of nodes. In this latter sense, any node
with no children is terminal. By contrast, the tree facility allows you to
create interior nodes with no children, which seems like a contradiction from a
theoretical viewpoint. But actually, all interior nodes have no children
when they are first created; you subsequently have the option to attach nodes to
them. However, if an interior node is left with no children, then the
tree may be regarded as incomplete, and may prove to be useless. The result is that,
after tree eval, a value of 0 will occur for all payoff variables at such a node,
and will contribute 0 to the parent node. More on this at Miscellaneous Remarks.

The converse situation, a terminal node with children, is impossible to
generate with the tree facility.

The children of an interior nodes might be...

all interior;

all terminal;

a mixture of interior and terminal.

Whether a mixture of types occurs will depend on the structure of the decision process being modeled.
Probably, most sibling sets are exclusively of one type, but mixtures do occur, in which case the
tree node command would have both the int(intnodenamelist)
and term(termnodenamelist) options.

The child nodes of a particular interior node may be specified in one or a multitude of tree node commands.
Thus,

tree node, at(a b c d) int(e f g}

is equivalent to the three commands:

tree node, at(a b c d) int(e)

tree node, at(a b c d) int(f)

tree node, at(a b c d) int(g}

That is, each call to tree node for a given location (at(treepath))
will attach additional child nodes to that location.
You may build up the set of children of a given interior node in stages or all at once, whichever suits you.

As noted above, the names of the children of a given node must be "locally unique" - unique
within that sibling set, though not necessarily unique over all.
This is similar to filenames in a computer's file system, in which a name is unique
within its directory (aka folder), but not necessarily unique across different directories.
(Typically, the file system in most computer systems is a directed rooted tree,
or possibly a forest, depending on the system. Directories are interior nodes; files
are terminal nodes; the whole system may be one tree with one root, or each storage device is
a root of a tree, depending on the system.)

Also as noted above, for each payoff variable specified in payoffvarlist, as well as prob,
two Stata variables will be generated: a string (strL) and a
"shadow" double variable. The string variable has the same name as given in payoffvarlist
(i.e., the basename) (or prob); the double has the same name, but with an R_ prefix.
For example, if you specify cost as a payoff variable, then you will have
cost (strL) and R_cost (double). You also automatically get R_prob.
The string variable is for expressions that you specify in tree setvals;
the double variable holds the numeric evaluation of those expressions.
The tree eval command performs the evaluation of the expressions
prior to propagating payoff values toward the roots.

Technical note:
For payoff variables, the expression variables pertain to terminal nodes only.

Certain other shadow variables may be generated: S_basename, T_basename,
and M_basename, in response to certain options in tree eval.
See Raw Sums and Means.

If you invoke tree preservepayoff, then each payoff variable acquires another
shadow variable, basenamechannel, for example, cost0.

If you invoke tree preserveprob, then you get probchannel,
e.g., prob0.

Because of these shadow variables, you should not attempt to create a payoff variable with
the base name being the same as another, but with a R_ prefix. Thus, for example, you should
not have both cost and R_cost. The same goes for the variant variables
that result from the rawsum and means options, for example,
S_cost, T_cost, and M_cost.
See Raw Sums and Means.

Similarly, if you plan to use tree preservepayoff, then you
should not create a payoff variable name that is the same as another, but with a
suffix of your chosen channel number. For example (using the default channel 0), you should not specify both
cost and cost0 as payoff variable names. Similarly, if you plan to use tree preserveprob,
then you should not create a payoff variable named prob0.

Payoff variable names are subject to the usual restrictions regarding reserved names.
Additionally, they must not replicate variables or local macros that are used internally by the
tree program. These mostly start with __ or setvals_, which are unlikely
to be chosen by the user; the complete list is

__nodename,
__nodetype,
__branch_head,
__branch_tail,
__next,
__probsum,
__n_starprobs,
__residprob,
__residual,
__weight,
prob,
R_prob,
setvals_qui,
setvals_node_id,
setvals_varstoset,
setvals_vval,
setvals_vars_affected),
verbose,
check,
sub.

What is the advantage of having the payoff and probability values input as expressions?
There are at least two uses for this.

1: You can use "global" factors in the specifications, by using scalars:

tree setvals treepath, cost(24000 * scalar(costfactor))

(...and similar expressions for cost in all terminal nodes...

scalar costfactor=1

(...run analysis...}

scalar costfactor=1.1

(...run analysis again...}

This way, you have done an alternative, with cost increased by 10%.
(Note that this does not involve a change to any payoff variable expression, and
there is no need to use a preserve subcommand.)

Alternatively, this setup could be done using global macros:

tree setvals treepath, cost(24000 * @costfactor)

global costfactor=1

(...run analysis...}

global costfactor=1.1

(...run analysis again...}

2: You can have dependency of one variable on another:

#delimit ;

tree setvals tavr_avail low_interm_risk tavr_elig age65_79 tavr lr,

...

age(70) sal_labor(1315.0) unpaid_work(15341.0) active_leisure(10855.8)

valact((R_sal_labor+R_unpaid_work+R_active_leisure) * `wage_cba_70') prob(.471805);

There are some things worth noting here.

valact is a payoff variable. Therefore, it is an option in tree setvals.

wage_cba_70 is a local macro, one of a series of similar macros which have been
defined prior to this command. More on this, below.

Importantly, references to other payoff variables use the R_ versions of these variables:
R_sal_labor, etc. This is because we need a reference to the numeric value,
not the expression (which is a string). (There is a way to invoke the evaluation
of such an expression, but it is more complicated, and would replicate what
tree eval does internally.)

Finally, and this is not apparent from what was shown here, the referenced variables
(R_sal_labor, etc.) come before the variable being evaluated (valact) in
the order as declared in tree init. The reason is that tree eval
evaluates the variables in the order as declared in tree init, and you want each
referenced variable to have been evaluated prior to being referenced. Otherwise, you
get a leftover or unassigned (missing) value, which is probably wrong.

Therefore, if you plan to have any such dependence of some variables on others, you must
declare them in tree init in an order which conforms to the order of dependency
in the expressions in tree setvals. Consequently, if there are multiple instances
of dependency of some variables on others within any given instance of tree setvals,
then all such dependencies must be compatible with the same ordering of variables.
Note, too, that there must be no cycles of dependency,
however, this latter point is implicit in the reliance on a single order of variables.

Similarly, if such depencencies occur in multiple instances of tree setvals,
then they all must conform to the same order of variables as was declared in tree init.

In this tree setvals example, the expressions for sal_labor, unpaid_work, and active_leisure
appear before that of valact, but that is irrelevant, and could have occured in
any order. What matters is the order in tree init.

(R_prob is evaluated prior to any payoff variables, but you shouldn't have a need to
reference it. For the same reason, the expression for prob() should not reference payoff variables;
you would not get the current value. But again, you shouldn't need to do this.)

Returning to the local wage_cba_70, we could, aternatively, use a variable:

...

valact((R_sal_labor+R_unpaid_work+R_active_leisure) * wage_cba) prob(.471805);

where wage_cba is a numeric variable that gets assigned appropriate values,
presumably dependent on age, in this case.
(If you use the check option, then it must be defined previously, though the
values are not relevant until tree eval is called. One could initially set wage_cba
to missing, prior to this call to tree setvals; then, later replace it with useful
values prior to calling tree eval.)

Note that, by having wage_cba be a variable,
you can adjust it and rerun the analysis to implement alternative scenarios.
(Or it could be a global macro or scalar, but then there ought to be a multitude of them,
corresponding to different ages.)

As noted, the tree diffs command generates scalars named d_basename
(or generally, prefbasename).
Some of these scalars may be of direct interest for analysis,
or they may be useful in further calculations, but that is for the user to work out.
One commonly used calculation is an icer (Incremental Cost-Effectiveness Ratio):

scalar(d_cost)/scalar(d_qaly)

Raw Sums and Means

tree eval can also calculate raw sums and means. This may be useful when modeling
hierarchical relationships.

The rawsum(rawsumvars) option allows you to specify payoff variables for which
you want raw sums to be propagated toward the roots. That is, at each interior node,
the sum of the values at the children is calculated. These values are carried in
variables named S_basename, for example, S_cost.

The means(meansvars) option allows you to specify payoff variables for which
you want means to be propagated toward the roots. That is, at each interior node,
the mean of the values at the children is calculated. This calculation is weighted
by the weight feature, which accepts iweights. The default weight is 1.
Thus, in the absence of a weight specification, the weight is the
count of terminal nodes that lie beyond the given node (in the subtree rooted at
the given node). See additional notes at Miscellaneous Remarks.

A variable named __weight is created (actually, it is present at all times,
not just when specifying a weighted mean). The weight expression may refer to R_ variables,
since these values are calculated prior to computing __weight.
__weight is calculated in the terminal nodes and summed back to the roots. (That is, references to
R_ variables are evaluated only in the terminal nodes. At an interior node, the
weight is the sum of weights in descendant nodes - not based on the "local" values
of R_ variables.)

If means(meansvars) is specified, then these variables are created:

T_basename - the weighted sum of basename

M_basename - the weighted mean of basename

For example, T_cost and M_cost.

The means(meansvars) option is the only action that is affected by the
weight feature.

In the absence of a weight specification (or with [weight=1]), T_basename=S_basename
if both the means and rawsum options are specified for the same payoff
variable(s).

The default behavior is that, any variables that result from earlier invocations of
tree eval with the rawsum or means options (that is, S_basename,
T_basename, or M_basename), such that the basenames
are not specified in the present invocation, will be dropped.

With the retain option, such variables are retained.

These rules apply, regardless
of whether rawsum or means was specified. (The option(s) might be absent,
or might be present, but not mentioning the variable basename(s) in question.)

When such variables are retained, they hold values that may or may not differ from
what they would have been, had you included their basenames in
rawsum or means options - that is, had they been recalculated in
the latest invocation of tree eval. This depends on whether the relevant input
values have changed since their original calculation. So it is the user's resposibility
to be aware and keep track of these effects.

When such variables are retained, notes are attached to the pertinent variables,
warning of this potential discrepancy. The text reads

retains value from earlier eval step

Additional instances of this note will be attached for each
relevant invocation of tree eval. Thus, of example, if
this note appears three times for S_cost, then the retained values came from
the third prior invocation of tree eval.

These notes are removed whenever the given variable is recalculated, that is
whenever the basename is mentioned in rawsum or means options in tree eval.

To illustrate the capability of modeling hierarchical relationships, we will show how to
constuct a tree of the states and counties of the US. We will include two payoff variables,
pop (population) and pcinc (per-capita income).

tree init pop pcinc

tree create usa

tree node, at(usa) int(al ak az ar ca co ct de)

etc., for all the states of the US.

(We used the postal abbreviations for the states)

tree node, at(usa al) term(jefferson montgomery chilton bibb morgan calhoun autauga)

etc., for all the countines in Alabama, then for Alaska, etc..

tree setvals usa al jefferson, pop(660) pcinc(20892)

tree setvals usa al montgomery, pop(230) pcinc(19385)

tree setvals usa al chilton, pop(44) pcinc(15303)

tree setvals usa al bibb, pop(23) pcinc(19918)

tree setvals usa al morgan, pop(120) pcinc(19223)

tree setvals usa al calhoun, pop(120) pcinc(20574)

tree setvals usa al autauga, pop(55) pcinc(24571)

etc., for all the counties in Alabama, and then for Alaska, and
so forth.

(For convenience pop is entered in thousands.)

You can then do...

tree eval [w=R_pop], mean(pcinc) rawsum(pop)

which will calculate the summed pop values and the mean pcinc, propagated
toward the roots, that is, the states and the whole US.

(Many warning messages appear because no prob values were set, but we are not
concerned with that in this case.)

At this point, you can type

tree draw pop pcinc S_pop M_pcinc

which will show S_pop (summed population) and M_pcinc (mean per-capita income)
in each state and the whole US, in addition to the counties. This is assuming that we had
completed the tree and entered all the pop and pcinc values for all the counties of the US.

Note that, in this case, the tree eval command has a weight factor and a rawsum
variable that are the same: pop. Consequently, we get __weight = S_pop.

The foregoing example started with the creation of a "main" tree named usa,
with the states as children of usa.
Another possibility is to set all the states as trees.
The construction would go like this:

tree init pop pcinc

tree create al ak az ar ca co ct de

etc..

{cmd:tree node, at(al) term(jefferson montgomery chilton bibb morgan calhoun autauga)

etc..

tree setvals al jefferson, pop(660) pcinc(20892)

tree setvals al montgomery, pop(230) pcinc(19385)

tree setvals al chilton, pop(44) pcinc(15303)

tree setvals al bibb, pop(23) pcinc(19918)

tree setvals al morgan, pop(120) pcinc(19223)

tree setvals al calhoun, pop(120) pcinc(20574)

tree setvals al autauga, pop(55) pcinc(24571)

etc..

The tree eval command would be unchanged.

Note that superroot (see below) would take the place of the usa tree.
That needs to be accounted for in any instances of tree values or tree diffs.

The data contained in this structure (either version) could also be configured in
a more traditional Stata manner, with state identifier values repeated. And results
could be effected by the use of egen or collapse commands.
But you may find it intuitive to use this tree-based approach, as it eliminates the
repitition of state identifier values.

(Another approach would be to split the state and county level data into separate but linked frames.
That still retains the repitition of state identifier values in the county table.)

Superroot

The trees are implemented as branches on (children of) a single master node, named superroot,
which is the parent of all trees in the whole forest.

Every treepath implicitly starts with superroot, which you may optionally include
when specifying a treepath. Thus,

tree node, at(a b) term(d e)

may, alternatively, be written as

tree node, at(superroot a b) term(d e)

The treepath superroot (alone) refers to this node, however there is a restriction
on how you may use it: you may not attach nodes to superroot using tree node;
only tree create does that, and it only attaches (new) tree roots.

You have the option to set prob in the tree roots. If you do so, then
tree eval will bring values back to the superroot. Thus, for example, if you code

tree setvals, at(x) prob(.25)

tree setvals, at(y) prob(*)

and if x and y are all the roots of the forest, then, tree eval
will bring payoff values into superroot. You may then refer to them in
tree values:

tree values, at(superroot)

This may be useful if the forest constitutes a meaningful whole entity, and you
can provide meaningful prob values for the trees. The same effect may be obtained
by placing all these "trees" as branches on a user-defined top-level tree.

You may also refer to superroot in tree diffs, however, this is an unlikely
situation.

Note that it is possible to set prob at superoot:

tree setvals, at(superroot) prob(.25)

however, this has no effect on a tree eval operation, and is therefore useless.

Note that the superroot is a feature of the tree program, and is not
generally included in the subject of topological trees.

Practical considerations

You may have a process that generates some of the input values for the tree(s):
payoff values in terminal nodes and/or probability values. You will need a way to
perform that process and then transfer the results into the tree(s); presumably, that
process will yield its output in scalars or global macros.

If this process involves calculations on Stata data, then you will need to switch
that dataset out; then bring in, or construct, the tree(s).

If you need to run that process just once, then you can...

run the input_generation process, yielding scalars or global macros;
presumably, this involves the use of other data;

clear the dataset;

constuct the tree(s), populate the payoff variables with references to
the scalars or global macros, and run the tree eval and analysis steps.

If you use scalars as the means for carrying values fromn the input-generation process
to the trees, then the clear step should not be clear all or clear *.
Similarly, do not type scalar drop _all. Any of these commands will drop all scalars.

Since the trees exist in a Stata dataset, you can constuct the tree(s) in advance,
and save it. Then, your procedure would be...

construct the tree dataset, including tree setvals to populate the
expressions for payoff variables and prob, with references to scalars or global macros;

save the dataset;

run the input_generation process, yielding scalars or global macros;

clear;

use the tree dataset and run the tree eval and analysis steps.

If you intend to repeatedly run the input-generation process, say, with varying input parameter
values, then you would definitely want to constuct the tree(s) in advance. Each iteration
would repeat the final three steps shown above. A program could be created to
perform these steps.

As this involves switching back and forth between different datasets, an natural technique
might be to use frames, switching between frames, rather than swapping datasets in and out.
frames is available in Stata 16 and higher. The author has tried this technique
with some success.

Some other possibilities for transferring values from the input-generation process
may include...

Use returned results. (One likely option is sreturn, but note that
tree uses the sreturn name node_id, so you should avoid using that name.)

Write the input-generation process in mata.

Write the input-generation process in Python. Python Integration is
available in Stata 16 and higher.

Presumably, the latter two options could obviate the need to swap the tree dataset
out and back in. But note that the author has not yet tried these techniques.

About trees

A tree, in the mathematical sense, is topological graph that is connected and acyclic.
A graph is a set of nodes (or vertices), together with a set of links, which are pairs of these same nodes.
Thus, a link, also known as an edge, serves to connect a pair of nodes.
The node set is typically taken to be finite, though infinite graphs can be considered;
they constitute a special topic,
with special considerations, and are not pertinent to the present discussion.
For more info, see
the Wikipedia article on Graph Theory.

An important feature is that one may construct a sequence of nodes
in which each sequential pair of nodes has a link joining them.
Call this a connected path. A link connects "neighboring" (aka "adjacent") nodes; a connected path
of more than one link connects a more distant pair of nodes.

Note that a connected path has a corresponding sequence of
links, in which each sequential pair of links shares a common node.
So you can think of a connected path as either a sequence of nodes or a sequence
of links.

We allow at most one link between any given pair of nodes.
(Actually, this is implicit if you regard the links as a set
of pairs of nodes.) The connected property states that
there is a connected path joining any two
distinct nodes. The acyclic property states that, as you follow a connected path,
without backtracking, you never
return to a node that was visited previously. This implies...

there is never a link from a node directly to itself;

the connected path from one node to another is unique;

there is at most one link between any given pair of nodes.

The trees that are managed by the tree commands have some additional properties:
they are directed and rooted.

Directed: the links have direction; they are ordered pairs of nodes.
Every link is from one node to another node. Thus, we may speak of following
a link in the forward direction, or the reverse direction.

Rooted: there is a unique distinguished node, known as the root, having the property
that there is a directed path (explained below) from the root to any other node.
More on this later.

If there is a directed link from node A to node B, then we say that
A is a parent of B, and B is a child of A.
A node may have multiple children; the children
of a node constitute a set of siblings. (Whether a node may
have multiple parents is not determined by just the directed and acyclic properties;
we will return to this soon.) The children of a node, and the children of the children
(etc...) are called descendants.

Some nodes may have no children; they are terminal nodes; all others are
interior or non-terminal. (The root can be considered as its own category,
or it may be regarded as interior, since it usually has children. One might consider
a tree that has only one node, which would be both the root and a terminal node. This
is a degenerate case, which we will ignore.)

In a directed tree, we may consider a directed path, a connected path
in which every link proceeds in the forward direction.

For directed trees, we must clarify that the acyclic property
is to be interpreted in the non-directed sense - in the underlying undirected graph.
There is another, related structure
known as a Directed Acyclic Graph (DAG), in which the acyclic property is interpreted
in the directed sense; a directed path never returns to a previously visited node.
A directed tree is more restrictive than a DAG. That is, every directed tree is a DAG;
not every DAG is a directed tree. A DAG may have a node that is the child of more than
one parent; multiple links converge on the same node. That situation is not allowed in a directed tree.

The rooted property states that the tree has a unique "entry point".
This designated node, the root, has no parents, and it is the only node to not
have any parents; all other nodes have at least one parent. (Actually, they have exactly one parent,
but that's a consequence of other properties, as we will soon see.)

As noted, a directed tree is more restrictive than a DAG.
When you combine the directed, acyclic, and rooted properties, one result is that
you never can have multiple edges converging to one node; a DAG may have such
edges. Thus, in a directed rooted tree, all non-root nodes have exactly one parent.
(In other words, the inverse of the directed link relation is a function.)

Since all non-root nodes have exactly one parent, then from any node, there is a unique
chain of parent nodes, a reverse route through a directed path, which must ultimately
end at the root. If you trace this path in the forward direction, you get a path from
the root to the given node. Since the graph is acyclic, this path is unique.

A forward-moving trip through the nodes presents you, at each interior node,
with a choice of which of possibly many children to go to;
these are the decisions that are modeled - the junctures in the decision process.

A directed rooted tree can model a hierarchy, though this may or may not be
relevant to a decision process. Also, a directed rooted tree
can be defined recursively: A directed rooted tree is either a terminal node or a node that
has children, where each child is a directed rooted tree.

A possibly multitudinous set of trees is called a forest. Within a forest, the trees
can be viewed as the connected components.

Terminal nodes are so-called because every directed path must eventially come to
one such node, and can go no further.

For further reading on trees, see
the Wikipedia article on trees.

Miscellaneous Remarks

In tree eval, the evaluation of R_basename occurs for all payoff variables,
every time tree eval is invoked, but S_basename, T_basename,
and M_basename are evaluated only when rawsum or means are
specified, and only for the specified payoff variables.

In tree eval, if a given payoff variable basename appears in both the
rawsum and means options, and the weight factor is 1 or absent, then
T_basename = S_basename.

The tree eval with the means option propagates the weights all the way
back to the roots. That is, the weight at an interior node is the sum of all weights
in the descendant terminal nodes. If you use a weight factor of 1 (or any non-zero constant),
then, the weight at any interior node is proportional to the number of descendant terminal nodes.
If the weight factor is 1 (or any non-zero constant), then,...

if a node has terminal nodes as its only children, then the resulting means at that
node are the simple (evenly weighted) means of the child values;

otherwise, the resulting means at that
node are not necessarily the simple means of the child values;

There is presently no provision for computing a simple mean at each interior node.

Be sure that the scalars generated by tree diffs or tree values
do not conflict with scalars that you reference in tree setvals.

Scalars persist; they stay around until explicitly dropped. Thus, when you reference a scalar,
either as input in tree setvals or output from tree values or tree diffs,
be sure that the value is from the desired instance in which the scalar was set.

In the expressions in tree setvals, if you type \@, it will be interpreted
as \$ but that \ will block the dereferencing of the global macro at eval time.
There is probably no need to use such a construct, but be warned that the appearance
of \ in such expressions may have undesired consequences, which the author makes
no claims about.

If a payoff variable has not yet been given a value in a terminal node, the result will be
a missing value in R_basename. The same goes for R_prob in any node.
Of course, you could also have an expression that evaluates to a missing value.
A missing value, for whatever reason, in R_basename will propagate to S_basename,
T_basename and M_basename if rawsum or means is
specified on the variable in question.

If a missing value occurs in a R_basename in a terminal node, or in R_prob
at any node, then a missing value will be propagated in R_basename back
to the root. That is, a missing value infects all nodes going back to the root.

This same effect occurs for S_basename and T_basename
where appropriate, except that
R_prob does not affect this situation; instead, __weight affects
T_basename (in terminal nodes). Also, since __weight is
summed back to the roots, it, too, can propagate missing values back to the roots.
(But omitting the weight factor in tree eval command (with means) does not generate
missing values in __weight; instead, it defaults to 1.)

On the other hand, and as noted elsewhere, an interior node with no children will
have R_basename evaluate to 0; the same holds for S_basename and T_basename,
as well as __weight, where appropriate. Note that

M_basename = T_basename / __weight,

which will yield a missing value in M_basename if __weight=0
or if T_basename is missing.

In tree setvals: you can't clear an expression value. But you shouldn't need to.

There is no capability to change a node type. Again, you shouldn't need to.
But you will likely do the tree construction using a do-file. This way, if
you decide to change the structure, you can edit the do-file, then clear
and rerun the file.

Do not sort the tree data; do not delete or insert observations. The tree
facility depends heavily on each observation remaining it its original location.

Similarly, do not alter any of the internal variables.

Some commands have a debug option; not documented.

Acknowledgement

The author is grateful to Jessica Klusty of Data for Decisions, for assistance in designing
the syntax and actions of this suite of programs.

Author

David Kantor. Email kantor.d@att.net if you observe any
problems.