# Digital Advertising: the Measure of Mobile Visits Lifts

PAOLO D’ALBERTO VERONICA MILENKIY FAIRIZ FI AZIZI  …  …  …  Paolo D’Alberto
Veronica Milenkiy  Fairiz Fi Azizi

###### Abstract

Mobile-phone advertising enables marketers to reach customers at a personal
level and it enables the measure of costumers’ reaction by novel approaches,
in real time, and at scale. By keeping a device anonymous, we can deliver
custom adverts and we can check when the device owner will visit a specific
mortar-and-brick location. This is the first step in a sale. By measuring
visits and sales, the original marketers can determine their return on
advertising and they can prove the efficacy of the marketing investments. We
turn our attention to the measure of lift: we define it as the visit
acceleration during the campaign flight with respect to a controlled baseline.
We present a theoretical description; we describe a general and a simplified
approach in composing the exposed and the control baseline; we develop two
different vertical approaches with different comparable solutions; finally, we
present how to carry the experiments and the measures for a few dozens
campaigns; these campaigns range from hundred thousands devices and counting a
few hundred visits to a handful locations, to sixty million devices and
counting million visits to thousands locations. We care about experiments at
scale.

###### category:

G.3 Probability and Statistics Nonparametric statistics, Statistical software,
Time series analysis

###### category:

A.3 Design and analysis of algorithms

###### category:

B.3 Theory and algorithms for application domains

###### category:

C.3 Computational advertising theory

###### keywords:

N-Sample, series, distribution comparisons, advertising

††terms: Statistics, Algorithms

P. D’Alberto, Veronica Milenkiy, and Fariz Fi Azizi. Visit Lifts

This paper has about 8 patents granted.

##  1 Introduction

Advertising reaches customers with propositions and suggestions to appeal the
features of a product to a tailored clientele in order to increase the product
acceptance and its craftsmen revenues. If the customer has a mobile device and
has been exposed to any adverts, we can measure their influence by counting
any form of active actions such as visiting brick-and-mortar locations. In
practice, advertising is a social experiment at large scale. Differently from
historical social experiments or medical trials, we do not have scale problems
and we have a rich often-continuous feature space describing our exposed and
control groups. As in a social experiment, we often have a clear intent for
the experiment but we may have limited or poor means to measures the effect of
the experiment. Common questions are: did the advertising campaign work? How
much did it work? How can we measure visits, goals? How can we claim that the
experiment brought more visits than a control baseline? We shall address most
of these questions in a constructive way: First, we shall propose one measure
and two methodologies; second, we shall describe how the methodologies are
related (one is more general than the other); and third, we present experiment
results and quantitative measures for the two different approaches. In the
following paragraph, we shall sketch an intuitive outline.

We measure a campaign goals by the lift, which is a visit acceleration. We use
a mental exercise as introduction. Two authors Paolo and Fi are reached by a
campaign advert on the same day (e.g., January 21, 2017), to play golf at
Pebble Beach during the next month of February. Fi plays regularly (at pebble)
and Paolo is no good. Fi is an example of re-targeting customers; that is, we
expose a customer already interested. Paolo is at best a new comer. Veronica
was not exposed but she regularly interacts with both Paolo and Fi: she is a
candidate for control because she could have being exposed on the same day
(January 21, 2017) but she was not then and thereafter. Intuitively, the
campaign has an effect if Fi will go more often than before or Paolo will tee
once or more. Inherently, there is a concept of acceleration; that is, exposed
has to do more after exposure and more than who is not exposed. Veronica will
give a reference how hard was to achieve the above goal. If Veronica plays
regularly, Fi should also be compared to Veronica. If they appear teeing off
at the same pace then they may prepare for the masters’ (more) or avoiding the
green because an incoming blizzard (less). If Veronica does not play but
Paolo’s excitement makes her aware of the beauty of the game, Paolo should be
compared to Veronica. Our measure of lift must capture this desire to change
the pace of visits as time unfold, this is why we use the term of
acceleration. Of course, we must consider an average acceleration and do not
forget this is a an intuitive but gross oversimplification.

The previous mental exercise introduces acceleration in combination with
matching across comparable people. How can we describe customers to draw a
comparison? In the example above, if we know that Fi has visited before
exposure and Veronica did as well, Fi and Veronica are better comparable than
Paolo and Veronica. The visits before exposure is a discriminating features.
If the campaign targets only males, Veronica would not be targeted and, thus,
we should not use her as control baseline. Some targeting features are
obtained by voluntary identification and others are the results of
approximations. We represent these approximated features using continuous
probabilities. In the best scenarios, we are targeting many-to-many matching
and thus once again aiming to the computation of average accelerations.

For third party campaigns, we do not know anything about the campaign
targeting and we must infer it by the people targeted. In the example,
Veronica is the closest control baseline to Fi or to Paolo as a function of
the features used: previous visits or gender. Interesting, there are different
approaches to matching and different matching algorithms will provide
different results. In this work, we encourage the application of different
methodologies and matching algorithms.

The organization of the paper follows. In Section 2, we introduce our
notations and the definition of Lift. We present also two interpretations: a
balanced approach in Section 2.1 and an unbalanced one in Section 2.2; we show
results for both. We present our original contribution for the features
computation in a continuous space in Section 3, which is composed of a
Location Graph, Section 3.1, and a User Profile, Section 3.6. We present our
original contribution about Matching in Section 4. We present experimental
results in Section 5 and we conclude in Section 6.

##  2 Problem Definition and Introductory Notations

We start by presenting yet another example: we start an advertising campaign
where we invite the exposed people to visit a coffee shop. The exposure is by
means of digital advertising and the visit is by means of a distance measure
between the mobile devices to coffee shops. The goal of any advertising is to
affect visits so that the exposed group has more visits than a control group
and, because exposed and control can be quite different in size, a better
visit rate. We may have very different ways to choose the exposed–control set.
We distinguish two ways based on the observation that the control group is
often larger than the exposed group: imagine the whole population versus
coffee drinkers.

  * Balanced:

We sample the control using a heuristic so to balance control and exposed,
without changing the average response of control, doing so, we can compare
directly the absolute number of visits but a relative measure is still
preferred. Then generalize the result to the whole experiment.

  * Unbalanced:

We keep the size of each set unbalanced, as they are, and we compare their
average response. There is no need to generalize the results found.

A balanced one will emphasize the actual response of each devices, because
their numbers are equal see Section 2.1 and Equation 15. This is natural we
like to compare things directly, one-to-one, but exposure touches a small set
and we have to make the control small. An unbalanced one may show how little
contribution the exposed group has in absolute number of visits, but because
the exposed and control groups are now different we must emphasize their
average performances. In principle, the balanced/unbalanced approach should
provide good estimates to the campaign performance especially for large
experiments. We shall show that the unbalanced approach is general enough so
that we can derive a version of the balanced approach. In practice, there are
constraints that will make the two approaches different. Of course, there can
be many variations and applications, a complete comparison is beyond the scope
of this work.

Assume that we have a tool to compute the response of any user: that is, for
any device $d_{i}$ and any date $e_{j}$ we have a quantitative measure

$r(d_{i},e_{j})$

that gives us the number of visits from time $e_{j}$ forwards and it subtracts
the number of visits before $e_{i}$. The response is a difference between two
interval of times in order to adjust for features that are time sensitive
(i.e., $e_{j}$); thus, we can account for their effects (better). In social
science and medical treatments, a device owner can have a response for being
exposed and a response for being not exposed: a treatment $\gamma$ and not
$\gamma$ (i..e., $r_{\not\gamma}$), sometimes placebo means no treatment and
sometime it means a different treatment, and both treatments could be given.
In such a scenario, the response would be this

$r(d_{i},e_{j})=r_{\gamma}(d_{i},e_{j})-r_{\not\gamma}(d_{i},e_{j})$

and we could estimate the effect of the campaign by estimating the expectation
of the response statistics:

$L=E[r(d_{i},e_{j})]=E[r_{\gamma(e_{i})}(d_{i},e_{j})-r_{{\not\gamma}(e_{i})}(d_{i},e_{j})].$
(1)

In practice, a user is either exposed or control. Thus for an exposed device
$r_{\not{\gamma}(e_{i})}(d_{i},e_{j})$ is zero and for a control device
$r_{\gamma}(d_{i},e_{j})$ is zero, thus for control the response has negative
contribution. At the limit, the fact that exposed and control can have
different sizes is no issue with the expectation of L; however, in practice
the lift should be written as follows

$Lift=E[r(d,t)|d\in\text{ Exposed}]+E[r(d,t)|d\in\text{ Control}].$ (2)

Where $E[x|y]$ is the conditional expectation of $x$ with respect to $y$, the
first mode of the response statistics, or lift, is a comparison between
expectations. Considering that control response is negative, lift is a
difference in expectations.111An explicit difference $E[r_{e}]-E[r_{c}]$ is
more common in literature as we report in the following. First, we must
consider correlation. Second, expectations are computed by averages (i.e., if
we use bootstraps, several samples of averages). Equation 2 is the foundation
of most comparative analysis in social science: our is yet another social
experiment and it can involve million of devices and people across the
country. In the following, we set the notations and definitions, and we do our
best in expressing Equation 2 on a clear mathematical footing. Our main goal
is the analysis of the statistics $r(d,t)$ and provide a clear and complete
characterization of it. We will dwell also in the lift statistics which is the
average of the original statistics.

We start with the definition of an impression $\iota(d_{i},t,\ell)$: an
impression has a device identification number $d_{i}$, it has a time stamp $t$
in seconds, and it may have a geographical locations as
$\ell=(latitude,longitude)$. In practice, an impression represents when a
device is exposed to an advert and possibly where this event happened. We may
distinguish two scenarios:

  1. 1.

The impression belongs to a campaign we want to measure performance, thus the
time is used to specify the first time a device is exposed and

  2. 2.

The impression has location $\ell$, we measure how close this device is to our
location of interest.

Intuitively, a campaign is a set of adverts delivered by different means:
mobile web, apps, sometimes using conventional digital advertising such as
websites’ banners and sometime by TV commercials. An exposed device has a
first time seen. We can define it also for a control device: it is when we
have the fist recorded impression during the campaign. Thus, all impressions
after the first time seen can be used for the measure of performance.

For us, the goal of a campaign is to invite the owner of a device, a user, to
visit a set of locations. These locations are the likes of coffee shops,
department stores, or movie-theater show rooms. Here, we define a location
$l_{i}$ by its geographical location $(lat,lon)$ and a campaign location set
as $L_{C}$.

