# Detection of Object Throwing Behavior in Surveillance Videos

Ivo P.C. Kersten, Erkut Akdag†, Egor Bondarev, and Peter H.N. de With
Eindhoven University of Technology, Department of Electrical Engineering, 5612
AP Eindhoven, The Netherlands
†$\mathit{Corresponding}$ $\mathit{author:}$<EMAIL_ADDRESS>
###### Abstract

Anomalous behavior detection is a challenging research area within computer
vision. Progress in this area enables automated detection of dangerous
behavior using surveillance camera feeds. A dangerous behavior that is often
overlooked in other research is the throwing action in traffic flow, which is
one of the unique requirements of our Smart City project to enhance public
safety. This paper proposes a solution for throwing action detection in
surveillance videos using deep learning. At present, datasets for throwing
actions are not publicly available. To address the use-case of our Smart City
project, we first generate the novel public ’Throwing Action’ dataset,
consisting of 271 videos of throwing actions performed by traffic
participants, such as pedestrians, bicyclists, and car drivers, and 130 normal
videos without throwing actions. Second, we compare the performance of
different feature extractors for our anomaly detection method on the UCF-Crime
and Throwing-Action datasets. The explored feature extractors are the
Convolutional 3D (C3D) network, the Inflated 3D ConvNet (I3D) network, and the
Multi-Fiber Network (MFNet). Finally, the performance of the anomaly detection
algorithm is improved by applying the Adam optimizer instead of Adadelta, and
proposing a mean normal loss function that covers the multitude of normal
situations in traffic. Both aspects yield better anomaly detection
performance. Besides this, the proposed mean normal loss function also lowers
the false alarm rate on the combined dataset. The experimental results reach
an area under the ROC curve of 86.10 for the Throwing-Action dataset, and
80.13 on the combined dataset, respectively.

Index Terms— Anomaly Detection, Throwing Actions, UCF-Crime, CNN

## Introduction

Surveillance cameras are increasingly deployed to monitor public spaces to
enhance safety. The presence of surveillance cameras deters people from
misbehaving and accelerates the detection of unsafe behavior in traffic.
However, the increasing amount of surveillance footage processed by control-
room operators adversely impacts the actual efficiency of these cameras. The
human operators try to follow many camera streams at once, which results in a
higher likelihood of missing anomaly events. Anomaly events are defined as
deviations from the normal patterns in traffic flow. Such events can range
from any type of traffic accident up to suspicious behavior of people.
Although anomalies in traffic flow occur rarely, they have a significant
impact on public safety. Therefore, detecting these anomalies should be
automated to ensure maximum efficiency of a surveillance system and improve
the detection of anomaly events to sustain public safety.

The automation of anomaly detection is a topic that has recently seen an
increase in attention from the research community, where a focus is placed on
detecting a limited number of severe anomalies. However, certain types of
anomalies have received hardly any attention from the research community, even
though they can result in dangerous situations. One such anomaly is the action
of throwing objects into the surroundings by car drivers or other traffic
participants. Such throwing activities can have crucial consequences, from
disrupting the traffic flow to creating dangerous situations for all traffic
participants. Given the impact of this action, it is worth noting that we have
found no research work that aims at the detection of throwing anomalies. For
this reason we have constructed a dataset with throwing actions by different
traffic participants. Furthermore, this study explores how to apply the
anomaly-analysis approaches to the problem of detecting throwing actions and
how to merge our throwing action dataset into existing anomaly detection
datasets. The ultimate goal of our research is to enable automated detection
of dangerous behavior using surveillance camera feeds. A dangerous behavior
has been neglected often in other research and contains multiple dimensions,
where throwing actions in traffic flow is one of the unique requirements and
an important use case in Smart City projects.

Figure 1: Example frame from one of the videos in the proposed generated
Throwing-Action dataset, where a pedestrian is throwing an object at another
pedestrian.

This paper is organized as follows. First, the section on Related Work
provides an overview of throwing action detection and general anomaly
detection in the literature. Next, in the Proposed Novel Dataset section, we
introduce the novel throwing action dataset. The Methodology section presents
our proposed method and contributions. Then we evaluate experimental results
in the Experiments, while in the False Alarm Analysis section, the performance
of the proposed anomaly detection method is analyzed with respect to the false
alarm rate and qualitative results. Finally, the paper is concluded in the
Conclusion section.

## Related Work

This section presents the literature overview on methods for throwing action
detection and on supervised, unsupervised, and semi-supervised anomaly
detection methods.

### A. Throwing Action Detection

Related to throwing action detection, previous studies mainly focus on the
detection of the thrown object itself instead of the action. In [5], a
modified version of YOLOv3 [17] is proposed to detect particular objects when
they are thrown out of a car window. This approach relies on the recognition
of specific small objects, which is difficult when dealing with low-resolution
video footage or throwing actions are performed far away from the camera.

Other studies in [4] and [18] concentrate on the trajectories of moving
objects. The authors fit parabolic trajectories into the potential
trajectories. In other words, any object that is found to follow a parabolic
trajectory is deemed as a thrown object. This approach requires long
trajectories of thrown objects to reliably fit a parabolic trajectory. In
practice, objects are often thrown horizontally or downwards, which results in
a short trajectory that renders this method inefficient and only partially
addressing the case.

### B. Anomaly Detection

Anomaly detection is a challenging computer vision problem aiming to detect
rare events from a video stream. Different approaches to this problem can be
split into unsupervised, supervised, and semi-supervised categories.

#### 1) Unsupervised Anomaly Detection

The most popular approach is unsupervised anomaly detection, where the
training set contains only normal sequences. This approach is employed in many
papers, such as [27, 21, 19, 15, 2, 6, 10, 14]. During the training stage, a
model of normal behavior is constructed. This model can properly characterize
normal data in the testing stage, whereas it cannot characterize anomalous
data. Applying this method is advantageous when the exact nature of the target
anomalies is unknown or uncertain. A drawback of unsupervised anomaly
detection is that creating a model capable of exactly capturing all possible
normal behaviors is complicated. In other words, similar behaviors can be
often both anomalous or normal, depending on the context. For example, a car
driving down the right side of the road is considered normal behavior, while
driving down the wrong side of the road is not.

#### 2) Supervised Anomaly Detection

The second type is supervised training to learn anomalous behavior. Several
authors [16, 13, 26] use supervised anomaly detection methods to predict the
presence of anomalies only at the temporal level, while others [27, 11] also
locate the anomalies at the spatial level. In contrast to the unsupervised
methods that typically rely on a reconstruction error to find abnormal inputs,
supervised learning generally learns to predict an anomaly score directly from
the input data. An advantage of the supervised anomaly detection methods is
that they often outperform unsupervised techniques for the specific anomalies
for which they are trained. One of the drawbacks is the ambiguity of where
specifically an anomaly begins and ends. The second drawback is that these
methods can only detect the anomalies existing in the dataset, furthermore,
annotating the training data is labor-intensive and expensive, as anomaly
locations should be specified in every video frame or segment.

#### 3) Semi-supervised Anomaly Detection

The last type of anomaly detection is semi-supervised anomaly detection. This
method for anomaly detection is first introduced in [23] and is further
expanded in [12, 24]. In this approach, the training data contains both videos
of normal and anomalous events, however, the data is annotated on a per-video
basis. It is significantly faster to annotate data in this way, compared to
labeling at individual frames or areas in each frame. This annotation brings a
major advantage over the fully-supervised anomaly detection methods. A
disadvantage of this approach is that it only learns to recognize anomalies
that occur in the training data.

As can be derived, previous studies mainly focus on object or trajectory
detection, instead of considering the throwing action detection as an anomaly
detection use case. Therefore, we consider these throwing actions as
anomalies, and generate a dataset of throwing actions performed by different
road users in real traffic flow. We opted for a semi-supervised anomaly
detection method, as opposed to a supervised anomaly detection method, because
of its advantages in requiring less labeled data, while still providing a
higher accuracy than the unsupervised methods.

## Proposed Novel Dataset

Class | Definition | Examples of video
---|---|---
Bicycle Dangerous |  | Object is thrown by a bicyclist
---
towards another traffic participant
|
---
Bicycle Safe |  | Object is throwing by a bicyclist
---
onto the ground
|
---
Car Dangerous |  | Object is thrown out of a car window
---
towards another traffic participant
|
---
Car Safe |  | Object is thrown out of a car window
---
onto the ground
|
---
Pedestrian Dangerous |  | Object is thrown by a pedestrian
---
towards another traffic participant
|
---
Pedestrian Safe |  | Object is thrown by a pedestrian
---
onto the ground
|
---
Normal |  | No throwing actions occur but
---
some of the traffic participants do
occur in the video
|
---
Table 1: Table 1. Definition and examples of each video category in the Throwing-Action dataset. | Throwing-Action
---|---
| Training | Testing | Total
Bicycle Dangerous | 42 | 21 | 63
Bicycle Safe | 20 | 10 | 30
Car Dangerous | 38 | 19 | 57
Car Safe | 22 | 11 | 33
Pedestrian Dangerous | 38 | 20 | 58
Pedestrian Safe | 20 | 10 | 30
Normal | 87 | 43 | 130
Table 2: Table 2. Distribution of the number of videos over the various
classes for the Throwing-Action dataset.

