This paper describes our winning solution for the ECMLPKDD ChAT Discovery Challenge 2020. We show that whether or not a Twitch user has subscribed to a channel can be well predicted by modeling user activity with boosting trees. We introduce the connection between target-encodings and boosting trees in the context of high cardinality categoricals and find that modeling user activity is more powerful then direct modeling of content when encoded properly and combined with a gradient boosting optimization approach.
The task of the ECML-PKDD ChAT Discovery Challenge 2020 [
The dataset consists of more than 400 million public Twitch comments taken from English channels that are published during the month of January 2020 along with metadata. The training data consists of over 29 million and the test dataset of 90,000 channel-user combinations and their comments. In more detail, each input training sample consists of the channel-id, the user-id, and a list of time-stamped comments from this user, including the specific game played in this channel at this particular time.
Copyright ©c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The ChAT competition presents two peculiarities. The first challenge is that
only half of the users in the test set have no history which requires special
attention when extracting users and channels features. This challenge draws
similarities with the cold start problem in recommendation systems [
subscribes Team voyTECH: User Activity Modeling with Boosting Trees user Our approach is based on the assumption that modeling user activity is more important than plays specific content (e.g. message text). User ac- /watches hosts tivity is modeled as interactions between the user and key objects of the system she interacts with (e.g. channels and games). game
This approach naturally leads to a high
dimensional categorical feature/variable rep- Fig. 1. Interactions
resentation that has been well studied in the
context of recommender systems, click-through-rate predictions and similar
industrial applications. It is also closely related to the concept of graph-based
relational features [
Our experimental results (Section 3) indicate that the interactions illustrated in Figure 1 together with features describing the quantity of user activity (e.g. days active, number of frequently used channels) have strong predictive power. Introducing game-id as a high level object is especially important for the 50% test set user without history (cold-start). For a cold-start user, their most frequent game-id can effectively proxy their user-id (more details in Section 3.1). Before presenting details of our solution (Section 3.3), we first introduce the concept of target encoding to motivate our choice to combine high dimensional feature representations with boosting tree models. 2
High Cardinality Categoricals and Boosting Trees
In this section, we discuss in detail the interaction between (high cardinality)
categoricals, mean target encodings and boosting trees which is at the core of
our winning solution in form of the popular CatBoost library that we used to
implement our models [
Several user and channel categorical features are present in the dataset such
as which game has been played and activity levels for user, games, and channels.
By computing the interaction features between user and channel representations,
several categoricals with high cardinality are extracted. Due to their sparsity,
such high cardinality categoricals pose several challenges in modeling and, in
general, can lead to poor generalization performance. A popular class of models
to handle such a semi-structured datasets containing high cardinality categoricals
are Gradient Boosting Trees [
The handling of categorical features usually happens during the feature engineering phase, where the modeler has the freedom to arbitrarily transform or extract the input features before those are fed into a model. However, models exist that can handle categorical features automatically, i.e., the modeler simply specifies the features that should be handled as categoricals without any further pre-processing required. The user of such models is only able to adjust the predefined categorical encoding process with input through hyper-parameters. For example, hyper-parameters for categorical features include ‘perform one-hotencoding if cardinality of any categorical is less than a threshold‘, ‘perform hash encoding with specified number of hashing dimensions‘ to name a few.
Here, we summarize a few recently proposed models that handle categorical
features as part of the model definition. Two gradient boosting tree
implementations, Microsoft’s LightGBM [
CatBoost is a gradient boosting tree implementation that applies a
regularized mean target encoding on the top-level tree split as a preprocessing step. Such
preprocessing could be considered sub-optimal, at least for the case of trees with
large depth [
In the following section, we provide more background on the fundamentals of CatBoost and, in particular, its connection to mean target encodings since mean target encodings are the core design principle behind CatBoost. 2.2
In this section, we setup the framework of feature extraction from categoricals that is usually called target encodings from machine learning practitioners.
We denote m samples with n features by a m × n design matrix X with column coefficients that are either numericals (in R) or categoricals4. In other words, the j-th column of X is in Rm or Cjm for a set of elements of categoricals Cj . Moreover, we denote by Xj the j-th column of X and by [n] the set {1, 2, . . . , n}. In addition, we denote by y the m-dimensional target vector. The mean value 4 Throughout this paper, a feature is an input variable/predictor that is used for prediction. A categorical feature (or categorical) is a feature with a domain that is a fixed set without an explicit ordering. The elements of a categorical are referred as levels. For example, postal code, favorite color, city or country of a specific individual are examples of categoricals. of y, also referred to as mean target value, is denoted by µ. The tuple (X, y) contains all relevant information for a prediction task and we call such a tuple design matrix pair or for simplicity, design matrix.
We focus on the typical binary classification task, i.e., assuming an input target vector y ∈ {0, 1}m. The analysis can be extended directly to the regression task. Now we are ready to define target encodings.
Definition 1 (Target Encodings). Given (X, y) and an integer j ∈ [n] so that the j-th column of X is categorical, it follows that target encoding is a function f(Xj,y) : Cj → R.
From now on, we write f instead of f(Xj,y) for notation convenience. It is important to note that we allow f to depend on the input dataset. Moreover, we say that f is defined (or fitted) on (X, y) to explicitly specify the input data used on the definition of f .
A very common example of target encoding is the mean target encoding. That is, assume that the j-th column of X is a categorical containing values/levels in Cj = {L1, L2, . . . , Lk}. The mean target encoding µj of the j-th column is defined as follows: µj support on Cj and for any L ∈ Cj , µj (L) = 1 m
! yi Xi,j=L N i=1 (1) where N equals to the number of occurrences of L in the j-th column of X and pred is the indicator function, i.e., equals to 1 if pred is true, otherwise equals to zero. In words, mean target encodings are roughly defined as the mean target value of any level of the categorical (group).
In general, any property of the target values distribution of the group can be also extracted. For example, ML practitioners frequently use the minimum, maximum, standard deviation, kurtosis, percentiles of the target values in addition to the mean value. The main idea is to extract as much statistical information of the target distribution of the group as possible.
Regularization of Target Encodings. By definition, target encodings
introduce target leakage and could lead to poor generalization performance, hence,
target encoding regularization must always be used [
Extra caution on regularization should be given in the presence of high
cardinality categoricals, i.e., categoricals with a large number of distinct levels as
present in this competition. In fact, it is relatively easy to construct an
example where the naive application of target encodings leads to severe overfitting.
In order to exemplify this behavior, a minimal example is constructed by the
authors of the ‘vtreat‘ package [
In our notation, the EB regularized version of the mean target encoding is defined as µjEB(L) := λ(N )µj (L) + (1 − λ(N ))µ (2) where N equals to the number of occurrences of L in the j-th column of X and λ(n) is a monotonically increasing function on n bounded between 0 and 1 1. A common choice of practitioners for λ is λ(n) = 1+exp(−((n−l)/σ) which is a s-shaped function with a value of 0.5 for n = l and σ representing the steepness [13, Equation 4]. Thus, Equation 2 is a smoothed version of the mean target encoding.
Bootstrapping / rolling mean. Bootstrapping is another approach to regularized
target encodings. A specific instance of bootstrapping and target encodings is
implemented in CatBoost [
CatBoost uses a bootstrapping rolling mean approach to reduce overfitting while utilizing the whole training dataset for estimating the target encodings. In a nutshell, CatBoost performs a random permutation on the rows of X and for the i-th row of X (with respect to the random permutation) the mean target encoding is computed using only the rows up to the (i−1)-row. Namely, CatBoost averages several independent random permutations and, moreover, adds a shrinkage prior to the global mean.
To sum up, CatBoost performs categorical encoding for a level L ∈ Cj as follows. For the i-th row and a fixed permutation of the rows, CatBoost computes µjCat(L, i) := λµj "L; (X1:(i−1),j , y1:(i−1)# + (1 − λ)µ where µ is the mean target value and λ is a smoothing hyper-parameter. 3
In this section, we describe the winning solution in more detail and present additional experimental results that better explain the critical choices made to achieve our result. 3.1
We have extracted a range of features from the message log representing the training data. The following features focus on different aspects of the data (time/activity, message, game). 1. t_min:day of first message 8. m_med:medium number of charac2. t_max:day of last message ter per message 3. t_days:number of days with mes- 9. g_n_mes:total number of messages sages 10. g_n:number of games 4. t_dur: t_max - t_min 5. t_active:t_days / t_dur 11. g_top:game with most messages 6. m_total: total number of charac- 12. g_chat:number of messages for ters for all messages game just chatting 7. m_max:max number of character 13. g_top_freq: fraction of messages per message for g_top
All features have been computed as user- and channel-features. This can be done efficiently by aggregating the messages on either the user or channel id. Features such as the number of days between the first and last message (t dur) are computed for individual channel-user combinations.
In addition the following features have been added: 1. uid:user id 2. n_channel:number of channels per
user 3. u_group[low, normal, high]: user activity 4. cid:channel id 5. n_user:number of user per chan
nel 6. c_group[low, normal, high]: channel activity
We show in Section 3.3 that only a small subset of all features is needed to achieve competitive performance.
(a) Top features (train) (b) Top features (test) 3.2
Model definition. The model is based on the CatBoost library version 0.23.1. The loss function is set to be logistic loss, also known as cross-entropy loss. Training of the model is stopped early based on the performance on our custom validation set using the autostop capabilities of CatBoost (‘od type‘ set to ”Iter” and ‘od wait‘ set to 20). The best model is selected automatically by setting use best model=True.
The top performing submission is a single CatBoost model trained with the following hyper-parameters: ’l2 leaf reg’: 64, ’learning rate’: 0.08, ’threshold’: 0.167, ’depth’: 9, ’random strength’: 0.5, ’max ctr complexity’: 2. These parameters have been manually selected on our constructed test set. Cross validation Setup. Training and testing data come from a vastly different distribution, hence, a careful cross validation setup was crucial for model training and hyper-parameter tuning. It is given from the competition description that half of the users in the test set have no history and user-channel interactions are sampled uniformly from low, normal, and high activity levels. Therefore, our goal is to construct a validation set with similar properties. The validation set is constructed as follows: we sample in total 45,000 channel-user pairs (5,000 pairs per activity level pair group), ensuring that these pairs do not appear in the training set. These 45,000 channel-pairs are then duplicated in the validation set by modifying the user-id with an unknown identifier not present in the training set.The training dataset is sub-sampled with a ‘max per group‘ parameter that restricts the number of samples per channel-user group. 3.3
We find that we can achieve strong performance (Table 3) even with a very small
subset of features (’uid’, ’cid’, ’t days’, ’g top’, ’g top c’, ’n user’, ’n channel’,
’m med’, ’m max’, ’t min’) selected by using CatBoot’s feature importance
(Figure 2). The sub-sampling of the training data decreases the model performance
(Figure 3) and the interaction between features (max ctr compl ≥ 2) is
important. However, the memory and run-time requirements increase dramatically
when max ctr compl > 2. We therefore had to trade higher interactions against
more training samples, which were more critical for performance.
(a) Leaderboard Model
(b) Best Features Model
In this work we showed that modeling user activity is more powerful than
direct modeling of content when encoded properly and combined with a suitable
optimization approach. We also introduced the connection between target
encodings and boosting trees in the context of high cardinality categoricals and
highlighted differences in the two popular boosting tree implementations
CatBoost and LightGBM. We plan to conduct further experiments that compare
Boosting Trees to Factorization Machines [
We would like to thank the organizers for the interesting competition and their support with the TIRA platform. From Palaimon we want to thank Phoebe Kuhn for her help with the manuscript and Alexander Pisarenko for his relentless work to provide us with a reliable and scalable infrastructure.