The first connection between impressions, locations, and campaign performance,
is by the definition of a hit: a hit is an impression with the following
properties:

$h(d_{i},t,\ell)=\begin{cases}1&\text{if }\exists l_{i}\in L_{C},\exists
K>0,\exists\|.\|:\ell\times\ell\rightarrow\mathbb{R},\text{ s.t.
}\|\ell,l_{i}\|<K\\\ 0&\text{otherwise }\end{cases}$ (3)

A hit is an impression arbitrarily close to one location. We intend to use the
$L_{2}$ norm thus the hint in the notation of $\|.\|$, and it is a distance
function. Having a distance function is general enough that, if we like, we
can reduce the distance to a zero-one function as to belong or not to any
polygon describing the outside boundary of a building. Eventually an altitude
will be part of any geographical location and more interesting distances will
be used.

We shall digress a little by introducing a few important variations enriching
the definition of a hit. This is not required for the understanding of our
approach and it can be skipped at first reading. After this digression we
shall define a visit in Equation 6 on page 6.

Deterministic and stochastic hits. In Equation 3, we say that an impression is
a hit if it is within a radius from our location of interest. The radius is an
arbitrary choice and it represents a meaningful area. This choice is made a
priori before the campaign started and by the client. This is the first
priority of being a hit and thus a visit.

Sometimes, the location is in a private parcel. This natural area is described
by a polygon or set of vertices. Once the parcel is identified, any impression
in the parcel can be a hit. This definition is extremely useful for
investigating locations with large real-estate: that is, where the parking lot
is as important as the inside of the facilities. For example, this simple
mechanism can actually double the signal coming from hits and thus enhance the
experiment. We can envisions several combinations between the radius and
parcel based hit, these are beyond this short digression.

There is a third type of hit that is worth considering: it is a stochastic
hit. A hit with a range in $[0,1]$ can be liberating because there are so many
uncertainties that may contribute to a different measure of distance between a
location and an impression. If we accept that the latitude and longitude of an
impression inherit an error, if we accept that our estimation of the earth
radius is an approximation that varies as function of the longitude, if we
accept that we may have just a sample of the impressions available, and
eventually that the users may have behavioral idiosyncrasies in their use of
the mobile phone. If we accept all of the above, then we can move into a
stochastic measure in order to relax the condition of zero hits.

This can be an error in measure, thus we could use a normal distribution: we
could argue that the distance is

$d+\epsilon\mbox{ where }\epsilon\in{\cal N}(0,\sigma_{\ell})$

Such an error could be used to create a gray area around the radius of
interest and thus smooth the hit response function accordingly.

Another point of view is to consider the device path (i.e., the record of
impressions) as a stochastic process. A user visiting a location must be
entering the location and then leaving. If we measure an impression just
outside of the interest radius, what could be the probability the device will
step in unnoticed or it has stepped out noticed?

With major arguments to be proven, a Brownian motion with a drift describes
our scenario nicely: we say that for the impressions just outside the radius,
their distance from the location is like an inverse Gaussian distribution.

$p_{x}(x|\mu,\lambda)=\sqrt{\frac{\lambda}{2\pi
x^{3}}}\exp^{-\frac{\lambda(x-\mu)^{2}}{2x\mu^{2}}}$ (4)

For example, we take a location and for all impressions with distance less
than three time the radius, we compute the average and variance

$\dot{\mu}{=}\frac{1}{N}\sum_{i=1}^{N}d_{i}\mbox{ \bf and
}S^{2}{=}\frac{1}{N-1}\sum_{i=1}^{N}(d_{i}-\dot{\mu})^{2}$

Thus we could describe our process by

$\dot{d}\in IG(\dot{\mu},\frac{\dot{\mu}^{3}}{S^{2}})$

and a stochastic hit is based on a survival function

$sh(d_{i},t,\ell)=\begin{cases}{1-CDF_{\dot{d}}(d_{i})}&\text{if }R<d_{i}\leq
R+\frac{R}{2}\\\ 0&\mbox{otherwise}\end{cases}$ (5)

As for the parcel, stochastic hits are enrichment to the original definition
of hits, we let the data help describing the hits in conjunction with external
and accepted definition. We shall present experimental results and further
discussions about this type of visits in Section 5.4.

We conclude here our digression and now we can define a visit from the
definition of hits. In Equation 6, we may choose to lump multiple hits in an
interval of time into a single hit that we call visit:

$v(d_{i},t,\Delta t)=\begin{cases}1&\text{if }\exists t_{i}\in[t,t+\Delta
t],i\in[0,N>0],\exists H>0,\exists\\{\ell_{m}\\}\\\ &\text{ \bf s.t.
}\sum_{j=0}^{N-1}h(d_{i},t_{j},\ell_{m})>H\\\ 0&\text{otherwise }\end{cases}$
(6)

A visit is a function of a device, the locations in $L_{C}$ where we have a
hit, and the interval of time $\Delta t$. Such interval can be arbitrary, for
us it can be up to one day.

Now consider the flight of a campaign as a segment on a straight line: there
is a beginning and there is an end. A day is a single tick on the segment and
we have a discrete set of intervals or epochs $e_{j}$:

$V(d_{i},e_{j})=\sum_{j}v(d_{i},t_{j},\Delta t_{j})\text{ where
}t_{j},t_{j}+\Delta t_{j}\in[e_{i},e_{i+1})$ (7)

Equation 7 represents the visits per day for the device $d_{i}$ in the day
specified by epoch $e_{j}$. This is a time series. Given any epoch in this
time line, we may want to compute a discrete differential function to
determine the grade of increase or decrease. We call this response and we use
an even symmetric weight function:

$w_{k}=-w_{-(1+k)},\forall k\geq 0$ (8)

where

$\begin{cases}w_{k}={\bf e}^{-k}&k\in[0,M-1]\\\ w_{k}=-{\bf
e}^{k+1}&k\in[-M,-1]\end{cases}$ (9)

such as a modified Laplace function to weight accordingly visits at different
times.

$\Delta_{M}r(d_{i},e_{j})=\sum_{k=-M}^{M-1}V(d_{i},e_{j+k})*w_{k}$ (10)

The weight function is symmetric and the response $\Delta_{M}r(d_{i},e_{j})$
follows. The present epoch $e_{j}$ has maximum weight $w_{0}\sim 1$ as well as
the previous day epoch $e_{j-1}$ ($w_{-1}\sim 1$ ). At a minimum, $e_{j-1}$
and $e_{j}$ summarize the discrete difference of the visit rate; such a
symmetric weight function will help to smooth the response function. In
practice, we introduce the concept that a visit can belong to the interval
$[0,1]$. Furthermore, not every user has a response or visits, for that
matter, at epoch $e_{j}$. For example, if a device $d_{i}$ has its first time
seen epoch after $e_{j}$, it will not contribute. If the last impression is
before the epoch $e_{j-M}$, it will not contribute either.

Given a campaign $C$, its locations $l_{C}$, the flight beginning $e_{1}$ and
its ending $e_{T}$ with $T>1$, and a set of devices $d_{i}$ with $i\in[1,N]$,
we call the set $D$; we may want to measure the performance of the campaign by
its expectation of the response; that is, the average acceleration of visits.
A clear caveat is that not all devices will be active and they will not
contribute to the response at every epoch: for each epoch $i$, $N_{i}$ of the
$N$ will contribute to the true acceleration; if we keep $M$ as a constant we
can omit the $\Delta_{M}$:

$E[r(d,e)|(D,T)]\sim\frac{1}{T}\sum_{i=1}^{T}\Big{[}\frac{1}{N_{i}}\sum_{j=1}^{N_{i}}\Delta_{M}r(d_{j},e_{i})\Big{]}$
(11)

Thus, we can finally express our performance measure: We identify the exposed
group, the set of devices that have been exposed to the campaign adverts by E,
we find a suitable and comparable control group that we identify by C. Then
the quality of the campaign is summarized by the following expectation that we
call lift:

$Lift=E[r(d,e)|(E,T)]-E[r(d,e)|(C,T)]$ (12)

The process summarized in Equation 12 explains our original definition of lift
as in Equation 2, where in this latter equations we show that time is common
to both expectations and the negative contribution of control is explicit
because the response is computed for exposed and control separately. However,
our formulation can be restated with little modifications if users have
multiple treatments, thus different responses, at different times.

Practical considerations. The lift as expectation is powerful, but it does not
resonate to whom design the campaign. The sign is easy to understand: there is
a positive effect or there is a negative effect. Often, we used to transform
the lift measure into a relative number, percentage:

$Lift_{p}=100*\frac{E[r(d,e)|(E,T)]-E[r(d,e)|(C,T)]}{E[r(d,e)|(C,T)]}$ (13)

This is palatable because it provides a relative measure to a reference
baseline (i.e., control). Unfortunately, for small control lifts, the relative
measure can be unbounded. A small campaign can be unreasonably
profitable/unprofitable and with large variances. In general, the measure that
appeals the most is a relative measure based on the number of visits. For
example, this is a simple normalization that we use often

$Lift_{v}\sim 100*(lift*N*time)/(totalvisits)$ (14)

This is a relative measure of extra visits provided by the campaign. We will
hide under the hood which computation we use. In the experimental section, we
shall show relative lift (always based on the expectation) and we use it to
appeal the practitioner and for presentation purpose: a projected measure in
the range $[-100,+100]$ is more pleasant than the real measure in the range
$[-10^{-6},10^{-6}]$.

###  2.1 Exposure effect: First Time of Exposure and Balanced Control

By construction, we know the first time when we expose a device. This is the
analogous to the start of treatment in a clinical trial and it is clear the
importance of the response value $\Delta_{M}r(d_{i},e_{j})$ when $e_{j}$ is
the first time seen (Equation 10). In practice, the $e_{j}$ is completely
defined by the device and we can describe this by $\xi(d_{j})=e_{i}$. With a
proper choice of the interval $M$ and weight function, the exposed device
contribution is limited to the interval $[e_{j-M},e_{j+M}]$. Thus Equation 11
can be simplified to

$E[r|E]\sim\frac{1}{N}\sum_{j=1}^{N}\Delta_{M}r(d_{j},\xi(d_{j})=e_{i})=\frac{1}{N}\sum_{j=1}^{N}\Delta_{M}r(d_{j})$

Even thought it is not necessary, for symmetric purpose and for computation
purpose, we should find a similar epoch for the control devices so that we can
compute $E[r|C]$ in a similar fashion. We can infer an epoch when the control
device could have been exposed but we did not expose them. Such a first time
seen will be given in correlation to the exposed devices and thus the
computation can be carried on. This is easier if the exposed–control set is
balanced, because we could use random sampling to infer an average response
for otherwise an arbitrary choice of epoch.

