Nonparametric Probabilistic Regression with Coarse Learners

Brian Lucena

Numeristical

###### Abstract

Probabilistic Regression refers to predicting a full probability density
function for the target conditional on the features. We present a
nonparametric approach to this problem which combines base classifiers
(typically gradient boosted forests) trained on different coarsenings of the
target value. By combining such classifiers and averaging the resulting
densities, we are able to compute precise conditional densities with minimal
assumptions on the shape or form of the density. We combine this approach with
a structured cross-entropy loss function which serves to regularize and smooth
the resulting densities. Prediction intervals computed from these densities
are shown to have high fidelity in practice. Furthermore, examining the
properties of these densities on particular observations can provide valuable
insight. We demonstrate this approach on a variety of datasets and show
competitive performance, particularly on larger datasets.

##  1 INTRODUCTION

In modern machine learning parlance, the term regression conveys the
prediction of a point estimate of numerical target. While classical linear
regression models can be thought of as predicting a distribution (based on
Gaussian noise), the underlying assumptions behind this density are rarely
true in practice. As such, linear regression is typically used for point
estimates. As modern machine learning approaches to regression have gained in
popularity, they have still primarily focused on point prediction as measured
by root mean-squared error (RMSE). The problem of probabilistic regression
attempts to specify a full conditional probability density for the target
variable given the features which is measurably realistic. This is a natural
next step in sophistication, enabled by larger datasets and more complex
machine learning methods.

There are many reasons why knowing a precise conditional density is superior
to a point estimate. For example, in predicting an individual’s rating of a
restaurant, there is a big difference between a bimodal and unimodel
distributions with the same mean of 5 out of 10. The former indicates a
polarity of opinion (“you’ll love it or you’ll hate it”) versus the assured
mediocrity of the latter. In a more serious matter, consider a cancer patient
choosing between two treatments both of which, on average, add 2 years of
longevity. Certainly, if one of them is ineffective 80% of the time but adds
10 years when effective, this is a different personal calculation than one
which almost certainly extends life about two years. This would be even more
important if a treatment had significant probability of decreasing lifespan.

Most approaches to probabilistic regression either assume a particular
parametric form, and/or require complicated and expensive computation to
implement, rendering them inaccessible to all but experts in the particular
method. This paper presents a nonparametric method which makes minimal
assumptions about the shape or form of the conditional probability density
function. Yet, to a practitioner, it is nearly as simple as fitting a standard
gradient boosting or random forest model. It is sophisticated enough to
capture predicted densities with multiple modes and nonstandard density
shapes, which can prove enlightening when visualized on real problems.
Moreover, having a full conditional density permits the user to define
prediction intervals, which we empirically show to provide appropriate
coverage in real-world examples.

In between the extremes of point prediction and probabilistic regression,
there are several different approaches to give some indication of the level of
uncertainty around the prediction. Examples of this “middle ground” include
quantile regression, conformal prediction, and other methods to output
confidence intervals around a prediction.

##  2 RELATED WORK

There are multiple techniques for probabilistic regression in the strictest
sense - that is, giving a precise probability density function for the target
value given the features. NGBoost (Duan et al., (2020)) is the most direct
analog to the method presented here, as it is simple to implement, usable by
non-experts, and also relies on gradient boosting. However, our method is
nonparametric, while NGBoost requires a parametric specification and then
predicts the value of the parameters given the features. Generalized Additive
Models for Shape, Scale, and Location (GAMLSS) (Rigby and Stasinopoulos,
(2005)) are similarly restricted to a specified model form. Bayesian
approaches such as Bayesian Additive Regression Trees (BART) ( Chipman et al.,
(2010)) require computationally expensive methods to sample the posterior
distribution and are generally difficult to use. Bayesian Deep Learning
methods (e.g. Blundell et al., (2015), Hernandez-Lobato and Adams, (2015),
Graves, (2011)) have shown some promise but are also relatively difficult to
use.

The approach of conformal prediction (Shafer and Vovk, (2008)) is related to
probabilistic regression in that both attempt to go beyond a mere point
estimate on regression problems. Conformal prediction uses any machine
learning model in conjunction with a user-specified confidence level to
predict a range of values for the target, such that the target falls into the
interval with the appropriate confidence. However, it differs from
probabilistic regression in that it does not explicitly output a probability
density function. Similarly, approaches like Quantile Regression (Koenker and
Hallock, (2001)), in conjunction with Bayesian Methods (Yang et al., (2016),
Yang and He, (2012)), Random Forests (Meinshausen and Ridgeway, (2006)), or
Neural Networks (Petneházi, (2021),Rodrigues and Pereira, (2020)) have been
attempted, but do not output a full conditional probability density function
and/or are not straightforward to use.

##  3 CONTRIBUTIONS

We present a nonparametric approach to probabilistic regression called PRESTO
(Probabilistic REgression with Structured Trees). Like NGBoost, it relies on
gradient boosting (Friedman, (2000), Chen and Guestrin, (2016)) and is easy to
implement and fit on new data. Specifically, models can be fit with the same
ease as standard gradient boosting or random forest models using the standard
fit/predict paradigm. However, unlike NGBoost, PRESTO does not make any
assumptions about the form of the conditional density. Rather, it approximates
the true conditional density by fitting multiple piecewise constant densities
and averaging the results. Consequently, it performs well in situations where
the true conditional density is multimodal or otherwise does not have a simple
or consistent parametric form.

We run the PRESTO algorithm on a benchmark collection of 10 datasets from the
UC-Irvine repository and show that its performance compares favorably to the
competitors. Since we have a full conditional density for each prediction, we
can directly create confidence intervals for the predicted values. We show
that, in practice, these intervals provide at least the guaranteed level of
coverage. Analysis of the predicted densities can provide useful insight into
scientific problems, as we are able to detect multi-modality and other
interesting effects in the conditional distribution. Furthermore, we show that
using a structured cross-entropy loss for the underlying gradient boosting
base classifiers improves performance both quantitatively and qualitatively.
Finally, we examine learning curves to show that relatively few forests are
needed to achieve near-optimal performance.

##  4 PRESTO ALGORITHM

Put simply, the PRESTO Algorithm builds multiple classifiers, converts their
predictions to densities, and averages the results. For each classifier, we
randomly subdivide the range of the target variable into intervals, thus
converting the regression problem into one of multi-classfication. The
resulting classifier yields a probability distribution over the various
intervals which can be cast as a probability density function (pdf) that is
piecewise constant. By building many probabilistic classifiers on different
choices of intervals, we can average the resulting distributions yielding a
final probability density function. The resulting pdf is still piecewise
constant, but with such fine grain intervals that it typically resembles a
curve, yet also handles discontinuities in the density function if they are
present.

