Web data often manifest high levels of uncertainty. We focus on categorical Web data and we represent these uncertainty levels as first or second order uncertainty. By means of concrete examples, we show how to quantify and handle these uncertainties using the BetaBinomial and the Dirichlet-Multinomial models, as well as how take into account possibly unseen categories in our samples by using the Dirichlet Process.
The World Wide Web and the Semantic Web offer access to an enormous amount of data and this is one of their major strengths. However, the uncertainty about these data is quite high, due to the multi-authoring nature of the Web itself and to its time variability: some data are accurate, some others are incomplete or inaccurate, and generally, such a reliability level is not explicitly provided.
We focus on the real distribution of these Web data, in particular of
categorical Web data, regardless of whether they are provided by documents, RDF
(see [
We assume that any kind of reasoning that might produce new statements
(e.g. subsumption) has already taken place. Hence, unlike for instance Fukuoe
et al. (see [
First we will describe the scope of these models (section 2), second we will introduce the concept of conjugate prior (section 3), and then two classes of models: parametric (section 4) and non-parametric (section 5). Finally we will discuss the results and provide conclusions (section 6). 2 2.1
Uncertainty is often an issue in case of empirical data. This is especially the case with empirical Web data, because the nature of the Web increases the relevance of this problem but also offers means to address it, as we will see in this section. The relevance of the problem is related to the utilization of the mass of data that any user can find over the network: can one safely make use of these data? Lots of data are provided on the Web by entities the reputation of which is not surely known. In addition to that, the fact that we access the Web by crawling, means that we should reduce our uncertainty progressively, as long as we increment our knowledge. Moreover, when handling our samples it is often hard to determine how representative such a sample is of the entire population, since often we do not own enough sure information about it.
On the other hand, the huge amount of Web data gives also a solution for managing this reliability issue, since it can hopefully provide the evidence necessary to limit the risk when using a certain data set.
Of course, even within the Web it can be hard to find multiple sources asserting about a given fact of interest. However, the growing dimension of the Web makes it reasonable to believe in the possibility to find more than one data set about the given focus, at least by means of implicit and indirect evidence.
This work aims showing how it is possible to address the described issues by handling such empirical data, categorical empirical data in particular, by means of the Beta-Binomial, Dirichlet-Multinomial and Dirichlet Process models. 2.2
Our approach will need to be quite elastic in order to cover several issues, as described below. The non-triviality of the problem comes in a large part from the impossibility to directly handle the sampling process from which we derive our conclusions. The requirements that we will need to meet are:
cremental, in order to reflect the process of data acquisition: as long as we collect more data (even by crawling), our knowledge will reflect that increase. Prudence It should derive prudent conclusions given all the available information. In case not enough information is available, the wide range of possible conclusions derivable will clearly make it harder to set up a decision strategy. Cope with biased sampling The model should deal with the fact that we are not managing a supervised experiment, that is, we are not randomly sampling from the population. We are using an available data set to derive safe consequences, but these data could, in principle, be incomplete, inaccurate or biased, and we must take this into account.
The data we have at our disposal may have been drawn from diverse distributions, so we can’t use the central limit theorem, because it relies on the fact that the sequence of variables is identically distributed. This implies the impossibility to make use of estimators that approximate by means of the Normal distribution.
can change over time, and this variability has to be properly accounted.
quantify the intrinsic uncertainty in the data provided by the reasoning layer, and, in turn, to provide to higher order layers (time series analysis, decision strategy, trust, etc.) reliable data and/or metadata. 2.3
The models adopted here are applied in a variety of fields. For the parametric
models, examples of applications are: topic identification and document
clustering (see [
Also non-parametric models are applied in a wide variety of fields. Examples
of these applications include document classification [
As to our knowledge, the chosen models have not been applied to categorical Web data yet. We propose to adopt them, because, as the following sections will show, they fit the requirements previously listed. 3
To tackle the requirements described in the previous section, we adopt some bayesian parametric and non-parametric models in order to be able to answer questions about Web data.
Conjugate priors (see [
P (A|B) =
P (B|A) ∗ P (A)
P (B) (1) This theorem describes how it is possible to compute the posterior probability, P (A|B), given the prior probability of our data, P (A), the likelihood of the model, given the data, P (B|A), and the probability of the model itself, P (B).
When dealing with continuous probability distributions, the computation of
the posterior distribution by means of Bayes theorem can be problematic, due to
the need to possibly compute complicated integrals. Conjugate priors allow us
to overcome this issue: when prior and posterior probability distributions belong
to the same exponential family, the posterior probability can be obtained by
updating the prior parameters with values depending on the observed sample
(see also [
p ∼ Q(α0) where α0 = f (α, obs), for some function f . For example, the Beta distribution is the conjugate of the Binomial distribution. This means that the Beta, shaped by the prior information and by the observations, defines the range within which the parameter p of the Binomial will probably be situated, instead of directly assigning to it the most likely value. Other examples of conjugate priors are: Dirichlet, which is conjugate to the Multinomial, and Gaussian, which is conjugate to itself.
Conjugacy guarantees ease of computation, which is a desirable characteristic when dealing with very big data sets as Web data sets often are. Moreover, the model is incremental, and this makes it fit the crawling process with which Web data are obtained, because crawling, in turn, is an incremental process. Both the heterogeneity of the Web and the crawling process itself increase the uncertainty of Web data. The probabilistic determination of the parameters of the distributions adds a smoothing factor that helps to handle this uncertainty. 4
In this section we will handle situations where the number of categories is known
a priori, by using the Dirichlet-Multinomial model and its special case with two
categories, i.e. the Beta-Binomial model [
Suppose that a museum has to annotate a particular item I of its collection. Suppose further, that the museum does not have expertise in the house about that particular subject and, for this reason, in order to correctly classify the item, it seeks judgments from outside people, in particular from Web users that provide evidence of owning the desired expertise.
After having collected judgements, the museum faces two possible classifications for the item, C1 and C2. C1 is supported by four experts, while C2 by only one expert. We can use these numbers to estimate a probability distribution that resembles the correct distribution of C1 and C2 among all possible annotations.
A basic decision strategy that could make use of this probability distribution, could accept a certain classification only if its probability is greater or equal to a given threshold (e.g. 0.75). If so, the Binomial distribution representing the sample would be treated as representative of the population, and the sample proportions would be used as parameters of a Bernoulli distribution about the possible classifications for the analyzed item: P (class(I) = C1) = 4/5 = 0.8, P (class(I) = C2) = 1/5 = 0.2. (A Bernoulli distribution describes the possibility that one of two alternative events happens. One of these events happens with probability p, the other one with probability 1 − p. A Binomial distribution with parameters n, p represents the outcome of a sequence of n Bernoulli trials having all the same parameter p.)
However, this solution shows a manifest leak. It provides to the decision strategy layer the probabilities for each of the possible outcomes, but these probabilities are based on the current available sample, with the assumption that it correctly represents the complete population of all existing annotations. This assumption is too ambitious. (Flipping a coin twice, obtaining a heads and a tails, does not guarantee that the coin is fair, yet.)
In order to overcome such a limitation, we should try to quantify how much
we can rely on the computed probability. In other words, if the previously
computed probability can be referred as a “first order” probability, what we need to
compute now is a “second order” probability (see [
By analyzing the shape of the conjugate prior Beta(5,2), we can be certain enough about the probability of C1 being safely above our acceptance threshold. In principle, our sample could be drawn by a population distributed with a 40% − 60% proportion. If so, given the threshold of acceptance of 0.75, we would not be able to take a decision based on the evidence. However, the quantification of that proportion would only be possible if we know the population. Given that we do not have such information, we need to estimate it, by computing (3), where we can see how the probability of the parameter p being above the threshold is less than 0.5. This manifests the need for more evidence: our sample suggests to accept the most popular value, but the sample itself does not guarantee to be representative enough of the population.
P (p ≥ 0.75) = 0.4660645, p ∼ Beta(5, 2) (3)
Finally, these considerations could also be done on the basis of the Beta-Binomial distribution, which is a probability distribution representing a Binomial which parameter p is randomly drawn from a Beta distribution. The Beta-Binomial summarizes model (2) in one single function (4).
We can see from Table 2 that the expected proportion of the probability distribution approaches the ratio of the sample (0.8), as the sample size grows. If so, the sample is regarded as a better representative of the entire population and the Beta-Binomial, as sample size grows, will converge to the Binomial representing the sample (see Fig. 1).
#C1 #C2 1 http://semanticweb.cs.vu.nl/lop
CCS website.2 Attack descriptions are provided, in particular covering their type (boarding, hijacking, etc.), place, time, as well as ship type.
Data about attacks is provided in RDF format, and a SPARQL (see [
However, directly estimating the
probability of a new attack given the 0.5
dataset, would not be correct, because,
although derived from data published 0.4
from an official entity like the Chamber )0.3
of Commerce, the reports are known to (XP
be incomplete. This fact clearly affects 0.2
the computed proportions, especially
because it is likely that this incom- 0.1
pleteness is not fully random. There are 0.0
ttpiaaccruktliactryuplzaeorsnoersreaaastrotenascnkowsthhryaeppppoearnrtteinidcg.uliTanrhpeaarert--- rcanhoed tttaepdem rboaded ifred_nopuAttacjickhaedk typeroedoms iitfcse_pnoed robebd iicssspuou ryeudnaw
fore, beyond the uncertainty about the
type of next attack happening (first or- Fig. 2: Attack type proportion and
der uncertainty), there will be an addi- confidence intervals
tional uncertainty order due to the
uncertainty in the proportions themselves. This can be handled by a parametric
model that will allow to estimate the parameters of a Multinomial distribution.
The model that we are going to adopt is the multivariate version of the model
described in section 4, that is, the Dirichlet-Multinomial model (see [
∀p ∈ param, CIp = (p − θ1, p + θ2), P (p − θ1 ≤ p ≤ p + θ2) = 0.95 (6) 5
In some situations, the previously described parametric models do not fit our needs, because they set a priori the number of categories, but this is not always possible. In the previous example, we considered and handled uncertainty due to the possible bias of our sample. The proportions showed by our sample could be barely representative of the entire population because of a non-random bias, and therefore we were prudent in estimating densities, even not discarding entirely those proportions. However, such an approach lacks in considering another type of uncertainty: we could not have seen all the possible categories and we are not allowed to know all of them a priori. Our approach was to look for the prior probability to our data in the n-dimensional simplex, where n is the number of categories, that is, possible attack types. Now such an approach is no more sufficient to address our problem. What we should do is to add yet another hierarchical level and look for the right prior Dirichlet distribution in the space of the probability distributions over probability distributions (or space of simplexes). Non-parametric models differ from parametric models in that the model structure is not specified a priori but is instead determined from data. The term non-parametric is not meant to imply that such models completely lack parameters, but that the number and nature of the parameters are flexible and not set in advance. Hence, these models are also called “distribution free”. 5.1
Dirichlet Processes [
Xn = (
Xk∗ new draw from H with probability numn−1(Xk∗) n−1+α α with probability n−1+α (7) where H is the continuous probability measure (“base distribution”) from which new values are drawn, representing our prior best guess. Each draw from H will return a different value with probability 1. α is an aggregation parameter, inverse of the variance: the higher α, the smaller the variance, which can be interpreted as the confidence value in the base distribution H: the higher the α value is, the more the Dirichlet Process resembles H. The lower the α is, the more the value of the Dirichlet Process will tend to the value of the empirical distribution observed. Each realization of the process is discrete and is equivalent to a draw from a Dirichlet distribution, because, if (8) (9) (10) (11)
G ∼ DP (H, α) is a Dirichlet Process, and {B}in=1 are partitions of S, we have that (G(B1)...G(Bn)) ∼ Dirichlet(αH(B1)...αH(Bn))
If our prior Dirichlet Process is (8), given (9) and the conjugacy between
Dirichlet and Multinomial distribution, our posterior Dirichlet Process (after
having observed n values θi) can be represented as one of the following two
representations:
(G(B1)...G(Bn))|θ1...θn ∼ Dirichlet(αH(B1) + nθ1 ...αH(Bn) + nθn )
G | θ1...θn ∼ DP
where δθi is the Dirac delta function (see [
The Dirichlet process, starting from a (possibly non-informative) “best guess”, as long as we collect more data, will approximate the real probability distribution. Hence, it will correctly represent the population in a prudent (smoothed) way, exploiting conjugacy like the Dirichlet-Multinomial model, that approximates well the real Multinomial distribution only with a large enough data set (see section 4). The improvement of the posterior base distribution is testified by the increase of the α parameter, proportional to the number of observations.
We aim at predicting the type distributions of incoming attack events. In order
to build an “infinite category” model, we need to allow for event types to be
randomly drawn from an infinite domain. Therefore, we map already observed
attack types with random numbers in [0..1] and, since all events are a priori
equally likely, then new events will be drawn from the Uniform distribution,
U (0, 1), that is our base distribution (and is a measure over [0..1]). The model
then is:
– type1 ∼ DP (U (0, 1), α): the prior over the first attack type in region R;
– attack1 ∼ Categorical(type1): type of the first attack in R during yeary.
After having observed attack1...n during yeary, our posterior process becomes:
typen+1 | attack1...n ∼ DP
where α is a low value, given the low confidence in U (0, 1), and typen+1 is the
prior of attackn+1, that happens during yeary+1. A Categorical distribution is
a Bernoulli distribution with more than two possible outcomes (see Section 4).
Results Focusing on each region at time, we simulate all the attacks that
happened there in yeary+1. Names of new types generated by simulation are matched
to the actual yeary+1 names, that do not occur in yeary, in order of decreasing
probability. The simulation is compared with a projection of the proportions of
yearn over the actual categories of yearn+1. The comparison is made by
measuring the distance of our simulation and of the projection from the real attack types
proportions of yeary+1 using the the Manhattan distance (see [
● 2007
● 2008
Years (a) Errors 0 1 − 2 −
Projection better than Simulation ● ● The fact that our proposed models fit well with the expressed requirements is apparently a good hypothesis to continue to explore, because we have seen how it is possible to handle such uncertainty and to transform it in a smoothing factor of the probability distribution that we estimate given our evidence, by allowing the parameters of our distributions to be probabilistically determined. Moreover, we have built models able to produce reliable forecasts also when not every class is know a priori. We also provided case study validation of the suggested models.
The set of models will be extended to deal with concrete domain data (e.g.
time intervals, measurements), for instance, by adopting the Normal or the
Poisson Process (see [