$\displaystyle E[r|E]{-}E[r|C]$ $\displaystyle\sim$ (15)
$\displaystyle\frac{1}{N}\sum_{j=1}^{N}\Delta_{M}r(d_{j},\xi(d_{j})|E)-\frac{1}{N}\sum_{j=1}^{N}\Delta_{M}r(d_{j},\xi(d_{j})|C)$
$\displaystyle\frac{1}{N}\sum_{j=1}^{N}\Delta_{M}r(e_{j})-\Delta_{M}r(c_{j})$
(16) $\displaystyle\sim E[r_{e}-r_{c}]$ (17)

This formulation and the computation are appealing for a few and important
reasons.

  1. 1.

The response statistics $r_{e}-r_{c}$ is very intuitive and computationally
appealing, it describes the original problem clearly.

  2. 2.

If the control set is independent of the exposed set and we have a good
estimate of the first time seen for both, this will be a well formulated
experiment. Thus we can do matching to remove targeting bias and compare
performance by slicing the data accordingly. We can compare the original lift
and the matched lift.

  3. 3.

The computation of lift as average is a sound estimate of the expectation and
thus of the campaign lift.

  4. 4.

Interesting constraints can be applied to expose and control together: for
example, we could count only visits that happen in a short interval after
exposure and thus reject long term effects.

  5. 5.

It is like 1-1 matching is applied already.

  6. 6.

The lift measure is an expectation of the difference of two functions and not
the difference of expectations; thus a single variance can be associated
instead of two and their correlation matrix.

From a different prospective, these advantages are hindrances. For example,
loosing the relation between visits and epoch may be too much of a
simplification. We may want to compute explicitly:

$\frac{1}{N_{i}}\sum_{j=1}^{N_{i}}\Delta_{M}r(d_{j},e_{i})$ (18)

In Equation 18, we represent a time series of the visits acceleration and we
show how a campaign is effective to the granularity of the epoch of $e_{i}$.
Also, exposure should have long term effects because exposure is a continuous
process limited only by a frequency cap.

The estimate of first time seen for control devices is a fragile process
especially for long campaigns and large control set: force a control user to
be measured at an arbitrary date in the process may not represent its average
behavior. Lift as expectation and variance as single number is very powerful:
it comes with the condition that the implicit pairing in Equation 17 is
proper, but matching will come only after this pairing, which could be too
late.

Nonetheless, we shall show experimental results using this balanced approach.

###  2.2 Unbalanced Control: A visit based choice.

Let us repeat here what is the goal of a campaign: it is an invitation to
visit a set of locations and the exposed group is given. However, just seeing
one location is another invitation to visit and this is an invitation directed
to any one nearby. Clearly, a close distance is of the utmost importance for
both exposed and control and this is obviously true for national campaigns
towards local enterprises: for example, Blue Bottle Coffee has locations in
Tokyo Japan, San Francisco, Palo Alto, Oakland, and New York and a
connoisseurs may visits all them during the span of a week, but someone living
in Los Angeles is neither a great target for exposure nor a great example for
control.

First, we can draw a circle of one mile around a coffee shop and suggest that
the people in this circle will visit our location. Considering that who visits
will be eventually in the circle, this seals a strong group and, in it, there
will be part of our exposed group. The connoisseurs will be there (if we have
impressions for them, yes even in Tokyo) but also any passer by.

Given this exposed–control set, we can compute the lift for the exposed and
for the control. These sets will have all the visits but they will not
represent the whole exposed population and will not have enough similarities
to compare to each other (i.e., matching). We may have to increase the circle
to two miles to capture twice as many exposed and twice as many control.
Notice, control will be much larger than exposed unless we saturate the area
and the population (economically not smart). We need to have enough users so
that we can do a meaningful matching and thus removing any bias in the sample:
this means, when most exposed can be matched with control and viceversa.

##  3 Audience Specification: User Profile and Location Graph

In the following section, we shall describe an original and deterministic
approach to create a feature space describing any user and any location by a
set of keywords, which are key–value pairs and the values are probabilities in
the continuous space in $[0,1]$. For example, we may introduce a probability
for a user to be female. We shall explain our inference process but
intuitively a user visiting a location will inherit some of the features of
the location and, in turn, the location will do the same. First, a business
location attracts an audience; Second, its neighbors will inherit some of this
audience; Third, a lot or a few people may visit a business location, and
Fourth, who is visiting also composes the audience of the business. All these
interactions will affect the features of both businesses and visitors. We
shall start describing the location graph in Section 3.1 and the user profile
in Section 3.6.

###  3.1 Location Graph

In general, a triplet $(pid_{i},lat_{i},lon_{i})$ defines a location $l_{i}$
and it may represent either a business location or a census-based location.
Given two locations, we can compute different type of distances: Haversine
formula, Manhattan, or a version of $L_{1}$. Independently, we denote the
distance between two locations as $d_{R}(l_{i},l_{j}).$ We use an estimate of
the Earth radius in line with the literature and, of course, the smaller is
the real distance the better is the approximation.

Consider a ${\bf cell}_{i,j}$ defined by point $(lat_{i},lon_{j})$ and point
$(lat_{i}+\Delta x,lon_{j}+\Delta y)$, where $\Delta x$ and $\Delta y$ are
arbitrary positive constants. The point $(lat_{i},lon_{j})$ describes a
rectangular cell. We define as cell any $(lat,lon)\in{\bf cell}_{i,j}$ so that

$lat_{i}\leq lat<lat_{i}+\Delta x\text{ \bf and }lon_{j}\leq
lon<lon_{j}+\Delta y.$

Assume we can draw a cell partition for any geographical area (i.e., the
United States): that is, any location is in one cell and any two cells have
empty intersection. Any ${\bf cell}_{i,j}$ has eight neighbors specified by
the following points in counter clockwise fashion ${\cal N}({\bf
cell}_{i,j})$:

$\begin{array}[]{ll}{\bf cell}_{i-1,j-1}&=(lat_{i}-\Delta x,lon_{i}-\Delta
y),\\\ {\bf cell}_{i-1,j}&=(lat_{i}-\Delta x,lon_{i}),\\\ {\bf
cell}_{i-1,j+1}&=(lat_{i}-\Delta x,lon_{i}+\Delta y),\\\ {\bf
cell}_{i,j+1}&=(lat_{i},lon_{i}+\Delta y),\\\ {\bf
cell}_{i+1,j+1}&=(lat_{i}+\Delta x,lon_{i}+\Delta y),\\\ {\bf
cell}_{i+1,j}&=(lat_{i}+\Delta x,lon_{i}),\\\ {\bf
cell}_{i+1,j-1}&=(lat_{i}+\Delta x,lon_{i}-\Delta y),\\\ {\bf
cell}_{i,j-1}&=(lat_{i},lon_{i}+\Delta y).\\\ \end{array}$

With the concept of distance, we know that any two locations $l_{m}$ and
$l_{n}$ in ${\bf cell}_{i,j}$ must have $0\leq d_{R}(l_{m},l_{n})\leq
d_{R}((lat_{i},lon_{j}),(lat_{i}+\Delta x,lon_{j}+\Delta y))=D$. Thus if one
location in ${\bf cell}_{i,j}$ has a neighbor at distance no farther than $D$
then it has to be in any of the 8 neighbor cells above. Now that we have
defined distance and cell partitions, we can define and compute a
geographically distributed location graph.

Figure 1: Example of geographical distributed location graph

Assume we set the constant $\Delta x=\Delta y=\Delta$ and we have a cell
partition. For any cell ${\bf cell}_{i,j}$, we collect all the locations in
${\bf cell}_{i,j}\cup{\cal N}({\bf cell}_{i,j})$. For every location
$l_{m}\in{\bf cell}_{i,j}$, we compute a distance with all other locations
$l_{n}\neq l_{m}\in{\bf cell}_{i,j}\cup{\cal N}({\bf cell}_{i,j})$. We then
create a node in a graph associated with $l_{m}$ where we store all the
neighbors information and their distances (edges) if the distance is less than
$D/2$ (say). The graph has a geographical key ${\bf cell}_{i,j}$ and each
location has information about its first degree neighbors, which must be in
${\bf cell}_{i,j}\cup{\cal N}({\bf cell}_{i,j})$. In Figure 1, we show an
example of location graph. The cell partition describes a grid and we shall
introduce grid algorithms. In the following section, we shall explain briefly
the graph building computation, which is the basis for all our graph
computations.

###  3.2 Location Graph: Distance Computation

For simplicity, we have a injective function that map any location $l_{m}$ to
only one cell,

$J(l_{m})={\bf cell}_{i,j},$

and given a ${\bf cell}_{i,j}$ we can compute ${\cal N}({\bf cell}_{i,j})$.
The computation of the location graph follows and it is the foundation for any
graph algorithms in this work:

  * Broadcast:

For every location $l_{m}$ in the graph, we compute the cells ${\cal
N}(J(l_{m}))$, and we broadcast $l_{m}$ to the them. In practice, the location
$l_{m}$ is associated with a node in the graph.

  * Computation:

For every cell ${\bf cell}_{i,j}$ and for every pair $l_{s}\neq l_{t}$ in the
cell, we compute all $d_{R}(l_{s},l_{t})$ distances and we create an edge
between the nodes with their distance.

  * Reduce:

For every cell ${\bf cell}_{i,j}$, we store the nodes $l_{s}$ so that ${\bf
cell}_{i,j}=J(l_{s})$

The location graph is a hierarchical graph, a cell describes a circumscribed
area where the graph has locations with connections within the cell and,
possibly, only to its neighbors cells. A location
$l_{i}=(pid_{i},lat_{i},lon_{i})$ identifies all its direct neighbors
$\pi(l_{i})$, its own cell $J(l_{i})$, and the neighbors’ cells ${\cal
N}(J(l_{i}))$. If a location has also an altitude, think the Dubai’s tower,
the distance can be enhanced in order to distinguish locations beyond latitude
and longitude but there is no changes about cells and neighbors.

###  3.3 Location Graph: Keywords

We are ready to dwell into keywords and their notations. Consider a location
$l_{j}$ where we enumerate the locations using an integer $\ell\in[1,J]$. In
the same way, we enumerate the keywords using an integer in $k\in[1,K]$. A
keyword is associated to a step $s$; this has two meanings. First, $s$
represents the time in a time series; Second, at any step $s$ we perform a
computation among only direct neighbors: thus from step $s-1$ to step $s$,
each step propagates keywords values in the graph by direct connections and
thus we propagate keywords to two level connected neighbors. The last and
important identification of a keywords is the category where this feature is
derived from, we enumerate the categories by $c\in[1,3]$: First, from its
direct neighbors; Second, weighted by number of visits and Third, the keywords
from visitors. We shall clarify these distinctions as soon as we express the
keywords and their applications. In short, we can represent any keyword by