While the approach is straightforward, there are many details that must be
handled elegantly for it to work in practice. In particular, how are the
random intervals chosen? For some applications, there may be an a priori known
range of possible values. However, in general we must learn appropriate
choices of intervals from the training data itself. Moreover, even within a
fixed range, there may be more resolution required in some areas than others,
meaning that a fixed-width grid is not sufficient. Further complications arise
when you consider that there may be target values on future (test)
observations that exceed the range seen in the test set. Thus we may want to
extend the range beyond what is seen in the training data so as to avoid
assigning those extreme values a zero probability.

###  4.1 Formal Description of PRESTO Algorithm

Data: Training dataset $\\{x_{i},y_{i}\\}_{i=1}^{n}$

Input : number of classifiers: $m$: Base classifier: $\mathcal{C}$, interval
selection method: INTMETHOD

Output : A probabilistic regressor $f$

1 for  _$i\leftarrow 1,\ldots,m$_ do

2 Use INTMETHOD to select a sequence of interval endpoints:
$b_{0},b_{1},\ldots,b_{k}$ with $b_{j}<b_{j+1}$.

3 Create a discretized version $\\{y^{\prime}_{i}\\}$ of $\\{y_{i}\\}$ where
$y^{\prime}=j$ iff $b_{j}\leq y_{i}<b_{j+1}$ (and $y^{\prime}_{i}=k$ if
$y_{i}=b_{k})$

4 $g_{i}\leftarrow\mathcal{C}(\\{x_{i},y^{\prime}_{i}\\}_{i=1}^{n})$

5 $f_{i}(x)\leftarrow\mathcal{D}(g_{i}(x),B)$

6

7

$f=avg(f_{1},f_{2},\ldots,f_{m})$

Algorithm 1 PRESTO

We assume a training dataset of size $n$, $\\{x_{i},y_{i}\\}_{i=1}^{n}$ where
$x_{i}\in\mathcal{X}$ (the feature space) and $y_{i}\in\mathbb{R}$. Let
$\mathcal{P}$ represent the space of probability density functions (pdfs) on
$\mathbb{R}$. We define a probabilistic regressor as a mapping
$f:\mathcal{X}\rightarrow\mathcal{P}$. Given a collection of $m$ probabilistic
regressors, we can average them by defining
$f(x)=avg(f_{1},f_{2},\ldots,f_{m}):=\frac{1}{m}\sum_{i=1}^{m}f_{i}(x)$ where
the pdfs are summed in the obvious (pointwise) manner. Let $g$ be a
(probabilistic) multi-classifier where the classes are represented by
$\\{1,2,\ldots,k\\}$. In this way, $g$ can be thought of as a mapping
$g:\mathcal{X}\rightarrow\mathcal{S}_{k}$ where $S_{k}$ is the
$(k-1)$-dimensional probability simplex (on $k$ classes). A classifier method
$\mathcal{C}$ when fit on a training dataset $\\{x_{i},y_{i}^{\prime}\\}$ with
$y_{i}^{\prime}\in\\{1,2,\ldots,k\\}$ yields a probabilistic multi-classifier,
denoted $\mathcal{C}(\\{x_{i},y_{i}^{\prime}\\})$.

Given a probability distribution $P=(p_{1},p_{2},\ldots,p_{k})$ on $k$
classes, and a set of $k$ intervals
$B=([b_{0},b_{1}],[b_{1},b_{2}],\ldots,[b_{k-1},b_{k}])$ with $b_{i}<b_{i+1}$,
define the associated density $\mathcal{D}(P,B)$ as:

$\mathcal{D}(P,B)=\begin{cases}p_{i}/(b_{i}-b_{i-1}),&\text{if
}x\in[b_{i-1},b_{i})\\\ p_{k}/(b_{k}-b_{k-1}),&\text{if }x=b_{k}\\\
0,&\text{otherwise}\end{cases}$

Clearly if $\sum_{i=1}^{k}p_{i}=1$ then
$\int_{-\infty}^{\infty}\mathcal{D}(P,B)=1$, so $\mathcal{D}(P,B)$ is a valid
probability density function.

The PRESTO algorithm is defined formally as Algorithm 1. We must specify a
base classifier, a number of classifiers $m$ and the interval selection method
(INTMETHOD). While any base classifier could be used in principle, in this
paper we exclusively use forests of Gradient Boosted Decision Trees. The
interval selection method requires more nuance. As discussed earlier, the
distribution of the numerical target, and what is known about it a priori, may
influence how we choose intervals. Generally speaking, if the target is known
a priori to take values only in a fixed interval and a consistent resolution
is appropriate across that interval, we can just use the same specified set of
intervals each time. We refer to this as the fixed interval selection method.
For example, in the Wine dataset, the target is known to be integers between 2
and 8, inclusive. Therefore, we can use a fixed set of points
$\\{2,2.5,3.5,\ldots,7.5,8\\}$ to define our intervals. We refer to this as
the fixed method. Alternatively, there may be a fixed range of values which is
larger in cardinality. For example in the Naval dataset, the target is known a
priori to take values in $\\{.95,.951,.952,\ldots,.999,1\\}$. We could use a
fixed set of points such as
$\\{.950,.9505,.9515,.9525,\ldots,.9985,.9995,1\\}$ to define intervals.
However, using the base classifier on 51 classes may not be most effective. So
we may want to choose only a (random) subset of those grid points (keeping the
min and the max) to define the intervals. We refer to this as the fixed-rss
method.

In the most general case, we know nothing about the possible range of target
values beyond what we see in the training data. In these situations, we use
the RandQuantile interval selection method, given as Algorithm 2. In this
method, we choose a subset of quantile values from the uniform distribution
and then find the corresponding quantiles in the empirical distribution of the
target training values. After sorting these values (removing duplicates) and
adding in the minimum and maximum observed values, we take the midpoints of
the neighboring values (keeping the min and max). This is done so that the
observed y-values fall in the center of the bin rather than at an endpoint.

Data: Training dataset $\\{x_{i},y_{i}\\}_{i=1}^{n}$

Input : Number of quantiles to sample: $r$, Boolean: Extend, Extend params:
$(q_{\min},q_{max},t)$

Output : A set of interval endpoints: $\\{b_{0},b_{1},\ldots,b_{k}\\}$ with
$b_{j}<b_{j+1}$

