Computational Intelligence - August 2015 - 33

generated randomly. Experimental results in [5], [6] have shown
that RP can achieve a significant speedup in computation time
with little distortion of pairwise information of data. RP is
emerging as a popular technique, for example, which is applied
to sentiment analysis in [13]. However, as pointed out in [5], if
the distances or similarities are not useful in the original space,
the performance of RP should be suspected. It was proven in
[14] that for any pairwise points in the high-dimensional space,
the similarity measures may become meaningless. This indicates
that for pattern classification tasks, the low-dimensional space
generated by RP may not guarantee the performance. In other
view, without data-based parameter tuning in transformation
vectors, RP may not capture the task-related information
underlying the original data.
As suggested in [6], one of the typical random assignments
for the transformation matrix W is based on an i.i.d sampling
described by:
Z
1
] 1 with prob. 2c
]
w i, j = c [ 0 with prob. 1 - 1
c
]
] -1 with prob. 1
2c
\

(5)

where c is set to d .
To demonstrate the limitation of RP, Fig. 1 shows a simple
4-dimension example in a 2-dimension subspace, where the
positive and negative samples are denoted by circles and triangles, respectively. According to Eq. (5), only two features out of
the original four features will contribute to the creation of a
new dimension in the reduced-dimensional space. The projection vector found by RP will be [1, -1], since the assignment
probabilities of 1 and -1 are equal to 1/4 according to Eq. (5).
The corresponding projected direction is shown in Fig. 1 by
the dashed line. It is obvious that the data projected in the
newly created dimension is not separable. However, the other
projected direction denoted by the solid line can preserve and
even emphasize the discriminative information. The simple
example illustrates the limitation of RP, and this motivates the
development of the "SRP" in this paper.

A. Random Feature Subsampling and
Transformation Vector Learning

In RP, only part of the weights in the transformation matrix
are non-zero. This is equivalent to random subsampling of features in SRP.
Different from RP whose non-zero weights are set to either
1 or -1, the weights for the chosen attributes in transformation vectors of SRP are learned from data. Assuming the number of chosen features is d s (d s is an integer close to d ), the
original data matrix X ! R d # N is reduced to a sub-matrix Z
Xi
with a smaller size of d s # N in the ith iteration. The transformation vector Z
w i ! R ds # 1 maps data Z
X i into the one-dimensional space as follows:
T
hi = Z
wi Z
Xi

where h i ! R 1 # N is a vector, in which each element is the
projection of a sample on the new dimension, and Z
w i is the
transformation vector. We adopt LDA to derive the transformation vector. By following the graph embedding framework
as described in Section II, the transformation vector can be
learned according to Eq. (2), in which matrices L and B can
be calculated as:
SRP : *

_c
_
_c
_
Nc
L = / c = 1 n c (X
x -V
x) (X
x -V
x) T
_ ci
_ ci
N
B = / i = 1 (X
xi - Y
x ) (X
x ) T + hI d s
xi - Y

(7)

where SRP denotes the transformation vector learning, I ds
denotes an identity matrix with a size of d s # d s, U) means the
corresponding value calculated on the randomly selected feature subset from the original high dimension space and h represents the regularization weight. In SRP, LDA is conducted in
the randomly generated low-dimensional subspace of the data,
the computational cost of the learning scheme is much less
than that in the original space. Here, the second term in B of
Eq. (7) represents a regularization term.
The optimization problem in Eq. (2) can be reformulated as
the following generalized eigenvalue problem:
(8)

L{ = mB{

III. Semi-Random Projection for
Dimensionality Reduction

Motivated by the analysis in Section II, we propose a novel
dimensionality reduction framework called Semi-Random
Projection (SRP). We aim to learn a latent space where the
beneficial task-related information can be preserved, while the
running speed is comparable to that of RP. As illustrated in Eq.
(5), approximately d elements in each row of the transformation matrix will be assigned 1 or -1. To reduce the randomness
of RP, these d elements will not be assigned 1 or -1, but
will be learned from the data. The SRP consists of two phases:
one is the random sampling of features and the other is the
transformation vector learning. The term "Semi-Random"
originates from the fact that the first phase is random, while the
second one is not.

(6)

Random Projection

Pos. Data
Neg. Data

Inseparable

Designed Projection
Separable

Figure 1 Illustrations of the possible ineffectiveness of RP.

august 2015 | IEEE ComputatIonal IntEllIgEnCE magazInE

Table of Contents for the Digital Edition of Computational Intelligence - August 2015