${}^{c}_{k}w^{s}_{\ell}.$

As reinforcement, we have: $\ell$ location, $s$ step, $k$ keyword and $c$
category.

Using matrices and using notations to describe each location $\ell$, our
computation is an exponential smoothing, we have
${\boldsymbol{W}}^{s}_{\ell}\in\mathbb{R}^{3\times K}$:

${\boldsymbol{W}}^{s}_{\ell}=\left[\begin{array}[]{c}{\boldsymbol{n}}^{s}_{\ell}\\\
{\boldsymbol{v}}^{s}_{\ell}\\\
{\boldsymbol{u}}^{s}_{\ell}\end{array}\right]\Leftarrow{\bf\Lambda}\oplus({\boldsymbol{W}}^{s-1}_{\ell})+({\bf
I-\Lambda})\oplus\varphi(\mathbb{X})$ (19)

We shall specify each term by unfolding the matrix notation completely (the
uncommon symbols $\oplus$) and we shall shed lights on the use of exponential
smoothing.

####  3.3.1 Neighbors $c=1$

In real estate, the location and its neighbors are key to any property value.
Given a location $\ell$ and its neighbors up to $|\pi(\ell)|=N_{\ell}$ at step
$s$, we compute the update keyword value by the following exponential
smoothing:

${\boldsymbol{n}}^{s}_{\ell}={\boldsymbol{\lambda}}*{\boldsymbol{n}}^{s-1}_{\ell}+\frac{({\boldsymbol{1}}-{\boldsymbol{\lambda}})D_{\ell}}{N_{\ell}}*\sum_{j\in\pi(\ell)}\frac{{\boldsymbol{n}}^{s-1}_{j}}{1+d(j,\ell)}$
(20)

Where we have

${\boldsymbol{a}}*{\boldsymbol{b}}=[a_{1}b_{1},a_{2}b_{2},..,a_{K}b_{K}]^{t},$

we identify the transpose of a vector ${\boldsymbol{v}}$ with the usual
superscript ${\boldsymbol{v}}^{t}$, the scalar by vector follows the usual
rules

$a{\boldsymbol{v}}=[av_{1},av_{2},..,av_{K}]^{t},$
$({\boldsymbol{1}}-{\boldsymbol{\lambda}})=[1-\lambda_{1},..,1-\lambda_{K}]^{t}$

and

$D_{\ell}=\sum_{j\in\pi(\ell)}\frac{1}{1+d(j,\ell)}$

and $d()$ is our distance function.

The notation tries to keep an intuitive format but we understand the
difficulties associated with it. Here is our interpretation of Equation 20. We
compute the average of the keywords of the neighbors; each neighbor
contributes as a linear and decreasing function of its distance from the
location: that is, the closest the distance is, the largest contribution will
be; intuitively it is the inverse of a cost and the cost is the time required
to go from one location to the other; we assume they will provide information
to the location $\ell$; if $\ell$ has no other source and the neighbor
keywords do not change, then at steady state ${\boldsymbol{n}}_{\ell}$ will
converge to the average of its neighbors.

####  3.3.2 By number of visits, $c=2$

Given a location $\ell$, we can compute the number of visits to this location
in between $s{-}1$ and $s$, and we identify this count by $V_{\ell}^{s}$. Thus
we express the update as follows

${\boldsymbol{v}}^{s}_{\ell}=\frac{V^{s}_{\ell}}{\Upsilon_{\ell}}({\boldsymbol{\mu}}*{\boldsymbol{v}}^{s-1}_{\ell})+\frac{({\boldsymbol{1}}-{\boldsymbol{\mu}})}{N_{\ell}}*\sum_{j\in\pi(\ell)}\frac{V^{s}_{j}}{\Upsilon_{\ell}}{\boldsymbol{v}}^{s-1}_{j}$
(21)

Where $\Upsilon_{\ell}$ is $\sum_{j\in\pi(\ell)}V_{j}^{s}$. In practice, a
location with a lot of visits will dominate the surrounding audience. By
construction, the neighbors locations are relatively close and thus inherit
these hot spots audience. In practice, a few business place themselves in
close proximity to others to gain access to their audiences.

####  3.3.3 By visit types, $c=3$

Assume we account for the keywords of the visitors of location $\ell$; for
example, we create a distribution of the visitor keywords from epoch $s{-1}$
to $s$ and to show that is related to the computation of the keywords we use
the following notation $\bar{{\boldsymbol{u}}}_{\ell}$, then we count the
number of visitors $V_{\ell}^{s}$ as above.

${\boldsymbol{u}}^{s}_{\ell}={\boldsymbol{\nu}}*{\boldsymbol{u}}^{s-1}_{\ell}+\frac{({\boldsymbol{1}}-{\boldsymbol{\nu}})}{\Upsilon_{\ell}(N_{\ell}+1)}*\sum_{j\in\pi(\ell)\cup\ell}V_{j}^{s}\bar{{\boldsymbol{u}}}^{t}_{\ell}$
(22)

The computation by visit type combines the traffic of all direct neighbors and
create a weighted average. For example, we can emphasize the direct visitors
instead of neighbors’. This is one approach to harness keywords associated to
users, it is independent from the graph, and create a ripple effect of
otherwise sparse and rare events such as visits.

####  3.3.4 All together

We foresee the case of other dimensions and categories that can be added to
the previous ones, but here we explain how we summarize the keywords weight.
In summary, ${\boldsymbol{n}}^{s}$ represents the graph contribution and it
changes only when the graph changes; ${\boldsymbol{v}}^{s}$ introduces the
idea that neighbors have different contribution as a function to the number of
visitors; ${\boldsymbol{u}}^{s}$ represent the contribution from each visitors
to each neighbors locations.

We combine them as independent

${\boldsymbol{w}}^{s}_{\ell}={\boldsymbol{\Gamma}}^{t}\left[\begin{array}[]{ccc}{\boldsymbol{n}}^{s}_{l}&{\boldsymbol{v}}^{s}_{l}&{\boldsymbol{u}}^{s}_{l}\end{array}\right]={\boldsymbol{\gamma}}^{n}*{\boldsymbol{n}}^{s}_{l}+{\boldsymbol{\gamma}}^{v}*{\boldsymbol{v}}^{s}_{l}+{\boldsymbol{\gamma}}^{u}*{\boldsymbol{u}}^{s}_{l}$
(23)

where

$\gamma^{n}_{k}=\begin{cases}0&[{\boldsymbol{n}}^{s}_{l}]_{k}=0\\\
1/\text{number of non zeros
}[{\boldsymbol{u/v/s}}^{s}_{l}]_{k}&\text{otherwise}\end{cases}$

In practice, we compute an simple average for each keywords but if any
dimension provide no keyword entry, that is zero, we do not account for them.
In this way, when we will add more dimensions, they will enrich the keywords,
density, and they will not increase their value.

####  3.3.5 Priors, distributions, and probabilities

Sometimes, a business knows the audience they have or they must have. This is
a priori information or simply prior. At first, it may seem difficult to
envision businesses with a specific and limited audience; however, in
practice, there are gender-specific services such as Obstetrics and
Gynecology, there are age-specific business such as liquor stores, there are
income-specific ZIP codes (upper east side) or business such as Ferrari
dealers.

In this prior category, we add averages as well: for example, by Census or
other means, we know the averages about the population of a ZIP code (thus a
location or locations). Such averages help to narrow down the most likely
features. In fact, we use probability as estimate of the feature distribution
and use these as prior information. For example, we may have information about
a ZIP+PLUS4 area, which we represent by its centroid latitude and longitude,
the locations in this ZIP will be either connected directly to it or a few
step way, and thus the ZIP will enrich their own keywords by proximity. Of
course, an area into a single node in the location graph is an approximation
but it is one simple way to feed the graph with priors otherwise not
available.

Prior features are set and no further computation is needed. There is only one
exception introduced to cope with imprecise and erroneous data: we normalize
the keyword values in order to keep meaningful distributions, this may require
scaling the keyword values.

###  3.4 Location Graph: Update

Once we have a location graph with its features, we may have to rebuild the
graph because a few businesses relocated, new businesses started, and old
business exited.

In the graph, a business exiting translates into a node deletion and thus
edges deletions to all its neighbors. Any modification to the list of
locations will require a graph update. In this scenario, the new graph will
inherit the keywords from the old graph but we must propagate the effect of
the new connection by updating the keywords accordingly to Equation 19.

###  3.5 Location Graph: Iterative Algorithm and cycles

We can iterate the computation of keywords in order to collect signal from
locations father away in the graph or just to adjust the keywords value
because of graph modifications.

  * Broadcast:

For every location $l_{m}$ in the graph, we determine ${\cal N}(J(l_{m}))$,
and we broadcast $l_{m}$.

  * Computation:

For every cell ${\bf cell}_{i,j}$ and for every $l_{s}$ in the cell, we
compute Equation 19–23

  * Reduce:

For every ${\bf cell}_{i,j}$, we store the nodes $l_{s}$ so that ${\bf
cell}_{i,j}=J(l_{s})$

This is an iterative algorithm that will propagate the keyword values across
the graph. In this scenario, the exponential smoothing introduces yet another
dimension: it will reduce, edge by edge, the effect of cycles in the graph. In
practice, one degree neighbor will contribute $(1-\lambda)$, two degree
neighbors will contribute $(1-\lambda)^{2}$ (i.e., $i$-degree will provide
$(1-\lambda)^{i}$). In practice $(1-\lambda)\sim 0.5$ and thus the effect will
be $\frac{1}{2^{i}}$, after three levels the contribution is negligible with
respect to the local nodes and its direct neighbors. Nonetheless the smoothing
can be tuned for the keyword and for the dimension.

###  3.6 User Profile

In the previous section, we show that if we have information about the users
visiting a location, then we can enrich the location and its neighbors. In
this section we show that we can also take the location information and enrich
its visitors.

Assume we have already a set of users ${\boldsymbol{V}}^{s-1}$ at step $s-1$
with their keywords and we want to compute the next step. We enumerate the
users $n\in[1,N]$ and we specify the users by the same keywords as for the
location graph: ${\boldsymbol{v}}_{n}$ is a vector of keywords. We have at our
disposal the following information: Prior (${\boldsymbol{P}}^{s}$), Visits,
and graph locations. The user profile computation has the following
formulation:

