# A Linear Time and Space Local Point Cloud Geometry Encoder
via Vectorized Kernel Mixture (VecKM)

Dehao Yuan  Cornelia Fermüller  Tahseen Rabbani  Furong Huang  Yiannis
Aloimonos

###### Abstract

We propose VecKM, a novel local point cloud geometry encoder that is
descriptive, efficient and robust to noise. VecKM leverages a unique approach
by vectorizing a kernel mixture to represent the local point clouds. Such
representation is descriptive and robust to noise, which is supported by two
theorems that confirm its ability to reconstruct and preserve the similarity
of the local shape. Moreover, VecKM is the first successful attempt to reduce
the computation and memory costs from $O(n^{2}+nKd)$ to $O(nd)$ by sacrificing
a marginal constant factor, where $n$ is the size of the point cloud and $K$
is neighborhood size. The efficiency is primarily due to VecKM’s unique
factorizable property that eliminates the need of explicitly grouping points
into neighborhoods. In the normal estimation task, VecKM demonstrates not only
100x faster inference speed but also strongest descriptiveness and robustness
compared with existing popular encoders. In classification and segmentation
tasks, integrating VecKM as a preprocessing module achieves consistently
better performance than the PointNet, PointNet++, and point transformer
baselines, and runs consistently faster by up to 10x.

††1Department of Computer Science. University of Maryland, College Park.
Correspondence to Dehao Yuan<EMAIL_ADDRESS>code is available at
github.com/dhyuan99/VecKM.

Machine Learning, ICML

##  1 Introduction

Figure 1: Our proposed VecKM encoding is descriptive, robust to noise, and
efficient in both computation and memory usage. Upper Left: Raw VecKM
encodings, _without any training_ , already capture rich geometric features
such as orientations and shapes. Lower Left: Under varying levels of noise,
VecKM encodings remain highly consistent. Upper Right: Unlike existing
encoders that face a computation and memory bottleneck with complexities
$O(n^{2}+nKd)$, VecKM only costs $O(nd)$ time and space. Lower Right: VecKM is
10x$\sim$100x faster than existing encoders in wall-clock time and scalable to
large point cloud inputs.

The ubiquity and low cost of 3D sensors have drawn increased interest in the
usage of three-dimensional point clouds for tasks such as autonomous driving
(Chen et al., 2020), robotics (Zampogiannis et al., 2019), and remote sensing
(Lu et al., 2020).

In point cloud analysis, encoding local geometry is a fundamental step. In
both low-level tasks such as feature matching and normal estimation, and high-
level tasks such as classification, segmentation, and detection, encoding
local geometry is usually required before passing the point cloud into any
deep network. Much effort has been placed into the design of local geometry
encoders, which can be loosely divided into two categories: hand-crafted
features and learnable encoders. Hand-crafted features (Han et al., 2023) are
manually defined features based on domain expertise, and learnable encoders
require computationally expensive processing through trainable structures such
as multi-layer perceptrons (MLP) (Qi et al., 2017a; Ma et al., 2022) or
convolutions (Li et al., 2018; Thomas et al., 2019).

These local geometry encoders follow a similar pipeline. They first group the
input point cloud into neighborhoods and then process each neighborhood
individually. As illustrated in Figure 1 (upper right), the pipeline involves
computing the mutual distance between points. Then for each point, a number of
$K$ points are sampled from its neighborhood, and MLP or convolution are used
to transform the sampled neighborhood. In this pipeline, grouping the point
cloud into neighborhoods requires $O(n^{2})$ time and space, and the MLP-based
architectures, in particular, requires a sequence of MLPs to transform $nK$
vectors and reaches an intermediate stage of $(n,K,d)$. The computations
result in bottlenecks in both computation and memory. Consequently, they
usually resort to downsampling the point cloud or the local neighbors, which
leads to information loss.

In this work, we address the computation and memory bottlenecks faced by the
existing encoders, reducing the computation and memory cost from
$O(n^{2}+nKd)$ to $O(nd)$. Our approach is inspired by Frady et al. (2022);
Yuan et al. (2023), which converts continuous functions into fixed-length
vectors. Building on this concept, we introduce VecKM, which conceptualizes
local point clouds as kernel mixtures (a form of continuous function) and
vectorizes them. This vectorized representation of kernel mixtures, being the
local geometry encoding, is proved to be reconstructive and isometric to the
original local point cloud. This theorem ensures the descriptiveness of the
encoding. Moreover, VecKM is robust to noise due to the robust nature of
kernel mixtures. One essential advantage of VecKM is its factorizable
property, which not only eliminates the need of explicitly grouping the
neighborhoods but also reuses many computations, which reduces the computation
and memory cost significantly.

The VecKM encodings can subsequently be passed to deep cloud point models,
such as PointNet++ (Qi et al., 2017b) and transformers (Vaswani et al., 2017).
VecKM’s light representation and ease of computation significantly speed up
the inference, while still achieving on-par or improved performance than other
networks in classification and segmentation tasks. Our contributions are
summarized below:

  * •

We present VecKM, a local geometry encoder that is descriptive, robust, and
only costs $O(nd)$ time and space. This is achieved through a novel approach
of vectorizing kernel mixtures, coupled with its unique factorizability. VecKM
is the only existing local geometry encoder that costs linear time and space.

  * •

We provide a solid theoretical foundation for VecKM’s descriptiveness,
efficiency, and noise robustness.

  * •

We evaluate our VecKM on multiple point cloud tasks. In normal estimation,
VecKM is $>100$x faster and achieves $>16\%$ lower error than other widely-
used learnable encoders and demonstrates the strongest robustness against
different types of data corruption. In classification and part segmentation,
integrating VecKM with PointNet, PointNet++ and transformers significantly
speeds up inference time by up to $9.5$x, while still achieving consistently
better performance. In semantic segmentation, VecKM improves the PointNet++
baseline by 3.4% mIoU and improves the point transformer baseline by 20%
inference speed.

##  2 Related Work

###  2.1 Local Geometry Encoder

The initial processing of raw point cloud data, an unordered collection of
points, typically begins with the extraction of local geometric features. This
step is essential before any further processing can occur. Existing methods
for encoding local geometry can generally be categorized into two groups:
hand-crafted features and learning-based encoders. All the encoders require
grouping point clouds into neighborhoods.

Hand-Crafted Features  are manually defined features that describe the local
geometry. Domain expertise of the point cloud dataset and the task of interest
are usually needed for constructing those features. We refer the reader to Han
et al. (2023) for a comprehensive survey of hand-crafted features.

Histogram-based features represent a significant category within hand-crafted
features, which transform the local point cloud into specific coordinate
systems such as Cartesian (Prakhya et al., 2017), polar (Ge, 2016), star-
shaped (Steder et al., 2010). Then the coordinate system is quantized, and the
local point cloud is binned accordingly. The resulting feature is formed by
concatenating the histograms. While these features induce minimal information
loss, the resolution of the point cloud affects the quality of such features.

Statistics-based features form another category within hand-crafted features,
which construct statistical descriptors from geometric parameters. Examples
include eigenvalues (Vandapel et al., 2004), covariance (Fehr et al., 2012),
normal orientation distribution (Triebel et al., 2006), angles between normals
(Rusu et al., 2008), local umbrella shapes (Ran et al., 2022). These types of
features can include rich geometric features and easily achieve rotation
invariance. But they tend to be lossy and are often not robust to noise and
variations in density.

Learning-Based Encoders transform the raw local point clouds into fixed-length
vectors through trainable networks. These encoders can be broadly categorized
into MLP-based encoders and convolution-based encoders.

MLP-based encoders use MLPs to transform the local point cloud and use max-
pooling to cast the point cloud into a fixed-length vector. These operations
can be performed repeatedly to retrieve deep point cloud features (Qi et al.,
2017b). Examples of MLP-based encoders include PointNet (Qi et al., 2017a),
CurveNet (Xiang et al., 2021), PointMLP (Ma et al., 2022). MLP-based encoders
are usually faster to compute than convolution-based ones. But they require
computing an intermediate step of $(n,K,d)$ to perform the max-pooling
operation. So they induce high memory cost when the input size $n$ and the
neighborhood size $K$ is large.

Convolution-based encoders use point or edge convolution to transform the
local point cloud into a fixed-length vector. Examples include KPConv (Thomas
et al., 2019), PointCNN (Li et al., 2018), PointConv (Wu et al., 2019),
SpiderCNN (Xu et al., 2018). Convolution-based encoders are more expensive to
compute, but they do not encounter the memory bottleneck faced by MLP-based
encoders.

VecKM is both a hand-crafted feature and a learning-based encoder. It not only
captures the geometric features, but also faithfully encodes the point
distribution. This duality allows VecKM to leverage the strengths of both
approaches.

###  2.2 Point Cloud Architectures

We describe two major families of architectures for processing point clouds:
PointNet++ and transformers. VecKM, as to be shown later, is compatible with
both architectures.

PointNet++ (Qi et al., 2017b) utilizes hierarchical neural layers to capture
fine geometric details at multiple scales. Within each layer, PointNets are
utilized to transform the features. Many works have been done to improve the
architecture. Examples include using different learning-based local geometry
encoders, as introduced in Section 2.1, and improving the neighborhood
grouping strategies (Xiang et al., 2021; Yan et al., 2020). PointNet++ and its
derivatives tend to be faster than but less accurate than transformers.

Transformers. Given their success on a wide variety of vision tasks, along
with their tolerance to permutations, many transformer-based models have been
proposed for 3D point cloud processing. Models such as PCT (Guo et al., 2021),
3CROSSNet (Han et al., 2022), and Point-BERT (Yu et al., 2022) apply
transformer blocks to individual points to extract global information. Other
models such as Point Transformer (PT) (Zhao et al., 2021), Pointformer (Pan et
al., 2021), and the Stratified Transformer (Lai et al., 2022) process local
patches to extract local feature information. However, transformer-based
models can suffer from computational and memory bottlenecks (Han et al., 2023)
as the attention map increases in size.

##  3 Methodology

###  3.1 Problem Definition and Main Theorems

Problem Definition. Let the input point cloud be
$X=\\{\mathbf{x}_{k}\\}_{k=1}^{n}$. Denote the centerized neighbor of the
point $\mathbf{x}_{k}$ as
$\mathfrak{N}(\mathbf{x}_{k}):=\\{\mathbf{x}_{j}-\mathbf{x}_{k}:||\mathbf{x}_{j}-\mathbf{x}_{k}||<r\\}$.
The output is the set of dense local geometric features
$G=\\{\mathbf{g}_{k}\\}_{k=1}^{n}$, where
$\mathbf{g}_{k}=E\big{(}\mathfrak{N}(\mathbf{x}_{k})\big{)}\in\mathbb{C}^{d}$.
We look for an encoder $E$ that maps the local point cloud into a fixed-length
vector, which “captures the underlying shape” sampled by the point cloud.

To better formalize the heuristic expression of “capturing the underlying
shape”, we think of the local shape around the point $x_{k}$ as a distribution
function $f_{k}:\mathbb{R}^{3}\rightarrow\mathbb{R}^{+}$, where
$f_{k}(\mathbf{x})$ gives the probability density that a point $\mathbf{x}$ is
on the local shape. We then think of the centerized local point cloud
$\mathfrak{N}(\mathbf{x}_{k})$ as random samples from the distribution
function $f_{k}$. We expect the local point cloud encoding
$E\big{(}\mathfrak{N}(\mathbf{x}_{k})\big{)}\in\mathbb{C}^{d}$ to represent
the distribution function $f_{k}$. For a good representation, we consider two
natural properties: 1. the distribution function can be reconstructed from the
encoding; 2. the correlation of the distribution functions is preserved by the
similarity of the encodings.

Pointwise Local Geometry Encoding. Under the problem definition, we present
the formula for encoding the local geometry around a single point. Unless
specified otherwise, all input points $\mathbf{x}_{j}$ are assumed to be
three-dimensional.

######  Theorem 1 (Pointwise Local Geometry Encoding).

Denote the neighbors of the point $\mathbf{x}_{0}$ as
$\mathfrak{N}(\mathbf{x}_{0}):=\\{\mathbf{x}_{k}-\mathbf{x}_{0}\\}_{k=1}^{n}$.
The local geometry encoding of $\mathbf{x}_{0}$ is computed as

$E_{\mathbf{A}}\big{(}\mathfrak{N}(\mathbf{x}_{0})\big{)}=\frac{1}{n}\sum_{k=1}^{n}\exp\big{(}i(\mathbf{x}_{k}-\mathbf{x}_{0})\mathbf{A}_{3\times
d}\big{)}\vspace{-18pt}$ (1)