Currently, datasets are not available from literature to train a throwing
anomaly detector. Therefore, we have generated a novel dataset, including the
throwing anomalies in six different outdoor categories to address the anomaly
use case from the Smart City project. The throwing anomalies are split into
classes based on the acting traffic participant (car, bicycle, pedestrian)
performing the throw, and whether or not the thrown object is directed towards
another traffic participant. If the throw is directed at another traffic
participant, it is called a ’dangerous’ throw, otherwise a ’safe’ throw. The
generated dataset includes six throwing anomaly classes as described in Table
1. All videos have a resolution of 320$\times$240 pixels. One of the
challenges in our dataset is that throwing anomaly videos can contain multiple
throwing actions up to a maximum of ten.

The objects used to create the throwing anomaly dataset are selected to have a
large diversity in object shape, size, and color. Additionally, some objects
maintain their shape during a throwing action, such as a football, while
others become deformed and change their shape during the throwing movement,
such as a sweater or plastic bag. Overall, the generated dataset consists of
130 normal videos without throwing anomalies and 271 anomalous videos divided
over all six anomaly classes, titled as the ”Throwing-Action” dataset
throughout the paper. Table 2 provides the number of videos of each anomaly
class in the dataset.

### A. Annotation

In the training set, each video is labeled as either normal or anomalous at
the video sequence level, while each video is annotated at the frame level in
the testing set. In other words, the start and end frames of each throwing
action are provided for the test set. While the start frame of an anomaly
action is defined as the first frame in which the object starts moving, the
end frame of it is considered as the first frame where the object touches the
ground or is occluded.

### B. Training and Testing Sets

The generated ”Throwing-Action” dataset is divided into a training and testing
set. The training set consists of 87 normal videos and 180 anomalous videos,
while the testing set contains the other 43 normal videos and 91 anomalous
videos. Table 2 shows the number of videos for each class in both subsets.

## Methodology

Figure 2: Flow diagram of the proposed methodology. Each video is split into
32 temporal segments. The videos are represented as a bag, and the segments as
instances within this bag. Features are then extracted from each segment by
the pre-trained C3D, I3D, or MFNet feature extraction networks. Next, these
features are provided with an anomaly score by a fully connected neural
network, resulting in one anomaly score for every instance in the bag. The
network uses a multiple instance learning ranking loss for training.

### A. Baseline Method

In this paper, we adopt an anomaly detection method inspired by [23] as a
baseline model, based upon the implementation of [9]. Figure 2 depicts a
diagram of the anomaly detection method. During the training process, input
videos are split into 32 non-overlapping segments of equal length. These
segments can be considered as instances in a bag, where the bag represents the
video as a whole. To describe these segments, feature vectors are extracted
from every 16-frame video clip within the instance, using a pre-trained
feature extractor network. To represent the instance, we take the average of
all 16-frame video clip features within that segment. Next, the instance-wise
feature vectors are supplied to a feed-forward network, which aims to predict
the likelihood that the input instance contains an anomaly, resulting in the
representation of each instance in the bag by the predicted anomaly score. A
multiple instance learning ranking loss ensures that one anomalous and one
normal video are used for each training step. The notations $\mathcal{V}_{a}$
and $\mathcal{V}_{n}$ represent an anomalous and a normal video, respectively,
while $\mathcal{A}_{a}^{i}$ and $\mathcal{A}_{n}^{i}$ represent the predicted
anomaly score of the i-th segment of an anomalous and a normal video,
respectively. The multiple-instance learning ranking loss function can then be
expressed by:

$\mathcal{L}_{\text{orig}}(\mathcal{V}_{a},\mathcal{V}_{n})=\max\ (\ 0\ ,\
1-\underset{i\in\mathcal{V}_{a}}{\max}f(\mathcal{A}_{a}^{i})+\underset{i\in\mathcal{V}_{n}}{\max}f(\mathcal{A}_{n}^{i})\
).$ (1)

This loss function forces the maximum anomaly score of the normal video
towards zero, while simultaneously increasing the maximum anomaly score of the
anomalous video towards unity. The assumption is made that the segment with
the highest anomaly score is the true anomaly.

Next to this multiple-instance learning ranking loss component, three more
components are added to the loss in order to ensure temporal smoothness,
sparsity and small model weights with scaling factor $\lambda_{1}$,
$\lambda_{2}$ and $\lambda_{3}$, respectively. These additions result in the
objective function given by

$\begin{split}\mathcal{L}_{\text{obj}}&=\mathcal{L}_{\text{orig}}(\mathcal{V}_{a},\mathcal{V}_{n})\
+\
\lambda_{1}\sum_{i}^{(n-1)}(f(\mathcal{A}_{a}^{i})-f(\mathcal{A}_{a}^{i+1}))^{2}\\\
&+\ \lambda_{2}\sum_{i}^{n}f(\mathcal{A}_{a}^{i})\ +\
\lambda_{3}\lVert\mathcal{W}\rVert_{F}\ ,\end{split}$ (2)

where $\mathcal{W}$ represents the model weights, and $n$ the number of
segments into which a video is split.

### B. Variations on the Baseline Method

We experiment with different feature extractors within our methodology and
forms of our loss functions, which both are discussed briefly below. The paper
that inspired our proposal applied the C3D network [25] only, whereas the
further investigated feature extractors are the I3D network [1], MFNet network
[3], and features concatenated from the aforementioned extractors.

C3D network: The C3D network is originally proposed in [25] and is one of the
first applications of a three-dimensional convolutional neural network
(3D-CNN) for supervised video action classification. We extract the output of
the first fully connected layer as our features. In this work, the C3D feature
extractor is pre-trained on the Sports1M dataset [8].

I3D network: The I3D network [1] is based on the Inception-V1 [7] detector. We
take the output of the average-pooling layer as our computed features,
resulting in a 1024-dimensional feature vector. Here, the I3D network is pre-
trained on two different datasets, the Charades dataset [20] and the Kinetics
dataset [1]. These feature extraction backbones are referred to as
I3D-charades and I3D-kinetics, respectively, throughout the paper.

MFNet network: The MFNet network [3] is used to extract features from the
input videos. In literature, this network is not yet applied for the purpose
of anomaly detection in videos. The MFNet network achieves slightly better
performance than I3D on action-recognition datasets, while at the same time,
it requires up to ten times fewer computations according to [3]. The MFNet
feature extraction backbone is pre-trained on the UCF-101 dataset [22]. The
MFNet features are represented by 6,144-dimensional vectors.

Concatenated features: Finally, we concatenate all the extracted features from
the C3D, I3D-charades, I3D-kinetics and MFNet networks together, of which we
construct a 12,288-dimensional feature vector. The anomaly detection model has
access to a wider range of information, thereby improving anomaly detection
performance with the help of these concatenated features. The downside of this
approach is the increase in computational cost to execute all feature
extraction networks.

In our method, the loss is based only on the maximum obtained anomaly score of
any segment in a video, both for normal and anomalous videos. For an anomalous
video, this makes sense because it could be possible that such a video only
contains one anomalous segment. However, all segments should ideally have an
anomaly score of zero for normal videos. Hence, we experiment with a loss
function that takes the mean predicted anomaly score into account, as opposed
to only the maximum. This loss is from now on referred to as the mean normal
loss and described formally below. This change allows the model to learn from
all normal segments at every training iteration, so that the mean normal loss
is specified by

$\mathcal{L}_{\text{mean-nl}}(\mathcal{V}_{a},\mathcal{V}_{n})=\max\ (\ 0\ ,\
1-\underset{i\in\mathcal{V}_{a}}{\max}f(\mathcal{A}_{a}^{i})+\underset{i\in\mathcal{V}_{n}}{\text{mean}}f(\mathcal{A}_{n}^{i})\
).$ (3)

Finally, we apply different optimizers in order to compare their effects on
the model performance. The baseline paper [23], uses the Adadelta optimizer,
while we also apply the Adam optimizer.

## Experiments

