Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
CA 02651165 2011-04-27
METHOD AND APPARATUS TO PERFORM REAL-TIME
AUDIENCE ESTIMATION AND COMMERCIAL SELECTION
SUITABLE FOR TARGETED ADVERTISING
FIELD OF INVENTION
The present invention relates to innovations in nonlinear filtering wherein
the
observation process is modeled as a Markov chain, as well as utilizing an
embodiment of the
invention to estimate the user composition of a user equipment device in a
communications
network, e.g., the number and demographics of television viewers in a digital
set top box
(DSTB) environment. Furthermore, the present invention provides methods to
optimally
determine which set of assets, e.g., commercials, to insert into available
network bandwidth
based on a sampling of optimal conditional estimates of the current network
usage (e.g.,
viewership).
BACKGROUND OF THE INVENTION
By and large, delivery of commercials to television audiences has changed
relatively
little over the past fifty years. Marketing firms and advertisers attempt to
determine what
their target audience watches using historical Nie1sonn4 rating information.
This data
provides an estimate of the number of households who watched a particular
episode of a
television show at a particular time, as well as a demographic breakdown
(usually based on
age, gender, income and ethnicity). Such data (an other rating data) is
currently gathered
using 'people meter' data, which automatically monitors what shows are being
watched once
a user indicates they are watching television. These samples are relatively
small ¨ currently,
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
only approximately 8,000 households are used to estimate the entire viewership
across the
United States. As the number of available television channels has increased,
along with the
shift in audience viewership from broadcast to cable television and coupled
with the
increasing number of television sets within a single household, it is
increasingly difficult to
accurately estimate the actual audiences of television shows based on such a
small sample.
As a result, smaller share cable channels are unable to properly estimate
their viewership and
consequently advertisers are unable to properly capture lucrative target
demographics.
As DSTB penetration continues due to the growing demand for digital cable
offerings, more precise information for individual households can
theoretically be obtained.
That is, set top boxes have access to information about what channel is being
watched, how
long the channel has been watched, and so on. This wealth of information, if
properly
processed, could provide insight into the behavior of a household. However,
none of this
information can directly provide the type of information that advertisers wish
¨ what types of
people are watching at a particular time. Advertisers wish to have their ads
displayed to their
target audiences with maximum precision, in order to reduce the cost of
marketing and
increase its effectiveness. Moreover, they wish to avoid the negative
publicity cost
associated with playing a commercial to inappropriate audiences. The key to
providing
advertisers with the power to maximize their investment is to change the way
viewership is
counted, which "potentially [changes] the comparative value of entire genres
as well as entire
demographic segments" (Gertner, J; Our Ratings, Ourselves; New York Times;
April 10,
2005).
Various systems have been proposed or implemented for identifying current
viewers
or their demographics. Some of these systems have been intrusive, requiring
users to
explicitly enter identification or demographic information. Other systems have
attempted to
develop behavioral profiles of viewers based on information from a variety of
sources.
However, these systems have generally suffered from one or more of the
following
drawbacks: 1) they focus on who is in the household rather than who is
watching now; 2)
they may only provide coarse information about a subset of the household; 3)
they require
user participation, which is undesirable for certain users and may entail
error; 4) they do not
provide a framework for determining when there are multiple viewers or for
accurately
defining demographics in multiple viewer scenarios; 5) they are fairly static
in their
2
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
assumptions and do not properly handle changing household compositions and
demographics; and/or 6) they employ sub-optimal technologies, require
extensive training,
require excessive resources or otherwise have limited practical application.
SUMMARY OF THE INVENTION
The present invention relates to analyzing observations obtained from a
measurement
device to obtain information about a signal of interest. In one application,
the invention
relates to analyzing user inputs with respect to a user equipment device of a
communications
network (e.g., a user input click stream entered with respect to a digital set
top box (DSTB)
of a cable television network) to determine information regarding the users of
the user
equipment device (e.g., audience classification parameters of the user or
users). Certain
aspects of the invention relate to processing corrupted, distorted and/or
partial data
observations received from the measurement device to infer information about
the signal and
providing a filter system for yielding a substantially real time estimate of a
state of the signal
at a time of interest. In particular, such a filter system can provide
practical approximations
of optimized non-linear filter solutions based on certain constraints on
allowable states or
combinations therefore inferred from the observation environment.
In accordance with one aspect of the present invention, a method and apparatus
("system") is provided for developing an observation model with respect to
data or
measurements obtained from the device under analysis. In particular, the
system models the
input measurements as a Markov chain, whose transitions depend upon the
signal. The
observation model may take into account exogenous information or information
external to
(though not necessarily independent of) the input measurements. In one
implementation, the
input measurements reflect a click stream of DSTB. The click stream may
reflect channel
selection events and/or other inputs, e.g., related to volume control. In this
case, the
observation model may further involve programming information (e.g.,
downloaded from a
network platform such as a Head End) associated with selected channels. Thus,
click stream
information is processed as a Markov chain.
Desired information related to the device can then be obtained by estimating
the state
of the signal at a time of interest. In the example of analyzing a click
stream of a DSTB, the
signal may represent a user composition (involving one or more users and/or
associated
3
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
demographics) and an additional factor affecting the click stream such as a
channel changing
regime as discussed in more detail below. Once the signal has been estimated,
a state of the
signal at a past, present or future time can be determined, e.g., to provide
user composition
information for use in connection with an asset targeting system.
In accordance with a still further aspect of the present invention, a system
generates
substantially real time estimates of a signal state based on an observation
model. In this
regard, a non-linear filter system can be used to provide an estimate of the
signal based on
the observation model. The non-linear filter system may involve a non-linear
filter model
and an approximation filter for approximating an optimal non-linear filter
solution. For
example, the approximation filter may include a particle filter or a discrete
state filter for
enabling substantially real time estimates of the signal based on the
observation model. In
the DSTB example, the non-linear filter system allows for identifying user
compositions
including more than one viewer and adapting to changes in the potential
audience, e.g.,
additions of previously unknown persons or departures of prior users with
respect to the
potential audience.
In accordance with a further aspect of the present invention, a system uses a
signal
obtained by applying a filter to an observation model to obtain information of
interest with
respect to the observation model. Specifically, information for a past,
present or future time
can be obtained based on an estimated state of the signal at the time of
interest. In the case of
analyzing usage of a DSTB, the identity and/or demographics of a user or users
of the DSTB
at a particular time can be determined from the signal state. This information
may be used,
for example, to "vote" or identify appropriate assets for an upcoming
commercial or
programming spot, to select an asset from among asset options for delivery at
the DSTB
and/or to determine or report a goodness of fit of a delivered asset with
respect to the user or
users who received the asset.
The above noted aspects of the invention can be provided in any suitable
combination. Moreover, any or all of the above noted aspects can be
implemented in
connection with a targeted asset delivery system.
In one embodiment of the present invention, a system is provided for use in
targeting
assets to users of user equipment devices in a communications network, for
example, a cable
television network. The system involves: developing an observation model based
on inputs
4
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
by one or more users with respect to a user equipment device; modeling the
observation
model as a signal reflective of at least a user composition of one or more
users of said user
equipment device with respect to time; determining the user composition at a
time of interest
as a state of the signal; and using the determined user composition in
targeting an asset with
respect to the user equipment device. In this manner, filtering theory is
applied with respect
to inputs, such as a click stream, of a user equipment device so as to yield a
signal indicative
of user composition.
The inputs can be modeled as a Markov chain. Moreover, a model of the signal
allows for representation of the user composition as including two or more
users.
Accordingly, multiple user situations can be identified for use in targeting
assets and/or better
evaluating audience size and composition (e.g., to improve valuation and
billing for asset
delivery). In addition, the signal model preferably allows for representation
of a change in
user composition, e.g., addition or removal of a person from a user audience.
A non-linear filter may be defined to obtain the signal based on the
observation
model. In this regard, the signal may represent the user composition of a
household with
respect to time and audience classification parameters (e.g., demographics of
one or more
current users) can be determined as a function of the state of the signal at a
time of interest.
In order to provide a practical estimation of an optimal non-linear filter
solution, an
approximation filter may be provided for approximating operation of the non-
linear filter.
For example, the approximation filter may include a particle filter or a
discrete space filter.
Moreover, the approximation filter may implement at least one constraint with
respect to one
or more signal components. In this regard, the constraint may operate to treat
one component
of the signal as invariant with respect to a time period where a second
component is allowed
to vary. Moreover, the constraint may operate to treat at least one state of a
first component
as illegitimate or to treat some combination of states of different signal
components as
illegitimate. For example, in the case of a click stream of a DSTB, the
occurrence of a click
event indicates the presence of at least one person. Accordingly, only user
compositions
corresponding to the presence of at least one person is permissible at the
time of a click
event. Other permissible or impermissible combinations may relate incomes to
locations.
The constraints may be implemented in connection with a finite space
approximation filter.
For example, values incident on an illegitimate cell may be repositioned,
e.g., proportionately
5
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
moved to neighboring legitimate cells. In this manner, the approximation
filter can quickly
converge on a legitimate solution without requiring undue processing
resources. Where the
constraint operates to define at least one potential calculated state as
illegitimate, the
approximation filter may redistribute one or more counts associated therewith.
Additionally, the approximation filter may be operative to inhibit convergence
on an
illegitimate state. Thus, the approximation filter is designed to avoid
convergence on a user
composition for a DSTB that is logically impossible or unlikely (a click event
when no user
is present) or deemed illegitimate by rule (an income range not permitted for
a given
location). In one implementation, this is accomplished by adding seed counts
to legitimate
cells of a discrete space filter to inhibit convergence with respect to an
illegitimate cell.
Preferably, the user composition information is determined at the digital set
top box.
That is, user information is calculated at the digital set top box and used
for voting, asset
selection and/or reporting. Alternatively, click stream data may be directed
to a separate
platform, such as a Head End, where the user composition information can be
determined,
e.g., where messaging bandwidth is sufficient and DSTB processing resources
are limited.
As a further altemative, the user composition information (as opposed to,
e.g., asset vote
information) may be transmitted to a Head End or other platform for use in
selecting content
for insertion.
The determined user composition information may be used by an asset targeting
system. For example, the information may be provided to a network platform
such as a Head
End that is operative to insert assets into a content stream of the network.
In this regard, the
platform may utilize inputs from multiple DSTBs to select assets for insertion
into available
network bandwidth. Additional information, such as information reflecting the
per user
value of asset delivery, may be utilized in this regard. The platform may
process information
from multiple user equipment devices as an observation model and apply an
appropriately
configured filter with respect to the observation model to estimate an overall
composition of
a network audience at a time of interest.
In accordance with another aspect of the present invention, stochastic control
theory
is applied to the problem of targeted asset delivery, e.g., dynamic viewer
classification and/or
television ad selection. Traditionally, stochastic control theory has been
applied in contexts
where a signal or function cannot be computed directly but only estimated
based on
6
CA 02651165 2011-04-27
observations that may be noisy or incomplete. In the present context,
measurements from a
measurement device can be processed according to stochastic control theory to
estimate a signal
from which state information can be determined. For example, measurements from
an input
device such as a click stream from a remote control are taken as noisy
observations and processed
using stochastic control to estimate a signal, which represents a household or
viewing audience
and a behavioral regime in relation to entry of the inputs. Stochastic control
allows tracking of the
signal such that the state of the signal at a particular time reflects the
viewer composition and
regime at that time. This information can be used to select targeted ads for
delivery, e.g., by
matching classification parameters of the viewing audience to targeting
parameters of available
ads.
In accordance with another aspect of the present invention there is provided a
method for
use in targeting assets to users of user equipment devices in a communications
network,
comprising the steps of:
developing an observation model based on first inputs by one or more users
with respect
to one or more user equipment devices;
developing a signal model reflective of possible states and dynamics of a user
composition of one or more users of a first user equipment device with respect
to time, wherein
said observation model probabilistically relates measurement data related to
said first inputs to
the possible states and dynamics;
employing a stochastic filter to estimate said user composition at a time of
interest
through an approximate conditional distribution of a signal given the signal
and observation
models and second inputs by one or more users; and
using said estimated user composition in targeting an asset with respect to
said user
equipment device.
In accordance with another aspect of the present invention there is provided
an apparatus
for use in targeting assets to users of user equipment devices in a
communications network,
comprising:
a port operative for receiving input information regarding first inputs by one
or more
users with respect to a user equipment device; and
a processor operative for providing an observation model based on said first
inputs,
modeling the observation model as dependent upon a signal model reflective of
at least a user
composition of one or more users of said user equipment device with respect to
time, where said
observation model probabilistically relates measurement data related to said
first inputs to said
user composition, employing a stochastic filter to estimate the user
composition at a time of
interest as a state of a signal through an approximate conditional
distribution of the signal given
7
CA 02651165 2012-08-03
=
the signal and observation models and second inputs by one or more users, and
using the
estimated user composition in targeting an asset with respect to the user
equipment device.
In accordance with yet another aspect of the present invention there is
provided a method
for use in targeting assets to users of user equipment devices in a broadcast
network, comprising
the steps of:
collectively analyzing a stream of data corresponding to a series of first
user inputs with
respect to one or more user equipment devices, wherein said step of
collectively analyzing
comprises establishing an observation model; and
applying logic for matching a pattern described by a stream corresponding to a
series of
second user inputs to a characteristic associated with an audience
classification of a user, wherein
said step of applying logic comprises employing a stochastic filter to
approximately estimate a
conditional distribution of a signal given the observation model and second
inputs and extract
signal estimates from said series of second user inputs to estimate said
audience classification at a
time of interest.
BRIEF DESCRIPTION OF THE DRAWINGS
For a more complete understanding of the present invention and further
advantages
thereof, reference is now made to the following detailed description, taken in
conjunction with
the drawings in which:
Fig. 1 is a schematic diagram of a targeted advertising system in accordance
with the
present invention;
Fig. 2 illustrates the REST structure in accordance with the present
invention;
Fig. 3 illustrates a cell structure for a cell of filter in accordance with
the present
invention;
Fig. 4 is a flowchart illustrating a filter evolution process in accordance
with the present
invention; and
Fig. 5 is a block diagram illustrating a process for simulating events in
accordance with
the present invention.
DETAILED DESCRIPTION
In the following description, the invention is set forth in the context of a
targeted asset
delivery (e.g., targeted advertising) system for a cable television network,
and the invention
provides particular advantages in this context as described herein. However,
it will be
appreciated that various aspects of this invention are not limited to this
context. Rather, the scope
of the invention is defined by the claims set forth below.
7a
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
Various targeted advertising systems for cable television networks have been
proposed or implemented. These systems are generally predicated on
understanding the
current audience composition so that commercials can be matched to the
audience so as to
maximize the value of the commercials. It will be appreciated that a variety
of such systems
could benefit from the structure and functionality of the present invention
for identifying
classification parameters (e.g., demographics) of current viewers.
Accordingly, although a
particular targeted asset delivery system is referenced below for purposes of
illustration, it
will be appreciated that the invention is more broadly applicable.
One targeted asset delivery system, in connection with which the present
invention
may be employed, is described in the above-noted U.S. Patent Application No.
11/331,835,
filed January 12, 2006. In the interest of brevity, the full detail of that
system is not repeated
herein. Generally, in that system, multiple asset options are provided for a
given time spot
on a given programming channel. Although various types of assets can be
targeted in this
regard as set forth in that description, targeted advertising (e.g., targeting
of commercials) is
an illustrative application and is used as a convenient shorthand reference
herein. Thus, a
given programming channel may be supported by multiple asset (e.g., ad)
channels that
provide ad options for one or more ad spots of a commercial break. A DSTB
operates to
invisibly (from the perspective of the viewer) switch to appropriate ad
channels during a
commercial break to provide targeted advertising to the current viewer(s).
The viewer identification structure and functionality of the present invention
can be
used in the noted targeted asset delivery system in a variety of ways. In the
noted system, an
ad list including targeting parameters is sent to DSTBs in advance of a
commercial break.
The DSTB determines classification parameters for a current viewer or viewers,
matches
those classification parameters to the targeting parameters for each ad on the
list and
transmits a "vote" for one or more ads to the Head End. The Head End
aggregates votes
from multiple DSTB and assembles an optimized flotilla of ads into the
available bandwidth
(which may include the programming channel and multiple ad channels). At the
time of the
commercial break, the DSTB selects a "path" through the flotilla to deliver
appropriate ads.
The DSTB can then report what ads were delivered together with goodness of fit
information
indicating how well the actual audience matched the targeting parameters.
8
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
The present invention can be directly implemented in the noted targeted asset
delivery
system. That is, using the technology described herein, the audience
classification
parameters for the current viewer(s) can be determined at the DSTB. This
information can
be used for voting, ad selection and/or goodness of fit determinations as
described in the
noted pending application. Alternatively, the description below describes a
filter theory
based Head End ad selection system that is an alternative to noted voting
processes. As a
still further alternative, click stream information can be provided to the
Head End, or another
network platform, where the audience classification parameters may be
calculated. Thus, the
audience classification parameter, ad selection and other functionality can be
varied and may
be distributed in various ways between the DSTBs, Head End or other platforms.
The following section is broken into several parts. In the first part, some
background
discussion of the relevant non-linear filter theory is provided. In the second
part, the
architecture and model classes are discussed.
1.1 Nonlinear Filtering
To properly solve the targeted advertisement viewership (potential and
current)
problem, one may look to the mathematically optimal field of filtering.
1.1.1 Traditional Nonlinear Filtering Overview
Nonlinear filtering deals with the optimal estimation of the past, present
and/or future
state of some nonlinear random dynamic process (typically called 'the signal')
in real-time
based on corrupted, distorted or partial data observations of the signal. In
general, the X, is
regarded as Markov process defined on some probability space (11, P) and is
the solution to
some Martingale problem. The observations typically occur at discrete times
tõ, and are
dependent upon the signal in some stochastic manner using a sensor function rk
a. MX a.,14..
Indeed, the traditional theory and methods are built around this type of
observations, where
the measurements are distorted (by nonlinear function h), corrupted (by noise
V), partial (by
the possible dependence of h on only part of the signal's state) samples of
the signal. The
optimal filter provides the conditional distribution of the state of the
signal given the
observations available up until the current time:
9
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
P(Xt in, 0 <t t})
The filter can provide optimal estimates for not only the current states of
the signal
but for previous and future states, as well as the entire path of the signal:
E Yk, 0 S th 5 t})
where a tr 5 to "4 cc.
In certain linear circumstances, an effective optimal recursive formula is
available.
Suppose the signal follows an Ito stochastic differential equation cixi
Aat)dt+B(X.idy,,
with A being the linear and B being constant. Furthermore, the observation
function takes the
form of Yk 10.4 ) " where (14=1 are independent Gaussian random variables.
This
formula is known as the Kalman filter. While the Kalman filter is very
efficient in
performing its estimates, its use in applications is inherently limited due to
the strict
description of the signal an observation processes. In the case where the
dynamics of the
signal are nonlinear, or the observations have non-additive and/or correlated
noise, the
Kalman filter provides sub-optimal estimates. As a result, other methods are
sought out to
provide optimal estimates in these more common scenarios.
While equations for optimal nonlinear estimation have been available for
several
decades, until recently they were found to be of little use. The optimal
equations were
unimplementable on a computer, requiring infinite memory and computational
resources to
be used. However, in the past decade, approximations to the optimal filtering
equations have
been created to overcome this problem. These approximations are typically
asymptotically
optimal, meaning that as an increasing amount of resources are used in their
computation
they converge to the optimal solution. The two most prevalent types of such
methods are
particle methods and discrete space methods.
1.1.2 Particle Filters
Particle filtering methods involve creating independent copies of the signal
(called
'particles') denoted as {d}:al, where /Nit is the number of particles being
used at time t. These
particles are evolved over time according to the signal's stochastic law. Each
particle is then
assigned a weight value Wimai) to effectively incorporate the information form
the sequence
of observations (1'1, ..., I'm). This can be done in such a way that the
weight after m
CA 02651165 2011-04-27
observations is the weight after m - 1 multiplied by a factor on dependent
upon the mm
observation Yni. However, these weights invariably become extremely uneven
meaning that
many particles (those with relatively low weights) become unimportant and do
little other
than consume computer cycles. Rather, removing these particles and reducing
calculation to
an ever-decreasing number of particles, one resamples the particles, which
means the
particles positions and weights are both adjusted to ensure that all particles
contribute to
conditional distribution calculation in a meaningful way while ensuring that
no statistical bias
is introduced in this adjustment. Early particle methods tended to do far too
much
resampling introducing excessive resampling noise into the system of particles
and degrading
estimates. Suppose that after resampling the weights of the particles after m
observations are
denoted as {wi,m(d)}141. Then, the particle filter's approximation to the
optimal filter's
conditional distribution is:
rjtrWion(e1)1e. EA
P(Xt E
Zr.:f WI,m(e)
As isit cc, the particle-filtering estimate yields the optimal nonlinear
filter estimate.
In U.S. Patent application 2002/0198681, entitled, "Flexible Efficient
Branching
Particle Tracking Algorithms," particles are duplicated, destroyed or left
unchanged
probabilistically at each time step. Based on the weight calculated for the
current time step
only (Wm(q)), particles are modified according to the following routine:
1. If 14-4-(4j)
w-(E!) - 1 (I, make 1.W.M.! copies of particle e and make one
additional copy with probability Wm(ejj
2. If -147-(e) <0, then eliminate the particle with probability 1 -
3. Perform an unbiased control algorithm to return the number of particles
to the
amount that existed prior to resampling.
This 'cautious' approach was an improvement over the previous known particle
filters and this filing also included a system to efficiently implement the
algorithm as well as
historical variants, where on wants to estimate the path of X up until time t
instead of merely
its current state. A further improvement that introduced even less performance
degradation
11
CA 02651165 2011-04-27
and improved computational efficiency was introduced in U.S. Patent No.
7,058,550,
entitled; "Selectively Resampling Particle Filter."
This method performed pair wise resampling as follows:
1. While WI,,n(ei) < PiT71,7,(e) for the highest weighted particle j and
the lowest
weighted particle i, then:
2. Set the state of particle i to j with probability vv1...(e,)rir,....(v)
and set the
state of particle j to i with probability wi.,-.(e)-fwt,-(e).
3. Reset the weight of particles i and j to Won (ei) Won (e) f"-(C).
In this method, a control parameter p is introduced to appropriately moderate
the
amount of resampling performed. As described in application 2005/0049830, this
value can
be dynamic over time in order to adapt to the current state of the filter as
well as the
particular application. This filing also included efficient systems to store
and compute the
quantities required in this algorithm on a computer.
1.1.3 Discrete Space Filters
When the state space of the signal is on some bounded finite dimensional
space, then
a discrete space and amplitude approximation can be used. A discrete space
filter is
described in detail in U.S. Patent No. 7,188,048, entitled "Refining
Stochastic Grid Filter"
(REST Filter). In this form, the state space D is partitioned into discrete
cells lc. For
instance, this space could be a d-dimensional Euclidean space or some counting
measure
space. Each cell yields a discretized amplitude known as A 'particle count'
(denoted as alc),
which is used to form the conditional distribution of the discrete space
filter:
P(X, E AlYi,...,11,7,) _______________________ '111 111ceit
TOQ
The particle counts of each state cell are altered according to the signal's
operator as
well as the observation data that is processed. As the number of cells becomes
infinite, then
the REST filter's estimate converges to the optimal filter. To be clear, this
filing considers
12
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
directly discretizing filtering equations rather than discretizing the signal
and working out an
implementable filtering equation for the disretize signal.
In application 2005/0071123, the invention utilized a dynamic interleaved
binary
index tree to organize the cells with data structures in order to efficiently
recursively compute
the filter's conditional estimate based on the real-time processing of
observations. While this
structure was amenable to certain applications, in scenarios where the
dimensional
complexity of the state space is small, the data structure's overhead can
reduce the method's
utility.
1.2 Stochastic Control
To properly solve the targeted commercial selection problem, one should look
to the
mathematically optimal field of stochastic control.
Conceptually, one could invent particle methods of direct discretization
methods to
solve a stochastic control problem approximately on a computer. However, these
have not
yet been done or at least gained widespread recognition. Instead,
implementation methods
usually discretize the whole problem and then solve the discretized problem.
2.1 Targeted Advertising System Architecture
Fig. 1 depicts the overall targeted advertising system. The system is composed
of a
Head End 100, which controls one or more Digital Set Top Boxes 200. The DSTBs
200 are
attempting to estimate the conditional probability of the state of potential
viewers in
household 205, including the current member(s) of the household watching
television, using
the DSTB filter 202. The DSTB filter 202 uses a pair of models 201 describing
the signal
(household) and the observations (the click stream data 206). The DSTB filter
202 is
initialized via the setting 302 downloaded from the Head End 100. To estimate
the state of
the household the DSTB filter 202 also uses program information 207 (which may
be
current, or in the recent past or future), which is available from a store of
program
information 208.
The DSTB filter 202 passes its conditional distribution or estimates derived
thereof to
a commercial selection algorithm 203, which then determines which commercials
204 to
display to the current viewers based on the filter's output, the downloaded
commercials 301,
13
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
and any rules 302 that govern what commercials are permissible given the
viewer estimates.
The commercials displayed to the viewers are recorded and stored.
The DSTB filter 202 estimates as well as commercial delivery statistics and
other
information may be randomly sampled 303 and aggregated 304 to provide
information to the
Head End 100. This information is used by a Head End filter 102, which
computes (subject
to its available resources) the conditional distribution for the aggregate
potential and actual
viewership for the set of DSTBs with which it is associated. The Head End
filter 101 uses an
aggregate household and DSTB feedback model 101 to provide its estimates.
These
estimates are used by the Head End commercial selection system 103 to
determine which
commercials should be passed to the set of DSTBs controlled by the Head End
100. The
commercial selection system 103 also takes into account any market information
105
available concerning the current commercial contracts and economics of those
contracts.
The resulting commercials selected 301 are subsequently downloaded to the
DSTBs 100. The
commercials selected for downloading affect the level settings 104, which
provide
constraints on certain commercials being shown to certain types of
individuals.
The following two sections describe certain detail elements of this system.
2.2 Household Signal and Observation Model Description
In this section, the general signal and observation model description are
given as well
as examples of possible embodiment of this model.
2.2.1 Signal Model Description
In general, the signal of a household is modeled as a collection of
individuals and a
household regime. In one preferred embodiment, this household represents the
people who
could potentially watch a particular television that uses a DSTB. Each
individual (denoted as
Xi) at a given point in time t has a state from the state space s E S, where S
represents the set
of characteristics that one wishes to determine for each person within a
household. For
example, in one embodiment one may wish to classify the age, gender, income,
and watching
status of each individual. Age and income may be considered as real values, or
as a discrete
range. In this example, the state space would be defined as:
14
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
S = 10 ¨ 12, 12 ¨ 18, 18 ¨ 24, 24 ¨ 38, 38+1X {Male, Female} X {0 - $50, 000,
$50, 000+}X {Yes, No)
oc
u sk
The state space of the household member is then k=0 , where k denotes the
number
of individuals and S denotes the single state with no individuals. The
household members
Xt ...,)qt)
have a time-varying random number of members, where nt is the number
of members at time t. Since the order of members within this collection is
immaterial to the
Çfli6 õ
problem, we use the empirical measure of the members 1=1
to represent the
household.
The household regime depicts a current viewing 'mindset' of the household that
can
materially influence the generation of click stream data. The household's
current regime rt is
a value from the state space R. In one embodiment of the invention, the
regimes can consist
of values such as 'normal', 'channel flipping', 'status checking', and
'favorite surfing'.
Thus, the complete signal is composed of the household members and the regime:
The state of the signal evolves over time via rate functions X, which
probalistically
govern the changes in signal state. The probability of a state change from
state i to j after
some time t is then:
R1(t) P (T > t) = exp (¨ f AT(s)ds)
0
There are separate rate functions for the evolution of each individual, the
household
membership itself, and the household's regime. In one embodiment of the
invention, the rate
functions for individual i may depend only on the given individual, the
empirical measure of
the signal, the current time, and some external environmental variables A(t,X
Xt, et).
The number of individuals within the household nt varies over time via birth
and
death rates. Birth and death rates do not merely indicate new beings being
born or existing
beings dying ¨ they can represent events that cause one or more individuals to
enter and exit
the household. These rates are calculated based on the current state of all
individuals within
the household. For example, in one embodiment of the invention a rate function
describing
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
the likelihood of a bachelor to have either a roommate or spouse enter the
household may be
calculated.
In one embodiment of the invention, these rate functions can be formulated as
mathematical equations with parameters empirically determined by matching the
estimated
probability and expected value of state changes from available demographic,
macroeconomic, and viewing behavior data. In another embodiment, age can be
evolved
deterministically in continuous state space [0, 120].
2.2.2 Observation Model Description
In general, the observation model is comprised of click stream information
that is
generated by one or more individuals' interaction with a DSTB. In one
preferred
embodiment of the invention, only current and past channel change information
is
represented in the observation model. Given a universe of M channels, we have
a channel
change queue at time tk of Yk= Ong I = -121k-13+1) channels that were watched
in the past B
discrete time steps. In one preferred embodiment of the invention, only the
times when a
channel change occurs as well as the channel that was changed to are recorded
to reduce
overhead.
In the more general case, a viewing queue contains this current and past
channels as
well as such things as volume history. In the aforementioned case, the viewing
queue
degenerates to the channel change queue.
The probability of the viewing queue changing from state i to state j at time
t based
on the state of the signal and some downloadable content D, (denoted as pi_.;
(D,X)) is then
determined. In one preferred embodiment, this downloadable content contains,
among other
things, some program information detailing a qualitative category description
of the shows
that are currently available, for instance, for each show, whether the show is
an "Action
Movie" or a "Sitcom", as well as the duration of the show, the start time of
the show, the
channel the show is being played on, etc.
In an absence of a special regime, an empirical method has been created to
calculate
the Markov chain transition probabilities. These probabilities are dependent
on the current
state of all members of the household and the available programs. This method
is validated
using observed watching behavior and Varadarajan's law of large numbers.
Suppose that P is
16
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
a discrete probability measure, assigning probabilities to
= {col ¨I K} and we have N
independent copies of the experiment of selecting an element. Then, the law of
large number
says that
E P,
k=1
where Liii is the ith random outcome of drawing an element from Q.
In one embodiment of the invention, this method focuses on calculating the
probabilities for a channel queue of size 1 (i.e., Yk = yk). The observation
probabilities, that
is, the probabilities of switching between two viewing queues over the next
discrete step, can
be first calculated by deteimining the probability of switching categories of
the programs and
then finding the probability of switching into a particular channel within
that category. The
first step is to calculate, often in a offline manner, the relative proportion
of category changes
that occur due to channel changes and/or changes in programs on the same
channel. In order
to perform this calculation, a mapping of all possible member states Xt are
mapped into a
discrete state space II such that f(Xt) = nt for some irt E a for all possible
Xt. We suppose
v
there are a fixed number of categories C CK). Furthermore, let there be N
viewer records, with each viewer record representing a constant period of time
At, and with
,2, , ,
each three-tuple viewing record V(k) (r, C1C) k 1 2
Nv containing information
about the discretized state of the household C.7r) and the category on the
beginning (CI) and
the end of the time period (C2). Then, for each r e 11 and VCr,Cj E C, we
calculate:
Nv
NtCj, Cj) = ly(k,c1,c2).(r,c1,04.
k=1
When the optimal estimation system is running the real-time, the probabilities
for the
category transition from C1 to Cj that occurs at a given time step are
calculated first by
calculating the probability of category changes given the currently available
programs:
N(7r,ci,CJ)
Pcp-.c.i(r) =
A
17
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
where A runs over all possible valid category switches based on the current
programs
available. Then, this probability is converted into the needed channel
transition probability
by:
( Tr)
Pi,j(r)
nt(J)
where n(J) is the number of channels that have shows that fall in category J
at the end of the
current time step.
An alternative probability measure to use is to calculate the 'popularity' of
channels
instead of the transition between channels at each discrete time step. This
above method can
be used to provide this form by simply summing over the transition
probabilities for a given
category:
P (1r) = Pou¨ci Or),
ia=1
Again, this probability is converted into the needed channel transition
probability by using an
instance of multiplication rule:
Pc (r)
(r) =
fl(J)
where n(J) is the number of channels that have shows that fall into category J
at the end of
the current time step.
In one embodiment of the invention, several or all of the categories will be
programs
themselves, given the finest level of granularity. In other instances, it is
preferable to have
broad categories to keep the number of probabilities that need to be stored
down.
2.3 Optimal Estimation with Markov Chain Observations
In the traditional filtering theory summarized above, one has that the
observations are
a distorted, corrupted partial measurement of the signal, according to a
formula like
Yk = h(Xtk)Vk))
where tk is the observation time for the /eh observation and {Vrk MI is some
driving noise
process, or some continuous time variant. However, for the DSTB model that we
described
18
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
in the immediately previous subsections, we have that Y is a discrete time
Markov chain
whose transition probabilities depend upon the signal. In this case, the new
state Yk can
depend upon the previous state, rendering the standard theory discussed above
invalid. In
this section, a new, analogous theory and system is presented for solving
problems where the
observations are a Markov chain. One noticeable generality of the system is
that Markov
chain observations may only be allowed to transition to a subset of all the
states that depends
upon the state that it is currently in. This is a useful feature in the
targeted advertising
application, since much of the viewing queue's previous data may remain in the
viewing
queue after an observation and the insertion of some new data. For
assimilation ease, this is
described in the context of targeted advertisement even though it clearly
applies in general.
Suppose that we have a Markov signal Xt with generator r and with an initial
0, co)
distribution v. To be precise, the signal is defined to be the unique DE[
process that
satisfies the (C711-martingale problem:
P(Xo, &,) = v(.)
and
it
¨ ¨
0
is a martingale of all C131 Ã D(4).
We wish to estimate the conditional distribution of Xt based upon 11,2,¨ = ,
MI-valued discrete-time Markov chain observation that depends upon Xt as well
as some
I I Do
exogenous information D. To make things manifest, suppose that l'uki k----= is
a sequence
of independent random variables that are independent of the signal and
observation such that
P(vk .---. i) -'.--- Iti for i = 1,2, ..., M arid k E Z. the observation Pk
occurs at time tk with
finite state space {1, ..., MI of events available and Yk 7"-= (Yric, lik-1,
¨.1Y/4--B-1-1), where
v I, O. ' 1 '0
k ''''' "
'''" transitions between values in {1, ..., M}B with homogeneous
transition probabilities Pi¨j(Dt, XL) of going from state i to state j at time
t. Here, Dr and Xt
are the current states of the pertinent exogenous information and signal
states at the time of
the possible state change.
19
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
To ease notation, we define Dk Dthl X k Xtk and set
Vk = (vk, vk-i vk-B-fi)T
for k 1, 2, ...
z. Ck-I (X0 for j =
¨ 1 for j = 0, -
1, -2, õ.
and
Z(t) Zj fort c
where
ck (Xk) = M (')k, Xk)
As a notational convenience, define Z0=1. Then, some mathematical calculations
show that
'Rif (X t)(Z (T))-1 ja {Y1, .
E[f (Xt)lcr{K, ,Yi}) = -
E[(Z(T))-110-{K,
fort; < T, where f: E -0 TR and
P(A) = .E!1A2(T)] VA E cr{(Xt, Yt), t <
Letting
, , 1
and noting the denominator and numerator of (6) are both calculated from
with g = 1 and g = f respectively, where
.7tY r7{K, ,Yj) for t E r,tit tj.4.1),
we just need an equation for
/2tf= EV(Xt)r/(t)1=Fi1
for a rich enough class of functions ir R.
More mathematics establishes that lit (dx) -E(lx.Edx77(t)IFtY) satisfies
nt
kit (V)) ¨ il0(1P) = (LIP)dS E
Pt, WCk)
k=1
for all t E [O, c ) and E 1)(e), where Z'(x) =1- T:111 and n. = max{k tk 4.
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
2.4 Filtering Approximations
In order to use the above derivation in a real-time computer system,
approximations
must be made so that the resulting equations can be implemented on the
computer
architecture. Different approximations must be made in order to use a particle
filter or a
discrete space filter. These approximations are highlighted in the sections
below.
2.4.1 Particle Filter Approximation
By equation (6) we only need to approximate
/it (d.z) TE[lxced.T11(t)l-%ri
where
LtJ
11(t) = x (Act X k) M X PYk_t-sYk ( kl Xtk)
1=i
is the weighting functions. Now, suppose that we introduce independent signal
particles
{Clot O} each each with the same law as the historical signal and
define the weights
Lti
x (Dki eit4 ).
k=1
Then, it follows by deFinnetti's theorem and the law of large numbers that
-
E re (-015ti (dr) Ilt(dx).
2.4.2 Discrete Space Approximation
If we set the state space of X, to be E, then for each N E N1, we let /N and
MN satisfy
/ 00 and MN 00 as N 00. For D N 11,-,c61 c N, we suppose that
E DN} is a partition of E such that Maxk charn(Civ) N-.¨+ 0, and that
all the discrete
states are in different cells, i.e., it is only expanding and contracting on
age amounting to
N 4
letting a = aiv ¨4 O. Then, we take vo":" 6 Cicsr and define fo,i,AfN1-,-
and do the
following intuitive justification:
21
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
Taking 71(CjY)---- j to mean n(Civ) = 31 for all i à DN and 77 E M(E), and
substituting the test functions 'P(17, r) = l'AC.")-"--,11 into (10), we get
t
ilt(r1(CN) = i) = Ih0(77(CN) = i) + f II, (Liv 1
0 rig
_ri(ON),,,.....i)d$ +
k---4
where Li v. =-**-4LaN
Then, it follows that
/At (77(CN) ' j) '' At ((Ix).
2.5 Refining Stochastic Grid Filter with Discrete Finite State
Spaces
In U.S. Patent No. 7,188,048, a general form of the REST filter was detailed.
This
method and system has demonstrated to be of use in several applications,
particularly in
Euclidean space tracking problems as well as discrete counting measure
problems. However,
several improvements upon this method have been discovered, which provide
dramatic
reductions in the memory and computational requirements for an embodiment of
the
invention, A new method and system for the REST filter is described herein
where the signal
can be modeled with a discrete and finite state space. Examples using the
targeted
advertising model are provided for clarity, but this method can be used with
any problem that
features the environment discussed below.
2.5.1 Environment Description
In certain problems, the signal is composed of zero or more targets Xti and
zero or
more regimes 4. For example, in targeted advertising one embodiment of the
signal model
is in the form Xt = (Xt, R), where Xt is the empirical measure of the targets
(or, more
specifically, the household members) and there is only one regime.
Furthermore, each target
and regime have only a discrete and finite number of states, and there are a
finite number of
targets and regimes (and consequently a finite number of possible combinations
of targets
and regimes). The finite number of combinations need not be all possible
combinations ¨
only a finite number of legitimate combinations are required. For instance, a
finite possible
types of households (meaning households with particular demographics within)
can be
22
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
derived from geography-dependent census information at relatively granular
levels. Instead
of having all potential combinations of individuals (up to some maximum
household
membership nilAx), only those combinations which can be possibly found within
a given
geographic region need to be considered legitimate and contained within the
state space.
In these restricted problems, some of the state of the target(s) and/or
regime(s) may
be invariant over short-term during which the optimal estimation is occurring.
In these cases,
such state information is held to be constant, while other portions of the
state information
remain variant. In one embodiment of the household signal model, the age,
gender, income,
and education levels of each individual within the household may be considered
to be
constant, as these values change over longer periods of time and the DSTB
estimation occurs
over a period of a few weeks. However, the current watching status of the
household regime
information change over relatively short time frames, and as a result these
states are left to
vary in the estimation problem. We shall denote the invariant portion of the
signal as 2 and
the variant portion of the signal as A. There are N possible invariant states
(the ith such state
donated by je 9 and Mi possible variant states for the ith invariant state
(the ith state denoted by
2.5.2 REST Finite State Space System Overview
Fig. 2 depicts one preferred embodiment of the REST filter in a finite state
space
environment. REST is composed of a collection of invariant state cells, each
of which
represents one possible collection of targets and regimes for the signal along
with their
invariant state properties. Each invariant cell contains a collection of
variant state cells, each
representing the possible time-variant states of the given invariant cell.
Implicitly, the
variant cells contain the invariant state information of their parent
invariant cell, meaning
each variant cell represents a particular potential state of the signal. The
invariant cells
themselves represent an aggregate container object only and are used for
convenience
purposes. The collections of variant and invariant cells may be stored on a
computer medium
in the form of arrays, vectors, list or queues. Cells which have no particle
count at a given
time t may be removed from such containers to reduce space and computational
requirements, although a mechanism is reinsert such cells at a later date is
then necessary.
23
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
As shown in Fig. 3, each variant state sell contains a particle count n=4.
This particle
count represents the discretized amplitude of that cell. As noted previously,
this amplitude is
used to calculate the conditional probability of a given state. Each variant
state cell also
Atµi,9
contains a set of imaginary clocks t . These imaginary clocks represent the
possible state
changes from the given state cell. For each variant state cell there are Qij
possible state
transitions. In this environment, all valid state transactions occur within
the same invariant
state cell. To account for simultaneous changes in the conditional
distribution of the REST
filter, temporary counter entitled particle count entitled particle count
delta is used to
store the number of particles that will be added or removed from the give
variant state cell
once the sequential processing of all cells is completed. Cells which have a
valid state
transition from the variant state cell with state Xli4 are said to be
neighbors of that cell.
As mentioned above, the invariant state cells are containers used to simplify
the
processing of information. Each invariant state cell's particle count 74 is an
aggregate to its
child variant state cell particle counts. Similarly the invariant state cell's
imaginary time
clock is an aggregation of all clocks from the variant cells. This aggregation
facilitates the
filter's evolution, as invariant states which have no current particle count
can be skipped at
various stages of processing.
2.5.3 REST Filter Evolution
Fig. 4 depicts the typical evolution of the REST filter. This evolution method
updates
the conditional distribution of the filter over some time period dt by
transferring particles
between neighboring cells using the imaginary clock values. The movement of a
particle
between neighboring cells is know as an event. (Well, we often replace the
movement of
particles with extra births and deaths to allow more rate cancellation to
occur.) Such events
are simulated en masse to reduce the computational overhead of the evolution.
The number
of events to simulate is based on the total imaginary clock sum At for all
cells. Fig. 5 shows
the method that determines how may particles move to each neighbor. When the
simulation
of events is complete, the particle counts can be update and the imaginary
clocks are sealed
back to represent the change in the state of the filter.
24
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
Compared to the previous method described in U.S. Patent No. 7,188,048,
additional
steps have been added to improve the effectiveness of the filter.
Specifically, an adjustment
to the cell particle counts now occurs prior to the push down observations
method, and a
draft back routine has been added prior to particle control. In certain
problems, some states
may have no possibility of being the current signal state based on observation
information.
For instance, a household must have a least one member current watching if a
channel
change is recorded. In these circumstances, the particles in all invalid
states must be
invadid
redistributed to proportionately to valid states. Thus, if there are nt
particles to
nitnvaLid i _________________________________________________
LE *IV
redistribute, then all valid variant state cells will receive
particles, and will
Eitt:4
receive an additional particle with probability . When this type of
observation-based adjustment is used, it is likely that the rates governing
the evolution of the
signal must be appropriately altered to coincide with the use of observation
data in this
manner.
To improve the robustness of the REST filter, a drift back method has been
added.
f ,t) to add 74" d
This method uses some function particles to variant state cells based
on the initial distribution v of the signal. The number of particles to add to
each cell depends
on time, the given cell, and the overall state of the filter. This method
ensures that the filter
does not converge to one or more invariant states without the ability to
recover from an
incorrect localization.
2.6 Head End Estimations
In order to maximize the profitability of multiple service operators'
advertising
operations, the determination of which commercials to distribute to a
collections DSTBS is
critical. As more information is available about the actual viewership of
commercials based
on the conditional distributions (or conditional estimates derived thereof) of
a DSTB-based
asymptotically optimal nonlinear filter, the pricing of specific commercial
slots can be more
dynamix, thus improving overall profits.
To capitalize upon this potential, an estimation of the aggregate households
that
includes such things as the number of people within each demographics) is
performed at the
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
Head End based on a random sampling of conditional DSTB estimates. The
following model
contains a prefer embodiment of the
2.6.1 Head End Signal Model
The Head End signal model consists of pertinent trait information of potential
and
current television viewers that have DSTB boxes connected to a particular Head
End. A state
space S is defined that represents such a collection of traits for a single
individual. In one
embodiment of the invention, this space could be made up of age ranges,
gender, and recent
viewing history for an individual. To keep track of individuals, we let Ca = 0
be the
household type of no individuals and C be the collection of household types
with n
individuals
Cn = {((si, ni ), ..., (sr, nr)) si E S and distinct, ni + n2 + + nr = n }
Cn
The collection of households would then be the union
of the households with n
people in them. Realistically, there would be a largest household N that we
could handle and
E Cn
we set the household state space to be a=o , where N is some large number.
To process the estimate transferred back from the DSTBs through the random
sample
mechanism, we also want to track the current channel for each DSTB. This means
that each
DSTB state; including potential household viewership, watching status, and
current channel;
is taken from
D
where there is M possible channels that the DSTB could be turned to.
We are not worried about a single DSTB nor even which DSTBS are in a
particular state but
rather with how many DSTBs are in state d E D. Therefore, we let the signal X
to be
tracked to a finite counting measure, counting the number of DSTBs in each
category
d E D.
In an embodiment of the invention, it is possible to track an aggregate the
possible
number of DSTBs in each category to minimize the computational requirements.
In such a
case, atoms of size o are used so that the total will still sum to the maximum
number of
26
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
DSTBs. For example, suppose that there are 1 million DSTBs. Then, we would
have
100,000 atoms (consisting of a = 10 DSTBs each) distributed over D. Suppose
M(D)
_
denotes the counting measure on D and M(D) denotes the subset of M(D) that has
exactly
100,000 atoms. The signal will evolve mathematically according to a martingale
problem
t
1
f (Xt) . f (X0) + i Z f (Xa )ds
0
where t ' Mt(f ) is a martingale for each continuous, bounded functional f on
ilf(D) and L is
some operator that would be determined largely from the DSTB rates and the
natural
assumption that the household act independently.
Any household that provide their demographics in exposed mode are not
considered
to be part of the signal.
2.6.2 Head End Observation Models
Herein we describe two observation models: one for the random sampling of
DSTBs
and one for delivery statistics.
For the random sample observation model, we consider the channel and
viewership
by letting X be our signal as in the previous section, and let Vk denote the
random selection at
time tk in the sampling process. To be precise, suppose that there are M DSTBs
for a
particular Head End and recall that a DSTB that believes at least one person
is currently
watching will supply a sample with a fixed probability of five percent. Then,
Vk would be a
matrix with a random number of rows, each row consisting of M entries with
exactly one
nonzero entry corresponding to the index of the particular DSTB, which has
provided a
sample. The number rows would be the number of DSTBs providing a sample. The
locations of the nonzero entries are naturally distinct over the rows and
would be chosen
uniformly over the possible permutations to reflect the actual sampling taken.
P
Now, we let \ ( t' 1U k,)
be the (column) vectors of the M DSTB's conditional
distribution viewership estimates and corresponding channel both at time tk.
Then, this
observation process would be
(
Otlx, = h(lik . Pk, U).
. _
27
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
Here, the Vk would do the random selection and the h would be a function
providing the
information that is chosen to be fed back.
For the aggregated ad delivery statistics model, we have time-indexed
sequences of
functions Ho that provide a count of the various ads delivered previously at
time tk ¨
There would be a small amount of noise Wkj due to the fact that some DSTBs may
not return
any information due to temporary malfunction (i.e. a 'missed observation'),
and due to the
fact that the estimated viewership used to determine a successful delivery is
not guaranteed to
be correct.
The second observation information from the aggregated delivery statistics
would be
nj 2,
v ¨ 44 k dt,,4 ¨ti 1471c,i
Here, j ranges back over the spot segments in the reporting periods and tk is
the reporting
period time.
2.6.3 Head End Filter
The signal for the Head End becomes the probability distributions from the
DSTB's.
2.7 Head End Commercial Selection
In certain embodiments of the invention, other information may be available
which
also can be used to perform the aggregate viewership estimation. For example,
aggregate
(and possibly delayed) ad delivery statistics can also provide inferences in
the estimated
viewership of DSTBs, as well as any 'exposed mode' information whereby
households opt to
provide their state information (demographics, psychographics, etc.) in
exchange for some
compensation.
In this setting, commercial contract is modeled as a graph of incremental
profit in
terms of the contract details, available resources and future signal state. We
call these graphs
contract graphs which arrive with rates that depend upon the contract details,
signal state and
economic environments. Some of the contract details include:
Number of times commercial is to be shown (could contain minimum and maximum
thresholds), likely in thousands;
Time range for time of day/week that commercial is to be shown;
28
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
The Target demographic(s) for the commercial;
Particular channels or programs that the commercial is to be shown on;
Customer that wrote the contract,
some of which may be optional.
The random arrival of the contract graphs is denoted as the contract graph
process.
Furthermore, an allotment of resources (that need not be maximum allotable to
any contract)
to a contract graph process is called a feasible selection if, given the state
(present and future)
and the environment, the allotted resources do not exceed the available
resources, i.e. the
available commercial spots over the various categories. Now, due to the fact
that these
limited resource become depleted as one accepts contracts, current versus
future potential
profits a modeled through a utility function. This utility function takes the
stream of contract
graphs available (both presently and with future random arrivals) and returns
a number
indicating profit in terms of dollar or some other form to satisfaction. Due
to the random
future behavior of contract graphs, the utility function cannot simply provide
maximum
profits without taking into account deviation from the expected profit to
ensure the
maximization does not allow significant risk of poor profit.
To perform optimal commercial selection, the following models need to be
defined
described: Head End signal model, Head End observation model, contract
generation model,
and utility (profit) model.
2.7.1 Contract Model
The commercial contracts that arise are modeled as a marked point process over
the
contract graphs. The rate of arrival for the contracts depends upon the
previous contracts
executed as well as external factors such as economic conditions..
Suppose that C denotes Lesbegue measure. Then, we let C denote the space of
possible contract graphs with some topology on it, {no t Cs} denote the
counting measure
stochastic process for the arrival of contract graphs up until time t and
denote a Poisson
measure over C x c ) x cx4 with some mean measure vxtx Ã. Furthermore, we let
A(c0110.0, t) be the rate (with respect to v) that a new contract will come
with contract graph
29
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
c E C at time t when 7/[0,t) the records the arrival of contract graphs from
time 0 up to but
not including time t. Then, we model by the following stochastic differential
equation
?it (A) = no(A) +A ip )4, 5 (v)vdc x dv x da) for all A E B(C).
x10,00) x [0, 10,1,
It is possible that the contract details noted above may be altered upon
acceptance of
a contract. As a result, the contract details are modeled to depend on
external environment
which can evolve over time.
2.7.2 Utility Function Description
To case notation, we let R(Ds) be the available resources, now and in the
future, based
upon the downloadable program information Ds at time s.
We will not be able to accept all contracts that arise and we have to make the
decision
whether to accept or reject a contract without looking into the future. We
denote an
admissible selection as a feasible selection such that each resource
allocation decision does
not use future contract or future observation information. In terms of the
notation of the
previous section, we suppose that nr represents the number of contracts that
have arrived of
the various types up to and including time t and take
(1) = tottic(is_, q)77(ds x dc)d1 far each t > 0,
Licx
where Q represents the set of all potential customers and {1,.
C}} is a selection process,
i.e., allocates resources to each contract c. Then, 05' $ ?O} is an admissible
selection if
is 5- 1?..(D-#) for each $ 0 and ls does not use future contract nor
observation information,
(In1 aj j,
i.e., is measurable with respect to crs_, .u1 ¨ < 4 {0
O N t < k I k " for each $ O.
(1)
Now, t, represents the profit obtained up to time t through admissible
selection l. To ease
notation, we let A be the set of all such admissible selections.
The utility function J balances current profit with future profit and the
change of
obtaining very high profits on a particular contract with the risk of no or
low profit. In order
to ensure that we start off reasonably, we will deweight future profit in an
exponential
manner. Moreover, in order that we are not overly aggressive we will include a
variance-like
condition. One embodiment of the resulting utility function is
CA 02651165 2008-11-03
WO 2007/131068 PCT/US2007/068075
CAI [7t(I) - a eyt (0)27 dt,
Pow)
for small constants A, a > O. Then, the goal of the commercial selection
process is to
maximize EiJ(X,1)] over the LEA. Such a goal can be solved using one or more
asymptotically optimal filters.
The foregoing description of the present invention has been presented for
purposes of
illustration and description. Furthermore, the description is not intended to
limit the
invention to the form disclosed herein. Consequently, variations and
modifications
commensurate with the above teachings, and skill and knowledge of the relevant
art, are
within the scope of the present invention. The embodiments described
hereinabove are
further intended to explain best modes known of practicing the invention and
to enable others
skilled in the art to utilize the invention in such, or other embodiments and
with various
modifications required by the particular application(s) or use(s) of the
present invention. It is
intended that the appended claims be construed to include alternative
embodiments to the
extent permitted by the prior art.
31