where $i$ is the imaginary unit and $\mathbf{A}\in\mathbb{R}^{3\times d}$ is a
fixed random matrix where each element follows the normal distribution
$\mathcal{N}(0,\alpha^{2})$. As to be shown in Section 3.2,
$E_{\mathbf{A}}\big{(}\mathfrak{N}(\mathbf{x}_{0})\big{)}$ is fundamentally
vectorizing a kernel mixture about $\mathfrak{N}(\mathbf{x}_{0})$, so we name
the encoding VecKM. Next, we present two propositions that claim VecKM
encoding produces a good representation of the local shape:

######  Proposition 1 (Reconstruction).

WLOG, let $f$ be the distribution function characterizing the local shape of
$\mathbf{0}$, $X=\\{\mathbf{x}_{k}\\}_{k=1}^{n}$ be the random samples drawn
from the distribution function $f$, and
$\mathbf{g}_{n}=\frac{1}{n}\sum_{k=1}^{n}\exp\big{(}i\mathbf{x}_{k}\mathbf{A}\big{)}$
be the VecKM encoding given by Eqn. (1). $\mathbf{A}\in\mathbb{R}^{3\times d}$
is a fixed matrix whose entries are drawn from $\mathcal{N}(0,\alpha^{2})$.
Then at all points $\mathbf{x}$ where $f(\mathbf{x})$ is continuous, as
$n\to\infty$ and $\alpha^{2}\to 0$,

$\langle\mathbf{g}_{n},\exp(i\mathbf{x}\mathbf{A})\rangle\rightarrow
f(\mathbf{x})$

where $\langle\cdot,\cdot\rangle$ denotes the inner product between two
complex vectors. The proposition states that under a suitable selection of the
parameter $\alpha^{2}$, the distribution function $f$ can be approximately
reconstructed from the VecKM encoding $\mathbf{g}_{n}$.

######  Proposition 2 (Similarity Preservation).

Let $f_{1}$, $f_{2}$ be two distribution functions characterizing two local
shapes and $X_{1}$, $X_{2}$ be the random samples from the two distribution
functions. $\mathbf{g}_{1}$, $\mathbf{g}_{2}$ are the VecKM encodings given by
Eqn. (1) with $X_{1}$, $X_{2}$ as inputs. $\mathbf{A}$ is a fixed matrix whose
entries are drawn from $\mathcal{N}(0,\alpha^{2})$. Then the function
similarity is preserved by the VecKM encodings: as $n\to\infty$ and
$\alpha^{2}\to 0$,

$\displaystyle\langle\mathbf{g}_{1},\mathbf{g}_{2}\rangle\rightarrow\langle
f_{1},f_{2}\rangle=\int_{\mathbb{R}^{3}}f(x)g(x)dx$

where $\langle\cdot,\cdot\rangle$ denotes the inner product between two
complex vectors. The proposition states that under a suitable selection of the
parameter $\alpha^{2}$, the correlation of functions (i.e. shapes) is
approximately preserved by the VecKM encoding.

In brief, Theorem 1 presents the formula for encoding the local geometry
around a single point. Proposition 1, 2 assert that VecKM well represents the
underlying local geometry. In Section 3.2, we will explain the mechanism
behind Theorem 1 and prove Proposition 1, 2 in detail.

Dense Local Geometry Encoder With Eqn. (1), we can already compute the local
geometry encoding for each point individually by grouping their neighborhoods.
However, VecKM has a unique factorizable property that enables us to reuse
computations and eliminate the intermediate step:

######  Theorem 2 (Dense Local Geometry Encoding).

Denoting the input point cloud as a matrix $\mathbf{X}_{n\times
3}=\left[\mathbf{x}_{1};\mathbf{x}_{2};\cdots;\mathbf{x}_{n}\right]$, the
dense local geometry encoding $\mathbf{G}_{n\times d}$ is computed by

$\displaystyle\begin{split}\mathcal{A}_{n\times d}&=\exp(i\mathbf{X}_{n\times
3}\mathbf{A}_{3\times d})\\\ \mathcal{B}_{n\times
p}&=\exp(i\mathbf{X}_{n\times 3}\mathbf{B}_{3\times p})\\\ \mathbf{G}_{n\times
d}&=normalize\big{(}(\mathcal{B}\times\mathcal{B}^{H}\times\mathcal{A})\>./\>\mathcal{A}\big{)}\end{split}$
(2)

where $\mathbf{A}$ and $\mathbf{B}$ are two random fixed matrix whose entries
are drawn from $\mathcal{N}(0,\alpha^{2})$ and $\mathcal{N}(0,\beta^{2})$.
$\times$ denotes the matrix multiplication, and $./$ denotes the elementwise
division. As to be explained in Section 3.3, computing the dense local
geometry encoding using Eqn. (2) has almost the same effect as computing the
pointwise local geometry encoding using Eqn. (1). However, Eqn. (2) only takes
$O(npd)$ time and $O(np+nd)$ space to compute, where $p$, to be shown, is a
marginal factor. The computation graph is visualized in Figure 1 (upper
right).

Structure of Proof. In Section 3.2, we explain the mechanism behind Theorem 1
and prove our assertion that VecKM produces a good representation of the local
geometry. In Section 3.3, we explain why Eqn. (2) has almost the same effect
as Eqn. (1) and the mechanism behind Theorem 2. In Section 3.4, we introduce
how to incorporate VecKM encodings into deep point cloud architectures.

###  3.2 Pointwise Local Geometry Encoder

In this section, we introduce why VecKM (Eqn. 1) produces a good
representation of the local geometry. The key idea, as illustrated in Figure
2, is that (i) VecKM vectorizes a Gaussian kernel mixture associated with the
local point cloud, where (ii) the associated kernel mixture can approximate
the local shape distribution function. Therefore, VecKM effectively represents
the local shape. We will separately validate assertion (i) and (ii).

(i) VecKM vectorizes a kernel mixture. We first present a lemma stating that
VecKM embodies a Gaussian kernel $\mathcal{G}$:

######  Lemma 1 (VecKM embodies a Gaussian kernel).

Let $\mathbf{x},\mathbf{y}\in\mathbb{R}^{3}$,
$\mathbf{A}\in\mathbb{R}^{3\times d}$. All elements in $\mathbf{A}$ are drawn
from normal distribution $\mathcal{N}(0,\alpha^{2})$. Then as $d\to\infty$,

$\displaystyle\begin{split}\frac{1}{d}\langle
e^{i\mathbf{x}\mathbf{A}},e^{i\mathbf{y}\mathbf{A}}\rangle\rightarrow\mathcal{G}_{\alpha}(\mathbf{x},\mathbf{y}):=\exp\big{(}-\frac{\alpha^{2}||\mathbf{x}-\mathbf{y}||^{2}}{2}\big{)}\end{split}$

Lemma 1 is a corollary from the Bochner’s theorem (Bochner, 2005; Rahimi &
Recht, 2007). We provide a detailed proof in Appendix A. Importantly, the
Gaussian kernel $\mathcal{G}$ is approximated by the inner product of finite-
length vectors $e^{i\mathbf{x}\mathbf{A}}$ and $e^{i\mathbf{y}\mathbf{A}}$.
This approximation is important in vectorizing the kernel mixture and ensures
the reconstructive and isometric properties in Proposition 1, 2, as detailed
in the subsequent two lemmas. Unless otherwise specified, all entries in
$\mathbf{A}$ are drawn from $\mathcal{N}(0,\alpha^{2})$ and $\mathcal{G}$
means $\mathcal{G}_{\alpha}$. The proofs are borrowed from Frady et al.
(2022).

Figure 2: Theoretical outline of VecKM illustrated by 2d shapes. A point
cloud, sampled from a shape distribution function, is associated with a
Gaussian kernel mixture and a corresponding VecKM encoding, where the VecKM
encoding is proved to be reconstructive and isometric to the Gaussian kernel
mixture. Since the Gaussian kernel mixture can approximate the shape function,
the VecKM encoding yields a good representation of the shape.

######  Lemma 2 (Reconstruction).

Let $\mathbf{g}=\frac{1}{n}\sum_{k=1}^{n}\exp(i\mathbf{x}_{k}\mathbf{A})$ be
the VecKM encoding, where all entries in $\mathbf{A}\in\mathbb{R}^{3\times d}$
are drawn from $\mathcal{N}(0,\alpha^{2})$.
$\hat{f}(\mathbf{x})=\frac{1}{n}\sum_{k=1}^{n}\mathcal{G}_{\alpha}(\mathbf{x},\mathbf{x}_{k})$
be the associated Gaussian kernel mixture. Then
$\langle\exp(i\mathbf{x}\mathbf{A}),\mathbf{g}\rangle\rightarrow\hat{f}(\mathbf{x})$
as $d\to\infty$.

The lemma states that the Gaussian kernel mixture can be approximately
reconstructed from the VecKM encoding $\mathbf{g}$, which theoretically shows
that VecKM is equivalent to the Gaussian kernel mixture when $d$ is large. The
lemma is readily derived from the linearity of the inner product:

$\displaystyle\langle\exp(i\mathbf{x}\mathbf{A}),\mathbf{g}\rangle$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}\langle\exp(i\mathbf{x}\mathbf{A}),\exp(i\mathbf{x}_{k}\mathbf{A})\rangle$
$\displaystyle\rightarrow\frac{1}{n}\sum_{k=1}^{n}\mathcal{G}(\mathbf{x},\mathbf{x}_{k})=\hat{f}(\mathbf{x})$

######  Lemma 3 (Similarity Preservation).

Let $\mathbf{g}_{1}$, $\mathbf{g}_{2}$ be two VecKM encodings and $f_{1}$,
$f_{2}$ be their associated Gaussian kernel mixtures. Then
$\langle\mathbf{g}_{1},\mathbf{g}_{2}\rangle\rightarrow\langle
f_{1},f_{2}\rangle$ as $d\to\infty$.

The lemma states that the VecKM encoding preserves the similarity/correlation
between kernel mixtures, which further verifies that the encoding is not only
equivalent but also isometric to the Gaussian kernel mixture. The lemma is
derived from the linearity of integration:

$\displaystyle\langle f_{1},f_{2}\rangle$
$\displaystyle=\int_{\mathbf{x}\in\mathbb{R}^{3}}\Big{(}\frac{1}{n}\sum_{p=1}^{n}\mathcal{G}(\mathbf{x},\mathbf{x}_{p})\Big{)}\Big{(}\frac{1}{m}\sum_{q=1}^{m}\mathcal{G}(\mathbf{x},\mathbf{x}_{q}^{\prime})\Big{)}d\mathbf{x}$
$\displaystyle=\frac{1}{mn}\sum_{p,q}\int_{\mathbf{x}\in\mathbb{R}^{3}}\mathcal{G}(\mathbf{x},\mathbf{x}_{p})\mathcal{G}(\mathbf{x},\mathbf{x}_{q}^{\prime})d\mathbf{x}$
$\displaystyle=\frac{1}{mn}\sum_{p,q}\mathcal{G}(\mathbf{x}_{p},\mathbf{x}_{q}^{\prime})\leftarrow\langle\mathbf{g}_{1},\mathbf{g}_{2}\rangle$

Lemma 1-3 complete the argument that the VecKM encoding is equivalent and
isometric to the kernel mixture when $d$ is large. In practice, the selection
of $d$ is independent of the size of the point cloud. $d$ as small as 256
yields good encoding in many scenarios, for example, in our experiments.

Figure 3: Visualization of Gaussian kernel $\mathcal{G}$ and its approximation
with Lemma 1.

(ii) The Gaussian kernel mixture associated with the point cloud approximates
the shape function. This is derived from the one-class support vector machine
(SVM). The input to the one-class SVM is a collection of points and a user-
defined kernel function, where the Gaussian (a.k.a. radial basis function)
kernel is a common choice. The output of the one-class SVM is a kernel mixture
which estimates the distribution of the input point set. Schölkopf et al.
(1999) proves that with an appropriately chosen parameter $\alpha^{2}$
(defined in Lemma 1), a Gaussian kernel mixture can approximate the
distribution function. This validates the assertion that the kernel mixtures
associated with VecKM can approximate the shape distribution function. Coupled
with Lemma 2, 3, we prove Proposition 1, 2, which reveal that VecKM
effectively represents the local geometry.

###  3.3 Dense Local Geometry Encoder

In the previous section, we explained why Eqn. 1 well represents the
underlying local shape. In this section, we introduce the unique factorizable
property that enables efficient computation of the dense local geometry
encoding.

The geometry encoding in Eqn. (1) can be factorized into:

$\displaystyle E_{\mathbf{A}}\big{(}\mathfrak{N}(\mathbf{x}_{0})\big{)}$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{n}\exp\big{(}i(\mathbf{x}_{k}-\mathbf{x}_{0})\mathbf{A}_{3\times
d}\big{)}$
$\displaystyle=\frac{1}{n}\Big{[}\sum_{k=1}^{n}\exp(i\mathbf{x}_{k}\mathbf{A})\Big{]}\>./\>\exp(i\mathbf{x}_{0}\mathbf{A})$