In this section, we perform experiments with our anomaly detection method
described in the Methodology section on the UCF-Crime dataset and the
generated Throwing-Action dataset to improve the anomaly detection
performance. The primary metric used to compare anomaly detection performance
between experiments is the area under the Receiver Operating Characteristic
(ROC) curve. This metric is commonly used to evaluate the performance of
anomaly detection methods and it gives insight into the achieved ratio between
the true-positive rate and false-positive rate for the full range of anomaly
thresholds.

Figure 3: Optimal ROC curves obtained on the testing set of the Throwing-
Action dataset when the anomaly detection model is trained with the Adadelta
and Adam optimizers.

### A. Comparison of Adadelta and Adam Optimizers

Our first contribution is determining the appropriate optimizer for the
training phase of all experimentation models. We train an anomaly detection
model on the Throwing-Action training dataset for 100,000 iterations, using
the Adadelta optimizer with a learning rate of 0.01, similarly to [23] and
using the Adam optimizer with a learning rate of 0.0005. Figure 3 depicts the
optimal ROC curves for each model.

Figure 4: Training loss curves of the anomaly detection model on the Throwing-
Action dataset for Adadelta and Adam optimizers, showing the mean loss of
every batch during training.

As shown in Figure 3, Adam outperforms Adadelta by a significant margin. This
difference indicates that the Adadelta training process has not reached an
optimum after 100,000 iterations. Figure 4 shows the batch loss during
training for both the Adadelta and Adam optimizers. From this graph, it can be
observed that the learning process is significantly slower for the Adadelta
optimizer. Therefore, the Adam optimizer is found more suitable to train
anomaly detection models. Since our anomaly detection model trained with the
Adam optimizer performs better and has a faster learning process, all models
are from now on trained using the Adam optimizer with a learning rate of
0.0005.

### B. Video Augmentation

Next, several approaches for data augmentation are explored to improve
performance. Augmentation methods are applied to the videos of the Throwing-
Action dataset to diversify the training data, which helps the model in
generalizing to new cases. Furthermore, test-time augmentation (TTA) is
explored for augmentation as well.

|  | No
---
Augment.
Augment. |  | Test Time
---
Augment.
C3D | 75.04 | 76.23 | 75.55
I3D-charades | 78.71 | 80.83 | 83.15
I3D-kinetics | 80.41 | 82.84 | 84.32
MFNet | 86.10 | 83.63 | 83.89
Concatenated | 85.29 | 85.58 | 85.52
Table 3: Table 3. Maximum area under the ROC curve achieved on the Throwing-
Action dataset for all feature extraction networks, when applying different
augmentation methods (best scores in bold). Figure 5: Visual examples of each
type of image augmentation applied to the Throwing-Action dataset. From left
to right and top to bottom: original, (no augmentation), salt and pepper
noise, inverted color, horizontal flip, independently scaled color channels
and random shearing.

#### 1) Training set augmentation

We have applied five augmentation methods to the original videos. The
augmentation methods used are salt-and-pepper noise, where in total 3% of all
sub-pixels are affected; inverting colors; horizontal flipping; independently
scaling the color channels by a factor between 0.8 and 1.2; and finally,
applying shear transformations. Visual examples of each augmentation output
are illustrated in Figure 5.

An anomaly detection model is trained on both the original Throwing-Action
dataset and the augmented Throwing-Action dataset for each feature extraction
network. Table 3 shows the largest area under the ROC curve obtained on the
test set of the Throwing-Action dataset for all feature extractors. From this
table, we can conjugate that the choice of the feature extraction has a
significant impact on the quality of the resulting model. The C3D feature
extraction network performs worst, while MFNet and the concatenated features
perform best. Training with the concatenated features does not improve the
performance of any individual feature extractor. The MFNet features contain
all necessary information for detecting the anomalies, while the other feature
extractors effectively only manage to extract a subset of this information.
This is visible because MFNet network obtains the highest score, while the
other ones and even the concatenated network score lower. Table 3 indicates
that training on augmented data improves the obtained results for all feature
extractors, except for MFNet. We obtain the best results for the MFNet feature
extractor without augmentation while for concatenated features augmentation is
needed. However, due to the significantly increased computational cost of the
concatenated feature extractor compared to the MFNet feature extractor, the
final model uses MFNet without data augmentation.

#### 2) Test time augmentation (TTA)

Another technique that can improve the performance of the anomaly detection
model is test time augmentation (TTA). The videos in the test set are
augmented using the same augmentation methods as used for the training set,
while predictions of the anomaly detection model are averaged over all
versions of the same video. Table 3 shows the maximum area under the ROC
curves when training the anomaly detection model on the augmented Throwing-
Action dataset and testing with TTA. TTA further improves the results for both
versions of the I3D feature extractors, but does not manage to improve results
for other feature extractors. Furthermore, TTA requires augmented test data
which makes the model more expensive at test time.

In conclusion, since the optimal area under the ROC curve is obtained by a
model trained without any augmentation and training with augmentation is more
computationally expensive, we have decided to leave out data augmentation in
the remainder of this paper.

### C. Experiments on UCF-Crime+Throwing Dataset

In addition to anomaly detection performance on the newly generated Throwing-
Action dataset, we are interested in combining the new Throwing-Action dataset
with the publicly available UCF-Crime [23] anomaly dataset. Therefore, we
first evaluate the performance achieved on the UCF-Crime dataset for all
feature extractors.

Table 4 shows the best maximum area under the ROC curve on the UCF-Crime
dataset for all feature extraction backbones. It indicates that the
performance for the C3D feature extraction is significantly lower than other
feature extractors. Another observation from Table 4 is that concatenated
features outperform any individual feature extraction backbone. For the UCF-
Crime dataset, the different feature extractors provide different sets of
information about the video, and concatenating these allows the detector model
to consider more information. Furthermore, comparing the performance on the
UCF-Crime dataset with the performance on the Throwing-Action dataset shown in
Table 3 reveals that for each feature extraction network the performance on
the UCF-Crime dataset is lower, leading to the conclusion that the UCF-Crime
dataset is overall a more difficult dataset.

| Exp. 1 | Exp. 2 | Exp. 3 | Exp. 4
---|---|---|---|---
C3D | 70.30 | 69.80 | 67.68 | 70.66
I3D-charades | 78.36 | 77.95 | 79.80 | 77.64
I3D-kinetics | 78.47 | 78.34 | 80.25 | 78.01
MFNet | 76.76 | 72.12 | 75.19 | 71.50
Concatenated | 79.84 | 79.16 | 81.08 | 78.86
| Concatenated
---
Mean normal loss
- | 80.13 | 78.59 | 80.31
Table 4: Table 4. Maximum area under the ROC curve achieved for different
experiments. Exp 1: model trained and evaluated on UCF-Crime dataset. Exp 2, 3
and 4: model trained on UCF-Crime+Throwing dataset, evaluated on UCF-
Crime+Throwing, Throwing-Action and UCF-Crime datasets, respectively.

Next, we combine the UCF-Crime dataset with our Throwing-Action dataset. This
new dataset is from now on referred to as UCF-Crime+Throwing. In order to
compare the performance, an anomaly detection model is trained on the training
subset of the UCF-Crime+Throwing dataset for each feature extraction backbone
and evaluated on the UCF-Crime+Throwing, the Throwing-Action, and the UCF-
Crime testing sets. Table 4 shows the maximum area under the ROC curve
obtained on each test set for every feature extraction backbone. The results
indicate that the performance on the UCF-Crime+Throwing dataset is generally
similar to the performance on only the UCF-Crime dataset. The results show
that it is possible to add throwing anomaly detection capabilities at only a
small cost in the detection performance of other anomalies. Therefore, it is
viable to integrate throwing anomaly detection into general anomaly detection
systems.

The final experiment is concerned with the proposed mean normal loss function.
Since this loss enables the model to learn from all normal segments at every
training iteration, changing the loss function allows the model to better
recognize normal sections of a video, which decreases the false positive rate
and increases the area under the ROC curve. Table 4 summarizes the performance
for this modified loss function when using concatenated features and training
on the UCF-Crime+Throwing dataset. This model achieves the highest overall
performance on the UCF-Crime+Throwing dataset, but at the cost of decreased
performance on the Throwing-Action testing set.

### D. Qualitative results

Figure 6: Qualitative results of the anomaly detection method on testing
videos from the Throwing-Action dataset. Red regions show ground-truth
anomalous regions, while the blue curve depicts the predicted anomaly score as
a function of the frame number. From left to right and from top to bottom, the
test videos cover anomaly classes: (a) bicycle safe, (c) pedestrian safe, (e)
car safe, (g) successful case normal, (b) bicycle dangerous, (d) pedestrian
dangerous, (f) car dangerous. Subfigure (h) shows a failure case for the
normal video class.