1 Let $z_{1},\ldots,z_{r}\sim U[0,1]$ iid and sorted s.t. $z_{j}<z_{j+1}$

2 Let $a_{j}$ be the $z_{j}$-quantile of $\\{y_{i}\\}$. (for $j$ in
$1,\ldots,r$)

3 Let $a_{0},a_{r+1}$ be the min (resp. max) value in $\\{y_{i}\\}$

4 Let
$A=\\{a_{0},(a_{0}+a_{1})/2,(a_{1}+a_{2})/2,\ldots,(a_{r}+a_{r+1})/2,a_{r+1}\\}$

5 if  _Extend_ then

6 $u\rightarrow$ $q_{\min}$-th quantile of $\\{y_{i}\\}$

7 $v\rightarrow$ $q_{\max}$-th quantile of $\\{y_{i}\\}$

8 $w\rightarrow(v-u)*t$

9 $A\rightarrow A\cup\\{y_{\min}-w,y_{\max}+w\\}$

10Let $b_{0},b_{1},\ldots,b_{k}$ be the sorted, unique values of $A$

Algorithm 2 RandQuantile Method

The RandQuantile method includes an option to Extend this set of intervals by
creating one more interval on each side of the range. This is done to allow
for the possibility that there are test points beyond the range of values seen
in training, and to avoid giving them zero probability. If Extend is specified
as true, we specify three parameters $(q_{\min},q_{\max},t)$ to determine the
width of an additional bin on each side of the $[y_{\min},y_{\max}]$ range
defined by the training data. This is a generalization of using the
interquartile range (IQR) as a standardizing measure for the spread of a
dataset. We define a distance between the $q_{\min}$-th and $q_{\max}$-th
quantiles and multiply it by a factor $t$. So, setting
$q_{\min}=.25,q_{\max}=.75,\text{and }t=1$ would be equivalent to adding an
additional bin with width the size of the IQR to each side of the previous set
of bins.

Figure 1: The densities predicted by 4 base classifiers on a single data
point.

Figure 2: The averages of 5, 10, 25, and 50 base classifiers on the same data
point

We illustrate the algorithm visually in Figure 2 using the Concrete data set
from the UCI repository. In the top row we see the predicted densities from 4
different classifiers on the same data point. These are the predictions from
individual coarse classifiers on a particular test data point. You can see
that each classifier uses different intervals, and thus the densities look
quite different from one another. In the bottom row we see the predicted
density on the same test data point when averaging $c$ coarse classifiers for
$c=5,10,25,50$. As we combine multiple coarse densities, the resulting average
density gets smoother.

###  4.2 Structured Cross-Entropy

One issue with applying a typical multi-classification algorithm to the
intervals, is that, in general, multi-classification algorithms do not
consider the structure of the classes. Suppose we divide our target range into
10 intervals, numbered 1 through 10 from left to right. If our algorithm puts
very high probability on the outcome 3 when the right answer was 2, we are
penalized just as much as if we had put equally high probability on 9. Loosely
speaking, the standard cross-entropy loss only considers the probability
placed on the exact right answer and does not give “partial credit” for the
probability placed near the correct answer. The 10 different classes are
equally different from one another, and no wrong answer is better than any
other.

The structured cross-entropy loss function (Lucena, (2022)) tries to mitigate
this phenomenon by specifying a set of partitions of the classes. Each
partition represents a “coarsening” of the state space, and is given a weight,
such that the weights sum to one. The (standard) cross-entropy is then
calculated with respect to each of these partitions - i.e., the prediction is
considered “right” if the true answer and the prediction are in the same
“block” of the partition, and the probability of the block is the sum of the
probabilities of the individual classes in the block.

####  4.2.1 Example

To make this more clear, we will walk through an example. Suppose the target
space is $\\{1,2,\ldots,10\\}$ and we expect an ordinal structure. We could
model this by specifying the partitions:

$\displaystyle\mathcal{P}_{0}$ $\displaystyle=$
$\displaystyle\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{6\\},\\{7\\},\\{8\\},\\{9\\},\\{10\\}\\}$
$\displaystyle\mathcal{P}_{1}$ $\displaystyle=$
$\displaystyle\\{\\{1,2\\},\\{3,4\\},\\{5,6\\},\\{7,8\\},\\{9,10\\}\\}$
$\displaystyle\mathcal{P}_{2}$ $\displaystyle=$
$\displaystyle\\{\\{1\\},\\{2,3\\},\\{4,5\\},\\{6,7\\},\\{8,9\\},\\{10\\}\\}$

with corresponding weights $w_{0},w_{1},w_{2}>0$ such that
$w_{0}+w_{1}+w_{2}=1$.

This structure means, in effect, that a distribution is credited, to some
degree, for the probability placed on values “adjacent” to the true value.
Suppose for a particular test data point, we predicted
$p_{a}=(.1,.2,.4,.1,.05,.05,.025,.025,.025,.025)$ as our probability
distribution over the 10 classes, and the true class was 2. Since, the
distribution $p_{a}$ assigns probability 0.2 to the outcome 2, the (standard)
cross-entropy loss would be $-\log(.2)=1.609$, as it only considers the
probability placed on the exact correct class 2.

By contrast, the structured cross-entropy (with the structure defined above)
averages the standard cross-entropy values taken with respect to the 3
partitions. $\mathcal{P}_{0}$ is the singleton partition and behaves just like
the standard cross-entropy, with a result of $-\log(.2)$. For
$\mathcal{P}_{1}$ the correct block was $\\{1,2\\}$. The distribution $p_{a}$
gave probability 0.1 to the outcome 1 and probability 0.2 to the outcome 2, so
the probabillity of the block $\\{1,2\\}$ under $p_{a}$ is $.1+.2=.3$. Thus
the cross-entropy of the data point with respect to $p_{a}$ is $-\log(.3)$.
For $\mathcal{P}_{2}$ the correct block was $\\{2,3\\}$ yielding a value of
$-\log(.2+.4)$. Averaging the three values together, using the corresponding
weights, would yield $-w_{0}\log(.2)-w_{1}\log(.3)-w_{2}\log(.6)$. For
$w_{0},w_{1},w_{2}=(.2,.4,.4)$ we would get a value of $1.008$. Note that the
structured cross-entropy considers the probability placed on values 1 and 3,
even though the correct answer was 2.