Under this observation, we can write the dense local geometry encoding in
terms of matrix computation:

$\displaystyle\begin{split}\mathcal{A}_{n\times d}&=\exp(i\mathbf{X}_{n\times
3}\mathbf{A}_{3\times d})\\\ \mathbf{G}_{n\times d}&=[\mathbf{J}_{n\times
n}\mathcal{A}_{n\times d}]\>./\>\mathcal{A}_{n\times d}\end{split}$ (3)

$\mathbf{J}_{n\times n}$ is the adjacency matrix of the point cloud
$\mathbf{X}_{n\times 3}$, where $\mathbf{J}[j,k]=1$ if
$||\mathbf{x}_{j}-\mathbf{x}_{k}||<r$ and 0 otherwise. Under this formulation,
we still require $O(n^{2})$ time to compute the adjacency matrix $\mathbf{J}$
and $O(n^{2}d)$ to compute $\mathbf{G}$. But one important idea can be applied
to speed up the computation: Instead of adopting a sharp threshold $r$ to
define the adjacency relation, we employ an exponential decay function to
establish this relationship:

$\hat{\mathbf{J}}[j,k]=\exp(-\beta^{2}||\mathbf{x}_{j}-\mathbf{x}_{k}||^{2}/2)$

where $\hat{\mathbf{J}}[j,k]$ decays from 1 to 0 as
$||\mathbf{x}_{j}-\mathbf{x}_{k}||$ increases and the parameter $\beta$
controls the speed of decaying. As comparison, $\mathbf{J}[j,k]$ drops sharply
from 1 to 0 when $||\mathbf{x}_{j}-\mathbf{x}_{k}||$ reaches $>r$. The
parameter $\beta$ in $\hat{\mathbf{J}}$ has the same functionality as the
parameter $r$ in $\mathbf{J}$, which is controlling the receptive field of the
local neighbors. Arguably, $\mathbf{J}$ and $\hat{\mathbf{J}}$ behave
similarly and it is natural to substitute $\mathbf{J}$ with $\hat{\mathbf{J}}$
in Eqn. (3). The motivation of this substitution is that $\hat{\mathbf{J}}$
can be factorized into a matrix multiplication:

$\displaystyle\mathcal{B}_{n\times p}$
$\displaystyle=\exp(i\mathbf{X}_{n\times 3}\mathbf{B}_{3\times p})$
$\displaystyle\hat{\mathbf{J}}_{n\times n}$
$\displaystyle\leftarrow\mathcal{B}\times\mathcal{B}^{H}\>\text{ as
$p\to\infty$ }$

where all entries in $\mathbf{B}\in\mathbb{R}^{3\times p}$ follow
$\mathcal{N}(0,\beta^{2})$. Such approximation is, again, guaranteed by Lemma
1. With such approximation, Eqn. (3) can be rewritten as

$\displaystyle\mathbf{G}_{n\times d}$
$\displaystyle=[\hat{\mathbf{J}}_{n\times n}\mathcal{A}_{n\times
d}]\>./\>\mathcal{A}_{n\times d}$ $\displaystyle\approx[\mathcal{B}_{n\times
p}\times(\mathcal{B}^{H}\times\mathcal{A})_{p\times
d}]\>./\>\mathcal{A}_{n\times d}$

By computing $\mathcal{B}^{H}\times\mathcal{A}$ first, the computation cost is
reduced to $O(npd)$. A large point cloud size usually requires a larger $p$ to
reduce the noise, but the value $p$ is much smaller than $n$. For a point
cloud with size 100k, $p=2048$ is sufficient. A large $p$ improves the quality
of the encoding, but does not increase the size of the encoding, and hence
does not increase the cost of subsequent processings. Such approximation-and-
factorization trick is inspired from Peng et al. (2021), which accelerates the
attention computation in transformers. This concludes the proof of Theorem 2.

Effect of $\alpha$ and $\beta$. We perform a qualitative analysis of the
effect of the parameters $\alpha$ and $\beta$ in Theorem 2. In short, $\alpha$
controls the level of details and $\beta$ controls the receptive field of the
local neighbor. As illustrated in Figure 8, when $\alpha$ is larger, more
high-frequency details are preserved in the encoding, and meanwhile the local
geometry encodings tends to be dissimilar to each other. A larger $\alpha$ is
usually preferred in tasks that require refined local geometry, such as normal
estimation. A smaller $\alpha$ is usually preferred in high-level tasks, such
as classification and segmentation. For $\beta$ selection, we provide a table
in Appendix D, which shows a matching between the neighborhood radius and the
corresponding $\beta$ value. More quantitative analysis will be presented in
Section 5.

Effect of $d$ and $p$. The parameters $d$ and $p$ control the quality of the
encoding. Higher values lead to better quality of encoding. Figure 9 provides
the qualitative analysis.

Uniqueness of VecKM. VecKM cannot be established without two important
properties: 1. VecKM embodies a kernel function (Lemma 1); 2. VecKM is
factorizable. Importantly, the family of exponential functions is the only
family of functions that has the factorizability property with respect to
multiplication and division: $f(x-y)=f(x)/f(y)$. But if we use the real
exponential functions, the computation is not numerically stable, and
meanwhile, the inner product between the constructed vectors will not induce a
kernel, i.e. Lemma 1 will not hold. Therefore, VecKM is the only choice to
enable both properties, i.e. both being factorizable and inducing a kernel
function. _Therefore, we conjecture that VecKM may be the only possible
$O(nd)$ local geometry encoder._ Fortunately, we are blessed with the
advantages offered by complex vectors, which provide the necessary
descriptiveness and efficiency for VecKM.

###  3.4 VecKM in Point Cloud Deep Learning

VecKM can seamlessly be integrated into widely-used deep point cloud
architectures, including PointNet (Qi et al., 2017a), PointNet++ (Qi et al.,
2017b), and transformers (Guo et al., 2021; Zhao et al., 2021). Typically,
these architectures compute the dense local geometry in the first layer, often
utilizing mini-PointNet or sequences of KPConvs (Thomas et al., 2019). To use
VecKM in those architectures, we simply replace the dense local geometry
modules with our VecKM encodings.

Note that VecKM produces complex vector outputs. To effectively utilize this
in subsequent layers, we employ a series of complex linear layers and complex
ReLU layers (Trabelsi et al., 2017) to process the encodings. Finally, we cast
the complex vectors into real vectors by calculating the squared norm of the
complex vectors, thereby making the output compatible with standard
architecture requirements. Figure 4 presents several examples of integrating
VecKM into deep point cloud architectures, which are capable of solving many
tasks involving point cloud inputs. Appendix B gives the elegant
implementation of VecKM in PyTorch.

Figure 4: VecKM can be seamlessly integrated into deep point cloud
architectures, improving both accuracy and efficiency.

##  4 Experiments

We present extensive experiments to evaluate our VecKM encoding. In Section
4.1, we present quantitative and qualitative analyses on the effectiveness,
efficiency, robustness, and scalability of the proposed VecKM encoding by
solving the low-level task of normal estimation. In Section 4.2-4.4, we
demonstrate the effectiveness and efficiency when incorporating VecKM into
deep point cloud architectures to solve high-level tasks. Depending on the
input point cloud size, we use different implementations (either Eqn. (2) or
Eqn. (3)) of VecKM to yield the better efficiency.

###  4.1 Normal Estimation on PCPNet Dataset

We compare our VecKM against other local geometry encoders in four dimensions:
accuracy, computational cost, memory cost, and robustness to noise. We select
local point cloud normal estimation as our evaluation task because of its
inherent challenges. This task requires the geometry encoders to adequately
understand the local geometry. Moreover, it presents significant challenges in
terms of memory and time complexity, given the large number of points in the
input and the large number of neighboring points that need to be considered.
As to be shown, VecKM outperforms other encoders in all four dimensions by
large margins.

Dataset and Metrics. We use PCPNet (Guerrero et al., 2018) as the evaluation
dataset. PCPNet includes 8 shapes in the training set and 19 shapes in the
test set. Each shape is sampled with 100,000 points and their ground-truth
normals are derived from the original meshes. PCPNet provides two types of
data corruption for testing: (1) point perturbations: adding Gaussian noise to
the point coordinates. (2) point density variation: resampling the point cloud
under two scenarios, where gradient simulates the effects of varying distances
from a sensor and strips simulates the occlusion effect. We use the root mean
squared angle error (RMSE) in degrees as the evaluation metrics.

Compared Encoders. We compare our VecKM against several widely-used local
geometry encoders: PointNet (Qi et al., 2017a), KPConv (Thomas et al., 2019)
and DGCNN (Wang et al., 2019). PointNet. The input point cloud is first
grouped into the shape of $(n,K,3)$ and transformed into the shape of
$(n,K,d)$ by multi-layer perceptrons. Finally, a maxpooling operation shapes
the data into $(n,d)$. $K$ is the number of neighboring points, which we
attempt different values. KPConv. KPConv convolutes the local neighbors
through a set of kernel points and transforms the convoluted features through
a fully-connected layer. KPConv has a tunable parameter: the number of kernel
points, which we attempt different values. DGCNN models the neighboring points
as dynamic graphs and performs edge convolution to aggregate the local
feature. We adopt the architecture in the original paper, which consists of
five layers of edge convolution. DGCNN has a tunable parameter: the number of
neighbors being convoluted, which we attempt different values. VecKM (Ours):
We adopt a multi-scale of $\alpha=60$ and $\beta=[10,20]$. Since the size of
the point cloud is large, we implement VecKM by Eqn. (2). We set $d$ as 512
and $p$ as 2048. We ensure the number of neighboring points considered by each
encoder to be within 500$\sim$1000, which is sufficient to estimate the local
normals. After encoding the local geometry, three layers of neural network are
applied to predict the normals.

Training Details. Each model is trained with a batch size of 200 for a total
of 200 epochs. We use the Adam optimizer, setting the learning rate at
$10^{-3}$. For data augmentation, Gaussian noise is added to the input point
cloud. The input point cloud and their normals are randomly rotated.

Table 1: Normal estimation RMSE on the PCPNet dataset.

| Perturbations | Density Variation | Average
---|---|---|---
| None | Low | Med | High | Gradient | Stripe
KPConv, #kp=16 | 22.68 | 23.09 | 25.21 | 29.05 | 34.40 | 25.61 | 26.67
KPConv, #kp=32 | 22.74 | 22.21 | 24.08 | 28.25 | 32.24 | 24.94 | 25.74
KPConv, #kp=64 | 22.09 | 22.12 | 23.90 | 28.45 | 28.60 | 24.05 | 24.86
DGCNN, #nbr=32 | 24.08 | 24.04 | 25.19 | 28.24 | 27.12 | 27.55 | 26.03
DGCNN, #nbr=64 | 23.21 | 25.34 | 25.66 | 26.01 | 28.86 | 28.20 | 26.21
DGCNN, #nbr=128 | 18.46 | 18.71 | 20.38 | 25.62 | 23.01 | 21.29 | 21.24
PointNet, #nbr=300 | 14.98 | 16.30 | 20.19 | 26.83 | 23.68 | 19.00 | 20.17
PointNet, #nbr=500 | 16.10 | 16.54 | 21.38 | 26.93 | 26.06 | 18.89 | 20.99
PointNet, #nbr=700 | 15.59 | 16.25 | 20.99 | 26.21 | 24.66 | 17.87 | 20.27
VecKM (Ours) | 13.59 | 13.99 | 18.04 | 22.21 | 18.98 | 17.20 | 17.34

Figure 5: VecKM’s robustness to data corruptions. VecKM can reconstruct the
local shape under corrupted inputs. The VecKM encodings remain highly similar
under data corruptions.

As shown in Table 1, VecKM achieves $>16\%$ lower errors than all the compared
encoders and performs the best under all data corruption settings. This
reveals that VecKM effectively captures the local geometry and is more robust
to input perturbation and density variation. The effectiveness of VecKM can be
attributed to its reconstructive and isometric properties, and its noise
robustness is derived from the robustness inherent in the kernel mixture.
Figure 5 visualizes the explanation, which shows that even under corruptions,
VecKM can still reconstruct local shapes and the VecKM encodings are
consistent. In the case of the stripe corruption setting, while the
reconstruction may appear less accurate, the downstream neural network
compensates for this discrepancy. This is evidenced by the relatively stable
RMSE of the stripe setting in Table 1, indicating that the overall impact on
performance is not substantial.

As shown in Figure 6, VecKM is $>$ 100x faster than all the compared encoders
and is scalable to large point cloud inputs. Even when the input size is as
large as 100k, VecKM only takes $150$ ms to run. For memory cost, PointNet and
DGCNN easily incur memory outrage when the neighbor size $K$ is large because
they require an intermediate step of $(n,K,d)$ to compute the encoding. KPConv
can be memory efficient through careful parallel programming, but existing
implementations are not scalable to the settings we experiment with. VecKM,
however, thanks to its unique factorizable property, only costs less than 8GB
memory even with pure PyTorch implementation.