This section presents qualitative results of the proposed anomaly detection
method. Figure 6 shows the output of the feed-forward network as a function of
time, expressed by the frame number of several testing videos of the Throwing-
Action dataset. This means that the $y$-axis shows the likelihood that a
segment is anomalous, according to our anomaly detection method, and the
$x$-axis shows the progression number of processed video frames. Furthermore,
the ground-truth anomalous regions within each video are given as red colored
areas. In Figure 6 (a)-(d), it can be observed that the performance is quite
good for pedestrian and bicycle-related anomalies. However, several segments
have a high predicted anomaly score, while being outside of the ground-truth
anomalous areas. This problem occurs most often between two distinct anomalies
or just after one anomaly. These segments contain relatively large person-arm
motions after completing a throw, which may seem similar to a throwing action.

In Figure 6 (e)(f) show predictions for car-related throwing anomalies, which
are more difficult to identify for our anomaly detection method. Anomalous
sections sometimes obtain a predicted anomaly score of zero. This is caused by
the fact that throwing anomalies from cars are more challenging to recognize,
as there could be no person-arm motions. Furthermore, the second peak with a
predicted anomaly score above 0.5 in subfigure (f) corresponds to the moment
that the car suddenly accelerates in the video. An explanation for this high
score is that the normal training videos do not contain sufficient video
material of accelerating cars, making this acceleration appear anomalous.

Finally, subfigures (g)(h) show predicted anomaly scores of two different
normal videos. As can be noticed, the example in (g) is close to the ideal
performance for a normal video, with a low predicted anomaly score in every
segment. However, subfigure (h) indicates two false alarms, which are most
likely caused by the presence of a fire truck in the footage of this normal
video, because they rarely occur in any normal training video.

| Original loss | Proposed loss
---|---|---
False alarm rate | 0.5667 | 0.4696
Table 5: Table 5. False alarm rate in percentage of normal video segments
where the predicted anomaly score is more than 0.5 on the combined UCF-
Crime+Throwing dataset.

Overall, the experiments show that the best results for the combined UCF-
Crime+Throwing dataset are achieved when training the anomaly detection model
with the Adam optimizer on concatenated features, and with the proposed mean
normal loss function using the mean anomaly score of normal videos. The UCF-
Crime+Throwing dataset contains a wider range of anomalies, compared to the
proposed Throwing-Action dataset. This variation explains why the concatenated
features increase the performance for the combined dataset, while they do not
provide an improvement for the Throwing-Action dataset. From the qualitative
analysis, we conclude that our throwing anomaly detection model works well for
pedestrian and bicycle-related anomalies. However, performance for car-type
anomalies can be further improved by involving more data and situations
appearing with cars.

## False Alarm Analysis

This section separately analyzes the performance of the proposed anomaly
detection method in terms of false alarm rate because it is an important
indicator for the correct focus on safety.

Figure 7: False alarm rate on normal testing data for anomaly detection models
trained using the original loss function and the mean normal loss function.
Both models are trained on the combined UCF-Crime+Throwing dataset and false
alarms are categorized as a predicted anomaly score of more than 0.5 on a
normal video segment.

A false alarm rate of even a few percent can render an anomaly detection
algorithm useless, since by definition most of the data encountered by an
anomaly detection method is normal. Therefore, the false alarm rate is an
important metric for industrial applications. We compare the false alarm rates
on the normal testing data of the combined UCF-Crime+Throwing dataset for
models trained on concatenated features with the original loss function and
the mean normal loss function, as shown in Figure 7. A false alarm is defined
as a predicted anomaly score above 0.5 for a segment of a normal video. This
figure shows that changing the loss function appears to positively affect the
false alarm rate, reducing it significantly. With the proposed loss function,
the model learns to recognize normal data faster, which results in an initial
false alarm rate of zero. As the training progresses, the model learns to
recognize anomalies, which sometimes introduce erroneous predictions.

## Conclusion

We have introduced a novel dataset consisting of normal behaviors and throwing
actions performed by car drivers, pedestrians, and bicyclists, to support the
development of throwing anomaly detection algorithms. Additionally, we have
compared the performance of different feature extraction networks, which are
C3D, I3D-charades, I3D-kinetics and MFNet, within our anomaly detection method
on the Throwing-Action dataset, the UCF-Crime dataset, and the combined
dataset. Furthermore, we have found that using the Adam optimizer for training
anomaly detection algorithms leads to improved results and shorter training
times over the Adadelta optimizer. Finally, using the proposed mean normal
loss function, we have significantly reduced the false alarm rate of the
anomaly detection method, thereby improving the area under the ROC curve.
Based on the experimental results, we have successfully improved the
performance on the combined dataset to an area under the ROC curve of 80.13 by
means of the proposed mean normal loss function, Adam optimizer and
concatenated features.

## Acknowledgments

This work is supported by the European ITEA project SMART on intelligent
traffic flow systems and Efficient Deep Learning (EDL) RMR project.

## References

  * [1] J. Carreira and A. Zisserman, “Quo Vadis, Action Recognition? A New Model and the Kinetics Dataset,” in _CVPR_ , 2017, pp. 6299–6308.
  * [2] Y. Chang, Z. Tu, W. Xie, and J. Yuan, “Clustering Driven Deep Autoencoder for Video Anomaly Detection,” in _Computer Vision – ECCV 2020. ECCV 2020\. Lecture Notes in Computer Science_ , vol. 12360 LNCS. Springer, Cham, 8 2020, pp. 329–345. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-030-58555-6_20
  * [3] Y. Chen, Y. Kalantidis, J. Li, S. Yan, and J. Feng, “Multi-Fiber Networks for Video Recognition,” in _ECCV_ , 2018, pp. 352–367.
  * [4] R. Csordás, L. Havasi, and T. Szirányi, “Detecting objects thrown over fence in outdoor scenes,” in _Proc. Int. Conf. Comput. Vision Theory Applicat. (VISAPP)_ , Berlin, 2015, pp. 593–599. [Online]. Available: http://eprints.sztaki.hu/8636/1/Csordas_593_2856278_ny.pdf
  * [5] Z. Dai and Z. Zheng, “A YOLOv3-Based Learning Strategy for Vehicle-Thrown-Waste Identification,” in _ICIC 2021: Intelligent Computing Theories and Application_. Springer, Cham, 8 2021, pp. 305–315. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-030-84529-2_26
  * [6] K. Deepak, S. Chandrakala, and C. K. Mohan, “Residual spatiotemporal autoencoder for unsupervised video anomaly detection,” _Signal, Image and Video Processing_ , vol. 15, no. 1, pp. 215–222, 7 2020. [Online]. Available: https://link.springer.com/article/10.1007/s11760-020-01740-1
  * [7] S. Ioffe and C. Szegedy, “Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift,” in _Proceedings of the 32nd International Conference on Machine Learning, PMLR_ , 2015, pp. 448–456.
  * [8] A. Karpathy, G. Toderici, S. Shetty, T. Leung, R. Sukthankar, and F. F. Li, “Large-scale video classification with convolutional neural networks,” in _Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition_. IEEE Computer Society, 9 2014, pp. 1725–1732. [Online]. Available: https://paperswithcode.com/paper/large-scale-video-classification-with-1
  * [9] E. Kosman, “Pytorch implementation of Real-World Anomaly Detection in Surveillance Videos.” [Online]. Available: https://github.com/ekosman/AnomalyDetectionCVPR2018-Pytorch
  * [10] Z. Li, Y. Li, and Z. Gao, “Spatiotemporal Representation Learning for Video Anomaly Detection,” _IEEE Access_ , vol. 8, pp. 25 531–25 542, 2020.
  * [11] K. Liu and H. Ma, “Exploring background-bias for anomaly detection in surveillance videos,” in _MM 2019 - Proceedings of the 27th ACM International Conference on Multimedia_. Association for Computing Machinery, Inc, 10 2019, pp. 1490–1499. [Online]. Available: https://doi.org/10.1145/3343031.3350998
  * [12] H. Lv, C. Zhou, Z. Cui, C. Xu, Y. Li, and J. Yang, “Localizing Anomalies from Weakly-Labeled Videos,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 4505–4515, 2021.
  * [13] N. Nasaruddin, K. Muchtar, A. Afdhal, and A. P. J. Dwiyantoro, “Deep anomaly detection through visual attention in surveillance videos,” _Journal of Big Data_ , vol. 7, no. 1, pp. 1–17, 10 2020. [Online]. Available: https://journalofbigdata.springeropen.com/articles/10.1186/s40537-020-00365-y
  * [14] R. Nawaratne, D. Alahakoon, D. De Silva, and X. Yu, “Spatiotemporal anomaly detection using deep learning for real-time video surveillance,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 1, pp. 393–402, 1 2020\.
  * [15] T.-N. Nguyen and J. Meunier, “Anomaly Detection in Video Sequence With Appearance-Motion Correspondence,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2019_ , 2019, pp. 1273–1283.
  * [16] S. Petrocchi, G. Giorgi, and M. G. Cimino, “A Real-Time Deep Learning Approach for Real-World Video Anomaly Detection,” in _ARES 2021: The 16th International Conference on Availability, Reliability and Security_. Association for Computing Machinery, 8 2021, pp. 1–9.
  * [17] J. Redmon and A. Farhadi, “YOLOv3: An Incremental Improvement,” _arXiv_ , 4 2018. [Online]. Available: https://arxiv.org/abs/1804.02767v1
  * [18] E. Ribnick, S. Atev, N. Papanikolopoulos, O. Masoud, and R. Voyles, “Detection of thrown objects in indoor and outdoor scenes,” in _IEEE International Conference on Intelligent Robots and Systems_ , 2007, pp. 979–984.
  * [19] M. Sabokrou, M. Fayyaz, M. Fathy, Z. Moayed, and R. Klette, “Deep-anomaly: Fully convolutional neural network for fast anomaly detection in crowded scenes,” _Computer Vision and Image Understanding_ , vol. 172, pp. 88–97, 7 2018.
  * [20] G. A. Sigurdsson, G. Varol, X. Wang, A. Farhadi, I. Laptev, and A. Gupta, “Hollywood in Homes: Crowdsourcing Data Collection for Activity Understanding,” in _ECCV_ , vol. 9905 LNCS. Springer, Cham, 2016, pp. 510–526. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-319-46448-0_31
  * [21] P. Singh and V. Pankajakshan, “A Deep Learning Based Technique for Anomaly Detection in Surveillance Videos,” in _2018 24th National Conference on Communications, NCC 2018_. Institute of Electrical and Electronics Engineers Inc., 1 2019.
  * [22] K. Soomro, A. R. Zamir, and M. Shah, “UCF101: A dataset of 101 human actions classes from videos in the wild,” _CoRR_ , vol. abs/1212.0402, 2012\. [Online]. Available: http://arxiv.org/abs/1212.0402
  * [23] W. Sultani, C. Chen, and M. Shah, “Real-World Anomaly Detection in Surveillance Videos,” in _Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 6479–6488. [Online]. Available: http://crcv.ucf.edu/projects/real-world/
  * [24] Y. Tian, G. Pang, Y. Chen, R. Singh, J. W. Verjans, and G. Carneiro, “Weakly-supervised Video Anomaly Detection with Robust Temporal Feature Magnitude Learning,” in _International Conference for Computer Vision_ , 2021.
  * [25] D. Tran, L. Bourdev, R. Fergus, L. Torresani, and M. Paluri, “Learning Spatiotemporal Features With 3D Convolutional Networks,” in _ICCV_ , 2015, pp. 4489–4497.
  * [26] W. Ullah, A. Ullah, I. U. Haq, K. Muhammad, M. Sajjad, and S. W. Baik, “CNN features with bi-directional LSTM for real-time anomaly detection in surveillance networks,” _Multimedia Tools and Applications_ , vol. 80, no. 11, pp. 16 979–16 995, 8 2020. [Online]. Available: https://link.springer.com/article/10.1007/s11042-020-09406-3
  * [27] J. T. Zhou, J. Du, H. Zhu, X. Peng, Y. Liu, and R. S. M. Goh, “AnomalyNet: An Anomaly Detection Network for Video Surveillance,” _IEEE Transactions on Information Forensics and Security_ , vol. 14, no. 10, pp. 2537–2550, 10 2019\.