Now consider another model, which on the same test data point predicts
$p_{b}=(.1,.2,.1,.1,.1,.1,.1,.1,.05,.05)$. Intuitively, this is a worse
prediction than $p_{a}$, as it put less probability mass near the true answer
of 2. But from the point of view of standard cross-entropy, it is equally
good: $-\log(.2)=1.609$. However, the structured cross-entropy (with the same
partitions and weights) would be
$-(.2)\log(.2)-(.4)\log(.1+.2)-(.4)\log(.2+.1)=1.285$. The structured cross-
entropy favors $p_{a}$ over $p_{b}$ whereas standard cross-entropy treats them
as equivalent.

In the experimental section of this paper, we use the PRESTO algorithm with
gradient boosted forests as the base classifier. We consider variants trained
under both the standard and structured cross-entropy loss functions. We will
see, both quantitatively and qualitatively, that the structured cross-entropy
yields better results.

####  4.2.2 Random Partitions

In general, a weighted partition set is a set of partitions
$\\{\mathcal{P}_{i}\\}$ of $\\{1,\ldots,k\\}$ with a corresponding set of
weights $w_{i}$ which sum to one. Since the weights sum to one, they could
also be perceived as probabilities, and the entire object seen as a random
variable taking values in the set of partitions. Thus, it is also referred to
as a random partition.

Dataset | N | PRESTO | NGBoost | Best Prev Score | Best Prev Method
---|---|---|---|---|---
Boston | 506 | 2.564 $\pm$ 0.075 | 2.43 $\pm$ 0.15 | 2.37 $\pm$ 0.24 | Gaussian Process
Concrete | 1030 | 2.996 $\pm$ 0.034 | 3.04 $\pm$ 0.09 | 3.03 $\pm$ 0.11 | Gaussian Process
Energy | 768 | 0.922 $\pm$ 0.027 | 0.60 $\pm$ 0.45 | 0.60 $\pm$ 0.45 | NGBoost
Kin8nm | 8192 | -0.550 $\pm$ 0.007 | -0.49 $\pm$ 0.02 | -1.20 $\pm$ 0.02 | Deep Ensembles
Naval | 11934 | -5.228 $\pm$ 0.004 | -5.34 $\pm$ 0.04 | -5.87 $\pm$ 0.05 | Concrete Dropout
Power | 9568 | 2.525 $\pm$ 0.007 | 2.79 $\pm$ 0.11 | 2.68 $\pm$ 0.05 | DistForest
Protein | 45730 | 1.441 $\pm$ 0.006 | 2.81 $\pm$ 0.03 | 2.59 $\pm$ 0.04 | DistForest
Wine | 1588 | 0.781 $\pm$ 0.016 | 0.91 $\pm$ 0.06 | 0.91 $\pm$ 0.06 | NGBoost
Yacht | 308 | 0.854 $\pm$ 0.088 | 0.20 $\pm$ 0.26 | 0.10 $\pm$ 0.26 | Gaussian Process
YearMSD | 515345 | 3.125$\pm$ NA | 3.43 $\pm$ NA | 3.35 $\pm$ NA | Deep Ensembles
Table 1: NLL values on UCI Datasets. The lowest value is in bold, as are those with standard errors that overlap the best value. Dataset | PRESTO | NGBoost | Prev Best111The previous best score was achieved by Gradient Boosting for all datasets except Protein and Wine, which were achieved by Random Forests. The results for Naval were reported only two decimal places, thus the best score cannot be evaluated.
---|---|---|---
Boston | 3.522 $\pm$ 0.243 | 2.94 $\pm$ 0.53 | 2.46 $\pm$ 0.32
Concrete | 5.524 $\pm$ 0.151 | 5.06 $\pm$ 0.61 | 4.46 $\pm$ 0.29
Energy | 0.990 $\pm$ 0.033 | 0.46 $\pm$ 0.06 | 0.39 $\pm$ 0.02
Kin8nm | 0.134 $\pm$ 0.001 | 0.16 $\pm$ 0.00 | 0.14 $\pm$ 0.00
Naval | 0.0013 $\pm$ 2e-5 | 0.00 $\pm$ 0.00 | 0.00 $\pm$ 0.00
Power | 3.378 $\pm$ 0.048 | 3.79 $\pm$ 0.18 | 3.01 $\pm$ 0.10
Protein | 3.371 $\pm$ 0.009 | 4.33 $\pm$ 0.03 | 3.60 $\pm$ 0.00
Wine | 0.579 $\pm$ 0.010 | 0.63 $\pm$ 0.04 | 0.50 $\pm$ 0.01
Yacht | 2.399 $\pm$ 0.138 | 0.50 $\pm$ 0.20 | 0.42 $\pm$ 0.09
YearMSD | 8.862 $\pm$NA | 8.94 $\pm$ NA | 8.73 $\pm$ NA
Table 2: RMSE values on UCI Datasets.

There are many possible ways to design random partitions which capture ordinal
structure. We define here the standard random ordinal partition on $k$ classes
with singleton weight $w_{0}$ and block size $s<(k/2)$ as follows:

$\displaystyle\mathcal{P}_{0}$ $\displaystyle=$
$\displaystyle\\{\\{1\\},\\{2\\},\\{3\\},\ldots,\\{k\\}\\}$
$\displaystyle\mathcal{P}_{1}$ $\displaystyle=$
$\displaystyle\\{\\{1,\ldots,s\\},\\{s+1,\ldots,2s\\},\ldots\\{\left\lfloor(k/s)\right\rfloor
s+1,\ldots,k\\}\\}$ $\displaystyle\mathcal{P}_{2}$ $\displaystyle=$
$\displaystyle\\{\\{1\\},\\{2,\ldots,s+1\\},\ldots\\{\left\lfloor(k/s)\right\rfloor
s+2,\ldots,k\\}\\}$ $\displaystyle\mathcal{P}_{3}$ $\displaystyle=$
$\displaystyle\\{\\{1,2\\},\\{3,\ldots,s+2\\},\ldots\\{\left\lfloor(k/s)\right\rfloor
s+3,\ldots,k\\}\\}$ $\displaystyle\ldots$ $\displaystyle\mathcal{P}_{s}$
$\displaystyle=$
$\displaystyle\\{\\{1,2,\ldots,s-1\\},\\{s,\ldots,2s-1\\},\ldots\\{\left\lfloor(k/s)\right\rfloor
s,\ldots,k\\}\\}$ $\displaystyle w_{i}$ $\displaystyle=$
$\displaystyle(1-w_{0})/s\text{\hskip 28.45274pt for $i=1,\ldots,s$}$

###  4.3 Usability

