Introduction to the Bonsai Decision Tree Language

Since its launch, the AppNexus Programmable Bidder has been an exciting and groundbreaking offering for advertisers, allowing them to decide how to value distinct impression parameters and prioritize them to determine an overall bid. This provides granular control over the bid price on each individual impression and enables media buyers to implement bespoke strategies for efficient and effective optimization. One way to achieve this via APB is using decision tree logic written in the Bonsai language.

The challenge for non-coders interested in turning over a new leaf has been understanding the Bonsai documentation in order to start writing a tree. This blog post aims to break this down for people familiar with advertising technology concepts but perhaps not familiar with coding, to make it easier for all budding gardeners!

What is a decision tree?

A decision tree is a popular way to model decisions and possible outcomes of those decisions, a bit like a flow chart but with a greener name! A tree is made up of nodes, branches and leaves. A node represents a decision to be made, and each branch represents the outcome of this decision. For Bonsai trees, there are exactly two branches from every node, because the decision node represents a test where the outcome can only be true or false (e.g. the test "Is the domain appnexus.com?" can only have two outcomes: "Yes" or "No").

The first decision node is often called the root node. A decision path in a tree is the route taken from the root node to the leaf. The leaf denotes the final outcome - a value to be used as the bid price or the bid multiplier, depending on the type of tree.

What is Bonsai?

Bonsai is a Domain Specific Language that AppNexus has developed to enable clients to express decision tree logic. Its simple grammar is similar to the programming language Python. We use Bonsai (and not Python) to ensure security, isolation and better performance.

How do I make decisions in Bonsai?

Features

In Bonsai, a feature represents a characteristic of the impression. This could be something:

  • directly from the bid request such as domain,
  • about the user or contextual environment such as segment presence, or
  • an Engineered Feature - a prediction provided by our own data science team's models, such as Estimated IAB viewthrough rate.

Within the nodes of your decision tree, you will test that a condition based on one or more features will hold true.

There are many different conditions that you could place on these features to represent decisions. See the following table for some examples.

Decision Bonsai condition
Has the user been in this segment for longer than 2 days?

segment[12345].age > 2

Does the impression originate from France, Germany or Italy?

country in ('FR','DE','IT')

Is the impression occurring on a weekend, OR between 7pm and 10pm?

any user_day in (0,6), user_hour range (19,22)

These decisions need to be translated into a machine-readable language: Bonsai conditions!

In order to discover which features are available and what values are valid in your tree, clients refer to the AppNexus Wiki for Bonsai Features.

Syntax

The syntax for this will look familiar, with operators such as = for equal to and > for greater than, but there's a few that are very specific to Bonsai.

To combine multiple features into a single decision, such as "Is it Friday AND is it between 6pm and 11pm AND is the user in segment 23456?" you can use the Bonsai syntax every and any to represent a logical AND and logical OR, respectively.

The decision in this example would look like:

if every user_day=5, user_hour in (18,23), segment[23456]:  

This simplification reduces the complexity of possible logical expressions within conditions and eliminates the need for bracketing.

Rather than listing out several key-value pairs as separate features, you can also use in or range to test for membership within a list or range of values as shown in the table above.

IF and ELSE logic

In order to understand how Bonsai decision tree logic relates to a decision tree that you would draw, it is useful to remember that in decision trees you branch in one direction only if certain conditions hold true. To reflect this in the code, we use an IF statement to create a branch in the code. An example is:

if condition:  
    do something

Notice how at the end of the IF statement there is colon. This shows that the next line of indented code should only be run IF the condition is true, which is where you would move along one branch of your decision tree.

The indentation is important as it is part of the language; in Bonsai, the indents must be created using tabs and not spaces otherwise the code will not compile (i.e. the machine will know that there is a decision but won't know what to do).

If the condition is not true, we need to know what to do when we move along the other branch, so every if statement must have a matching else statement.

(Note: this is different from Python where an else or elif statement is optional.)

An if...else statement looks like this:

if condition:  
    outcome_1
else:  
    outcome_2

Here, if the condition is not true, the next line of indented code is skipped and we move to the third line. else statements have no condition that has to be met so the next line of indented code will be run.

ELIF logic

elif is simply a contraction of "else if" and is used to simplify the code where there may be numerous conditions.

if condition:  
    outcome_1
elif other_condition:  
    outcome_2
elif another_condition:  
    outcome_3
else:  
    outcome_4

The indented code will only be run if the outdented line above it holds true. It should be important to note that order matters here because once you start moving along a branch (i.e. moving into an indented piece of code) you can't go backwards (i.e. outdent).

SWITCH statements

A switch expression can be used as an alternative to many chained if / elif statements. This can be useful if you have many values you want to test for a single feature. You can enter multiple values within a single case using commas, or a range using .. for features with integer values.
Just as every if statement must have a matching else statement, every switch statement must end with a default case.

switch feature:  
    case (condition_value_1):
        outcome_1
    case (condition_value_2):
        outcome_2
    case (condition_value_3):
        outcome_3
    default:
        outcome_4

The following switch statement expresses bids based on the day of the week in the user's timezone, beginning with a $2.40 CPM bid on the weekend (where 6=Saturday and 0=Sunday), $1.30 Monday to Wednesday (using a range) and $4.10 every other day (Thursday and Friday).

switch user_hour:  
    case (0,6):
        value: 2.4
    case (1..3):
        value: 1.3
    default:
        value: 4.1

To discover what syntax is available, clients should refer to the AppNexus Wiki article on the Bonsai Language.

What can the outcome of the decision be?

A node will always have two branches - one for when the condition evaluates to true and another for when the condition evaluates to false.

Each branch will lead to either:

  1. Another node (which will be the root node of a sub-tree) to include further decision conditions
  2. A leaf, which provides the final value for bid price / bid modification

A basic leaf is simply a numerical value representing the desired bid expressed in cost per thousand (CPM) or a multiplier on the AppNexus optimization-determined bid value.

There is also a feature available called Smart Leaves, which can provide more sophisticated ways to generate the CPM bid value as well as other advanced features. Stay tuned for the next article in this tutorial series to find out more about Smart Leaves! If you have questions or comments, please join the discussion below!

Anne Coghlan and Steve Paule are Implementation Consultants working mainly with buy-side clients. They have both been AppNexians since Fall 2014.

Steve Paule and Anne Coghlan

Read more posts by this author.

Subscribe to AppNexus Developer Blog

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!