## Author Biography

Ivo Kersten obtained a B.S. degree in electrical engineering from the
Eindhoven University of Technology in 2020, and a M.S. degree in electrical
engineering with a specialization in artificial intelligence engineering
systems from the same university in 2022. For his thesis work he conducted
research on the detection of object throwing behavior in surveillance videos.

Erkut Akdag received the B.S. and M.S. degrees in electrical and electronics
engineering from Middle East Technical University, Ankara, Turkey, in 2012 and
2015, respectively. He is currently working toward the Ph.D. degree at the
Video Coding and Architectures Group, Eindhoven University of Technology,
Eindhoven, The Netherlands. His research interests include critical vehicle
detection, anomaly detection and computer vision for surveillance.

Egor Bondarev obtained his PhD degree in the Computer Science Department at
TU/e, in research on performance predictions of real-time component-based
systems on multiprocessor architectures. He is an Assistant Professor at the
Video Coding and Architectures group, TU/e, focusing on sensor fusion, smart
surveillance and 3D reconstruction. He has written and co-authored over 50
publications on real-time computer vision and image/3D processing algorithms.
He is involved in large international surveillance projects like APPS and PS-
CRIMSON.

Peter H.N. de With is Full Professor of the Video Coding and Architectures
group in the Department of Electrical Engineering at Eindhoven University of
Technology. He worked at various companies and was active as senior system
architect, VP video technology, and business consultant. He is an IEEE Fellow
and member of the Royal Holland Society of Academic Sciences and Humanities,
has (co-)authored over 600 papers on video coding, analysis, architectures,
and 3D processing and has received multiple papers awards. He has served as a
program committee member of various IEEE conferences and holds some 30
patents.


# Causal Inference Based Single-branch Ensemble Trees For Uplift Modeling

Fanglan Zheng, Menghan Wang, Kun Li, Jiang Tian, Xiaojia Xiang

###### Abstract

In this manuscript (ms), we propose causal inference based single-branch
ensemble trees for uplift modeling, namely CIET. Different from standard
classification methods for predictive probability modeling, CIET aims to
achieve the change in the predictive probability of outcome caused by an
action or a treatment. According to our CIET, two partition criteria are
specifically designed to maximize the difference in outcome distribution
between the treatment and control groups. Next, a novel single-branch tree is
built by taking a top-down node partition approach, and the remaining samples
are censored since they are not covered by the upper node partition logic.
Repeating the tree-building process on the censored data, single-branch
ensemble trees with a set of inference rules are thus formed. Moreover, CIET
is experimentally demonstrated to outperform previous approaches for uplift
modeling in terms of both area under uplift curve (AUUC) and Qini coefficient
significantly. At present, CIET has already been applied to online personal
loans in a national financial holdings group in China. CIET will also be of
use to analysts applying machine learning techniques to causal inference in
broader business domains such as web advertising, medicine and economics.

## Introduction

Uplift modeling involves a set of methods for estimating the expected causal
impact of taking an action or a treatment at an individual or subgroup level,
which could lead to an increase in their conversion probability (Zhao and
Harinen 2019). Typically for financial services and commercial companies
looking to provide additional value-added services and products to their
customers, marketers may be interested in evaluating the effectiveness of
numerous marketing techniques, such as sending promotional coupons. With the
change in customer conversion possibilities, marketers are able to efficiently
target prospects. More than marketing campaigns, uplift modeling can be
applied to a variety of real-world scenarios related to personalization, such
as online advertising, insurance, or healthcare, where patients with varying
levels of response to a new drug are identified, including the discovery of
adverse effects on specific subgroups (Jaskowski and Jaroszewicz 2012).

In essence, uplift modeling is a problem that combines causal inference and
machine learning. For the former, it is mutually exclusive to estimate the
change between two outcomes for the same individual. To overcome this
counterfactual problem, samples are randomly assigned to a treatment group
(receiving online advertisement or marketing campaign) and a control group
(not receiving online advertisement nor marketing campaign). For the latter,
the task is to train a model that predicts the difference in the probability
of belonging to a given class on the two groups. At present, two major
categories of estimation techniques have been proposed in the literature,
namely meta-learners and tailored methods (Zhang, Li, and Liu 2022). The first
includes the Two-Model approach (Radcliffe 2007), the X-learner (Künzel et al.
2017) and the transformed outcome methods (Athey and Imbens 2015) which extend
classical machine learning techniques. The second refers to direct uplift
modeling such as uplift trees (Rzepakowski and Jaroszewicz 2010) and various
neural network based methods (Louizos et al. 2017; Yoon, Jordon, and van der
Schaar 2018), which modify the existing machine learning algorithms to
estimate treatment effects. Also, uplift trees can be extended to more general
ensemble tree models, such as causal forests (Wager and Athey 2018; Athey,
Tibshirani, and Wager 2019), at the cost of losing true interpretability.