${\boldsymbol{V}}^{s}={\boldsymbol{\rho}}*\mathbb{F}({\boldsymbol{V}}^{s-1},{\boldsymbol{P}}^{s}))+({\boldsymbol{1}}-{\boldsymbol{\rho}})*{\boldsymbol{X}}^{s}.$
(24)

We shall expand and clarify all terms and how we compute visits (briefly
explained and used in Equation 7). The order of the computation is important
and the evaluation goes naturally from left to right because priors have
priority.

####  3.6.1 Visits and location graph ${\boldsymbol{X}}^{s}$

From step $s-1$ to $s$ we gather the foot print of users. Listening to real
time bidding, we can observe a sample of impressions: geographical location,
time, and keywords associated to the users for an advert; also we can collect
similar information from third parties pixels. These two sources do not
overlap. The interval from $s-1$ to $s$ represents an interval of time of one
week. This is a geographical distribution of impressions: $G^{s}$ for short.

We can gather all user information and thus average the keywords in different
geographical locations and create a distributions of the keywords: we
describes this information by ${\boldsymbol{f}}^{s}_{n}\leftarrow G^{s}$.

We merge the location graph at step $s-1$ with the $G^{s}$. We can compute the
user visits with respect the location graph and we can collect the keywords
from the location visited: ${\boldsymbol{g}}^{s}_{n}$. Thus, we have

${\boldsymbol{x}}^{s}_{n}={\boldsymbol{\gamma}}^{t}_{f}*{\boldsymbol{f}}^{s}_{n}+{\boldsymbol{\gamma}}^{t}_{g}*{\boldsymbol{g}}^{s}_{n}$
(25)

####  3.6.2 Priors

In every interval from $s-1$ to $s$, we collect registration information, that
are voluntary information the users provide to a carrier, phone application,
and others. This information will change and it will describe the current
users of the device. Priors are so important that we can use them stand alone
and create discrete classes. This finds application to the balanced approach
as we shall describe in Section 5.

In the contest of applying priors to user keywords, we must take care of any
inconsistencies with the previous priors:

$\bar{{\boldsymbol{V}}}^{s-1}=\mathbb{F}({\boldsymbol{V}}^{s-1},{\boldsymbol{P}}^{s}))$

this computation assesses the effect of the current Prior and we update the
user profile accordingly: a simple example is when the user suggested to be a
female and now to be a male. If left unattended, this user will belong to male
and female category. In this scenario, current priors will not substitute the
past prior, it will clear both genders and we will be open to suggestions from
their visits patterns, opening the opportunity of a probability of gender
based on their foot traffic.

As for the location graph, priors are unchangeable, we consider them as simple
truths. Thus, Equation 24 involves no computation using priors. However, as
for the location graph, we perform an adjustment in order to keep keywords
distributions consistent.

This concludes the description of how we compute the user features. As a
summary, we compute features for locations and users as a function of time and
their interactions. Now, we shall describe how we use these feature for
matching, that is the art of compensating the original bias introduced into
the exposed group.

##  4 Matching

To describe the efficiency of a campaign, we compute the variance and the
expectation of the response statistics, that is, the lift as in Equation 2:

$Lift=E[r(d,t)|d\in E]+E[r(d,t)|d\in C]$ (26)

With the term quasi experiments, we refer our inability to choose the exposed
and the control group before the experiment as in a randomized clinical
experiment. However, we can still choose how the control group interacts with
the exposed group by an appropriate selection: in practice, we sample the
universe and we find for every device $d_{i}$ a corresponding
${d^{\prime}}_{i}$ in the control and the best we can do is to compute the
following,:

$E_{d}\big{(}E(r_{\gamma}|d,E)-E(r_{\not\gamma}|d^{\prime},C)\big{)}$ (27)

where we represent conditional expectation as usual, $r_{\gamma}$ is the
response to exposure, and $r_{\not\gamma}$ the response to not exposure, from
the original work and notation. We notice that the notation infers a matching
with suitable pairing for every device $d$ a device $d^{\prime}$. In the
following, we shall provide an interpretation of Equation 27. Notice that
Equation 26 and 27 are equivalent if the choice of exposure (i.e.,
$z(d_{i})=1$ if $d_{i}$ in Exposed) is strongly ignorable, Rosenbaum and Rubin
(1983). This is clear by using the original notations:

$(r|E,r|C)\mathrel{\raisebox{1.00006pt}{\reflectbox{\rotatebox[origin={c}]{90.0}{$\models$}}}}z|d$
(28)

For every person in the sample $d_{i}$, the fact that $d_{i}$ is exposed or
not, is orthogonal to the value of the response. As Dawid’s stated Dawid
(1979)
$X\mathrel{\raisebox{1.00006pt}{\reflectbox{\rotatebox[origin={c}]{90.0}{$\models$}}}}Y$
where $X$ and $Y$ are random variables, then

  1. 1.

$P(X=x,Y=y)=P(X=x)P(Y=y)$,

  2. 2.

$P(x|y)=P(x)$,

  3. 3.

$P(x,y)=a(x)b(y)$, and

  4. 4.

$P(x|y)=a(x)$.

The second case is the most practical for us: the distribution of the response
is independent of the distribution of the exposure selection. In practice, we
call general lift the result of Equation 26. We do not expect targeting to be
strongly ignorable.

This is not just a mathematical tool; Equation 27 suggests that exposed and
control must be paired equally. This has a natural application to the
methodology described in Section 2.1 where the exposed-control pair is
balanced and matching will provide an estimate of Equation 27 by 1-1 matching.
In general, a good control can be large, the computation of Equation 27
difficult, and targeting specific and not ignorable, then we must estimate
something like the following instead:

$E[r_{\gamma}(d,t)|d\in\text{ E and
}M(d)\in\Omega]-E[r_{\not\gamma}(d,t)|d\in\text{ C and }M(d)\in\Omega]$ (29)

where $M()$ is an appropriate function and
$\Omega=[M(d):\text{E}\rightarrow\mathbb{R}]\cap[M(d):\text{C}\rightarrow\mathbb{R}]$,
is the intersection of the projection of exposed and control into the image of
$M$. This means we are changing the response statistics by filtering,
clustering, and weighting within the cluster; then we compute expectations for
the average lift. The Equation 29 provides an insight to the Equation 26 and,
in general, there is no equality.

###  4.1 Matching: Previous Work

The seminal work by Dawid Dawid (1979) introduces the notation and the
formalism of ignorable, the main property to make a quasi experiment closer to
a random experiment.

The population composing our experiments has explanation features, see Section
3. The feature space is a multidimensional space: multivariate. As the
features can be used to discriminate the exposed group from the control, we
can use them to build $M()$ of Equation 29. The author in Rubin (1976a, b)
introduced examples thus paving the path for matching using propensity score.
The authors in Rosenbaum and Rubin (1983) developed the theory connecting the
importance of the propensity scores to matching. The propensity score
transforms a multidimensional space problem, which users have the closest set
of features, into a one-dimensional problem, which users have the closest
score number.

Assume that ${\boldsymbol{x}}_{i}$ is a feature vector for the person $i$; we
estimate $z_{i}$ as $\zeta({\boldsymbol{x}}_{i})$ in the following Equation
30, in turn we may use a linear model such as in McCullagh and Nelder (1989),
Chapter 4.3:

$\log\frac{\zeta({\boldsymbol{x}})}{1-\zeta({\boldsymbol{x}})}\sim\beta_{0}+\sum_{i=1}^{K}\beta_{i}x_{i}$
(30)

Rosenbaum and Rubin explain how any function based on
$\zeta({\boldsymbol{x}})$ or, for that matter, its linear model in Equation
30, can be used for the computation of the matching. We can use it in Equation
27 and we can determine $M()$ in Equation 29. Compute the model and determine
the $\dot{\beta}$. Take two people from the experiment with their feature set
${\boldsymbol{x}}_{i}$ and ${\boldsymbol{x}}_{j}$. If
${\boldsymbol{x}}_{i}={\boldsymbol{x}}_{j}$,
$\zeta({\boldsymbol{x}}_{i})=\zeta({\boldsymbol{x}}_{j})$. Also, thanks to the
linearity and continuity of the estimation,
$|{\boldsymbol{x}}_{i}-{\boldsymbol{x}}_{j}|<\epsilon$ translates to
$|\zeta({\boldsymbol{x}}_{i})-\zeta({\boldsymbol{x}}_{j})|<\delta$ with
$\epsilon,\delta>0$ and arbitrary small, whether or not $z_{i}=z_{j}$.

The work by the authors in Dehejia and Wahba (1998) is probably the most cited
attempt to provide a first evaluation of all the matching algorithms using
propensity scores. As of today, this work is a great beginning and most of the
current libraries implementing matching provide the data from this reference
(see Hansen and Klopfer (2006); Iacus et al. (2012); Griffin et al. (2014); Ho
et al. (2007); Sekhon (2011); Sekhon and Grieve (2012)). For a better view of
the research, please consult the references in Morgan and Winship (2007); Goo
and Fraser (2014).

Often the estimate of the propensity scores provides only a handful of values,
discrete, and thus classes with very large gaps. By construction and in this
scenario, any matching will be balanced and thus it does not provide any
meaningful measure of quality. Also it means that the matching is many-to-
many. Also, assuming we have to match one exposed user with one control user,
eventually we have to sample either one. We may believe that random sampling
should not change the average behavior; however, in practice, when the events
are rare, sampling will remove them further and actually affect the final
results. This simple consideration explains why it is difficult computing
Equation 27 and also undermines balanced matching based on
$\zeta({\boldsymbol{x}})$, which is unrelated to the response.

In this work, we present a single algorithm that will work with both
propensity score and clustering algorithm. Also we show the danger of perfect
matching while estimating the exposed effect in Equation 29. To overcome this
problem, we introduce a novel quality measure of the matching algorithm and an
un-balanced algorithm where the response distribution is not known a priori
and thus it is not affected by matching.

###  4.2 The algorithms

The propensity score describes a multidimensional vector by a probability or a
score with a continuity property stemming from Equation 30. The propensity
model for $N$ users with $K$ features is computed by an iterative algorithm
with $J$ iterations computing a $QR$-factorization in each step: $O(JKN^{2})$.
For us $K=25$ and $J<10$. Thus $O(N^{2})$ is a good approximation of the
complexity but it is often executed in native and fast code.