Figure 6: Runtime of local geometry encoders under different input point cloud
size and neighbor size. All models are tested on an RTXA-5000 with 24 GB
memory. Dash lines mean the memory is not sufficient to process all the points
in one batch and has to process the points batches by batches.

###  4.2 Classification on ModelNet40 Dataset

We evaluate our VecKM on 3D object classification using the ModelNet40 dataset
(Wu et al., 2015). We compare classification accuracy and inference time with
the baselines.

Training Details. We use the same training setting for all the methods. We use
the official split with 9,843 objects for training and 2,468 for testing. Each
point cloud is uniformly sampled to 1,024 points. During training, random
translation in $[-0.2,0.2]$, and random scaling in $[0.67,1.50]$ are applied.
We set the batch size to 32 and train the models for 250 epochs. We use the
Adam optimizer, setting the initial learning rate as 0.001, with a cosine
annealing scheduler. All models are trained and tested on an RTXA-5000.

Baselines. For our experiments, we select three widely-used point cloud
architectures: PointNet (Qi et al., 2017a), PointNet++ (Qi et al., 2017b) and
the Point Cloud Transformer (PCT) (Guo et al., 2021). We integrate VecKM
encoding into these architectures as outlined in Sec. 3.4, which involves
adding or replacing the original local geometry encoding modules with VecKM
with $\alpha=30$, $\beta=6$ and $d=256$. Since the size of the point cloud is
small, we implement VecKM by Eqn. (3). We also compare VecKM-based
architectures with the another light-weight network PointMLP (Ma et al.,
2022).

Specifically, for PointNet, since it does not have a local geometry encoding
module, we _add_ the VecKM module before the PointNet, which means the
PointNet receives the geometry encoding as input instead of the raw point
coordinates. Since we _add_ (denoted by $\rightarrow$) VecKM as an additional
module, the runtime is going to be longer. For PointNet++, we _replace_
(denoted by $\leftrightharpoons$) the first set abstraction layer with our
VecKM encoding and leave the rest unchanged. For PCT, we _replace_ the initial
input embedding module with the VecKM while retaining the transformer modules.
For PointNet++ and PCT, since we _replace_ the dense local geometry encoding
module with the more efficient VecKM, the runtime is expected to decrease.

As demonstrated in Table 2, architectures based on VecKM consistently
outperform their baseline counterparts in accuracy while also benefiting from
significantly reduced runtime. When VecKM is integrated with PointNet++ and
PCT, not only is performance enhanced, but the speed of operation is also
faster compared to the baselines. When comparing VecKM $\rightarrow$ PN
against PointNet, there is a notable improvement in accuracy by 2.1% and 2.6%,
with only a minimal increase in runtime. This is significant since the VecKM
$\rightarrow$ PN architecture exhibits superior performance compared to both
PointNet++ and PCT, and meanwhile operating 7.18x and 9.5x faster,
respectively. Compared with PointMLP, VecKM-based architectures are even more
efficient, achieving on-par accuracies.

Table 2: Classification performance on the ModelNet40 dataset. VecKM
$\rightarrow$ PN means _adding_ VecKM as a preprocessing module to PointNet,
so the runtime is expected to be longer than the PointNet baseline. VecKM
$\leftrightharpoons$ PN++/PCT means _replacing_ the original dense local
geometry encoding in the original architectures with VecKM. Since VecKM is
more efficient, the runtime is reduced.

|  | Instance
---
Accuracy
| Avg. Class
---
Accuracy
| Inference Time (ms)
---
(1 batch)
# parameters
PointMLP | 93.2% | 90.1% | 325.85 | 13.2M
PointNet | 90.8% | 87.1% | 3.04 | 1.61M
VecKM $\rightarrow$ PN | 92.9% | 89.7% | 14.32 | 9.06M
Difference |  $\uparrow$ 2.1% | $\uparrow$ 2.6% | not comparable | +7.61M
PointNet++ | 92.7% | 89.4% | 117.13 | 1.48M
VecKM $\leftrightharpoons$ PN++ | 93.0% | 89.7% | 65.78 | 3.94M
Difference | $\uparrow$ 0.3% | $\uparrow$ 0.3% | 78% faster | +2.46M
PCT | 92.9% | 89.8% | 149.72 | 2.88M
VecKM $\leftrightharpoons$ PCT | 93.1% | 90.6% | 21.44 | 5.07M
Difference | $\uparrow$ 0.2% | $\uparrow$ 0.8% | 5.98x faster | +2.19M

Table 3: Part segmentation performance on the ShapeNet dataset. Similar to the
classification, $\rightarrow$ means adding VecKM as a preprocessing module, so
the runtime is expected to be longer. $\leftrightharpoons$ means replacing the
dense local geometry encoding module with VecKM. Since VecKM is more
efficient, the runtime is reduced.

|  | Instance
---
mIoU
| Avg. Class
---
mIoU
| Inference Time (ms)
---
(1 batch)
# parameters
PointMLP | 85.1% | 82.1% | 240.39 | 16.76M
PointNet | 83.1% | 77.6% | 15.1 | 8.34M
VecKM $\rightarrow$ PN | 84.9% | 81.8% | 40.8 | 1.29M
Difference | $\uparrow$ 1.8% | $\uparrow$ 4.2% | not comparable | +7.05M
PointNet++ | 85.0% | 81.9% | 130.8 | 1.41M
VecKM $\leftrightharpoons$ PN++ | 85.3% | 82.0% | 65.9 | 1.50M
Difference | $\uparrow$ 0.3% | $\uparrow$ 0.1% | 98% faster | +0.09M
PCT | 85.7% | 82.6% | 145.2 | 1.63M
VecKM $\leftrightharpoons$ PCT | 85.8% | 82.6% | 46.6 | 1.71M
Difference | $\uparrow$ 0.1% | 0.0% | 2.11x faster | +0.08M

###  4.3 Part Segmentation on ShapeNet Dataset

We evaluate our VecKM on 3D object part segmentation. Our experiment utilizes
the ShapeNet (Chang et al., 2015) dataset. Similar to the classification
experiment, we compare the IoU and inference time with PointNet, PointNet++,
PCT, and PointMLP. The baselines and their VecKM counter-parts are obtained
like the classification experiment in Section 4.2. The parameters of VecKM are
selected as $\alpha=30,\beta=9$ and $d=256$. Since the size of the point cloud
is small, we implement VecKM by Eqn. (3).

Training Details. We use the same training setting for all the methods. We use
the official split with 14,006 3D models for training and 2,874 for testing.
Each point cloud is uniformly sampled to 2,048 points. During training, random
translation in $[-0.2,0.2]$, and random scaling in $[0.67,1.50]$ are applied.
We set the batch size to 16 and train the model for 250 epochs. We use the
Adam optimizer, setting the initial learning rate as 0.001, with a cosine
annealing scheduler. All models are trained and tested on an RTXA-5000.

As demonstrated in Table 3, similar to the classfication experiment,
architectures based on VecKM consistently outperform their baseline counter-
parts in accuracy while also benefiting from significantly reduced runtime.

###  4.4 Semantic Segmentation on S3DIS Dataset

We evaluate our VecKM on 3D semantic segmentation. We use the S3DIS dataset
(Armeni et al., 2017), which is an indoor scene dataset. It contains 6 areas
and 271 rooms. Each point in this dataset is classified into one of 13
categories. Each scene contains around 10,000$\sim$100,000 points. We use the
same training setting as Zhao et al. (2021).

Baselines. We select PointNet++ and Point Transformer (Zhao et al., 2021) as
the baselines. For PointNet++, in its first layer, PointNet++ first
downsamples the point cloud by $1/4$ and for each sampled point, $32$
neighboring points are sampled and transformed by a PointNet. The VecKM
$\rightarrow$ PN++ counter-part is obtained by _adding_ the dense local
geometry encoder before the first layer. Consequently, the PointNet in the
first layer will transform the local geometry encoding instead of the raw 3d
coordinates. Because of the downsampling operation in PointNet++, its
inference time is much shorter. Therefore, PN++ and VecKM $\rightarrow$ PN++
are not comparable in terms of inference time. For Point Transformer, its
first layer is a dense local geometry encoder with PointNet. We _replace_ the
dense local geometry encoder with our VecKM encoding to obtain the PT
$\leftrightharpoons$ VecKM architecture. In both architectures, since the size
of the point cloud is large, we implement VecKM by Eqn. (2). We set
$\alpha=30,\beta=9,d=256,p=2048$, and we use a sequence of two complex linear
layers to transform the local geometry encoding from $\mathbb{C}^{256}$ to
$\mathbb{C}^{64}$.

As shown in Table 4, VecKM improves PointNet++ baseline significantly. This is
because the downsampling of the point cloud induces information loss in the
PointNet++ baseline, while the dense VecKM encoding effectively bridges the
gap. On the other hand, VecKM improves the inference speed of point
transformer, which is expected given the efficiency of VecKM especially on
large point cloud input. Regarding why VecKM $\leftrightharpoons$ PT does not
yield better accuracy, it is possibly because the heavy-weight point
transformer architecture already adequately reasons on the geometry. Unlike
PointNet++, the local geometry encoding is not a bottleneck for point
transformer. Since the subsequent processing costs the majority of the running
time, the acceleration is not as significant as the previous experiments.

Table 4: Semantic segmentation performance on the S3DIS dataset. Similar to
the classification experiment, $\rightarrow$ means adding VecKM as a
preprocessing module. Since PointNet++ downsamples the point cloud at the
first layer while VecKM $\rightarrow$ PN++ does not, their inference time is
not comparable. $\leftrightharpoons$ means replacing the original dense local
geometry encoding module with VecKM. Since VecKM is more efficient, the
runtime is reduced.

|  | Instance
---
mIoU
| Avg. Class
---
mIoU
| Overall
---
Accuracy
| Inference Time (ms)
---
(per scene)
#parameters
PointNet++ | 64.05 | 71.52 | 87.92 | 96 | 0.968M
VecKM $\rightarrow$ PN++ | 67.48 | 73.53 | 89.33 | 391 | 1.11M
Difference | $\uparrow$ 3.43 | $\uparrow$ 2.01 | $\uparrow$ 1.41 | not comparable | +0.142M
Point Transformer | 69.29 | 75.66 | 90.36 | 559 | 7.77M
VecKM $\leftrightharpoons$ PT | 69.53 | 75.84 | 90.39 | 447 | 7.93M
Difference | $\uparrow$ 0.24 | $\uparrow$ 0.18 | $\uparrow$ 0.03 | 20% faster | +0.16M

##  5 Ablation Studies

In Section 3.3, we qualitatively analyze the effect of the parameters $\alpha$
and $\beta$ in Theorem 2. In this section, we quantitatively analyze the
effect of the parameters in the context of the ModelNet40 classification
experiment, with the VecKM $\rightarrow$ PN architecture. For $\alpha$
selection, when the input point cloud is normalized within a unit ball,
setting $\alpha$ in the range of $(20,35)$ yields good performance. As shown
in Table 5, appropriate selections of $\alpha$ and $\beta$ are important to
yield a good performance on the downstream tasks.

Table 5: Ablation study on the selection of the parameters $\alpha$ and
$\beta$ in Theorem 2, in the context of ModelNet40 classification experiment.
Numbers greater than $92.5\%$ are bolded.

| $\alpha=20$ | $\alpha=25$ | $\alpha=30$ | $\alpha=35$
---|---|---|---|---
$\beta=4$ | 91.73% | 91.94% | 91.73% | 91.77%
$\beta=6$ | 92.59% | 92.14% | 92.87% | 92.50%
$\beta=9$ | 92.18% | 92.71% | 92.95% | 92.50%
$\beta=12$ | 92.10% | 92.54% | 92.59% | 92.38%

Figure 7: Average RMSE of normal estimation trained with different numbers of
layers.

We study how many fully-connected layers are needed for transforming the VecKM
encoding, in the context of normal estimation tasks. As shown in Figure 7, two
layers are sufficient for stably satisfactory performance, highlighting the
inherent descriptiveness of VecKM encoding.

Notice that the selection of the $\alpha$ parameter varies across different
tasks. In classification, where refined local geometry is less critical, a
smaller $\alpha$ is used to abstract away finer details. For normal estimation
tasks, where accurate local shape representation is crucial, a larger $\alpha$
is employed to retain essential details. These findings demonstrate VecKM’s
adaptability in meeting the diverse requirements of various tasks, adjusting
to the specific level of detail needed.

##  6 Conclusion