In order to take advantage of decision trees and the ensemble approach, we
propose causal inference based single-branch ensemble trees for uplift
modeling (CIET) with two completely different partition criteria that directly
maximizes the difference between outcome distributions of the treatment and
control groups. When building a single-branch tree, we employ lift gain and
lift gain ratio as loss functions or partition criteria for node splitting in
a recursive manner. Since our proposed splitting criteria are highly related
to the incremental impact, the performance of CIET is thus expected to be
reflected in the uplift estimation. Meanwhile, the splitting logic of all
nodes along the path from root to leaf is combined to form a single rule to
ensure the interpretability of CIET. Moreover, the dataset not covered by the
rule is then censored and the above tree-building process continue to repeat
on the censored data. Due to this divide and conquer learning strategy, the
dependencies between the formed rules can be effectively avoided. It leads to
the formation of single-branch ensemble trees and a set of decorrelated
inference rules.

Note that our CIET is essentially different from decision trees for uplift
modeling and causal forests. There are three major differences: (1) single-
branch tree $vs$ standard binary tree; (2) lift gain and its ratio as loss
function or splitting criterion $vs$ Kullback-Leibler divergence and squared
Euclidean distance; and (3) decorrelated inference rules $vs$ correlated
inference rules or even no inference rules. It is demonstrated through
empirical experiments that CIET can achieve better uplift estimation compared
with the existing models. Extensive experimental results on synthetic data and
the public credit card data show the success of CIET in uplift modeling. We
also train an ensemble model and evaluate its performance on a large real-
world online loan application dataset from a national financial holdings group
in China. As expected, the corresponding results show a significant
improvement in the evaluation metrics in terms of both AUUC and Qini
coefficient.

The rest of this ms is organized as follows. First, causal inference based
single-branch ensemble trees for uplift modeling is introduced. Next, full
details of our experimental results on synthetic data, credit card data and
real-world online loan application data are given. It is demonstrated that
CIET performs well in estimating causal effects compared to decision trees for
uplift modeling. Finally, conclusions are presented.

## Causal Inference Based Single-Branch Ensemble Trees (CIET) for Uplift
Modeling

This section consists of three parts. We first present two splitting criteria,
single-branch ensemble approach and pruning strategy specially designed for
the uplift estimation problem. Evaluation metrics for uplift modeling are then
discoursed. Three key algorithms of CIET are further described in detail.

### Splitting Criteria, Single-Branch Ensemble Method and Pruning Strategy

Two distinguishing characteristics of CIET are splitting criteria for tree
generation and the single-branch ensemble method, respectively.

As for splitting criteria in estimating uplift, it is motivated by our
expectation to achieve the maximum difference between the distributions of the
treatment and control groups. Given a class-labeled dataset with $N$ samples,
$N^{T}$ and $N^{C}$ are sample size of the treatment and control groups
(recall that $N=N^{T}+N^{C}$, $T$ and $C$ represent the treatment and control
groups). Formally, in the case of a balanced randomized experiment, the
estimator of the difference in sample average outcomes between the two groups
is given by:

$\displaystyle\tau=(P^{T}-P^{C})(N^{T}+N^{C})$ (1)

where $P^{T}$ and $P^{C}$ are the probability distribution of the outcome for
the two groups. Motivated by Eq. (1), the divergence measures for uplift
modeling we propose are lift gain and its ratio, namely LG and LGR for short.
The corresponding mathematical forms of LG and LGR can be thus expressed as

$\displaystyle LG$
$\displaystyle=(P_{R}^{T}-P_{R}^{C})N_{R}-\tau_{0}=\tau_{R}-\tau_{0}$ (2)
$\displaystyle LGR$
$\displaystyle=\frac{(P_{R}^{T}-P_{R}^{C})}{(P_{0}^{T}-P_{0}^{C})}\propto(P_{R}^{T}-P_{R}^{C})=\frac{\tau_{R}}{N_{R}}$
(3)

where $P_{0}^{T}$ and $P_{0}^{C}$ are the initial probability distribution of
the outcome for the two groups, $\tau_{0}=(P_{0}^{T}-P_{0}^{C})N_{R}$. And
$N_{R}$ and $Y_{R}$ for a node logic $R$ represent coverage and correction
classification, while $P_{R}^{T}$ and $P_{R}^{C}$ are the corresponding
probability distribution of the outcome for both groups, respectively.
Evidently, both Eq. (2) and Eq. (3) represent the estimator for uplift, which
are proposed as two criteria in our ms. Compared to the standard binary tree
with left and right branches, only one branch is created after each node
splitting in this ms. It is characterized by the fact that both LG and LGR are
calculated using the single-branch observations that present following a node
split. Accordingly, subscript $k$ indicating binary branches doesn’t exist in
the above equation. Furthermore, the second term of LG makes every node
partition better than randomization, while LGR has the identical advantages to
information gain ratio.

The proposed splitting criterion for a test attribute A is then defined for
any divergence measure $D$ as

$\Delta=D(P^{T}(Y):P^{C}(Y)|A)-D(P^{T}(Y):P^{C}(Y))$ (4)

where $D(P^{T}(Y):P^{C}(Y)|A)$ is the conditional divergence measure.
Apparently, $\Delta$ is the incremental gain in divergence following a node
splitting. Substituting for $D$ the $LG$ and $LGR$, we obtain our proposed
splitting criteria $\Delta_{LG}$ and $\Delta_{LGR}$. The intuition behind
these splitting criteria is as follows: we want to build a single-branch tree
such that the distribution divergence between the treatment and control groups
before and after splitting an attribute differ as much as possible. Thus, an
attribute with the highest $\Delta$ is chosen as the best splitting one. In
order to achieve it, we need to calculate and find the best splitting point
for each attribute. In particular, an attribute is sorted in descending order
by value when it is numerical. For categorical attributes, some encoding
methods are adopted for numerical type conversion. The average of each pair of
adjacent values in an attribute with $n$ value, forms $n-1$ splitting points
or values. As for this attribute, the point of the highest $\Delta$ can be
seen as the best partition one. Furthermore, the best splitting attribute with
the highest $\Delta$ can be achieved by traversing all attributes. As for the
best splitting attribute, the instances are thus divided into two subsets at
the best splitting point. One feeds into a single-branch node, while the other
is censored. Note that the top–down, recursive partition will continue unless
there is no attribute that explains the incremental estimation with
statistical significance. Also, histogram-based method can be employed to
select the best splitting for each feature, which can reduce the time
complexity effectively.

Due to noise and outliers in the dataset, a node may merely represent these
abnormal points, resulting in model overfitting. Pruning can often effectively
deal with this problem. That is, using statistics to cut off unreliable
branches. Since none of the pruning methods is essentially better than others,
we use a relatively simple pre-pruning strategy. If $\Delta$ gain is less than
a certain threshold, node partition would stop. Thus, a smaller and simpler
tree is constructed after pruning. Naturally, decision-makers prefer less
complex inference rules, since they are considered to be more comprehensible
and robust from business perspective.

### Evaluation Metrics for Uplift Modeling

As noted above, it is impossible to observe both the control and treatment
outcomes for an individual, which makes it difficult to find measure of loss
for each observation. It leads that uplift evaluation should differ
drastically from the traditional machine learning model evaluation. That is,
improving the predictive accuracy of the outcome does not necessarily indicate
that the models will have better performance in identifying targets with
higher uplift. In practice, most of the uplift literature resort to aggregated
measures such as uplift bins or curves. Two key metrics involved are area
under uplift curve (AUUC) and Qini coefficient (Gutierrez and Gérardy 2016),
respectively. In order to define AUUC, binned uplift predictions are sorted
from largest to smallest. For each $t$, the cumulative sum of the observations
statistic is formulated as below,

$f(t)=(\frac{Y_{t}^{T}}{N_{t}^{T}}-\frac{Y_{t}^{C}}{N_{t}^{C}})(N_{t}^{T}+N_{t}^{C})$
(5)

where the $t$ subscript implies that the quantity is calculated on the first
or top $t$ observations. The higher this value, the better the uplift model.
The continuity of the uplift curves makes it possible to calculate AUUC, i.e.
area under the real uplift curve, which can be used to evaluate and compare
different models. As for Qini coefficient, it represents a natural
generalization of Gini coefficient to uplift modeling. Qini curve is
introduced with the following equation,

$g(t)={Y_{t}^{T}}-\frac{Y_{t}^{C}N_{t}^{T}}{N_{t}^{C}}$ (6)

There is an obvious parallelism with the uplift curve since
$f(t)=g(t)(N_{t}^{T}+N_{t}^{C})/N_{t}^{T}$. The difference between the area
under the actual Qini curve and that under the diagonal corresponding to
random targeting can be obtained. It is further normalized by the area between
the random and the optimal targeting curves, which is defined as Qini
coefficient.

### Algorithm Modules