The other property is that the scores can be sorted and a caliper can be
introduced naturally using the strong order of the scores. Sorting $N$ scores
takes $O(N\log N)$ and thus creating the matches with any caliper takes an
extra $O(N)$, a further pass. Optimal algorithms will circumvent calipers and
try to find the closest element independently. This takes $O(\frac{N^{2}}{2})$
comparisons; for example, this is the default implementation in Sekhon (2011).
For large $N$ a full comparison is not efficient 222Even though the complexity
$O(N^{2})$ is the same as the QR-factorization, this is not highly optimized,
the constant factor if much larger than 250 and it is often not acceptable for
$N>10^{6}$.  and sorting is by far the better solution.

Complexity is one problem. The other problem is sampling due to matching: when
exposed and control have different number of users and we match one-exposed-
user-to-one-control-user, we sample the larger one. If the events we measure
in the response have a distribution with long (fat) tails such as in stable
distributions Mandelbrot (1960), sampling will censor rare but important
events. In general, we do not want to use the response for matching, to avoid
bias; however, the change in the response distribution can be used as a
measure of quality: for example, we can provide distance measure and its
confidence using several methods D’Alberto and Dasdan (2009). Here, we use a
simple, consistent, and intuitive measure: entropy Shannon (1948). Small
entropy changes for exposed and control before and after matching mean a
representative matching. To achieve this entropy balance, we may opt for
unbalanced matching and get away from one-to-one matching. We shall explain
how we use weights and how they affect the computation of Equation 29

###  4.3 The Idea

The propensity score defines clusters; that is, users with the same score are
in the same cluster. If we sort these scores, then we sort/organize the
clusters. By construction, consecutive scores in the sorted list represent
close clusters thanks to the continuity property of the propensity score.

In practice, we score each user in the corpora composed of both exposed and
control. We sort the corpora by the score; then we apply the following
algorithm:

     1: i = 1
     2: scoreR = Corpora.scores[i]
     3: i = i +1
     4: while (i<length(Corpora)) {
     5:  score = Corpora.scores[i]
     6:  if (scoreR != score) { # New Cluster
     7:    TE = length(tmpE) # Exposed
     8:    TC = length(tmpC) # Control
    10:    if (TE > 1 && TC>1)  { # Non Empty cluster
    11:      N = max( TE, TC)
    12:      if (BALANCED) # or further random sample
    13:        U = union(tmpE[1:N],tmpC[1:N])
    14:      else
    15:        U = union(tmpE,tmpC)
    16:      matches = union(matches, U)
    17:    }
    18:    tmpE =c(); te = 0
    19:    tmpC = c(); tc = 0
    20:    scoreR = score;
    21:  } else  {
    22:    if (Corpora.exposed[i]==1)    tmpE[te++] = i
    23:    else                          tmpC[tc++] = i
    24:  }
    25:  i = i+1
    26: }
    27: Corpora = Corpora[matches] # Matching done

The pseudo code above matches the exposed and control by clusters. We can
choose to have a balanced matching or unbalanced. Notice that there is no
matching in between clusters: exposed or control coming from different
clusters will have different scores. It is actually easy to encompass this
problem by moving the assignments at lines 18 and 19 inside the loop and at
the end of the condition at line 10 (we call this Caliper activation and it
makes sense only for propensity-score algorithms).

In practice, we could use any other means to cluster the users. For example,
if we use any $k$-mean clustering algorithms, the scores are the cluster
labels and the algorithm above will not change. The matching is actually
decoupled by the scores: propensity score and $k$-mean algorithms can be
applied in combination. For example, we use propensity score first with
adaptive calipers to estimate the number of clusters and, then optionally, we
apply $k$-mean algorithm.

In practice, we compute the propensity score by generalized linear model (GLM)
McCullagh and Nelder (1989) and the $k$-mean by Forgy (1965); Hartigan and
Wong (1979). Both methodologies are well known and available. From our side,
we would like to expose the matching algorithm as a computational kernel and
thus apply it to large problems.

###  4.4 Quality Measure and Confidence

We are aware of several matching algorithms: exact, cem, subclass, nearest,
genetic, full, and optimal. The list is longer. Our implementation falls among
the first four. This scenario begs for a simple question: how can we compare
the results of matching. The package MatchIt, which offers an interface to all
of the above algorithms, takes a step back and lets the user decide the
statistics about the matched sets, even the computation of the lift is
avoided.

Often the quality of matching is based on the estimate of the variance of some
sort.

Sampling a normal distributed corpora. Each user has a response $r_{i}$ (i.e.,
$\Delta_{M}r(d_{j},e_{i})$ in Equation 11), with $N$ users, we can measure the
average

$\mu_{N}=\frac{1}{N}\sum_{i=0}^{N-1}r_{i}$

and the variance

$\sigma_{N}^{2}=\frac{1}{N-1}\sum_{i=0}^{N-1}(r_{i}-\mu_{N})^{2}$ (31)

If we sample, $M_{s}<N$, we can compute the average and variance and we can
compute $\sigma_{M}$. If we sample $M_{s}$ randomly, then
$\frac{\sigma_{M}}{\sigma_{N}}\sim\sqrt{\frac{M}{N}}$: in particular the ratio
$\frac{\sigma_{M}}{\sigma_{N}}$ should be distributed in the vicinity of
$\sqrt{\frac{M}{N}}$ as a normal standard distribution. We can express the
confidence that the sampling is in accordance with the corpora by computing
the probability

$2\Big{(}1-\Phi(\frac{\sigma_{M}}{\sigma_{N}}-\sqrt{\frac{M}{N}})\Big{)}.$
(32)

That is, the probability to be close to the expected variance, the higher the
better.

Variance decrease. In principle, matching should decrease the variance
$\sigma_{M}<\sigma_{N}$; because we reduce $M<N$ and because we remove
outliers; if they do appear in both exposed and control, thus they will not be
outliers. We could choose the matching that reduces the variance the most.
Unfortunately, the classic way to perform matching will sample either exposed
or control, not both; thus if the variance is computed as in Equation 31, then
this criterion does not apply.

ATT Response as normal distribution. One-to-one matching takes one exposed
$r^{i}_{e}$ and finds a control $r^{j}_{c}$ . We can see that

$E[r|E]-E[r|C]\sim\frac{1}{K}\sum_{i=0}^{K-1}r^{i}_{e}-r^{i}_{c}$ (33)

Thus we can create a distribution of the ATT response by
$r^{i}_{e}-r^{i}_{c}$. In general, the computation $r^{i}_{e}-r^{i}_{c}$ is
actually $r^{i}_{e}-w_{i}r^{i}_{c}$ where $w_{i}$ is a weight associated with
the multiplicity of the matched control and distance from exposed. For us,
$w_{i}=1$ represents perfect match. As such, we can compute average $\mu_{E}$
and variance $\sigma_{E}$. If the distribution above is normal we can use the
ratio of average and variance to describe how well the matching represents the
final result: $2(1-\Phi(|\mu_{E}|)/\sigma_{E})$.

In our cases, while the two moments specify completely an ideal normal
distribution, they do not give justice to the empirical distribution. In fact,
the normal distribution is fatter close to the average and thinner at the
tails.

ATT Response as Laplace distribution. The Laplace distribution provides a
different approximation, sharper close to the average and still symmetric.

Figure 2: Each element and Cluster contribution of the response distribution

If we build a cluster, each cluster has its own response: we can estimate the
distribution of the response by the contribution of each pair or by cluster.
While using cluster responses, the distribution may not be approximated by a
Normal distribution nor by Laplace, see Figure 2.

Skewness. Normal and Laplace distributions are poor approximations of the
tails of the empirical distributions. The computation of the skewness
describes with a single measure whether these assumptions are appropriate and
also whether or not we can trust the confidence levels that we measure using
the Normal or Laplace distribution assumption. By construction, if the
exposure is effective, the distribution will be skewed and thus the normality
assumption will fail.

$\chi^{2}_{k}$ distributions of users’ response. Each cluster has a collection
of users and thus responses. The responses are correlated in the clusters, by
construction (or assumption). They should be independent otherwise, across
clusters. If the cluster has $k$ components, we can take the variance of each
and their addition should be the realization of the $\chi^{2}_{k}$ with $k$
degrees of freedom. Then we can use the difference and the known distribution
of the $\chi^{2}_{k}$ to compute a confidence level, see Figure 3.

Figure 3: Approximation by $\chi^{2}_{k}$

The main goal of these quality metrics and their description as confidence
level is to provide a measure of how well the clustering and matching work.
Basically, these metrics use two (or three) moments of the response (average
and variance) and the assurance of quality is based on variations from an
average, which comes from a known distribution. Unfortunately, the response
distribution seems to have a mixed distribution and thus two moments cannot
capture this nature.

Exposed and Control Entropy Constancy. The clustering/matching should be
independent of the response, just to avoid systematic bias. One way to compare
the quality of the matching is by measuring the information contained in the
original corpora and in the matched one. Actually, we expect to have different
distributions for exposed and control.

We should and can compare the response distributions before and after
matching; in D’Alberto and Dasdan (2009), we provide not only distance but
also confidence. Here, we simplify the problem and compute and compare
entropy. Take the exposed distinct response or the original corpora

${\cal E}_{e}^{N}=-\sum_{\ell=0}P[r_{e}^{\ell}]\log_{2}(P[r_{e}^{\ell}])$ (34)

${\cal E}_{e}^{N}$ is the expected information of the exposed response. We can
compute ${\cal E}_{c}^{N}$, which is the entropy of control. We then can
compare the entropy after the matching. Simply put, we compute the pair:

$({\cal E}_{e}^{M}{-}{\cal E}_{e}^{N},{\cal E}_{c}^{M}{-}{\cal E}_{c}^{N})$
(35)

if the pair is positive, it means that the matching increased the entropy and
thus it censored responses with less information. Otherwise, the matching is
sampling responses with more information. Among the matching algorithms, we
should choose the one with the smallest entropy difference for both exposed
and control. In fact, we are after the computation of Equation 27 where the
distribution affects the averages.

Boostrap. We can consider the lift as a statistics and as such we can estimate
a variance using bootstrap. If the response $r(d,e)$ has $lift=E[r]$ and
variance $\sigma^{2}_{r}=E[(r-lift)^{2}]$, then by bootstrapping the lift as
average $\hat{lift}=\frac{1}{N}\sum_{i}r_{i}$ has an average, say
$\mu_{lift}$, and $\sigma_{\mu}$.

Larger is the number of devices used in the experiment, smaller will be the
$\sigma_{\mu}$. This is because the average approximates the expectation
asymptotically

$\lim_{N\rightarrow\infty}(E[r]-\frac{1}{N}\sum_{i}r_{i})\rightarrow 0.$

