I am reading the paper, Classification in Networked Data: A Toolkit and a Univariate Case Study. And I have a question about the terminology of this paper, on page 938:

enter image description here

Also, see the following equation, on page 947:

enter image description here

Here we have,

  1. $\mathbf{X}$
  2. $X_i$
  3. $x_i$
  4. $\chi$ (not quite the same font with the paper)

I can understand that 1 is the vector of all class labels since it is big and bold. That makes totally sense.

And 2 is an item of (1) on the index $i$, if I understand correctly. However what is the difference between 2 and 3?

4 also makes sense. However, why do we have $c_1, c_2, ...$ etc. instead of basically having $\chi_1$, $\chi_2$, etc.

Is the second equation even correct? Instead of $P(x_i = c~|~N_i)$ don't we need big $X$ like $P(X_i = c~|~N_i)$?

Summary: Can you explain the difference between these 4 X's like explaining to a 10-year-old? (examples are strongly encouraged)

  • 1
    $\begingroup$ I think they wanted to represent $X_i$ like a random variable, whose possible values are denoted as $\mathbf{x}_i$. Does anyone agree with this? $\endgroup$ – user13791 Jun 19 '15 at 7:02
  • $\begingroup$ Item 4 should be $\mathcal{X}$, calligraphic X, rather than the Greek letter chi. $\endgroup$ – Yuval Filmus Jun 19 '15 at 20:13
  • $\begingroup$ @YuvalFilmus It is actually not calligraphic X, it is \mathpzc{X} indeed. However, I couldn't use that library on here. Please see: tex.stackexchange.com/questions/250893/… $\endgroup$ – Sait Jun 19 '15 at 20:25
  • $\begingroup$ It is some kind of X, but definitely not a lower case chi. $\endgroup$ – Yuval Filmus Jun 19 '15 at 20:28

Typically in probability and statistics, capital letters such as $X_i$ are used to denote a random variable, while lower-case letters such as $x_i$ denote realizations of the random variable. Rigorously speaking, you are correct in pointing out that $P(x_i = c|\mathcal{N}_i)$ should have been written as $P(X_i = c|\mathcal{N}_i)$, although this distinction is often overlooked when the underlying random variable is clear from context. For example, the technically correct way of writing $P(x_i|\mathcal{N}_i)$ should be $P(X_i = x_i|\mathcal{N}_i)$, but this slight abuse of notation is often employed and perhaps even preferred for its simplicity.

As for $\mathcal{X}$, careful authors tend to prefer script-letters, such as $X\in\mathcal{X}, Y\in\mathcal{Y}, x\in\mathbb{R}$ for denoting domains/ranges of numbers, random variables, and functions. However, when referring to particular elements of the domain/range, one would still abide by regular typography (lower-case for real numbers and upper-case for random variables) since it would be too much hustle and slightly abusing to use a calligraphic character for a real number.

Keep in mind, however, that these are all typographical conventions used by the community, and different authors may have different preferences depending on the level of exposition and their personal style. For instance, introductory linear algebra textbooks often denote matrices and vectors in bold letters such as $\boldsymbol{A}$ and $\boldsymbol{\beta}$, but this convention is often neglected in higher-level texts and papers$-$it may be unnecessary, not to mention troublesome, to embolden every letter in a book on multivariate analysis or matrix analysis.


The paper is concerned with a graph with attributes. The attributes are $X_1,\ldots,X_n$, and are collectively known as $\mathbf{X}$, which is either the vector $X_1,\ldots,X_n$ or the set $\{X_1,\ldots,X_n\}$.

Each attribute $X_i$ can take a value in the set $\mathcal{X} = \{c_1,\ldots,c_m\}$.

The value of the attribute $X_i$ is denoted $x_i$. There are two possibilities to interpret this distinction:

  1. $X_i$ is the name of the property, and $x_i$ is its value. This seems like a superfluous distinction, since usually we identify the name of a variable with its value.

  2. $X_i$ is a random variable, and $x_i$ is its value in a specific instantiation. This distinction is useful so that we can write expressions of the form $\Pr[X_1 = x_1 | X_2 = x_2]$. There is a difference, however, between $X_i$ and $x_i$: while $X_i$ is the "official" name of the attribute, $x_i$ is just an arbitrary choice for the specific value of $X_i$ in some context.

The equation on page 947 suggests the first interpretation, and that the authors have background in some very formal disciple such as program verification, programming languages or philosophical logic, in which such distinctions are given importance.

  • $\begingroup$ What is the difference between $P(X_i=c~|~N_i)$ and $P(x_i=c~|~N_i)$? $\endgroup$ – Sait Jun 19 '15 at 20:41
  • $\begingroup$ The second is either $0$ or $1$, since $x_i$ is a value rather than a random variable, or so one would hope. On the other hand, your example from page 947 suggests that $X_i$ is the name of a property, and $x_i$ is its value, which seems like a superfluous distinction to me. Perhaps this is a programming language paper? $\endgroup$ – Yuval Filmus Jun 19 '15 at 20:42
  • $\begingroup$ If $P(x_i=c~|~N_i)$ either 0 or 1, equation on page 947 do not makes sense. I think the way you interpret the distinction between x's, is not the same with the authors of the paper. $\endgroup$ – Sait Jun 19 '15 at 20:46
  • $\begingroup$ Yes, I agree. I think that the authors make a useless distinction between $X_i$ and $x_i$, which refer to the same quantity. I don't think that "$X_i = c$" is syntactically valid as far as the authors are concerned. But I could be wrong. $\endgroup$ – Yuval Filmus Jun 19 '15 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.