The following representation of three algorithms includes: selecting the best
split for each feature using the splitting criteria described above, learning
a top-down induced single-branch tree and forming ensemble trees with each
resulting tree progressively.

Algorithm 1 depicts how to find the best split of a single feature $F$ on a
given dataset $D[group\\_key,feature,$ $target]$ using a histogram-based
method with the proposed two splitting criteria. Gain_left and Gain_right are
the uplift gains for the child nodes after each node partition. If the maximum
value of Gain_left is greater than that of Gain_right, the right branch is
censored and vice versa. Thus, the best split with its corresponding splitting
logic, threshold and uplift gain is found, which is denoted by
Best$\\_$Direction, Best$\\_$Threshold and Best$\\_\Delta$. Besides, there are
several thresholds to be initialized before training a CIET model, including
minimum number of samples at a inner node $min\\_samples$, minimum recall
$min\\_recall$ and minimum uplift gain required for splitting $min\\_\Delta$.
The top-down process would continue only when the restrictions are satisfied.

Algorithm 1 Selecting the Best Split for One Feature

Input: D, the given class-labeled dataset, including the group key
(treatment/control);
Parameter: feature $F$, min$\\_$samples, min$\\_$recall, min$\\_\Delta$
Output: the best split that maximizes the lift gain or lift gain ratio on a
feature

1: Set Best$\\_$Value = 0, Best$\\_$Direction = ””, Best$\\_\Delta$ = 0,
Best$\\_$Threshold = None

2: calculate $Y^{T}$, $Y^{C}$, $N^{T}$, $N^{C}$ on D

3: For each feature value $v$ , calculate the values of $Y_{F\leq v}^{T}$,
$Y_{F\leq v}^{C}$, $N_{F\leq v}^{T}$, $N_{F\leq v}^{C}$, and then the
Gain_left($v$) and Gain_right($v$) with LG (2) or LGR (3).

4: set the Gain_left($v$) and Gain_right($v$) to their minimum value on the
$v$, whose split does not satisfy the restrictions on number of samples/recall
rate/divergence measure gain.

5: $v_{1}$ = argmax(Gain_left($v$)), $v_{2}$ = argmax(Gain_right($v$))

6: if max(Gain_left) $\geq$ max(Gain_right) then

7: Best$\\_$Value = max(Gain_left)

8: Best$\\_$Direction = ”$\leq$”

9: Best$\\_$Threshold = $v_{1}$

10: else

11: Best$\\_$Value = max(Gain_right)

12: Best$\\_$Direction = ”$>$”

13: Best$\\_$Threshold = $v_{2}$

14: end if

15: return Best$\\_$Value, Best$\\_$Direction, Best$\\_$Threshold

Algorithm 2 presents a typical algorithmic framework for top–down induction of
a single-branch uplift tree, which is built in a recursive manner using a
greedy depth-first strategy. The parameter $max\\_depth$ represents the depth
of the tree and $cost$ indicates the threshold of LG or LGR. As the tree grows
deep, more instances are censored since they are not covered by the node
partition logic of each layer. As a result, each child node subdivides the
original dataset hierarchically into a smaller subset until the stopping
criterion is satisfied. Tracing the splitting logics on the path from the root
to leaf nodes in the tree, an ”IF-THEN” inference rule is thus extracted.

Finally, adopting a divide-and-conquer strategy, the above tree-building
process is repeated on the censored samples to form ensemble trees, resulting
in the formation of a set of inference rules as shown in Algorithm 3.

Algorithm 2 Learning An ”IF-THEN” Uplift Rule of A Single-branch Tree

Input: D, the given class-labeled dataset, including the group key
(treatment/control);
Parameter: max$\\_$depth, cost, min$\\_$samples, min$\\_$recall,
min$\\_\Delta$
Output: an ”IF-THEN” uplift rule

1: Set Rule$\\_$Single = [], Max$\\_$Gain = 0.0

2: Set Add_Rule = True

3: while depth $\leq$ max$\\_$depth and Add_Rule do

4: if the treatment group or control group in D is empty then

5: break

6: end if

7: Set Keep = { }, Best$\\_$Split = { }

8: depth $\leftarrow$ depth + 1

9: Add_Rule = False

10: for feature in features do

11: Keep[feature] = Best_Split_for_One_Feature(D, feature, min$\\_$samples,
min$\\_$recall, min$\\_\Delta$) (Algorithm 1)

12: end for

13: for feature in Keep do

14: if feature’s best gain $>$ Max_Gain + cost then

15: Max$\\_$Gain = feature’s best gain

16: Add Keep[feature] to Best$\\_$Split

17: Add_Rule = True

18: else

19: continue

20: end if

21: end for

22: Add Best$\\_$Split to Rule$\\_$Single

23: D $\leftarrow$ D $\setminus$ { Samples covered by Rule$\\_$Single}

24: end while

25: return Rule$\\_$Single

Algorithm 3 Learning A Set of ”IF-THEN” Uplift Rules

Input: D, the given class-labeled dataset, including the group key
(treatment/control);
Parameter: max$\\_$depth, rule$\\_$count, cost, min$\\_$samples,
min$\\_$recall, min$\\_\Delta$
Output: a set of ”IF-THEN” uplift rules

1: Set Rule$\\_$Set = {}, number = 0

2: while number $\leq$ rule$\\_$count do

3: rule = Single$\\_$Uplift$\\_$Rule(D, cost, max$\\_$depth, min$\\_$samples,
min$\\_$recall, min$\\_\Delta$) (Algorithm 2)

4: Add rule to Rule$\\_$Set

5: D $\leftarrow$ D $\setminus$ dataset covered by rule

6: number $\leftarrow$ number + 1

7: end while

8: return Rule$\\_$Set

Figure 1: The uplift curves of four analyzed classifiers with four different
colors for the synthetic dataset, while the dashed line corresponding to
random targeting.

## Experiments

In this section, the effectiveness of our CIET is evaluated on synthetic and
real-world business datasets. Since CIET fundamentally stems from tree-based
approaches, we implement it and compare it with uplift decision trees based on
squared Euclidean distance and Kullback-Leibler divergence (Rzepakowski and
Jaroszewicz 2010), which are referred as baselines.

rule number | ”1” | ”2” | ”3”
---|---|---|---
node logic | x9$\\_$uplift $\leq$ 0.17 | x3$\\_$informative $>$ -1.04 | x6$\\_$informative $>$ 0.95
node logic | x10$\\_$uplift $\leq$ 2.59 | x1$\\_$informative $\leq$ 2.71 | x1$\\_$informative $\leq$ 1.58
node logic | null | x2$\\_$informative $\leq$ 1.28 | x9$\\_$uplift $\leq$ 2.09
$N_{before}$ | 3000 | 2210 | 675
$N_{before}^{T}$ | 1500 | 1117 | 348
$N_{before}^{C}$ | 1500 | 1093 | 327
$N_{rule}$ | 790 | 1535 | 180
$N_{rule}^{T}$ | 383 | 769 | 76
$N_{rule}^{C}$ | 407 | 766 | 104
net gain | 195.99 | 87.14 | 37.66
$recall_{treatment}$ | 36.62$\%$ | 70.42$\%$ | 42.11$\%$
$recall_{control}$ | 28.00$\%$ | 63.70$\%$ | 44.90$\%$
Table 1: A set of inference rules found by CIET and their corresponding
statistical indicators with $criterion\\_type=$”LG”, $rule\\_count=3$ and
$max\\_depth=3$.

### Experiments on Synthetic Data

Dataset We can test the methodology with numerical simulations. That is,
generating synthetic datasets with known causal and non-causal relationships
between the outcome, action (treatment/control) and some confounding
variables. More specifically, both the outcome and the action/treatment
variables are binary. A synthetic dataset is generated with the
$make\\_uplift\\_classification$ function in ”Causal ML” package, based on the
algorithm in (Guyon 2003). There are 3,000 instances for the treatment and
control groups, with response rates of 0.6 and 0.5, respectively. The input
consist of 11 features in three categories. 8 of them are used for base
classification, which are composed of 6 informative and 2 irrelevant
variables. 2 positive uplift variables are created to testify positive
treatment effect. The remaining one is a mix variable, which is defined as a
linear superposition of a randomly selected informative classification
variable and a randomly selected positive uplift variable.

Parameters and Results There are four hyper-parameters in CIET:
$criterion\\_type$, $max\\_depth$ and $rule\\_count$. $criterion\\_type$
includes two options, LG and LGR. More precisely, two main factors of business
complexity and difficulty in online deployment, determine parameter
assignment. Due to the requirement of model generalization and its
interpretability, $max\\_depth$ is set to 3. That is, the business logics of a
single inference rule are always less than or equal to 3. And, $rule\\_count$
is given a value of 3, indicating that a set of no more than three rules is
defined to model the causal effect of a treatment on the outcome. Meanwhile,
the default values for $min\\_samples$, $min\\_recall$, $cost$ and
$min\\_\Delta$ are 50, 0.1, 0.01 and 0, respectively.