As such, $\sigma_{\mu}$ and $\sigma_{r}$ are not related: the response can
have stable distribution with unbounded variance $\sigma_{r}$ (i.e., have
undefined variance for $\alpha<2$) and the $\sigma_{\mu}$ still will converge
to zero because the distribution has a finite expectation.

If we are prepared to run enough iterations, and considering that
$\sigma_{\mu}$ must be bound, we can use the equation
$2(1-\Phi(|lift-\hat{lift}|)/\sigma_{\mu})$ to achieve a p-value and thus a
confidence level. Bootstrapping is also used to determine if the $lift$ of
this sample is a good approximation of the larger population Heinrich et al.
(2010). For matching without replacement, 1-1 matching, this is a welcome
approach Austin and Small (2014) and suggested to fill in the missing
information due to small experiments. For matching with replacement,
bootstrapping must be used carefully Abadie and Imbens (2008). For matching
with replacement and large sample it may be not needed because the
distribution is known Abadie and Imbens (2009, 2006); the application of
bootstrap for continuous distribution of the features and continuous response
is an open question.

Campaign as sample. Any matching algorithm samples the experiment to remove
the original bias, unfortunately the lift after matching does not generalize
to the original experiment because, in advertising, targeting is not strongly
ignorable and because the original experiment is not a sample (it contains all
exposed) and we are not trying to estimate the lift for the hypothetical
exposed.

##  5 Experiments

In this section, we shall present our experimental results. One way to be able
to use the methods above for large corpora is to sample randomly. We show the
hidden danger of this expedient Section 5.1. We then provide examples where
all methods provide information and thus none cannot be excluded a priori,
Section 5.2. We show how the matching algorithms presented here are comparable
to the current available Section 5.3. We conclude in Section 5.5 where we
compare the average lift computations for balanced approach of Section 2.1 and
the more general and unbalanced approach, showing how large experiments can be
matched.

###  5.1 The danger of Sampling

The different lifts by random sampling 200,000 users out of 310,000  iteration
sort sort-time k-means k-time subclass sub-time exact e-time cem c-time 1 -122
-145 -132 -150 -124 -88 -100 -132 -100 -132 2 326 538 346 594 297 357 400 308
400 308 3 -101 -673 0 26 -163 166 185 -209 185 -209 4 -3 14 3 -3 23 52 52 -3
52 -3 5 -42 123 -10 -22 -154 -104 -70 -97 -70 -97 6 -118 -52 -133 -59 -156
-109 -82 -113 -82 -113 7 -110 454 -157 587 -187 -167 -141 -43 -141 -43 8 -37
112 -47 166 -134 -113 -111 38 -111 38 9 1637 941 1257 3795 -1660 -1019 -1119
-969 -1119 -969 10 -63 -4 -79 -48 -84 -60 -88 -45 -88 -45 all -96 -91 -100 -50
-131 -71 -60 -88 -60 -88

When we started our research, we applied known methods such as Match() Sekhon
(2011). To cope with the long execution time for large experiments, we sampled
the users randomly but keeping the ratio. Our experiments may have rare
responses, fat tails; for features represented in binary format, we have large
classes creating many-to-many matching; we noticed that sampling can bring
forth inconsistent results. For example, we took an experiment using a
balanced control-exposed set and discrete classes, the experiment had about
310,000 users and we sampled it to 200,000. We ran 10 different sampled
matching and computed the lift ($(E[r|E]-E[r|C])/E[r|C]$) as relative measure.
Also, we added features with time information (i.e., two extra dimensions) to
help the propensity score matching. We summarize the results in Table 5.1.
Considering that in Section 2.1 we suggest to sample Control, thus the
response, the table results should be a warning for large and small campaigns.

What is confusing with this experiment? First, adding features does not help
provide consistent measures; what is lost during sampling is lost and further
space investigations seem helpless. Second, each run provides quite different
lifts in absolute values and in signs (opposite). In three out of ten
iterations all matching results show only negative lifts, one shows only
positive lifts, and for six we have mixed results. The experiment is not
robust, but as we can see the original experiment produce consistent, although
negative, results. In our scenario, the control group has much more signal as
the exposed group, thus sampling the experiment or sampling control must be
done with care and not randomly.

###  5.2 Match comparisons

Let us take the example used in Section 5.1. We do not perform sampling and
also we set to compute an unbalanced matching. The number of users is exactly
302862. For each algorithm, we use 25 and 27 features (whether or not we use
time information). If we use 25 features, the algorithm is fully specified by
its name (i.e., sort, k-means, subclass, exact and cem), if we use 27 features
we use longer names: sort-time/s-time, k-means-time/k-time, subclass-
time/s-time, exact-time/e-time and cem-time/c-time (features are discrete
again).

Match(), full and optimal from MatchIt() results are not reported because they
will take more than 3 hrs, which is not acceptable for our purpose. The
execution time to model the propensity score and to score the user is about
8sec. Also further tests show that their performance increases linearly with
the number of users in the matching tests (considering the number of features
fixed).

In Table 5.2, we show the performance of the same tests, the entropy
difference (see Equation 35), and the standard deviation of the users’
responses. The corpora has variance of 0.0980. Notice that our methods tend to
decrease the entropy but in absolute value, this is the minimum.

Unbalanced computation: difference in entropy and variance  algorithm exposed
control variance sort -0.00016 -5.91886e-05 0.0978 sort-time -0.00056 -0.00061
0.0959 k-means -6.45606e-05 -6.06477e-05 0.0979 k-means-time 0.00281 -0.00028
0.0970 subclass 0 0.00404 0.0975 subclass-time 0 0.00600 0.0965 exact
4.52999e-05 0.00808 0.1009 exact-time 0.00252 0.01500 0.0978 cem 4.52999e-05
0.00808 0.1009 cem-time 0.00252 0.01500 0.0978

If we use the moments and a few assumptions about the users’ responses, we can
compute the probability such that the empirical distribution is
indistinguishable from the assumed distribution, see Table 5.2; then, all
matching algorithms accept the equality assumption. Sort and k-mean use the
clusters: by using the Normality assumption the matching will be accepted,
using the Laplace assumption the matching will be rejected. Other methods use
single user response and thus due to the number of users (300,000 users) they
converge to normality and the others follow.

Unbalanced computation: confidence in the matching process  Algorithm Normal
Laplace $\chi^{2}_{k}$ Eq. 32 sort 0.99911 0.95689 0.94941 0.99943 sort-time
0.99798 0.72556 0.99178 0.98933 kmeans 0.99824 0.67636 0.97187 0.99940 kmeans-
time 0.99749 0.65775 0.98537 0.98061 subclass 0.99867 1 0.99825 0.99581
subclass-time 0.99927 1 0.99926 0.98781 exact 0.99941 1 0.99958 0.97563 exact-
time 0.99913 1 0.99910 0.97086 cem 0.99941 1 0.99846 0.97563 cem-time 0.99913
1 0.99936 0.97086

###  5.3 Audience Selection, Features, and Algorithms (Cor)Relation

In our experience, our problem space has three basic dimensions: First is the
choice of the exposed group and thus control; Second is the dimension number
and quality of the feature space describing our audience; Third is the set of
algorithms and what they can expose for all the above. Eventually, we would
like to infer recommendations about what works, especially at scale. In this
section, the largest campaign has ten million devices and the smallest a few
hundred thousands.

In this section, we consider a few dozen campaigns and we applied a balanced
approach, Section 2.1, with discrete feature space Section 3.6 using only
registration data, known as prior. In this scenario, the user response is
discrete covering a set of discrete values. The feature space specifies a
discrete space, although possibly large, it is limited and users could be
clustered into a few thousands classes. The estimate of the targeting function
reflects the discrete space nature; thus, the matches are often many-to-many
and the exposed group has priority, that is, we sample control. For all the
matching algorithms, there is always a many-to-many matching because the
calipers will infer classes and within any class we do not apply a nearest
matching. Even for the standard algorithms, they apply a 1-to-many matching
introducing weights.

Figure 4: Audience keywords: Unbalanced $k$-to-$m$ matching (above) and
Balanced many-to-many matching (below))

In Figure 4, we compare our algorithms together with more standard ones. We
can appreciate that the final lift values differ little. This simple
experiment shows that our matching algorithms are equivalent to others with
the advantage that can be applied to larger campaigns without loss of
accuracy. We make sure that the matching as we designed and developed does not
loose information for the type of our experiments. In practice, we show
experimentally that our matching are a useful contribution to the literature
especially as meaningful extension, if not the only available extension. In
the following section, we go even bigger. To do so, we need a different
framework and we need to use an unbalanced approach.

###  5.4 Experiments and analysis of stochastic hits

Setting a specific radius or the contour of a parcel as a boundary for the
computation of a hit is simple to explain and to use. However, how we can
account for those impressions close by those boundaries by users we do not see
inside those same boundaries. They may have stepped out of the location we are
interested in and sent us a signal. In this section, we discuss the
application of what we called stochastic hit, if an impression is close enough
to a location we may consider to give it a probability (of a hit) by using a
known distribution such as the IG presented in Equation 4 or a lognormal
distribution.

We consider two campaigns A and B, they have more than thirty locations of
interests relatively sparse geographically. One campaign is to advertise a car
company and the other is a restaurant chain.

We create these two experiments for both campaigns: we consider $R=30$ and
$R=96$ meters, $R$ is the radius we use to consider an impression a hit. For
each experiment, we consider all the users that have a hit at distance $d<=R$.
Then we count the number of times and the distances $0\leq d\leq 10R$ with a
precision of one meter.

Figure 5: Campaign A: Conditional distance distribution with users who has a
visit within 30 and 100 meters

In Figure 5, we present the two experiments when we observe the distribution
of who hit ($d<R$ for $R=30$ and $R=100$ meter). Within $0\leq d\leq R$, we
have investigated a simple polynomial curve fit and we have found that
$p[x=d]\sim\alpha d$. This simple observation means that $P[x\leq R]\sim
R^{2}$ and, thus, the number of hits is proportional to the area. This is not
true for each location, but for the aggregate of 30 or more locations, we
achieve such a nice property, which is intuitive.

Figure 6: Campaign B: Conditional distance distribution with users who has a
visit within 30 and 100 meters

In Figure 6, we present the second campaign and we can appreciate that the
experiment have similar results. The slope is different, specific to the
campaign and locations set, $p[x=d]\sim\beta d$. In principle, we can fit
multiple distribution models: we fit the inverse Gaussian (IG) and a log-
normal. We plot the correspondent distribution for the models.