PRESTO is available for public use via in the (pip-installable) StructureBoost
package in Python. It uses the standard fit/predict paradigm familiar to users
of scikit-learn. As such, it is simple to implement and accessible to non-
experts.

###  4.4 Computational Complexity

This computation time for PRESTO is dominated by the training of the $m$ base
classifiers, so it is equivalent to training $m$ multi-class gradient boosted
forests (where the number of classes is approximately $r$ in the RandQuantile
method). Using the structured cross-entropy loss function slightly increases
the training time, as the gradients are somewhat more complicated to compute.
However, this difference is typically not significant. We trained a single
forest with 200 trees, a max-depth of 7 and $r=25$ across 10 different splits
of the Power dataset using both structured and stand took an average of 34.82
seconds while the equivalent forest trained with standard cross-entropy took
an average of 34.22 seconds (on a 2019 MacBookPro). Our experiments used 10
classifiers ($m=10$), so the computation time would be roughly 10 times that
of a single forest. Note also that although we did not implement any parallel
computing techniques, the base classifiers can easily be trained in parallel,
thereby reducing computation time considerably.

##  5 EXPERIMENTS

To evaluate PRESTO, we use a benchmark collection of 10 datasets from the UCI
Machine Learning repository. Overall, we rely heavily on the results presented
in Duan et al., (2020) and follow their methodology closely. As such, we
follow closely the protocol they used, which originated in Hernandez-Lobato
and Adams, (2015) and was used subsequently in Gal and Ghahramani, (2016), Gal
et al., (2017), and Lakshminarayanan et al., (2017). For each dataset, we set
aside 10% as a test set, and split the remainder 80-20 for training /
validation. The training/validation split is used for hyper-parameter
optimization (including the number of boosting stages for each base
classifier). Then the model is retrained on the combined training/validation
data for the best choice of parameters and evaluated on the test set. As in
Duan et al., (2020), we ran 20 trials for each dataset, except for Protein (5)
and YearMSD (1). The latter was a particularly large dataset with a single
train/test split, and therefore required special handling.

###  5.1 Parameter Tuning

The parameters of PRESTO fall into 3 main categories: 1) PRESTO-specific
parameters including the interval selection method and number of classifiers,
2) parameters for the base classifier (gradient boosting) and 3) parameters
regarding the structured entropy loss function. As described below, we
generally took an approach of simply choosing reasonable default values and
did not do full parameter optimization. Full details and code are available in
the Supplementary Material

####  5.1.1 PRESTO-Specific Parameters

We used 10 classifiers for each dataset except for YearMSD, for which we used
only a single classifier. For the interval selection method, we used the
RandQuantile method with $r=25$ and Extend with parameters $(.25,.75,.25)$
(i.e. extending 25% of the InterQuartile Range). There were 3 exceptions where
the range and resolution of target values were known a priori: Wine, Naval,
and YearMSD. We used the fixed-rss method for Naval and the fixed method for
Wine and YearMSD .

####  5.1.2 Gradient Boosting Parameters

We chose learning rate values in relation to the size of the dataset. We used
a learning rate of 0.01 for the datasets with less than 2,000 datapoints, 0.05
for those between 2,000 and 12,000, .07 for Protein and .1 for YearMSD. The
max-depth was tuned on a single train/valid trial set, with the best value
used for all subsequent trials. The number of trees was tuned separately for
each base classifier (forest) on each train/valid split. The YearMSD contained
a large number of rows (500K) and features (90) which precluded hyper-
parameter optimization, so we arbitrarily chose a max-depth of 4 and randomly
sampled .1 of the columns at each node for efficiency considerations.

####  5.1.3 Structured Entropy Loss Parameters

We trained PRESTO under two conditions: first, using a structured cross-
entropy loss function (referred to as the structured variant), and second,
using the standard cross-entropy loss function (referred to as the standard
variant). When using the structured variant, we used the standard ordinal
random partition defined in Section 4.2 with $w_{0}=.1$ and $s$ as the
(rounded) square root of number of intervals.

###  5.2 Negative Log Likelihood

We use the average negative log-likelihood (a.k.a log-loss) measured on the
test set as our primary metric of performance. In Table 1 we summarize the
results of NGBoost and the suite of competitors that were evaluated in Duan et
al., (2020) and then add in the results for PRESTO (structured variant). For
brevity, we report the values only for NGBoost and the method that gave the
best value for that particular dataset. We will briefly summarize the
competing methods here - for full details see Duan et al., (2020) and the
associated papers. The Concrete Dropout method (Gal et al., (2017)) fits a
neural network and uses a continuous relaxation to tune the dropout
probability. Deep Ensembles (Lakshminarayanan et al., (2017)) fit multiple
neural networks and then approximate a Gaussian mixture to obtain a
probability distribution. The Gaussian Processes method (Rasmussen and
Williams, (2005)) used a relevance detection kernel optimized by gradient
descent and employing a variational inference technique from Titsias, (2009).
The DistForest method (Schlosser et al., (2018)) used forests of 200 trees to
estimate the parameters of a Normal distribution.

We see that PRESTO performs competitively overall, scoring best on 5 out of
the 10 datasets and statistically close on a 6th. It is particularly effective
on the larger datasets: the improvement on the Protein dataset is particularly
notable in its magnitude. It outperforms NGBoost on 6 out of the 10 datasets -
with NGBoost typically achieving better results on the smaller datasets. This
is not surprising - PRESTO should have lower bias and higher variance and
therefore require more data.

Dataset | 20% | 50% | 80% | 90% | 95%
---|---|---|---|---|---
Boston | 0.249 | 0.632 | 0.934 | 0.986 | 0.989
Concrete | 0.293 | 0.689 | 0.953 | 0.987 | 0.992
Energy | 0.392 | 0.851 | 0.985 | 0.99 | 0.995
Kin8nm | 0.246 | 0.621 | 0.913 | 0.974 | 0.993
Naval | 0.544 | 0.883 | 0.958 | 0.961 | 0.962
Power | 0.261 | 0.621 | 0.898 | 0.961 | 0.984
Protein | 0.283 | 0.624 | 0.881 | 0.949 | 0.977
Wine | 0.498 | 0.740 | 0.874 | 0.928 | 0.956
Yacht | 0.355 | 0.721 | 0.984 | 0.995 | 0.995
YearMSD | 0.197 | 0.500 | 0.800 | 0.902 | 0.948
Table 3: Coverage Rate on UCI Datasets

###  5.3 Point Estimation