dataset | KL | Euclid | LG | LGR
---|---|---|---|---
training | 0.187 | 0.189 | 0.239 | 0.235
test | 0.176 | 0.178 | 0.210 | 0.225
Table 2: Qini coefficients of four analyzed classifiers on the training and
test sets of the synthetic data.

The stratified sampling method is used to divide the synthetic dataset into
training and test sets in a ratio of fifty percent to fifty percent. Figure 1
shows the uplift curves of the four analyzed classifiers. The AUUC of CIET
with LG and LGR are 294 and 292 on the training set, which are significantly
greater than 266 and 265 for the decision trees for uplift modeling with KL
divergence and squared Euclidean distance. At the 36th percentile of the
population, the cumulative profit increase reach 303 and 354 for LG and LGR,
resulting in a growth rate of more than 18$\%$ and 37$\%$ compared to
baselines. Besides, AUUC shows little variation in the training and test
datasets, indicating that the stability of CIET is also excellent. According
to Table 2, Qini coefficients of CIET are also obviously greater, with an
increase of more than 24.5$\%$ and 17.8$\%$. Furthermore, all three rules are
determined by uplift and informative variables as expected, which can be seen
from Table 1.

### Experiments on Credit Card Data

Dataset We use the publicly available dataset $Credit$ $Approval$ from the UCI
repository as one of the real-world examples, which contains 690 credit card
applications. All the 15 attributes and the outcome are encoded as nonsense
symbols, where $A7\neq v$ is applied as the condition for dividing the dataset
into treatment and control groups. There are 291 and 399 observations in the
two groups with response rates of 0.47 and 0.42, respectively. Attributes with
more than 25$\%$ difference in distribution between the two groups should be
removed before any experiments are performed. This leads that 12 attributes
are left as input variables. For further preprocessing, categorical features
are binarized through one-hot encoding.

Figure 2: The uplift curves of four analyzed classifiers with four different colors for the $Credit\ Approval$ dataset, while the dashed curve corresponding to the random targeting. metrics | KL | Euclid | LG | LGR
---|---|---|---|---
AUUC | 37.337 | 40.887 | 42.893 | 48.222
Qini | 0.201 | 0.236 | 0.257 | 0.310
Table 3: Model performance of four analyzed classifiers on the $Credit\
Approval$ dataset.

Parameters and Results Based on the business decision-making perspective, the
initial parameters are also the same as above.

Figure 3: The uplift curves of four analyzed classifiers with four different
colors for the real world online loan application dataset, while the dashed
line corresponding to random targeting.

In order to avoid the distribution bias caused by the division on such small
sample size dataset, there is no need to divide $Credit\ Approval$ into
training and test parts. Figure 2 shows the uplift curves for the four
analyzed classifiers, from which we can see that CIET is able to obtain higher
AUUC and Qini coefficients. As shown in Table 3, the former increases from
37$\sim$40 at baselines to 42$\sim$48 at CIET approximately, while the latter
also improves significantly from 0.20$\sim$0.23 to 0.25$\sim$0.31. Especially
when LGR serves as the splitting criterion, the cumulative profit has a
distinguished peak of 74.5, while only 48.4$\%$ of the samples are covered.

### Experiments on Online Loan Application Data

Dataset We further extend our CIET to precision marketing for new customer
application. A telephone marketing campaign is designed to promote customers
to apply for personal credit loans at a national financial holdings group in
China via its official mobile app. The target is 1/0, indicating whether a
customer would submit an application or not. The data contains 53,629
individuals, consisting of a treated group of 32,984 (receiving marketing
calls) and a control group of 20,645 (not receiving marketing calls). These
two groups have 300 and 124 credit loan applications with response rates of
0.9% and 0.6%, which are typical values in real world marketing practice.
There are 24 variables in all, which are characterized as credit card-related
information, loan history, customer demographics et al.

dataset | KL | Euclid | LG | LGR
---|---|---|---|---
training | 0.173 | 0.168 | 0.414 | 0.302
test | 0.108 | 0.124 | 0.385 | 0.319
Table 4: Qini coefficients of four analyzed classifiers on the training and
test sets of the real world online loan application data.

Parameters and Results All parameters are the same as in the above
experiments. The dataset is first divided into training and test sets in a
ratio of sixty percent to forty percent. The response rates are consistent
across two sets for two groups. Figure 3 diplays the results graphically. As
for the training dataset, CIET based on LG and LGR reach AUUC of about 104 and
89, while the decision trees based on KL divergence and squared Euclidean
distance are 73 and 72. It can be seen that CIET achieves a significant
improvement compared to baselines on this real-world dataset even with a very
low response rate. Moreover, as can be seen in Table 4, Qini coefficient based
on our approaches increases to 0.30$\sim$0.41 from 0.16$\sim$0.17 on the
training dataset. Meanwhile, Qini coefficient changes little when crossing to
test dataset, indicating a better stability. Consequently, classifier with our
CIET for precision marketing is effectively improved as well as stabilized in
terms of AUUC and Qini coefficient. At present, CIET has already been applied
to personal credit telemarketing.

## Conclusion

In this ms, we propose new methods for constructing causal inference based
single-branch ensemble trees for uplift estimation, CIET for short. Our
methods provide two partition criteria for node splitting and strategy for
generating ensemble trees. The corresponding outputs are uplift gain between
the two outcomes and a set of interpretable inference rules, respectively.
Compared with the classical decision tree for uplift modeling, CIET can not
only be able to avoid dependencies among inference rules, but also improve the
model performance in terms of AUUC and Qini coefficient. It would be widely
applicable to any randomized controlled trial, such as medical studies and
precision marketing.

## References

  * Athey and Imbens (2015) Athey, S.; and Imbens, G. 2015.  Machine Learning Methods for Estimating Heterogeneous Causal Effects.
  * Athey, Tibshirani, and Wager (2019) Athey, S.; Tibshirani, J.; and Wager, S. 2019.  Generalized random forests.  _The Annals of Statistics_ , 47(2): 1148 – 1178.
  * Gutierrez and Gérardy (2016) Gutierrez, P.; and Gérardy, J.-Y. 2016.  Causal Inference and Uplift Modelling: A Review of the Literature.  In _International Conference on Predictive Applications and APIs_.
  * Guyon (2003) Guyon, I. 2003.  Design of experiments for the NIPS 2003 variable selection benchmark.
  * Jaskowski and Jaroszewicz (2012) Jaskowski, M.; and Jaroszewicz, S. 2012.  Uplift modeling for clinical trial data.
  * Künzel et al. (2017) Künzel, S. R.; Sekhon, J. S.; Bickel, P. J.; and Yu, B. 2017.  Meta-learners for Estimating Heterogeneous Treatment Effects using Machine Learning.  _arXiv: Statistics Theory_.
  * Louizos et al. (2017) Louizos, C.; Shalit, U.; Mooij, J. M.; Sontag, D. A.; Zemel, R. S.; and Welling, M. 2017.  Causal Effect Inference with Deep Latent-Variable Models.  In _NIPS_.
  * Radcliffe (2007) Radcliffe, N. 2007.  Using control groups to target on predicted lift: Building and assessing uplift model.  _Direct Marketing Analytics Journal_ , 14–21.
  * Rzepakowski and Jaroszewicz (2010) Rzepakowski, P.; and Jaroszewicz, S. 2010.  Decision Trees for Uplift Modeling.  In _2010 IEEE International Conference on Data Mining_ , 441–450.
  * Wager and Athey (2018) Wager, S.; and Athey, S. 2018.  Estimation and Inference of Heterogeneous Treatment Effects using Random Forests.  _Journal of the American Statistical Association_ , 113(523): 1228–1242.
  * Yoon, Jordon, and van der Schaar (2018) Yoon, J.; Jordon, J.; and van der Schaar, M. 2018.  GANITE: Estimation of Individualized Treatment Effects using Generative Adversarial Nets.  In _ICLR_.
  * Zhang, Li, and Liu (2022) Zhang, W.; Li, J.; and Liu, L. 2022.  A Unified Survey of Treatment Effect Heterogeneity Modelling and Uplift Modelling.  _ACM Computing Surveys (CSUR)_ , 54: 1 – 36.
  * Zhao and Harinen (2019) Zhao, Z.; and Harinen, T. 2019.  Uplift Modeling for Multiple Treatments with Cost Optimization.  _2019 IEEE International Conference on Data Science and Advanced Analytics (DSAA)_ , 422–431.