Our goal is to estimate the probability that an impression with distance $d>R$
could be a probability of a hit. In practice, we could use $IG(\mu,\lambda)$
to estimate the probability for every impression in the range
$[R,R+\frac{R}{2}]$, in Figure 5 and 6 we represent this space by the first
two vertical gray lines (from the far left). And we could use the
$LogNormal(\mu,\sigma)$ for the interval $(R+\frac{R}{2},3R]$.

###  5.5 Large scale lift comparison

To the best of our knowledge, the system we present in Section 2.1 and show
results in Section 5.3 is the only one capable to tackle an experiment with 2
million users in any practical way. In this section, we present a different
prospective in order to create and to measure even larger experiments and show
how sampling is still a lingering issue, although for different reasons.

Let us introduce the impression space: We formally introduced the concept of
impression and we used to specify visits as in Equation 6. Where do these
impressions come from? We are listening to a fire-hose of streaming
impressions that we can bid through a collection of exchanges. Our budgets
dictates how much we can listen and it changes. Here, we call this fire-hose
real time bid (RTB) exchanges, the volume of RTB is a function of an
allocation budget and it will change as a function of company wide budget,
hardware allocation and hardware/software failure. The RTB is composed of
three non intersecting parts:

  * •

Listening RTB (LRTB) is a random sample of the fire-hose used only for
collection purpose, let us say that LRTB is 10% of the RTB.

  * •

Won RTB (ND), we bid and we win the impression, thus we deliver our advert.
The volume of impressions here is a function of campaign budget and pacing.

  * •

Unwanted RTB (URTB) is the remaining impressions, the larger portion of RTB.

Using all URTB, LRTB, and ND (i.e., urtb-lrtb-nd) impressions and our
unbalanced approach, we will not sample impressions, visits, nor users. This
is the ultimate representation of our experiment space. As such, it puts quite
a few practical and economical constraints in the experiment measure. For
example, a national campaign like Starbucks counting 10 thousands locations
and three months period, will touch approximately 100 million devices and
(hundred of) billions impressions. This experiments will have maximum number
of users and visits.

Historically and thus in Section 2.1, the balanced approach uses the URTB and
ND impressions, it intersects the exposed users to those impressions and it
samples the control, (i.e., c-urtb-nd). For national campaigns as above, the
sheer size of impressions to manage can be quite large. As a practical effect,
we sample control, we sample visitors, and thus we sample visits.

Assume we embrace a different sampling: sampling of impression in time. The
LRTB has the property of being an unbiased and random sample of RTB, thus the
space LRTB-ND (i.e., lrtb-nd) may have all the information we need, a critical
size to compare users and visits, and a practical size to have the experiment
measures in a more economical way.

A long tail distribution is applicable here. There are a lot of users with few
impressions, there are a lot of users with zero visits. The c-urtb-nd samples
mostly control, even though we use the terminology of balanced approach, we
can appreciate the irony of the name, if or when we are control. The lrtb-nd
approach will sample the impressions, we will pick users with enough
impressions, but we do that without any bias to the targeting. Of course, a
critical mass has to be met by both, otherwise the sampling curse will be
visible at this level as well. Now, we can introduce the final experiment.

We took twelve campaigns of various sizes. For each we measure lift without
any matching, we use the term of general lift. These experiments have
different goals. In Figure 7, we show the results.

Figure 7: General Lift using different methodology and sampling

To provide a clear presentation of the small differences, we opted for a non
standard box plot. For any lift in the range $[-1,1]$, we present it as it is.
For any lift in the range $[1,\infty)$, we represent it as
$1+\log_{10}(lift)$. We work out similarly the negative lift smaller than
$-1$. Thus, we use a logarithmic scale but only for large enough lifts.

We can appreciate that the general lift for all campaigns is negative (on an
average). There is only one exceptions where c-urtb-nd is not correlated to
urtb-lrtb-nd (i.e., campaign $20592$), and only one exception for rtb-nd
(i.e., campaign $20601$). This means that sampling can be an issues even at
this scale but it is moderate. Why is it always negative? The main reason is
targeting: targeting is far from being ignorable and the control group is not
really comparable. We need to apply matching and we show the lift comparison
in Figure 8.

Figure 8: Effect of Matching

There is even a stronger correlation on the sign of the lift while applying
matching: only campaign $20483$ is the exception. In general, sampling
increases the variance of the lifts (a little obscured by the log scale) and
the absolute value of the lift; that is, sampling reduce the population of the
experiments, making the visit per user effect larger.

The larger the experiment is, then the smaller the lift is. This is an
important and practical consideration. Lift is basically a comparison measure
with respect to a control that it can be much larger than the exposed group
and thus the control visits can be much larger. Eventually, we are bound to
measure lift as number of relative visits with respect to all visits, if all
visits increases the lift will decrease. This is the course of relative
measures: A larger campaign may have a larger effect (more visits) than a
smaller one, but relatively to the population it reached, the larger campaign
will have smaller lift.

##  6 Conclusions

In this work, we present a common and important problem for advertising
companies: how to quantify the effect of a digital campaign. Specific to our
field, we need to measure visits and the speed of visits for an exposed group
with respect to a control baseline. We introduce a general approach and we
explain two different methodologies using a balanced and an unbalanced
exposed-control selection. We follow through by presenting two implementations
and showing their different capabilities and similarities. We show that we can
write scalable matching algorithms that can be practical, accurate as much as
the ones available in the literature. We show that our algorithms can be
applied to very large experiments.

After all, the two methods should agree on an average especially if the
experiments are well deployed. Our goal is to share our intuitions, our
development solutions, and insights. This is a complex problem: our solutions
have often been driven by practical necessities, limited resources, and clear
goals. Here we show our best and always moving effort to present our
understanding and shed some light to possible, sound, and practical solutions.

## References

  * Abadie and Imbens (2006) Abadie, A. and Imbens, G. W. 2006\.  Large sample properties of matching estimators for average treatment effects.  Econometrica 74, 1, 235–267.
  * Abadie and Imbens (2008) Abadie, A. and Imbens, G. W. 2008\.  On the Failure of the Bootstrap for Matching Estimators.  Econometrica 76, 6, 1537–1557.
  * Abadie and Imbens (2009) Abadie, A. and Imbens, G. W. 2009\.  Matching on the estimated propensity score.  Working Paper 15301, National Bureau of Economic Research. August.
  * Austin and Small (2014) Austin, P. C. and Small, D. S. 2014\.  The use of bootstrapping when using propensity-score matching without replacement: a simulation study.  Statistics in Medicine, n/a.
  * D’Alberto and Dasdan (2009) D’Alberto, P. and Dasdan, A. 2009\.  Non-parametric information-theoretic measures of one-dimensional distribution functions from continuous time series.  In SDM (2009-06-12). SIAM, 685–696.
  * Dawid (1979) Dawid, A. P. 1979\.  Conditional Independence in Statistical Theory.  Journal of the Royal Statistical Society. Series B (Methodological) 41, 1, 1–31.
  * Dehejia and Wahba (1998) Dehejia, R. H. and Wahba, S. 1998\.  Propensity score matching methods for non-experimental causal studies.  Working Paper 6829, National Bureau of Economic Research. December.
  * Forgy (1965) Forgy, E. 1965\.  Cluster analysis of multivariate data: Efficiency versus interpretability of classification.  Biometrics 21, 3, 768–769.
  * Goo and Fraser (2014) Goo, S. and Fraser, M. 2014\.  Propensity Score Analysis: statistical MEthods and Applications.  SAGE.
  * Griffin et al. (2014) Griffin, B. A., McCaffrey, D. F., Martin, C., Burgette, L. F., Almirall, D., Ramchand, R., and Jaycox, L. H. 2014\.  Toolkit for weighting and analysis of nonequivalent groups (twang).  RAND Corporation.
  * Hansen and Klopfer (2006) Hansen, B. B. and Klopfer, S. O. 2006\.  Optimal full matching and related designs via network flows.  Journal of Computational and Graphical Statistics 15, 3, 609–627.
  * Hartigan and Wong (1979) Hartigan, J. A. and Wong, M. A. 1979\.  A k-means clustering algorithm.  JSTOR: Applied Statistics 28, 1, 100–108.
  * Heinrich et al. (2010) Heinrich, C., Maffioli, A., and Vázquez, G. 2010\.  A primer for applying propensity-score matching.  SPD Working Papers 1005, Inter-American Development Bank, Office of Strategic Planning and Development Effectiveness (SPD).
  * Ho et al. (2007) Ho, D., Imai, K., King, G., and Stuart, E. 2007\.  Matching as nonparametric preprocessing for reducing model dependence in parametric causal inference.  Political Analysis 15, 199–236.
  * Iacus et al. (2012) Iacus, S. M., King, G., and Porro, G. 2012\.  Causal inference without balance checking: Coarsened exact matching.  Political Analysis 20, 1–24.
  * Mandelbrot (1960) Mandelbrot, B. 1960\.  The Pareto–Levy law and the distribution of income.  International Economic Review 1, 2, 79–106.
  * McCullagh and Nelder (1989) McCullagh, P. and Nelder, J. A. 1989\.  Generalized Linear Models, Second Edition.  Chapman & Hall/CRC Monographs on Statistics & Applied Probability. Taylor & Francis.
  * Morgan and Winship (2007) Morgan, S. and Winship, C. 2007\.  Counterfactuals and Causal Inference: Methods and Principles for Social Research.  Cambridge.
  * Rosenbaum and Rubin (1983) Rosenbaum, P. R. and Rubin, D. B. 1983\.  The central role of the propensity score in observational studies for causal effects.  Biometrika 70, 41–55.
  * Rubin (1976a) Rubin, D. B. 1976a.  Multivariate matching methods that are equal percent bias reducing. I: Some examples (corr: V32 p955).  Biometrics 32, 109–120.
  * Rubin (1976b) Rubin, D. B. 1976b.  Multivariate matching methods that are equal percent bias reducing. Ii: Maximums on bias reduction for fixed sample sizes (corr: V32 p955).  Biometrics 32, 121–132.
  * Sekhon (2011) Sekhon, J. S. 2011\.  Multivariate and propensity score matching software with automated balance optimization: The Matching package for R.  Journal of Statistical Software 42, 7, 1–52.
  * Sekhon and Grieve (2012) Sekhon, J. S. and Grieve, R. D. 2012\.  A matching method for improving covariate balance in cost-effectiveness analyses.  Health Economics 21, 6, 695–714.
  * Shannon (1948) Shannon, C. 1948\.  A mathematical theory of communication.  Bell System Technical Journal 27, 379–423, 623–656.