While PRESTO is intended to yield a full conditional density rather than a
single point estimate, it is still possible to provide a point estimate by
calculating the mean of the predicted density. In Table 2 we report
performance results for predicting point estimates as measured by RMSE. Again,
we summarize the results provided in Duan et al., (2020) and add in the
results for PRESTO. In general, the methods designed to predict point
estimates outperform both PRESTO and NGBoost as measured by RMSE.
Nevertheless, PRESTO gets the best results on 2 out of the 9 datasets. In
head-to-head with NGBoost, PRESTO gets better results on the 5 datasets
containing more than 1500 datapoints, while NGBoost outperforms on the 4
smaller datasets. One possible explanation for the lack of performance on
point prediction regards the nature of density prediction. Since there is a
high penalty for putting a low probability on an observed value, density
predictions must be more conservative and put some probability mass on the
most extreme values. Consequently, these “fat tails” influence the mean, which
hurts performance on the RMSE metric.

###  5.4 Prediction Intervals

One valuable aspect of predicting a full conditional density is the ability to
specify a range of values and a probability that the target will fall within
that range. Of course, such intervals are only useful insofar as the coverage
guarantees prove to be true in practice. To test, we created
$(1-\alpha)$-prediction intervals by computing the $\alpha/2$ quantile and the
$1-(\alpha/2)$ quantiles of the predicted (conditional) density and evaluating
what percentage of time the true target value fell into the associated
interval. This was done for $\alpha=0.8,0.5,0.2,0.1,0.05$ to create prediction
intervals at coverages of (20%, 50%, 80%, 90% and 95%) respectively. The
results are in Table 3. For all but the YearMSD dataset, we see that the 95%
prediction intervals contained the true value more than 95% of the time, and
that this pattern applied to the other prediction intervals as well. In fact,
the data suggest that the intervals are wider than necessary, and perhaps too
conservative. This may be another consequence of minimizing the negative log-
likelihood, which encourages “fatter tails” due to the extreme penalties of
low densities. Nevertheless, this analysis demonstrates that, in practice, the
prediction intervals give at least the promised coverage, which is a valuable
property. For the YearMSD dataset, we see that the empirical coverage tracks
very closely to the purported coverage. This may be a consequence of the large
size of that dataset.

Dataset | N | PRESTO-struc | PRESTO-std
---|---|---|---
Boston | 506 | 2.564 $\pm$ 0.075 | 2.635 $\pm$ 0.076
Concrete | 1030 | 2.996 $\pm$ 0.034 | 3.054 $\pm$ 0.035
Energy | 768 | 0.922 $\pm$ 0.027 | 0.953 $\pm$ 0.027
Kin8nm | 8192 | -0.550 $\pm$ 0.007 | -0.500 $\pm$ 0.006
Naval | 11934 | -5.228 $\pm$ 0.004 | -5.199 $\pm$ 0.004
Power | 9568 | 2.525 $\pm$ 0.007 | 2.546 $\pm$ 0.007
Protein | 45730 | 1.441 $\pm$ 0.006 | 1.447$\pm$ 0.006
Wine | 1588 | 0.781 $\pm$ 0.016 | 0.784 $\pm$ 0.015
Yacht | 308 | 0.854 $\pm$ 0.088 | 0.933 $\pm$ 0.089
YearMSD | 515345 | 3.125 $\pm$ NA | 3.167 $\pm$ NA
Table 4: NLL values for PRESTO Variants

###  5.5 Loss Function Evaluation

To assess the impact of using the structured entropy loss function, we compare
the structured and standard variants of PRESTO. The results are in Table 4.
The structured variant consistently, if modestly, outperforms the variant
trained with the standard cross-entropy across all 10 datasets. Therefore, a
simple one-sided sign test against the null hypothesis of no difference
indicates a p-value of $(1/2^{10})<.001$. On a more qualitative level, the
densities resulting from the structured variant are smoother. This is
demonstrated in Figure 3. The top row shows predicted densities from models
using the standard variant (from the Kin8nm, Power, Energy and Boston
datasets, from left to right). The bottom row shows the corresponding
predictions from the structured model. Visually, we can see that the densities
on the bottom row are smoother and less jagged.

Figure 3: Top row: Predicted densities using standard variant from kin8nm,
Power, Energy, and Boston (left to right). Bottow row: same densities using
structured variant.

Figure 4: Learning Curves for Power and Kin8nm.

###  5.6 Learning Curves

In our experiments, we (somewhat arbitrarily) chose 10 as the default number
of classifiers (forests). Since we average the classifiers in our ensemble, we
would expect that performance should improve and then level off as we add more
classifiers, but that we should not overfit by adding more classifiers. (The
individual classifiers, of course, must be trained carefully to avoid
overfitting, but that is a different issue.) To explore this empirically we
ran PRESTO with 100 forests on a single trial for the Power and Kin8nm
datasets and plotted the the performance (negative log-likelihood) as a
function of the number of forests used. The results are in Figure 4. For the
Power dataset, we see that performance quickly reaches its optimum level:
between 10 and 100 forests the performance level is essentially constant. For
the Kin8nm dataset, it takes longer to level off: performance is notably
better at 25 forests than at 10. This suggests we may be able to improve
performance on some datasets by increasing the number of forests. The results
from both datasets suggest that overfitting due to a high number of forests is
not a concern.

##  6 SUMMARY

PRESTO is shown to be an effective method for probabilistic regression. It
makes minimal assumptions about the form of the predicted densities,
effectively learning the shape from the data. It performs competitively on a
benchmark set of datasets against a suite of competing algorithms, yielding
the best result on 5 out of the 10 datasets. It outperforms considerably on
the largest datasets (of sizes 45K and 515K), while its weakest results came
on smaller datasets ($<$1K data points). Associated prediction intervals are
empirically shown to have appropriate coverage. The intervals were too
conservative on most of the datasets, providing a higher rate of coverage than
expected, and suggesting that narrower intervals could have provided the
promised coverage. However, for the largest dataset (515K), the intervals were
quite well calibrated, suggesting that the precision may improve given enough
data - but more research is needed to validate this. Finally, it can be useful
as a tool for inference, as it learns the form and shape of the conditional
density, potentially yielding valuable insights. It employs the standard
fit/predict paradigm and is therefore easy to use by experts and non-experts
alike.

There are several potential avenues for future work in this area. For example,
it would be interesting to explore why the prediction intervals are wider than
necessary. Potentially this may arise from a lack of calibration in the base
classifiers. If that is the case, perhaps performing post-hoc calibration on
the individual base classifiers may improve the quality of those intervals (as
well as the general performance). Moreover, since multimodal predictions are
not uncommon, there is also the potential to provide disconnected prediction
regions - that is, choosing the intervals of highest density rather than just
using the center of the distribution. Such prediction regions would be
narrower (in aggregate) than the central quantile approach used in this paper.