VecKM, our novel local point cloud encoder, stands out for its efficiency and
noise robustness. VecKM vectorizes a kernel mixture associated with the local
point cloud, providing a solid theoretical foundation for its descriptiveness
and robustness. Thanks to its special formulation, VecKM is the only existing
local geometry encoder that costs $O(nd)$ space and time. Through extensive
experiments, VecKM has demonstrated significant improvements in speed and
accuracy across a variety of point cloud processing tasks. VecKM has many
potential applications due to its notable features. Its efficiency facilitates
faster inference, ideal for time-critical tasks like event data processing.
Additionally, its robustness makes it an ideal candidate for local geometry
encoding in point cloud foundation models.

##  7 Acknowledgement

The support of NSF under awards OISE 2020624 and BCS 2318255, and ARL under
the Army Cooperative Agreement W911NF2120076 is greatly acknowledged. We
extend our gratitude to Pixabay for providing free access to the icon used in
drafting Figure 2 and 8.

## References

  * Armeni et al. (2017) Armeni, I., Sax, S., Zamir, A. R., and Savarese, S.  Joint 2d-3d-semantic data for indoor scene understanding.  _arXiv preprint arXiv:1702.01105_ , 2017.
  * Bochner (2005) Bochner, S.  _Harmonic analysis and the theory of probability_.  Courier Corporation, 2005.
  * Chang et al. (2015) Chang, A. X., Funkhouser, T., Guibas, L., Hanrahan, P., Huang, Q., Li, Z., Savarese, S., Savva, M., Song, S., Su, H., et al.  Shapenet: An information-rich 3d model repository.  _arXiv preprint arXiv:1512.03012_ , 2015.
  * Chen et al. (2020) Chen, S., Liu, B., Feng, C., Vallespi-Gonzalez, C., and Wellington, C.  3d point cloud processing and learning for autonomous driving: Impacting map creation, localization, and perception.  _IEEE Signal Processing Magazine_ , 38(1):68–86, 2020.
  * Fehr et al. (2012) Fehr, D., Cherian, A., Sivalingam, R., Nickolay, S., Morellas, V., and Papanikolopoulos, N.  Compact covariance descriptors in 3d point clouds for object recognition.  In _2012 IEEE international conference on robotics and automation_ , pp. 1793–1798. IEEE, 2012.
  * Frady et al. (2022) Frady, E. P., Kleyko, D., Kymn, C. J., Olshausen, B. A., and Sommer, F. T.  Computing on functions using randomized vector representations (in brief).  In _Proceedings of the 2022 Annual Neuro-Inspired Computational Elements Conference_ , pp. 115–122, 2022.
  * Ge (2016) Ge, X.  Non-rigid registration of 3d point clouds under isometric deformation.  _ISPRS Journal of Photogrammetry and Remote Sensing_ , 121:192–202, 2016.
  * Guerrero et al. (2018) Guerrero, P., Kleiman, Y., Ovsjanikov, M., and Mitra, N. J.  Pcpnet learning local shape properties from raw point clouds.  In _Computer graphics forum_ , volume 37, pp. 75–85. Wiley Online Library, 2018.
  * Guo et al. (2021) Guo, M.-H., Cai, J.-X., Liu, Z.-N., Mu, T.-J., Martin, R. R., and Hu, S.-M.  Pct: Point cloud transformer.  _Computational Visual Media_ , 7:187–199, 2021.
  * Han et al. (2022) Han, X.-F., He, Z.-Y., Chen, J., and Xiao, G.-Q.  3crossnet: Cross-level cross-scale cross-attention network for point cloud representation.  _IEEE Robotics and Automation Letters_ , 7(2):3718–3725, 2022.
  * Han et al. (2023) Han, X.-F., Feng, Z.-A., Sun, S.-J., and Xiao, G.-Q.  3d point cloud descriptors: state-of-the-art.  _Artificial Intelligence Review_ , pp. 1–51, 2023.
  * Lai et al. (2022) Lai, X., Liu, J., Jiang, L., Wang, L., Zhao, H., Liu, S., Qi, X., and Jia, J.  Stratified transformer for 3d point cloud segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 8500–8509, 2022.
  * Langley (2000) Langley, P.  Crafting papers on machine learning.  In Langley, P. (ed.), _Proceedings of the 17th International Conference on Machine Learning (ICML 2000)_ , pp. 1207–1216, Stanford, CA, 2000. Morgan Kaufmann.
  * Li et al. (2018) Li, Y., Bu, R., Sun, M., Wu, W., Di, X., and Chen, B.  Pointcnn: Convolution on x-transformed points.  _Advances in neural information processing systems_ , 31, 2018.
  * Lu et al. (2020) Lu, X., Yuan, D., Chen, Y., Fung, J. C., Li, W., and Lau, A. K.  Estimations of long-term nss-so42–and no3–wet depositions over east asia by use of ensemble machine-learning method.  _Environmental Science & Technology_, 54(18):11118–11126, 2020.
  * Ma et al. (2022) Ma, X., Qin, C., You, H., Ran, H., and Fu, Y.  Rethinking network design and local geometry in point cloud: A simple residual mlp framework.  _arXiv preprint arXiv:2202.07123_ , 2022.
  * Pan et al. (2021) Pan, X., Xia, Z., Song, S., Li, L. E., and Huang, G.  3d object detection with pointformer.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 7463–7472, 2021.
  * Peng et al. (2021) Peng, H., Pappas, N., Yogatama, D., Schwartz, R., Smith, N. A., and Kong, L.  Random feature attention.  _arXiv preprint arXiv:2103.02143_ , 2021.
  * Prakhya et al. (2017) Prakhya, S. M., Lin, J., Chandrasekhar, V., Lin, W., and Liu, B.  3dhopd: A fast low-dimensional 3-d descriptor.  _IEEE Robotics and Automation Letters_ , 2(3):1472–1479, 2017.
  * Qi et al. (2017a) Qi, C. R., Su, H., Mo, K., and Guibas, L. J.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 652–660, 2017a.
  * Qi et al. (2017b) Qi, C. R., Yi, L., Su, H., and Guibas, L. J.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  _Advances in neural information processing systems_ , 30, 2017b.
  * Rahimi & Recht (2007) Rahimi, A. and Recht, B.  Random features for large-scale kernel machines.  _Advances in neural information processing systems_ , 20, 2007.
  * Ran et al. (2022) Ran, H., Liu, J., and Wang, C.  Surface representation for point clouds.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 18942–18952, 2022.
  * Rusu et al. (2008) Rusu, R. B., Marton, Z. C., Blodow, N., and Beetz, M.  Persistent point feature histograms for 3d point clouds.  In _Proc 10th Int Conf Intel Autonomous Syst (IAS-10), Baden-Baden, Germany_ , pp. 119–128, 2008.
  * Schölkopf et al. (1999) Schölkopf, B., Williamson, R. C., Smola, A., Shawe-Taylor, J., and Platt, J.  Support vector method for novelty detection.  _Advances in neural information processing systems_ , 12, 1999.
  * Steder et al. (2010) Steder, B., Rusu, R. B., Konolige, K., and Burgard, W.  Narf: 3d range image features for object recognition.  In _Workshop on Defining and Solving Realistic Perception Problems in Personal Robotics at the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , volume 44, pp. 2. Citeseer, 2010.
  * Thomas et al. (2019) Thomas, H., Qi, C. R., Deschaud, J.-E., Marcotegui, B., Goulette, F., and Guibas, L. J.  Kpconv: Flexible and deformable convolution for point clouds.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pp. 6411–6420, 2019.
  * Trabelsi et al. (2017) Trabelsi, C., Bilaniuk, O., Serdyuk, D., Subramanian, S., Santos, J. F., Mehri, S., Rostamzadeh, N., Bengio, Y., and Pal, C. J.  Deep complex networks.  _CoRR_ , abs/1705.09792, 2017.  URL http://arxiv.org/abs/1705.09792.
  * Triebel et al. (2006) Triebel, R., Kersting, K., and Burgard, W.  Robust 3d scan point classification using associative markov networks.  In _Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006._ , pp. 2603–2608. IEEE, 2006.
  * Vandapel et al. (2004) Vandapel, N., Huber, D. F., Kapuria, A., and Hebert, M.  Natural terrain classification using 3-d ladar data.  In _IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004_ , volume 5, pp. 5117–5122. IEEE, 2004.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2019) Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., and Solomon, J. M.  Dynamic graph cnn for learning on point clouds.  _ACM Transactions on Graphics (tog)_ , 38(5):1–12, 2019.
  * Wu et al. (2019) Wu, W., Qi, Z., and Fuxin, L.  Pointconv: Deep convolutional networks on 3d point clouds.  In _Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition_ , pp. 9621–9630, 2019.
  * Wu et al. (2015) Wu, Z., Song, S., Khosla, A., Yu, F., Zhang, L., Tang, X., and Xiao, J.  3d shapenets: A deep representation for volumetric shapes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 1912–1920, 2015.
  * Xiang et al. (2021) Xiang, T., Zhang, C., Song, Y., Yu, J., and Cai, W.  Walk in the cloud: Learning curves for point clouds shape analysis.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 915–924, 2021.
  * Xu et al. (2018) Xu, Y., Fan, T., Xu, M., Zeng, L., and Qiao, Y.  Spidercnn: Deep learning on point sets with parameterized convolutional filters.  In _Proceedings of the European conference on computer vision (ECCV)_ , pp. 87–102, 2018.
  * Yan et al. (2020) Yan, X., Zheng, C., Li, Z., Wang, S., and Cui, S.  Pointasnl: Robust point clouds processing using nonlocal neural networks with adaptive sampling.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pp. 5589–5598, 2020.
  * Yu et al. (2022) Yu, X., Tang, L., Rao, Y., Huang, T., Zhou, J., and Lu, J.  Point-bert: Pre-training 3d point cloud transformers with masked point modeling.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 19313–19322, 2022.
  * Yuan et al. (2023) Yuan, D., Huang, F., Fermüller, C., and Aloimonos, Y.  Decodable and sample invariant continuous object encoder.  _arXiv preprint arXiv:2311.00187_ , 2023.
  * Zampogiannis et al. (2019) Zampogiannis, K., Fermüller, C., and Aloimonos, Y.  Topology-aware non-rigid point cloud registration.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 43(3):1056–1069, 2019.
  * Zhao et al. (2021) Zhao, H., Jiang, L., Jia, J., Torr, P. H., and Koltun, V.  Point transformer.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pp. 16259–16268, 2021.

##  Appendix A Proof of Lemma 1

######  Lemma 1 (VecKM embodies a Gaussian kernel).

Let $\mathbf{x},\mathbf{y}\in\mathbb{R}^{3}$,
$\mathbf{A}\in\mathbb{R}^{3\times d}$. All elements in $\mathbf{A}$ are drawn
from normal distribution $\mathcal{N}(0,\alpha^{2})$. Then as $d\to\infty$,

$\displaystyle\begin{split}\frac{1}{d}\langle
e^{i\mathbf{x}\mathbf{A}},e^{i\mathbf{y}\mathbf{A}}\rangle\rightarrow\mathcal{G}_{\alpha}(\mathbf{x},\mathbf{y}):=\exp\big{(}-\frac{\alpha^{2}||\mathbf{x}-\mathbf{y}||^{2}}{2}\big{)}\end{split}$

###### Proof.

Let $\mathbf{a}\in\mathbb{R}^{3}$ where
$\mathbf{a}\sim\mathcal{N}(\mathbf{0},\alpha^{2}\mathbf{I}_{3\times 3})$ be
one column of the matrix $\mathbf{A}$, we claim that
$\mathbb{E}\big{[}\Re\big{(}e^{i\mathbf{a}\cdot(\mathbf{x}-\mathbf{y})}\big{)}\big{]}=\mathcal{G}_{\alpha}(\mathbf{x},\mathbf{y})$:

$\displaystyle\mathbb{E}\Big{[}\Re\big{(}e^{i\mathbf{\mathbf{a}}\cdot(\mathbf{x}-\mathbf{y})}\big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\cos\big{(}\mathbf{a}\cdot(\mathbf{x}-\mathbf{y})\big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{k=0}^{\infty}(-1)^{k}\frac{\big{(}\mathbf{\mathbf{a}}\cdot(\mathbf{x}-\mathbf{y})\big{)}^{2k}}{(2k)!}\Big{]}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{(2k)!}\mathbb{E}\Big{[}\big{(}\sum_{j=1}^{3}(\mathbf{x}_{j}-\mathbf{y}_{j})\mathbf{a}_{j}\big{)}^{2k}\Big{]}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{(2k)!}\mathbb{E}\Big{[}\big{(}\alpha||\mathbf{x}-\mathbf{y}||Z\big{)}^{2k}\Big{]}\quad\text{where
$Z\in\mathcal{N}(0,1)$}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{(2k)!}\cdot\alpha^{2k}||\mathbf{x}-\mathbf{y}||^{2k}\cdot\frac{(2k)!}{k!2^{k}}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{k!2^{k}}\cdot\alpha^{2k}||\mathbf{x}-\mathbf{y}||^{2k}$
$\displaystyle=\exp\big{(}-\frac{\alpha^{2}||\mathbf{x}-\mathbf{y}||^{2}}{2}\big{)}$

On the other hand,
$\mathbb{E}\big{[}\Im\big{(}e^{i\mathbf{a}\cdot(\mathbf{x}-\mathbf{y})}\big{)}\big{]}=0$
because normal distribution is a symmetric distribution around 0:

$\displaystyle\mathbb{E}\Big{[}\Im\big{(}e^{i\mathbf{\mathbf{a}}\cdot(\mathbf{x}-\mathbf{y})}\big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sin\big{(}\mathbf{a}\cdot(\mathbf{x}-\mathbf{y})\big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{k=0}^{\infty}(-1)^{k}\frac{\big{(}\mathbf{\mathbf{a}}\cdot(\mathbf{x}-\mathbf{y})\big{)}^{2k+1}}{(2k+1)!}\Big{]}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{(2k+1)!}\mathbb{E}\Big{[}\big{(}\sum_{j=1}^{3}(\mathbf{x}_{j}-\mathbf{y}_{j})\mathbf{a}_{j}\big{)}^{2k+1}\Big{]}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{(2k+1)!}\mathbb{E}\Big{[}\big{(}\alpha||\mathbf{x}-\mathbf{y}||Z\big{)}^{2k+1}\Big{]}\quad\text{where
$Z\in\mathcal{N}(0,1)$}$ $\displaystyle=0\quad\text{because
$\mathbb{E}(Z^{2k+1})=0$}$

Therefore, when we randomize $d$ rows of such $\mathbf{a}$ vector, the inner
product $\frac{1}{d}\langle
e^{i\mathbf{x}\mathbf{A}},e^{i\mathbf{y}\mathbf{A}}\rangle=\frac{1}{d}\sum_{k=1}^{d}e^{i\mathbf{a}_{k}\cdot(\mathbf{x}-\mathbf{y})}$
will converge to $\mathcal{G}_{\alpha}(\mathbf{x},\mathbf{y})$ thanks to the
Law of Large Number and the Central Limit Theorem. ∎

##  Appendix B PyTorch Implementation of VecKM

⬇

1import torch

2import torch.nn as nn

3

4class VecKM(nn.Module):

5 def __init__(self, d=256, alpha=30, beta=9, p=2048):

6 super().__init__()

7 self.sqrt_d = d ** 0.5

8

9 self.A = torch.randn((3, d)) * alpha

10 self.A = nn.Parameter(self.A, False) # (3, d)

11

12 self.B = torch.randn((3, p)) * beta

13 self.B = nn.Parameter(self.B, False) # (3, p)

14

15 def forward(self, pts):

16 """ Compute the dense VecKM encodings of the given point cloud.

17 Args:

18 pts: (bs, n, 3) or (n, 3) tensor, the input point cloud.

19

20 Returns:

21 G: (bs, n, d) or (n, d) tensor

22 the dense VecKM local geometry encodings.

23 note: it is complex valued.

24 """

25 eA = torch.exp(1j * (pts @ self.A)) # (bs, n, d)

26 eB = torch.exp(1j * (pts @ self.B)) # (bs, n, p)

27

28 G = torch.matmul(

29 eB,

30 eB.transpose(-1,-2).conj() @ eA

31 ) / eA # (bs, n, d)

32 G = G / torch.norm(G, dim=-1, keepdim=True) * self.sqrt_d # (bs, n, d)

33

34 return G

35

36vkm = VecKM()

37pts = torch.rand((10,1000,3))

38print(vkm(pts).shape)

39# >> ComplexTensor with shape (10, 1000, 256)

40pts = torch.rand((1000,3))

41print(vkm(pts).shape)

42# >> ComplexTensor with shape (1000, 256)

43

44

45""" You may want to use apply a two-layer feature transform to the encoding.

46"""

47from complexPyTorch.complexLayers import ComplexLinear, ComplexReLU

48feat_trans = nn.Sequential(

49 ComplexLinear(256, 128),

50 ComplexReLU(),

51 ComplexLinear(128, 128)

52)

53G = feat_trans(vkm(pts))

54G = G.real**2 + G.imag**2

55# >> RealTensor with shape (10, 1000, 128) or (1000, 128).

##  Appendix C Effect of Parameters $\alpha,\beta,d,p$

Figure 8: Effect of the parameters $\alpha$ and $\beta$ in Theorem 2. Figure
9: Effect of the parameters $d$ and $p$ in Theorem 2.

##  Appendix D Guidance for Selecting the Parameter $\beta$

The statistics is obtained by $r=\min_{r}\\{r:e^{-r^{2}/2}<0.1\\}$. The beta
and the radius have a relation of $\beta_{1}r_{1}=\beta_{2}r_{2}$.

Table 6: Relation between the parameter $\beta$ and the neighborhood radius.

beta | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
radius | 1.800 | 0.900 | 0.600 | 0.450 | 0.360 | 0.300 | 0.257 | 0.225 | 0.200 | 0.180
beta | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
radius | 0.163 | 0.150 | 0.138 | 0.129 | 0.120 | 0.113 | 0.106 | 0.100 | 0.095 | 0.090
beta | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30
radius | 0.086 | 0.082 | 0.078 | 0.075 | 0.072 | 0.069 | 0.067 | 0.065 | 0.062 | 0.060


11institutetext: Electronics and Communication Sciences Unit
Indian Statistical Institute, Calcutta, 700108, India
11email<EMAIL_ADDRESS>

# Understanding the classes better with class-specific and rule-specific
feature selection, and redundancy control in a fuzzy rule based framework

Suchismita Das  0000-0002-3952-3605 Nikhil R. Pal  0000-0001-6935-901X

###### Abstract

Recently, several studies have claimed that using class-specific feature
subsets provides certain advantages over using a single feature subset for
representing the data for a classification problem. Unlike traditional feature
selection methods, the class-specific feature selection methods select an
optimal feature subset for each class. Typically class-specific feature
selection (CSFS) methods use one-versus-all split of the data set that leads
to issues such as class imbalance, decision aggregation, and high
computational overhead. We propose a class-specific feature selection method
embedded in a fuzzy rule-based classifier, which is free from the drawbacks
associated with most existing class-specific methods. Additionally, our method
can be adapted to control the level of redundancy in the class-specific
feature subsets by adding a suitable regularizer to the learning objective.
Our method results in class-specific rules involving class-specific subsets.
We also propose an extension where different rules of a particular class are
defined by different feature subsets to model different substructures within
the class. The effectiveness of the proposed method has been validated through
experiments on three synthetic data sets.

###### Keywords:

Class-specific Feature selection Rule-specific Feature Selection Redundancy
Control Fuzzy rule-based Classifiers Within-class substructures.

##  1 Introduction

Feature selection is an important step for many machine learning tasks. The
main motto of the feature selection methods is to reject unnecessary and
derogatory features and select the features that benefit the intended task.
Traditional feature selection methods choose a single subset of the features
as the “optimal” subset for the entire dataset. Apart from the commonly used
global approach, some studies [8, 6, 9, 10, 11, 12, 13, 14] have used class-
specific approaches for selecting features, where for each class, a unique
subset of the original features is selected. If there are $C$ classes, in the
class-specific approach, $C$ subsets are chosen. In a traditional feature
selection method, the selected feature subset is chosen based on the global
characteristics of the data. It does not take into account any class-specific
or local characteristics of the data which may be present. For example, there
may exist a group of features that follows a distinct distribution for a
specific class but varies randomly over the remaining classes. Such a group of
features plays a significant role in distinguishing the specific class from
other classes. However, such a group may not be a very useful feature subset
for the $C$-class problem as a whole. Class-specific characteristics may also
exist in the form of class-specific redundancy. Different sets of features
could be redundant for different classes. The class-specific feature selection
(CSFS) works in [8, 6, 9, 10, 11, 12, 13, 14] have proposed suitable
frameworks that exploit class-specific feature subsets to solve classification
problems. They have shown that the classifiers built with the subsets chosen
by class-specific methods performed better than or comparable to the
classifiers built with subsets chosen by the traditional global feature
selection methods. The CSFS may also enhance the transparency/explainability
of the classification process associated with it [6].

The majority of the CSFS methods [8, 6, 10, 11, 13, 14] follow the one-versus-
all (OVA) strategy to decompose a $C$-class classification problem into $C$
binary classification problems. They choose $C$ class-specific feature subsets
optimal for the $C$ binary classification problems. OVA strategy-based class-
specific feature selection methods have certain drawbacks. Generally, it leads
to class imbalance. The performance of an OVA-based method would depend on how
efficiently the class imbalance problem is handled. The OVA strategy-based
methods is computationally intensive and complex as we need to design $C$
classifiers and for testing we need an aggregation mechanism.

Here, we propose a CSFS scheme embedded in a fuzzy rule-based classifier
(FRBC) that does not use the OVA strategy. Our method selects class-specific
feature subsets by learning a single FRBC and hence avoid the issues
introduced in the OVA-based approaches. Moreover, we extend our framework to
deal with- (i) CSFC with redundancy control, and (ii) rule-specific feature
selection (RSFS) that can exploit presence of substructure within a class. The
rules provided by the FRBC are generally interpretable and more specific.
Exploiting the class-specific local features, the proposed FRBC enjoys more
transparency and interpretability than a standard classifier exploiting class-
specific feature subsets. Our contributions are summarised as follows.

  1. 1.

We propose a class-specific feature selection method that is not based on the
OVA strategy like most of the existing class-specific feature selection
schemes. Thus, our method is free from the weaknesses of the OVA strategy.

  2. 2.

Our method can monitor the level of redundancy in the selected features.

  3. 3.

We also propose a general version of our class-specific feature selection
method that not only chooses different subsets for different classes but also,
chooses different subsets within a class if different substructures are
present.

##  2 Proposed Method

We want to develop a method for CSFS based on a training dataset. Let, the
input data be
$\mathbf{X}=\\{\mathbf{x}^{i}=(x_{1}^{i},x_{2}^{i},\cdots,x_{P}^{i})^{T}\in\mathcal{R}^{P}:i\in\\{1,2,\cdots,n\\}\\}$.
The collection of class labels of $\mathbf{X}$ be
$\mathbf{y}=\\{y^{i}\in\\{1,2,\cdots,C\\}:i\in\\{1,2,\cdots,n\\}\\}$, where,
$y^{i}$ is the class label corresponding to $\mathbf{x}^{i}$. For our purposes
we represent the class label of $\mathbf{x}^{i}$ as
$\mathbf{t}^{i}\in\\{0,1\\}^{C}$, where ${t}_{k}^{i}=1$ if $y^{i}=k$ and
${t}_{k}^{i}=0$, otherwise. We denote the $j$th feature by $x_{j}$, the class
label by $y$, and the target vector by $\mathbf{t}$. The set of original
features be $\mathbf{f}=\\{x_{1},x_{2},\cdots x_{P}\\}$. Let the optimal
class-specific subset for the $k$th class be $\mathbf{s}_{k}$. We need to find
out $\mathbf{s}_{k}$s where, $\mathbf{s}_{k}\subset\mathbf{f}\hskip
2.0pt\forall k\in\\{1,2,\cdots,C\\}$. We propose a CSFS mechanism embedded in
a fuzzy rule-based classifier (FRBC). So next we discuss the FRBC.

###  2.1 FRBC

We employ the FRBC framework used in [4, 5]. Each class is represented by a
set of rules. Let there are $N_{k}$ rules for the $k$th class. The $l$th rule
corresponding to the $k$th class, $\mathrm{R}_{kl}$ is given by

$\mathrm{R}_{kl}:\texttt{If }x_{1}\texttt{ is }A_{1,kl}\texttt{ and
}x_{2}\texttt{ is }A_{2,kl}\texttt{ and}\cdots x_{P}\texttt{ is
}A_{P,kl}\texttt{then }y\texttt{ is }k.$ (1)

Here, $k\in\\{1,2,\cdots,C\\}$, $l\in\\{1,2,\cdots,N_{k}\\}$, and $A_{j,kl}$
is a linguistic value (fuzzy set) defined on the $j$th feature for the $l$th
rule of the $k$th class. Let, $\alpha_{kl}$ be the firing strength of the rule
$\mathrm{R}_{kl}$. The rule firing strength is computed using a $T$-norm [7]
over the fuzzy sets $A_{1,kl},A_{2,kl},\cdots A_{P,kl}$. We use the product
$T$-norm. Let the membership to the fuzzy set $A_{j,kl}$ be $\mu_{j,kl}$. So,
$\alpha_{kl}$ is given by, $\alpha_{kl}=\prod_{j=1}^{P}\mu_{j,kl}$. The final
output of the FRBC is of the form $\mathbf{o}=(o_{1},o_{2},\cdots,o_{C})$,
where, $o_{k}$ is the support for $k$th class, computed as
$o_{k}=\max\\{\alpha_{k1},\alpha_{k2},\cdots,\alpha_{kN_{k}}\\}$. To learn an
efficient classifier from the initial fuzzy rule-based system, the parameters
defining the fuzzy sets $A_{j,kl}$s can be tuned by minimizing the
classification error,

$E_{cl}=\textstyle{\sum_{i=1}^{n}\sum_{k=1}^{C}(o^{i}_{k}-t^{i}_{k})^{2}}.$
(2)

To extract the $l$th rule of the $k$th class, $\mathrm{R}_{kl}$ we need to
define the fuzzy sets $A_{j,kl}$s. Following [4, 5], we cluster the training
data of the $k$th class into $N_{k}$ clusters. We note here that the $k$th
class may not have $n_{k}$ clusters in the pattern recognition sense. By
clustering we just group the nearby points and then define a rule for each
group. Let the centroid of the $l$th cluster of the $k$th class be represented
as $\mathbf{v}_{kl}=(v_{1,kl},v_{2,kl},\cdots,v_{P,kl})$. The cluster centroid
$\mathbf{v}_{kl}$ is then translated into $P$ fuzzy sets, $A_{j,kl}=\text{
``close to" }v_{j,kl}\hskip 3.0pt\forall j\in\\{1,2,\cdots,P\\}$. The fuzzy
set ‘$\text{ ``close to" }v_{j,kl}$’ is modeled by a Gaussian membership
function with mean $v_{j,kl}$. Although the membership parameters can be tuned
to refine the fuzzy rules, in this study, we have not done that. We have used
fixed rules defined by the obtained cluster centers.

###  2.2 Feature Selection

Following [2, 3, 4, 5], we use feature modulators which stop the derogatory
features and promote useful features to take part in the rules of the FRBC. We
choose the modulator function same as used in [5]. For each feature, there is
an associated modulator of the form $M(\lambda_{j})=\exp{(-\lambda_{j}^{2})}$,
where $j\in\\{1,2,\cdots,P\\}$. To select or reject a feature using the
modulator function, the membership values associated with the $j$th feature
are modified as

$\textstyle{\hat{\mu}_{j,kl}=\mu_{j,kl}^{M(\lambda_{j})}=\mu_{j,kl}^{\exp{(-\lambda_{j}^{2})}}\forall
k,l}$ (3)

Note that, $\lambda_{j}\approx 0$ makes $\hat{\mu}_{j,kl}\approx\mu_{j,kl}$.
Similarly, when $\lambda_{j}$ is high (say, $\lambda_{j}\geq 2$),
$\hat{\mu}_{j,kl}\approx 1$. The rule firing strength is now calculated as
$\alpha_{kl}=\prod_{j=1}^{P}\hat{\mu}_{j,kl}$. So, when
$\hat{\mu}_{j,kl}\approx\mu_{j,kl}$, $j$th feature influences the rule firing
strength $\alpha_{kl}$ and in turn influences the classification process,
whereas, if $\hat{\mu}_{j,kl}\approx 1$ then the $j$th feature has no
influence on the firing strength and hence on the predictions by the FRBC.
This would be true for any T-Norm as $T(x,1)=x,x\in[0,1]$. Thus, for useful
features, $\lambda_{j}$s should be made close to zero and for derogatory
features $\lambda_{j}$s should be made high. The desirable values of
$\lambda_{j}$s are obtained by minimizing $E_{cl}$ defined in (2) with respect
to $\lambda_{j}$s. The training begins with $\lambda_{j}=2+$ Gaussian noise.
$M(\lambda_{j})\approx 0$ indicates a strong rejection of $x_{j}$, while
$M(\lambda_{j})\approx 1$ suggests a strong acceptance of $x_{j}$. However,
training may lead $\lambda_{j}$s such that $M(\lambda_{j})$ takes a value in
between $0$ and $1$. This implies that the corresponding feature influences
the classification partially. This is not desirable in our case, as our
primary goal is to select or reject features. To facilitate this, we add a
regularizer term $E_{select}$ to $E_{cl}$ such that $E_{select}$ adds penalty
if any $\lambda_{j}$ allows the corresponding feature partially. In [5],
$E_{select}$ is set as follows.

$E_{select}=\textstyle{(\nicefrac{{1}}{{P}})\sum_{j=1}^{P}\exp{(-\lambda_{j}^{2})}(1-\exp{(-\lambda_{j}^{2})})}$
(4)

So, the overall loss function for learning suitable $\lambda_{j}$s becomes

$\textstyle{E=E_{cl}+c_{1}E_{select}}.$ (5)

####  2.2.1 Class-specific feature selection

So far we have not considered selection of class-specific features. In the
class-specific scenario, for each class, a different set of $P$ modulators is
engaged. So, a total of $C\times P$ feature modulators are employed.
Consequently, for each class a different set of features, if appropriate, can
be selected. Here, we represent the feature modulator for the $j$th feature of
the $k$th class as $M(\lambda_{j,k})=\exp{(-\lambda_{j,k}^{2})}$, where
$j\in\\{1,2,\cdots,P\\};k\in\\{1,2,\cdots,C\\}$. The modulator value
$M(\lambda_{j,k})$ modify the membership values corresponding to the $j$th
feature of the $k$th class as following:

$\textstyle{\hat{\mu}_{j,kl}=\mu_{j,kl}^{M(\lambda_{j,k})}=\mu_{j,kl}^{\exp{(-\lambda_{j,k}^{2})}}\forall
l}$ (6)

For this problem, the $E_{select}$ is changed to

$E_{select}=\textstyle{(\nicefrac{{1}}{{CP}})\sum_{k=1}^{C}\sum_{j=1}^{P}\exp{(-\lambda_{j,k}^{2})}(1-\exp{(-\lambda_{j,k}^{2})})}$
(7)

We now Minimize (5) with respect to $\lambda_{j,k}$s to find the optimal
$\lambda_{j,k}$s.

###  2.3 Monitoring Redundancy

Suppose a data set has three useful features say $x_{1},x_{2},x_{3}$ such that
each of $x_{2}$ and $x_{3}$ is strongly dependent on (say correlated with)
$x_{1}$ then all the three features carry the same information and only one of
them is enough. These three form a redundant set of features. However, if we
just use one of them and there is some error in measuring that feature, the
system may fail to do the desired job. Therefore, instead of minimizing
redundancy, a controlled use of redundant features is desirable. For the
global feature selection framework, redundancy control has been realized using
the feature modulators [2, 3, 5] by adding the regularizer (8) to (5):

$E_{r}=\textstyle{(\nicefrac{{1}}{{P(P-1)}})\sum_{j=1}^{P}\sum_{m=1,m\neq
j}^{P}\sqrt{\exp{(-\lambda_{j}^{2})}\exp{(-\lambda_{m}^{2})}\rho^{2}(x_{j},x_{m})}}$
(8)

Here, $\rho()$ is the Pearson’s correlation coefficient, which is a measure of
dependency between two features. When $x_{j}$ and $x_{m}$ are highly
correlated, $\rho^{2}(x_{j},x_{m})$ is close to one (its highest value). In
this case, to reduce the penalty $E_{r}$, the training process will adapt
$\lambda_{j}$ and $\lambda_{m}$ in such a way that one of
$\exp{(-\lambda_{j}^{2})}$ and $\exp{(-\lambda_{m}^{2})}$ is close to $0$ and
the other is close to $1$. Note the (8) is not suitable for class-specific
scenario. Next we change (8) for class-specific redundancy.

####  2.3.1 Class-specific redundancy

For class-specific redundancy, we need to compute class-specific dependency of
a feature pair. So we compute $\rho_{k}(x_{j},x_{m})$ between features $x_{j}$
and $x_{m}$ considering only instances of the $k$th class. In the class-
specific case, for each class, we have $P$ feature modulators,
$M(\lambda_{j,k})=\exp{(-\lambda_{j,k}^{2})}$, where
$j\in\\{1,2,\cdots,P\\};k\in\\{1,2,\cdots,C\\}$. So, (8) is modified as
following.

$E_{r_{c}}=\textstyle{(\nicefrac{{1}}{{CP(P-1)}})\sum_{k=1}^{C}\sum_{j=1}^{P}\sum_{m=1,m\neq
j}^{P}\sqrt{\exp{(-\lambda_{j,k}^{2})}\exp{(-\lambda_{m,k}^{2})}\rho_{k}^{2}(x_{j},x_{m})}}$
(9)

Considering the class-specific redundancy, our new loss function for learning
the system becomes:

$\textstyle{E_{tot}=E_{cl}+c_{1}E_{select}+c_{2}E_{r_{c}}}.$ (10)

###  2.4 Exploiting Substructures Within a Class.

For some real world problems, the data corresponding to a class may have
distinct clusters and some of the clusters may lie in different sub-spaces.
For example,in a multi-cancer gene expression data set, each cancer may have
several sub-types, where each sub-type is characterized by a different set of
genes/features. This generalizes the concept of class-specific feature
selection further. To exploit such local substructures within a class while
extracting rules, we need to use rule-specific feature modulators. Each rule
of the $k$th class is assumed to represent a local structure or cluster
present in the $k$th class. So, for the $k$th class there are $n_{k}\times P$
feature modulators. For the overall system there are $n_{rule}\times P$
feature modulators where, $n_{rule}(=\sum_{k=1}^{C}n_{k})$ is the total number
of rules. A modulator function is now represented by $M(\lambda_{j,kl})$ and
the corresponding modulated membership is the following.

$\textstyle{\hat{\mu}_{j,kl}=\mu_{j,kl}^{M(\lambda_{j,kl})}=\mu_{j,kl}^{\exp{(-\lambda_{j,kl}^{2})}}}$
(11)

The regularizer, $E_{select}$ is now modified as

$E_{select}=\textstyle{(\nicefrac{{1}}{{CP}})\sum_{k=1}^{C}(\nicefrac{{1}}{{n_{k}}})\sum_{l=1}^{n_{k}}\sum_{j=1}^{P}\exp{(-\lambda_{j,kl}^{2})}(1-\exp{(-\lambda_{j,kl}^{2})})}$
(12)

In this framework, we do not consider redundancy. Using (11) for $E_{cl}$ and
(12) for $E_{select}$ we define the loss function $E=E_{cl}+c_{1}E_{select}$
for discovering rule-specific feature subset.

##  3 Experimentation

We do three experiments to validate three main contributions of our proposed
framework. In Experiment 1, we show effectiveness of the proposed class-
specific feature selection over the usual global feature selection using a
FRBC. In Experiment 2, we demonstrate the significance of class-specific
redundancy control using our approach. In Experiment 3, a data set having
multiple sub-structures in different sub-spaces within a class is considered
to show the utility of our method. We do not tune the rule base parameters of
the FRBC and only tune the feature modulators to select/reject features. For
clustering, we use the $K$-means algorithm. To minimize the error functions
using stochastic gradient descent, we use the optimizer,
train.GradientDescentOptimizer from TensorFlow [1]. For all experiments, the
learning rate is set to $0.2$. As mentioned in sec.2 we denote the class-
specific feature subset for class 1 as $\mathbf{s}_{1}$, for class 2 as
$\mathbf{s}_{2}$ and so on.

###  3.1 Experiment 1

For the first experiment, we have considered a three class synthetic data set
Synthetic1 with six features having distributions as described in Table 1.

Table 1: Description of the dataset Synthetic1 Instances | Features | Class
---|---|---
$x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $x_{5}$ | $x_{6}$ | $\mathbf{y}$
$\mathbf{x}^{1}\cdots\mathbf{x}^{100}$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ | $1$
$\mathbf{x}^{101}\cdots\mathbf{x}^{200}$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ | $2$
$\mathbf{x}^{201}\cdots\mathbf{x}^{300}$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{N}(0,0.5)$ | $3$

Here, $\mathcal{N}(m,s)$ represents a normal distribution with mean, $m$ and
standard deviation, $s$; $\mathcal{U}(a,b)$ represents a uniform distribution
over the interval $(a,b)$. Without loss, we have assigned the first $100$
points to class $1$, next $100$ points to class 2 , and last $100$ points to
class 3. From Table 1 we can see that class 2 and class 3 are uniformly
distributed over a given interval for features $x_{1}$ and $x_{2}$. On the
other hand, class 1 is clustered around $(0,0)$ in the feature space formed by
$x_{1}$ and $x_{2}$. Hence the feature space formed by $x_{1}$ and $x_{2}$,
discriminate class 1 from the other two classes. Similarly, the feature spaces
formed of $(x_{3},x_{4})$ and $(x_{5},x_{6})$ discriminate class 2 and class 3
respectively, from the corresponding remaining classes. To understand the
importance of CSFS, we perform both global feature selection (GFS) and CSFS,
and compare their performances. We have also computed the performance of the
FRBC with all features. Number of rules considered per class is one. We have
conducted $5$ runs for each of the FRBC.

Table 2: Performance on Synthetic1 Run | Features selected | Avg. accuracy of FRBC (%)
---|---|---
Class-specific | Global | Class-specific | Global | All features
1-5 |  $\mathbf{s}_{1}:x_{1},x_{2}$; $\mathbf{s}_{2}:x_{3},x_{4}$; $\mathbf{s}_{3}:x_{5},x_{6}$ | $x_{3},x_{6}$ | 98.7 | 34.7 | 62.08

We observe from Table 2 that in class-specific feature selection, in all five
runs, for each class its characteristic features (i.e. $x_{1},x_{2}$ for class
1 and so on) are selected. The FRBC with the class-specific selected features
has achieved an average accuracy of $98.7\%$ \- in fact, each run achieved the
same accuracy. Whereas, in global feature selection, the selected subset is
$x_{3},x_{6}$. The FRBC using globally selected feature subset has achieved an
accuracy of of $34.7\%$ in each of the five runs. One can argue that the
class-specific model uses all six features, hence performs better than the
global model which uses two features. But, when we learn the FRBC rules using
all six features it has achieved an average accuracy of $62.08\%$ over the
five runs. Importance of class-specific feature selection is clearly
established through this experiment.

###  3.2 Experiment 2

For Experiment 2, we have considered another synthetic dataset Synthetic2
which is produced by appending two additional features $x_{7}$ and $x_{8}$ to
Sythetic1 data set. For class 1, $x_{7}$ and $x_{8}$ are generated as
$x_{1}+\mathcal{N}(0,0.1)$ and $x_{2}+\mathcal{N}(0,0.1)$, respectively. For
the other two classes, $x_{7}$ and $x_{8}$ are generated from
$\mathcal{U}(-10,10)$ and $\mathcal{U}(-10,10)$, respectively. We observe that
$x_{7}$ is dependent on $x_{1}$ and $x_{8}$ is dependent on $x_{2}$ for class
1 but the remaining two classes are indiscernible among themselves considering
a feature space with $x_{7}$ and $x_{8}$. Clearly, the features $x_{7},x_{8}$
are also discriminatory for class 1. However, do $x_{7},x_{8}$ add any
information over $x_{1},x_{2}$ for class 1? The answer is no, as for class 1,
$x_{7}$ and $x_{8}$ are noisy versions of $x_{1}$ and $x_{2}$, respectively.
This feature redundancy is specific to class 1. In Table 3 we have described
the performances of the FRBCs in the CSFS framework without and with class-
specific redundancy control.

Table 3: Class-specific feature selection with and without class-specific redundancy control on Synthetic2 data set Run | Without redundancy control | With class-specific redundancy control
---|---|---
Selected features | Acc. | Selected features | Acc.
1 |  $\mathbf{s}_{1}$:$x_{1},x_{2},x_{7},x_{8}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3 |  $\mathbf{s}_{1}$:$x_{2},x_{7}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3
2 |  $\mathbf{s}_{1}$:$x_{1},x_{2},x_{7}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3 |  $\mathbf{s}_{1}$:$x_{1},x_{8}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99
3 |  $\mathbf{s}_{1}$:$x_{1},x_{2},x_{7},x_{8}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3 |  $\mathbf{s}_{1}$:$x_{7},x_{8}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3
4 |  $\mathbf{s}_{1}$:$x_{1},x_{2},x_{7},x_{8}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3 |  $\mathbf{s}_{1}$:$x_{7},x_{8}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3
5 |  $\mathbf{s}_{1}$:$x_{1},x_{2},x_{7},x_{8}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99.3 |  $\mathbf{s}_{1}$:$x_{1},x_{7}$; $\mathbf{s}_{2}$:$x_{3},x_{4}$; $\mathbf{s}_{3}$:$x_{5},x_{6}$ | 99

Here also, we have set the number of fuzzy rules per class as one and repeated
the experiments five times with each model. The term ‘Acc.’ mentioned in Table
3 refers to accuracy of the FRBC in percentage. Table 3 confirms the
effectiveness of using class-specific redundancy control. For class 1,
features $x_{1}$ and $x_{7}$ are heavily dependent. Hence, to avoid redundancy
only one of them should be selected. The same argument is true for features
$x_{2}$ and $x_{8}$. Using an objective function (10) which considers a
regularizer on class-specific redundancy associated penalty (9), the FRBC has
successfully chosen only one from $x_{1}$ and $x_{7}$ and one from $x_{2}$ and
$x_{8}$ to include in $\mathbf{s}_{1}$ in all five runs. On the other hand, we
observe that without any redundancy control, the class-specific feature
selection framework selects all the four discriminating features to include in
$\mathbf{s}_{1}$ in four runs. The best accuracy achieved by the CSFS
framework without any redundancy control and that of CSFS with class-specific
redundancy control are same and equal to $99.3\%$ although the later selects
only two features. This experiment establishes the benefit of class-specific
redundancy control.

###  3.3 Experiment 3

In experiment 3, we validate our proposed framework for handling the presence
of different clusters or structures in different sub-spaces within a class. We
have synthesized, Synthetic3, a two class data having four features where each
class is composed of two distinct clusters lying in two different sub-spaces.
The data set Synthetic3 is described in Table 4.

Table 4: Description of the dataset Synthetic3 Instances | Features | Class
---|---|---
| $x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $\mathbf{y}$
$\mathbf{x}^{1}\cdots\mathbf{x}^{100}$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{N}(-5,0.5)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ | $1$
$\mathbf{x}^{101}\cdots\mathbf{x}^{200}$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{N}(0,0.5)$ | $1$
$\mathbf{x}^{201}\cdots\mathbf{x}^{300}$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{N}(0,0.5)$ |  $\mathcal{N}(-5,0.5)$ |  $\mathcal{U}(-10,10)$ | $2$
$\mathbf{x}^{301}\cdots\mathbf{x}^{400}$ |  $\mathcal{N}(5,0.5)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{U}(-10,10)$ |  $\mathcal{N}(-5,0.5)$ | $2$

Without loss, we have assigned the first $200$ points to class $1$, and the
last $200$ points to class 2. For class 1, instances $1$ to $100$ create a
distinct cluster around $(0,-5)$ in the feature space formed of $x_{1},x_{2}$
and instances $101$ to $200$ create a distinct cluster around $(0,0)$ in the
feature space formed of $x_{3},x_{4}$. Similarly, class 2 is also composed of
two groups of points creating two distinct clusters in the feature spaces
formed of $x_{2},x_{3}$ and $x_{1},x_{4}$ respectively. To handle a dataset
like Synthetic3 having within-class substructures we employ our proposed rule-
specific approach implemented using (11), and (12).

Table 5: Features subsets selected for synthetic3 Run | Rule-specific | Class-specific
---|---|---
| Class 1 | Class 2 | $\mathbf{s}_{1}$ | $\mathbf{s}_{2}$
1 | rule 1:$x_{1},x_{2}$; rule 2:$x_{3},x_{4}$ | rule 1:$x_{2},x_{3}$; rule 2:$x_{1},x_{4}$ | $x_{1}$ | $x_{1},x_{2}$
2 | rule 1:$x_{1},x_{2}$; rule 2:$x_{3},x_{4}$ | rule 1:$x_{1},x_{4}$; rule 2:$x_{2},x_{3}$ | $x_{2}$ | $x_{1},x_{2}$
3 | rule 1:$x_{3},x_{4}$; rule 2:$x_{1},x_{2}$ | rule 1:$x_{1},x_{4}$; rule 2:$x_{2},x_{3}$ | $x_{2}$ | $x_{2}$
4 | rule 1:$x_{3},x_{4}$; rule 2:$x_{1},x_{2}$ | rule 1:$x_{1},x_{4}$; rule 2:$x_{2},x_{3}$ | $x_{2}$ | $x_{1},x_{2}$
5 | rule 1:$x_{3},x_{4}$; rule 2:$x_{1},x_{2}$ | rule 1:$x_{2},x_{3}$; rule 2:$x_{1},x_{4}$ | $x_{2}$ | $x_{2}$

As observed from Table 5, the rule-specific feature selection is successful in
identifying the two important sub-spaces i.e. $x_{1},x_{2}$ and $x_{3},x_{4}$
for class 1 and $x_{2},x_{3}$ and $x_{1},x_{4}$ for class 2. It is noteworthy
that for both the classes the selected rule-specific subsets interchange
between rule 1 and 2. This is natural as the cluster number assignment to
different groups of points for a class varies. We also note from Table 5,
using the class-specific feature selection method, in different runs,
$\mathbf{s}_{1}$ comprises of $x_{1}$ or $x_{2}$ and $\mathbf{s}_{2}$
comprises of $x_{2}$ or $x_{1},x_{2}$. These subsets obviously do not
characterize the classes correctly. The average accuracy of the FRBC with
using feature subsets selected by rule-specific, class-specific feature
selection and using all features are $100\%$, $77.4\%$, and $87.5\%$,
respectively. This demonstrates the usefulness of our proposed RSFS framework
in data sets having multiple subspace-based structures or clusters within a
class.

##  4 Conclusion

In this work, first, we have proposed a class-specific feature selection
scheme using feature modulators embedded in a fuzzy rule-based classifier. The
feature modulators can allow or stop the features from participating in the
classification process by modifying their parameters. The feature modulator
parameters are tuned by minimizing a loss function comprising of
classification error and a regularizer to make the modulators completely
select or reject features. This framework is used in [4, 5] for selecting
globally useful features. We modified it to make it suitable for CSFS. Our
proposed class-specific feature selection method does not employ OVA strategy
like most of the existing class-specific feature selection works and hence
free from the enhanced computational overload and hazards associated with the
existing OVA based methods. We have two more contributions. First, we have
extended the CSFS scheme so that it can monitor class-specific redundancy by
adding a suitable regularizer. Second, our CSFS framework is generalized to a
rule-specific feature selection framework to handle the presence of multiple
sub-space based structures or clusters within a class. All three approaches
are validated through three experiments on appropriate synthetic data sets.

## References

  * [1] Abadi, M., et al.: Tensorflow: A system for large-scale machine learning. In: 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). pp. 265–283 (2016), https://www.usenix.org/system/files/conference/osdi16/osdi16-abadi.pdf
  * [2] Banerjee, M., Pal, N.R.: Unsupervised feature selection with controlled redundancy (ufescor). IEEE Transactions on Knowledge and data engineering 27(12), 3390–3403 (2015)
  * [3] Chakraborty, R., Pal, N.R.: Feature selection using a neural framework with controlled redundancy. IEEE transactions on neural networks and learning systems 26(1), 35–50 (2014)
  * [4] Chen, Y.C., Pal, N.R., Chung, I.F.: An integrated mechanism for feature selection and fuzzy rule extraction for classification. IEEE Transactions on Fuzzy Systems 20(4), 683–698 (2011)
  * [5] Chung, I.F., Chen, Y.C., Pal, N.R.: Feature selection with controlled redundancy in a fuzzy rule based framework. IEEE Transactions on Fuzzy Systems 26(2), 734–748 (2017)
  * [6] Ezenkwu, C.P., Akpan, U.I., Stephen, B.U.A.: A class-specific metaheuristic technique for explainable relevant feature selection. Machine Learning with Applications 6, 100142 (2021)
  * [7] Gupta, M.M., Qi, J.: Theory of t-norms and fuzzy inference methods. Fuzzy sets and systems 40(3), 431–450 (1991)
  * [8] de Lannoy, G., François, D., Verleysen, M., et al.: Class-specific feature selection for one-against-all multiclass svms. In: ESANN. Citeseer (2011)
  * [9] Nardone, D., Ciaramella, A., Staiano, A.: A sparse-modeling based approach for class specific feature selection. PeerJ Computer Science 5, e237 (2019)
  * [10] Panthong, R., Srivihok, A.: Liver cancer classification model using hybrid feature selection based on class-dependent technique for the central region of thailand. Information 10(6), 187 (2019)
  * [11] Pineda-Bautista, B.B., Carrasco-Ochoa, J.A., Marti$\acute{n}$ez-Trinidad, J.F.: General framework for class-specific feature selection. Expert Systems with Applications 38(8), 10018–10024 (2011)
  * [12] Qian, Y.: Class-specific guided local feature selection for data classification. In: 2019 IEEE 4th International Conference on Cloud Computing and Big Data Analysis (ICCCBDA). pp. 645–649. IEEE (2019)
  * [13] Yuan, L.m., Sun, Y., Huang, G.: Using class-specific feature selection for cancer detection with gene expression profile data of platelets. Sensors 20(5), 1528 (2020)
  * [14] Zhou, W., Dickerson, J.A.: A novel class dependent feature selection method for cancer biomarker discovery. Computers in biology and medicine 47, 66–75 (2014)