## References

  * Blundell et al., (2015) Blundell, C., Cornebise, J., Kavukcuoglu, K., and Wierstra, D. (2015).  Weight uncertainty in neural network.  In Bach, F. and Blei, D., editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1613–1622, Lille, France. PMLR.
  * Chen and Guestrin, (2016) Chen, T. and Guestrin, C. (2016).  Xgboost: A scalable tree boosting system.  In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785–794. ACM.
  * Chipman et al., (2010) Chipman, H. A., George, E. I., and McCulloch, R. E. (2010).  Bart: Bayesian additive regression trees.  The Annals of Applied Statistics, 4(1):266–298.
  * Duan et al., (2020) Duan, T., Anand, A., Ding, D. Y., Thai, K. K., Basu, S., Ng, A., and Schuler, A. (2020).  Ngboost: Natural gradient boosting for probabilistic prediction.  In International Conference on Machine Learning, pages 2690–2700. PMLR.
  * Friedman, (2000) Friedman, J. H. (2000).  Greedy function approximation: A gradient boosting machine.  Annals of Statistics, 29:1189–1232.
  * Gal and Ghahramani, (2016) Gal, Y. and Ghahramani, Z. (2016).  Dropout as a bayesian approximation: Representing model uncertainty in deep learning.  In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, ICML’16, page 1050–1059. JMLR.org.
  * Gal et al., (2017) Gal, Y., Hron, J., and Kendall, A. (2017).  Concrete dropout.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 3584–3593, Red Hook, NY, USA. Curran Associates Inc.
  * Graves, (2011) Graves, A. (2011).  Practical variational inference for neural networks.  In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS’11, page 2348–2356, Red Hook, NY, USA. Curran Associates Inc.
  * Hernandez-Lobato and Adams, (2015) Hernandez-Lobato, J. M. and Adams, R. (2015).  Probabilistic backpropagation for scalable learning of bayesian neural networks.  In Bach, F. and Blei, D., editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1861–1869, Lille, France. PMLR.
  * Koenker and Hallock, (2001) Koenker, R. and Hallock, K. F. (2001).  Quantile regression.  Journal of Economic Perspectives, 15(4):143–156.
  * Lakshminarayanan et al., (2017) Lakshminarayanan, B., Pritzel, A., and Blundell, C. (2017).  Simple and scalable predictive uncertainty estimation using deep ensembles.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6405–6416, Red Hook, NY, USA. Curran Associates Inc.
  * Lucena, (2022) Lucena, B. (2022).  Loss functions for classification using structured entropy.  arXiv preprint arXiv:2206.07122.
  * Meinshausen and Ridgeway, (2006) Meinshausen, N. and Ridgeway, G. (2006).  Quantile regression forests.  Journal of machine learning research, 7(6).
  * Petneházi, (2021) Petneházi, G. (2021).  Quantile convolutional neural networks for value at risk forecasting.  Machine Learning with Applications, 6:100096.
  * Rasmussen and Williams, (2005) Rasmussen, C. E. and Williams, C. K. I. (2005).  Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning).  The MIT Press.
  * Rigby and Stasinopoulos, (2005) Rigby, R. A. and Stasinopoulos, D. M. (2005).  Generalized additive models for location, scale and shape.  Journal of the Royal Statistical Society: Series C (Applied Statistics), 54(3):507–554.
  * Rodrigues and Pereira, (2020) Rodrigues, F. and Pereira, F. C. (2020).  Beyond expectation: Deep joint mean and quantile regression for spatiotemporal problems.  IEEE transactions on neural networks and learning systems, 31(12):5377–5389.
  * Schlosser et al., (2018) Schlosser, L., Hothorn, T., Stauffer, R., and Zeileis, A. (2018).  Distributional regression forests for probabilistic precipitation forecasting in complex terrain.  The Annals of Applied Statistics, 13.
  * Shafer and Vovk, (2008) Shafer, G. and Vovk, V. (2008).  A tutorial on conformal prediction.  Journal of Machine Learning Research, 9(3).
  * Titsias, (2009) Titsias, M. (2009).  Variational learning of inducing variables in sparse gaussian processes.  Journal of Machine Learning Research - Proceedings Track, 5:567–574.
  * Yang and He, (2012) Yang, Y. and He, X. (2012).  Bayesian empirical likelihood for quantile regression.  The Annals of Statistics, 40(2):1102–1131.
  * Yang et al., (2016) Yang, Y., Wang, H. J., and He, X. (2016).  Posterior inference in bayesian quantile regression with asymmetric laplace likelihood.  International Statistical Review / Revue Internationale de Statistique, 84(3):327–344.


1032 Technical  Application of EQSA on the VAST Challenge 2019: Mini-Challenge
3 dataset. The main control panel (A) is built as a stacked area chart,
showing the volume of messages according to chosen categories from selection
panel (A1). For the chosen time frame and the chosen categories: Panel (B)
presents topic evolution, panel (C) is a map in which each neighborhood’s
color indicates the number of posts, panel (D) is a network user interaction
and panel (E) is a chart for ranking content creators. Detail-on-demand and
interactive features are also added to support the analysis such as sliding
window with adjustable window size for updating the system and specific
messages on mouse-over events (at the black arrow). In panel (A), three high
red peaks correspond three times the earthquake strikes.

#  EQSA: Earthquake Situational Analytics from Social Media

Huyen N. Nguyen
Department of Computer Science e-mail<EMAIL_ADDRESS>Texas Tech
University  Tommy Dang
Department of Computer Science e-mail<EMAIL_ADDRESS>Texas Tech
University

###### Abstract

This paper introduces EQSA, an interactive exploratory tool for earthquake
situational analytics using social media. EQSA is designed to support users to
characterize the condition across the area around the earthquake zone,
regarding related events, resources to be allocated, and responses from the
community. On the general level, changes in the volume of messages from chosen
categories are presented, assisting users in conveying a general idea of the
condition. More in-depth analysis is provided with topic evolution, community
visualization, and location representation. EQSA is developed with intuitive,
interactive features and multiple linked views, visualizing social media data,
and supporting users to gain a comprehensive insight into the situation. In
this paper, we present the application of EQSA with the VAST Challenge 2019:
Mini-Challenge 3 (MC3) dataset.

Earthquake AnalysisSocial Media Data; Interactive VisualizationVisual
AnalyticsEQSAWordStream; VAST Challenge 2019Mini-Challenge 3

Introduction The earthquake analytics is implemented based on the general
workflow including 1) characterize the overall conditions by events occurred
and resources needed, then 2) discover and explore the story behind these
situations on finer granularities of the data. In particular, the user
utilizes the stream graph to detect the time points with a high volume of
messages (for events or resources, or both), the scope of view can be adjusted
by customizable time frame with a sliding window. The interactive features in
supporting panels characterize the situation with the chosen range, presenting
detail information and assisting users gaining insights into the dataset.

##  1 Design decisions

With a large dataset of messages from a social media platform, we first build
a taxonomy for classifying these messages. For this particular earthquake
dataset, we develop two main categories, which are “event” and “resource”.
Sub-categories for “event” are: earthquake, ground damage, flooding,
aftershock, and fire; sub-categories for “resources” are: water, energy,
medical, shelter, transportation, and food. Each sub-category contains a set
of keywords to determine if a message belong to it or not. One message can
belong to more than one category, e.g., a message can indicate that there are
needs for both water and food. The reasoning for this assumption comes from
the possibility that the meaning of a message can be ambiguous, hence we need
to take all data into account.

For time-series data, the stacked area chart is frequently utilized for
visualizing changes of data over time, for multiple categories. We utilize
this chart type to represent the volume of classified messages and provide an
overall view of the condition. To explore detail, a sliding window on top of
the area chart is provided for brushing.

In terms of exploring specific topics to characterize the condition, there are
many approaches to handle text data. We utilize WordStream [1], a technique
for visualizing evolution of topic over time. Besides the overall or global
trending of terms, this technique represents the local evolution of an
individual topic. Similar approach could also be found from IoTNegViz [2].
Regarding community, a network of users represents the existing clusters,
based on the relationships among users: the source is the sender and target(s)
are the users that are mentioned in the message. This strategy is used to
detect who are the users that have multiple connections in the community;
hence, they are likely to spread the important messages. The location and
ranking of users by amount of content are provided with a map and a horizontal
bar chart.

##  2 System model

Figure EQSA: Earthquake Situational Analytics from Social Media shows the main
components of our system designed for the VAST Challenge 2019: Mini-Challenge
3 dataset111https://vast-challenge.github.io/2019/MC3.html including a stacked
area chart, a WordStream, a geographical map, a network of users and a
horizontal bar chart. Detail-on-demand is provided with tooltip and applied
for the WordStream, network, and bar chart.

The analytics application includes active and interactive components that can
work with dynamic data. The main control panel (A) is built as a stacked area
chart, showing the volume of messages according to chosen categories from
selection panel (A1). The vertical axis shows the number of posts, while the
horizontal axis shows the timeline. A sliding window across the timeline has
expandable width from 1 hour to 31 hours. For each change in main panel (A) –
whether it is adjusting time frame, timestamp or category, all other four
panels (B to E) are updated according to (A).

Panel (B) provides a WordStream, demonstrating the evolution of topics
extracted from the messages’ content. The WordStream consists of two topics:
the keywords within the content of messages and the location of the message.
The thickness of the stream is proportional to the number of posts – the
global trend. Users can also explore the local trend of an individual term and
detail of messages.

Panel (C) is a geographical map, in which the color of each neighborhood
indicates the number of posts. User can use this map for highlighting
corresponding messages from a location in the WordStream and vice versa.

Panel (D) is a network of user interaction. The network demonstrates the
connection between users, through the account mentioning in the content of
messages. Via this network, we can spot which one is the account that has an
essential role in the community.

Panel (E) is an account list for ranking content creators. This chart shows
the accounts that create the largest number of posts. Users can see who writes
many posts and their connection to the community; exploring these points can
help detect irrelevant accounts.

##  3 Implementation

The demonstration link, explanatory video of EQSA, and report for the
challenge of VAST Challenge 2019: Mini-Challenge 3 can be found at our GitHub
page222https://idatavisualizationlab.github.io/VAST2019mc3/.

##  4 Analyzing VAST Challenge 2019: MC3 dataset

Figure 1 shows the visualization with data from five hours after the third
strike. The sliding window in the stacked area chart has a width of 6 hours.
Inside the window, the brown stream - transportation has two major regions,
one arise from right when the earthquake strikes and one towards the end of
the window, showing that issues with transportation occurred within this time,
we can come up with the observation: The problem happens and then it is
addressed.

Figure 1: Five hours after the third strike, the main problem comes from
“bridges” and “route” (terms emphasized in the WordStream), with multiple
notifications from Department of Transportation of St. Himark.

Three blue boxes are highlighted, from 1) The WordStream, 2) The network and
3) The ranking of content creators. In the WordStream, “bridge”, “one-lane”
and “routes” are emphasized, support the observation from the main panel.
Moving on to the network, the node of “dot-sthimark”, the DoT - Department of
transportation of St. Himark, is in large size - an important component of the
community at this time. This means that the community is connecting to the
department for information. On the ranking bar chart, the department provides
25 notifications within 5 hours, a large number comparing to the next ranked
account (only 3). In the map, the neighborhood of Downtown is in the darkest
shade - with biggest number of posts, because the DoT is located in Downtown.
By exploring the detail messages from the department, we discover that the
bridges to get in and out of St.Himark are closed and then re-opened for
safety inspection. This confirmation helps validate the observation mentioned
above.

##  5 Conclusions and future works

This paper proposes an interactive exploratory visualization to analyze
earthquake and characterize the condition from social media posts. The general
view and brushing/linking features support users to explore and discover the
patterns and relating events. The application of this technique to VAST
Challenge 2019: Mini-Challenge 3 dataset also confirms the design decisions of
multiple linked views help users to convey the messages from the perspectives
of community, location and volume of related posts. Future work will focus on
optimization of the overall layout and scalability to big data.

## References

  * [1] T. Dang, H. N. Nguyen, and V. Pham.  WordStream: Interactive Visualization for Topic Evolution.  In J. Johansson, F. Sadlo, and G. E. Marai, eds., EuroVis 2019 - Short Papers. The Eurographics Association, 2019. doi: 10 . 2312/evs . 20191178
  * [2] H. N. Nguyen, V. T. Nguyen, N. V. Nguyen, V. Pham, and T. Dang.  IoTNegViz: An interactive tool for visualizing negative aspects of IoT.  In 2018 IEEE International Conference on Big Data (Big Data), pp. 4565–4568, Dec 2018. doi: 10 . 1109/BigData . 2018 . 8621984