# Autonomous Search of Semantic Objects in Unknown Environments

Zhentian Qian1, Jie Fu2, and Jing Xiao1 1Zhentian Qian* and Jing Xiao are with
the Robotics Engineering Department, Worcester Polytechnic Institute,
Worcester, MA, USA<EMAIL_ADDRESS><EMAIL_ADDRESS>2Jie Fu is with the
Department of Electrical and Computer Engineering, University of Florida,
Gainesville, FL, USA<EMAIL_ADDRESS>
###### Abstract

This paper addresses the problem of enabling a robot to search for a semantic
object in an unknown and GPS-denied environment. For the robot in the unknown
environment to detect and find the target object, it must perform simultaneous
localization and mapping (SLAM) at both geometric and semantic levels using
its onboard sensors while planning and executing its motion based on the ever-
updated SLAM results. In other words, the robot must be able to conduct
simultaneous localization, semantic mapping, motion planning, and execution in
real-time in the presence of sensing and motion uncertainty. This is an open
problem as it combines semantic SLAM based on perception and real-time motion
planning and execution under uncertainty. Moreover, the goals of robot motion
change on the fly depending on whether and how the robot can detect the target
object. We propose a novel approach to tackle the problem, leveraging semantic
SLAM, Bayesian Networks, Markov Decision Process, and real-time dynamic
planning. The results demonstrate the effectiveness and efficiency of our
approach.

###### Index Terms:

Reactive and Sensor-Based Planning, Semantic SLAM, Semantic Scene
Understanding, Planning under Uncertainty.

##  I INTRODUCTION

This paper is motivated by the problem of searching an unknown environment for
some target object, which is a fundamental problem in many application
scenarios from search and rescue to reconnaissance to elderly care.

###  I-A Related Work

There is a significant amount of literature on simultaneous localization and
mapping (SLAM) for robot mapping and navigation in an unknown environment
based on perception, such as visual and odometry sensing. SLAM methods model
and reduce sensing uncertainties in mapping the unknown environment and
localizing the robot in it at the same time. Semantic SLAM and active SLAM are
particularly relevant.

Semantic SLAM methods are focused on representing, mapping, and localizing 3D
objects and use different representations of objects such as meshes [1],
quadric [2, 3], cuboid [4], and OctoMap [5].

Active SLAM aims to choose the optimal trajectory for a robot to improve map
and localization accuracy and maximize the information gain. The localization
accuracy is typically measured by metrics such as A-opt (sum of the covariance
matrix eigenvalues)[6, 7], D-opt (product of covariance matrix eigenvalues)
[8], E-opt (largest covariance matrix eigenvalue) [9]. Information gain is
measured in metrics such as joint entropy [10] and expected map information
[11].

However, neither semantic nor active SLAM considers performing tasks other
than mapping an unknown environment. The planning aspect is not addressed for
semantic SLAM and is downplayed in active SLAM with simple methods such as
A*[8].

Robot path and motion planning is one of the most studied areas in robotics.
The basic objective is to find an optimal and collision-free path for a robot
to navigate to some goals in an environment. Many traditional path-planning
approaches assume a more or less known environment, i.e., the robot already
has a map and models of objects [12]. On the other hand, real-time, sensing-
based planning in an unknown environment still largely remains a challenge
[13].

Earlier work includes grid-based planning approaches such as D* [14] and D*
Lite [15], sampling-based approaches such as ERRT[16] and DRRT [17], and
adaptive approaches such as [18]. These approaches consider the environment
dynamic and partially known, but assume the goal position is known, disregard
the uncertainties in sensing, the robot pose, and dynamics, and do not
consider semantic information.

Recently, various techniques based on partially observable Markov decision
processes (POMDPs) have been developed [19, 20, 21] to incorporate sensing and
robot motion uncertainties into planning in partially observable environments.
However, POMDP suffers from the curse of dimensionality and is computationally
expensive, particularly when the state space is large. For the POMDP to scale,
high-level abstraction must be made for the state space. For example, treat
objects [20] or rooms[19] as state variables. The downside is that highly-
abstracted models can lose touch with reality. To bypass this problem, some
researchers turn to deep learning to learn semantic priors and make
predictions on the unobserved region [22, 23]. These methods tend to suffer
from poor generalization.

Next-best view planning is another highly related topic, designed for
efficient visual exploration of unknown space. Unlike active SLAM, approaches
for next-best view planning typically do not consider robot localization
uncertainty. A next-best view planner starts by sampling a set of views in the
environment, evaluates the estimated information gain for each view, and
selects the view with the maximum information gain as the next view [24].
Different methods differ in the sampling methods (uniform sampler, frontier-
based coverage sampler [25]), information gain (path costs are incorporated in
[26, 25]), and the selection of the next view (receding horizon scheme in
[27], Fixed Start Open Traveling Salesman Problem (FSOTSP) solver in [25]).

However, existing planning methods in unknown environments usually do not
consider real-time results from SLAM with embedded and changing uncertainties,
such as the robot’s pose, the metric map, and the semantic map (generated by
semantic SLAM). Only the metric map was used by next-best view planning
approaches [24, 25, 26].

###  I-B Approach and Contributions

The problem we focus on in this paper, i.e., searching a target object in an
unknown and GPS-denied environment, requires real-time planning and execution
of the robot’s motion to perform the following two necessary tasks
concurrently, which are intertwined and mutually facilitating:
– Simultaneous localization and mapping at both semantic and geometric levels
to facilitate the search of the target object.
– Real-time planning and execution of search motion towards the target object
based on semantic SLAM results or to expand and improve semantic SLAM results
to find and identify the target object.
This paper addresses such novel challenges by leveraging the probabilistic
representation of semantic SLAM outcomes (constantly improved), Bayesian
network [28] representation of semantic knowledge relating the target object
to surrounding objects and Markov decision process (MDP) formulation. It
introduces a novel, adaptive planner that synergizes:
1) active semantic SLAM with improved SLAM results,
2) real-time motion planning under sensing and motion uncertainty in the
partially observed world represented by ever-updated semantic SLAM results,
3) real-time determination of (intermediate) goals of motion on the fly and
based on ever-improved semantic knowledge.

##  II System Overview

Fig. 1 provides an overview of our system. The robot starts by scanning the
environment with its onboard RGB-D sensor. The color and depth images from the
RGB-D sensor are fed into geometric and semantic SLAM modules. The SLAM
modules then update the robot’s location, the (observed) free and occupied
space, and objects detected in the environment; the updated localization and
map information are fused in a single map $E_{t}$, where the subscript $t$
stands for time instance.

Next, the robot determines a goal of motion and plans a path based on $E_{t}$,
to either explore new regions or inspect the candidate target object. It first
checks whether it has reached the current goal. If not, the robot executes the
planned path. Otherwise, either the task is complete, or the robot forms a new
goal.

In the goal-forming process, based on $E_{t}$ and additional semantic
information about the target object $o_{T}$, the robot decides if it should
search for $o_{T}$ in the explored space or further observe a detected object
that is likely $o_{T}$. It then updates the optimal policies for reaching the
newly formed goal. During the entire operation, the robot continuously checks
if it has found the target object instance $o_{T}$ with high confidence. If
not, the robot will repeat the above processes until it has reached the time
limit or explored all regions.

Figure 1: System Overview

##  III Mapping and localization

In this section, we describe how geometric and semantic SLAM is achieved, and
the information from different levels is fused into a single map $E_{t}$.

###  III-A Geometric SLAM

Geometric SLAM and semantic SLAM modules run in parallel in our system. We
employ the RTAB-MAP [29] algorithm for geometric SLAM. It generates a grid map
$\mathbf{G}_{t}\in\\{0,1,-1\\}^{W\times H}$, where $W$ and $H$ are the width
and height of the grid map. $0$, $1$, and $-1$ in the grid map represent free,
occupied, and unknown space respectively, as shown in Fig. 2. The geometric
SLAM module also estimates the robot pose
$(\mathbf{\mu}_{p,t},\mathbf{\Sigma}_{p,t})$, where $\mathbf{\mu}_{p,t}$ and
$\mathbf{\Sigma}_{p,t}$ are the mean and covariance of the robot pose at time
instance $t$.

Figure 2: Grid map at time $t$. The grey, white, and black areas represent
unknown, free, and occupied regions.

We use off-the-shelve tools [30] to segment the grid map into different
geometric rooms: a room is defined as any space enclosed within a number of
walls to which entry is possible only by a door or other dividing structure
that connects it either to a hallway or to another room. Every grid on the
grid map $\mathbf{G}_{t}$ is assigned with a corresponding room ID:
$\mathbf{R}_{t}\in\mathbb{N}^{W\times H}$. An example is provided in Fig. 3.

Figure 3: Segmented geometric rooms at time $t$. The two segmented rooms are
encoded in different colors.

###  III-B Semantic SLAM

We adapt the system introduced in [31] for semantic SLAM. At time instance
$t-1$, the position estimation $\mathbf{m}_{i,t-1}\in\mathbb{R}^{2}$ for the
semantic object $o_{i}$ is:

$bel(\mathbf{m}_{t-1})\sim\mathcal{N}(\mu_{t-1},\mathbf{\Sigma}_{t-1}),$ (1)

Where $bel(\cdot)$ stands for the belief over a variable. Note that for
simplicity, the subscript $i$ is dropped in (1), as in (2)–(4).

At time instance $t$, the robot pose $\mathbf{x}_{t}\in\mathbb{R}^{2}$
estimated by geometric SLAM is
$bel(\mathbf{x}_{t})\sim\mathcal{N}(\mathbf{\mu}_{p,t},\mathbf{\Sigma}_{p,t})$.

If the semantic object $o_{i}$ is detected on the color image
$\mathbf{I}_{t}$, range-bearing measurement $\mathbf{z}_{t}$ will be generated
based on the depth information of $o_{i}$ from the depth image. The range-
bearing measurement noise $\mathbf{\delta}_{t}$ is:

$\mathbf{\delta}_{t}\sim\mathcal{N}(0,\mathbf{\Sigma}_{\delta}).$ (2)

The covariance of the range-bearing measurement $\Sigma_{\delta}$ is assumed
to be independent of time. Then the posterior belief $bel(\mathbf{m}_{t})$ at
time $t$ can be updated using Bayes’ theorem:

$\begin{split}bel(\mathbf{m}_{t})&=p(\mathbf{m}|\mathbf{z}_{1:t})=\frac{p(\mathbf{z}_{t}|\mathbf{m},\mathbf{z}_{1:t-1})\cdot
p(\mathbf{m}|\mathbf{z}_{1:t-1})}{p(\mathbf{z}_{t}|\mathbf{z}_{1:t-1})}\\\
&=\eta\int p(\mathbf{z}_{t}|\mathbf{m},\mathbf{x}_{t})\cdot
bel(\mathbf{x}_{t})\cdot bel(\mathbf{m}_{t-1})d\mathbf{x}_{t},\end{split}$ (3)

where $\eta$ is a normalizing term.

Substituting the probability density functions of
$p(\mathbf{z}_{t}|\mathbf{m},\mathbf{x}_{t})$, $bel(\mathbf{x}_{t})$, and
$bel(\mathbf{m}_{t-1})$ into (3), the final result after simplification
suggests that the updated posterior belief $bel(\mathbf{m}_{t})$ can be
approximated by a multivariate Gaussian distribution
$bel(\mathbf{m}_{t})\sim\mathcal{N}(\mu_{t},\mathbf{\Sigma}_{t})$, where

$\displaystyle\mathbf{\Sigma}_{t}$
$\displaystyle=\Big{(}\mathbf{K}_{1}^{T}\mathbf{\Sigma}_{\delta}^{-1}\mathbf{K}_{1}+\mathbf{\Sigma}_{t-1}^{-1}-\mathbf{K}_{1}^{T}\mathbf{\Sigma}_{\delta}^{-1}\mathbf{K}_{2}\mathbf{\Psi}\mathbf{K}_{2}^{T}\mathbf{\Sigma}_{\delta}^{-1}\mathbf{K}_{1}\Big{)}^{-1},$
$\displaystyle\mu_{t}$
$\displaystyle=\mu_{t-1}+\mathbf{\Sigma}_{t}\mathbf{K}_{1}^{T}(\mathbf{\Sigma}_{\delta}^{-1}-\mathbf{\Sigma}_{\delta}^{-1}\mathbf{K}_{2}\mathbf{\Psi}\mathbf{K}_{2}^{T}\mathbf{\Sigma}_{\delta}^{-1})\Delta\mathbf{z}_{t}.$

$\Delta\mathbf{z}_{t}$ is the error between expected and actual range-bearing
measurement. The complete derivation is omitted here.

The object class probability distribution $p_{t}(\cdot)$ is updated using
Bayes’ theorem:

$\begin{split}p_{t}(c)&=p(c|\mathbf{L}_{1:t})=\frac{p(\mathbf{L}_{t}|c,\mathbf{L}_{1:t-1})\cdot
p(c|\mathbf{L}_{1:t-1})}{p(\mathbf{L}_{t}|\mathbf{L}_{1:t-1})}\\\ &=\eta
p(\mathbf{L_{t}}\lvert c)\cdot p_{t-1}(c)=\frac{p(\mathbf{L_{t}}\lvert c)\cdot
p_{t-1}(c)}{\sum_{c^{\prime}\in\mathbb{C}}p(\mathbf{L}_{t}\lvert
c^{\prime})p_{t-1}(c^{\prime})},\end{split}$ (4)

where $\eta=1/p(\mathbf{L}_{t}|\mathbf{L}_{1:t-1})$ is a normalization
constant, $\mathbf{L}_{t}\in\mathbb{R}^{\lvert\mathbb{C}\rvert}$ is the
confidence level distribution of an object in different classes, returned by
an object detector, such as YOLOv3 [32] at time $t$. $c\in\mathbb{C}$ is one
of the possible object classes. $p(\mathbf{L}_{t}|c)$ is the object detector
uncertainty model, representing the probability of object detector outputs
$\mathbf{L}_{t}$ when the object class is $c$. We use the Dirichlet
distribution ${\displaystyle\operatorname{Dir}({\boldsymbol{\alpha}}_{c})}$ to
model this uncertainty, with a different parameter
$\boldsymbol{\alpha}_{c}\in\mathbb{R}^{\lvert\mathbb{C}\rvert}$ for each
object class $c$.

Finally, based on the locations of map objects, the corresponding geometric
room IDs are assigned to the objects. Formally, the map object $o_{i}$ is
represented as a 4-tuple $o_{i}=\langle\mu_{i},\Sigma_{i},p_{i},r_{i}\rangle$
with $\mu_{i}$ and $\Sigma_{i}$ the mean and covariance of the object $o_{i}$
pose, $p_{i}$ the object class distribution, and $r_{i}$ the room ID of
$o_{i}$. The object map is the set of observed map objects
$\mathbb{O}_{t}=\\{o_{1},o_{2},\ldots,o_{n}\\}$. The fused map
$E_{t}=\langle\mathbf{G}_{t},\mathbb{O}_{t},\mathbf{R}_{t}\rangle$ collects
the grid map $\mathbf{G}_{t}$, object map $\mathbb{O}_{t}$, as well as the
room information $\mathbf{R}_{t}$.

##  IV Information for Goal Forming.

As the robot’s mission is to find a target object in an unknown environment,
its goal of motion will be determined on the fly depending on the information
provided by the fused map $E_{t}$ and the robot’s location. The mission is
accomplished if the target object is visible and identified as such.
Otherwise, there are several types of intermediate goals for the robot motion:
– if the target object is not included in the current map $E_{t}$, the robot
chooses to explore more. This intermediate goal requires frontier detection;
– if an object in the map is likely the target object (with a low
probability), the robot chooses to observe more of the object in its
visibility region;
– if an object in the map is related to the target object based on the
semantic information that they are likely in the same geometric room, the
robot chooses to move to that room in the hope of being able to see the target
object once it is there.

###  IV-A Frontier Detection

The Frontier region is the set of cells between free and unknown space in the
grid map $\mathbf{G}_{t}$. Formally, a grid cell $(i,j)$ belongs to the
frontier region if and only if $\mathbf{G}_{t}[i,j]=0$ and $\exists
k\in\\{0,1,-1\\},\exists l\in\\{0,1,-1\\}\colon\mathbf{G}_{t}[i+k,j+l]=-1$.

We use the Canny edge detector [33] to detect the grid cells between free and
unknown. The detected cells are grouped into edges using 8-connectivity, i.e.,
each cell with coordinates $(i\pm 1,j\pm 1)$ is connected to the cell at
$(i,j)$. Similar to map objects, a frontier edge $e_{j}$ is also assigned a
room ID $r_{j}$ based on its position. The frontier region is defined as
$\mathbb{F}_{t}=\\{\langle e_{1},r_{1}\rangle,\langle
e_{2},r_{2}\rangle,\ldots,\langle e_{m},r_{m}\rangle\\}$, where $m$ is the
number of frontier edges. Edges with area $\lvert e_{j}\rvert$ smaller than 15
cells are deemed as noise and excluded from $\mathbb{F}_{t}$. The frontier
region at time $t$ is drawn in green in Fig. 4.

Figure 4: The frontier region computed at time $t$, marked in green.

###  IV-B Visibility Region Computation

At time $t$, the visibility region $\mathbb{V}_{t}$ for an object $o_{i}$ in
the grid map $G_{t}$ with obstacles is the region of all cells on the grid map
$G_{t}$ that object $o_{i}$ is visible. That is, if a line connecting the
position of $o_{i}$ and a cell $q$ does not intersect with any obstacle cell
and is within the sensing range, then $q\in\mathbb{V}_{t}$. We apply a uniform
ray-casting algorithm to compute the visibility region. Rays originating from
the object’s position are cast in many directions. Regions illuminated by the
ray (reached by it) are considered the visibility region $\mathbb{V}_{t}$. The
visibility region for one object is drawn in blue in Fig. 5.

For efficient planning, we only compute the visibility region for the object
most likely in the target object category $c_{T}$. We refer to this object as
the object of interest $o_{I}$, $I=\operatorname*{arg\,max}_{i}p_{i}(c_{T})$.

Figure 5: The visibility region computed for one object instance at time $t$,
marked in blue.

###  IV-C Semantic Prior Knowledge

We leverage prior semantic knowledge to facilitate efficient exploration. The
key idea is that objects in the target category may have a closer affinity to
some categories of objects than others. The co-occurrence relationship between
objects of two categories is estimated based on Lidstone’s law of succession
[34]:

$p(c_{i}\mid
c_{j})=\frac{N(c_{i},c_{j})+\alpha}{N(c_{j})+\alpha\lvert\mathbb{C}\rvert},$
(5)

where $p(c_{i}\mid c_{j})$ is the conditional probability of object of class
$c_{i}$ being in a geometric room given object of class $c_{j}$ is already
observed in the same room. $N(c_{i},c_{j})$ is the number of times objects of
classes $c_{i}$ and $c_{j}$ are observed in the same room. $N(c_{j})$ is the
number of times object of category $c_{j}$ are obsereved in a room.
$\alpha\in[0,\infty)$ is a smoothing factor, and finally
$\lvert\mathbb{C}\rvert$ is the number of classes.

The probabilistic co-occurrence relationships of multiple pairs of objects are
captured using Eq. (5) and further assembled into multiple Bayesian networks.
We construct a set of Bayesian networks
$\mathcal{B}=\\{B_{1},B_{2},\ldots\\}$, with one for each semantic space
$\mathcal{S}=\\{S_{1},S_{2},\ldots\\}$. Each semantic space corresponds to one
room category, such as kitchen, bedroom, bathroom, etc. An example of a
Bayesian Network is illustrated in Fig. 6, demonstrating common object classes
found in a kitchen and their conditional dependency. For each geometric room
$r_{i}$ in the environment, we will collect the set of object classes
$\mathbb{E}_{i}=\\{c_{1},c_{2},\ldots\\}$ that are observed in the room
$r_{i}$. Recall that we keep a class probability distribution for each map
object. Thus we cannot draw a deterministic conclusion regarding the presence
of a certain object class in the room $r_{i}$. However, to keep the problem
tractable, we assume the presence of object class $c_{k}$ if for any object
$o_{j}$ in the room, the probability of the object $o_{j}$ being in class
$c_{k}$ exceeds some threshold $\lambda$: $c_{k}\in\mathbb{E}_{i}\iff\exists
j,\,p_{j}(c_{k})>\lambda$.

Given the evidence set $\mathbb{E}_{i}$, we only consider the Bayesian
networks in $\mathcal{B}$ that contains the target object instance $c_{T}$ and
shares nodes with $\mathbb{E}_{i}$; name this new set $\mathcal{B}_{i}$. By
doing so, we narrow down the possible semantic space categories for the
geometric room $r_{i}$ to a subset $\mathcal{S}_{i}$, which corresponds to
$\mathcal{B}_{i}$. For each Bayesian network $B_{j}\in\mathcal{B}_{i}$, we can
compute the probability of finding the target object instance $o_{T}$ in the
room $r_{i}$ based on evidence $\mathbb{E}_{i}$, denoted as
$P(c_{T}\mid\mathbb{E}_{i},r_{i},B_{j})$.

We can then infer the probability of finding the target object instance
$o_{T}$ in the same room $r_{i}$ by feeding $\mathbb{E}_{i}$ into the Bayesian
network set $\mathcal{B}_{i}$:

$P(c_{T}\mid\mathbb{E}_{i}=\\{c_{1},c_{2},\ldots\\},r_{i})=\max_{B_{j}\in\mathcal{B}_{i}}P(c_{T}\mid\mathbb{E}_{i},r_{i},B_{j}).$

This probability is computed for all geometric rooms.

Figure 6: Bayesian Network

##  V Planning Approach

We now describe how the intermediate goal is determined for the robot on the
fly and how the optimal policy for reaching the intermediate goal is computed
for the robot.

###  V-A Robot Model

The robot is a stochastic dynamic system and can be represented by a Markov
decision process (MDP) $\text{M}_{t}=\langle S,A,P,R,F\rangle$ with the
following components:
— $S$ is the discrete state space, representing the mean of the Gaussian
distribution of the robot position. The mean of the robot’s position is
discretized and clipped to the closest grid cell in the grid map
$\mathbf{G}_{t}$ to avoid an infinite state space.

— $A$ is a set of actions. We consider eight actions that allow the robot to
move horizontally, vertically, and diagonally to reach its eight neighboring
grid cells. A low-level controller is used to map the actions into the robot
command.

— $P\colon S\times A\times S\to[0,1]$ is the transition probability function,
where $P(\cdot\mid s,a)$ represents the probability distribution over next
states given an action $a$ taken at the current state $s$. For example, for
the move-up action, the robot has a high probability of moving up one cell,
but it also has a small probability of moving to the upper-left or upper-right
cell.

— $R\colon S\times A\times S\to\mathbb{R}$ is the reward function, where
$R(s,a,s^{\prime})$ is the reward for executing action $a\in A$ at state $s\in
S$ and reaching next state $s^{\prime}\in S$.

— $F\subset S$ is the set of (intermediate) goal states, which are determined
on the fly, as described in Section V-C.

###  V-B Reward Shaping

To compute policies that can drive the robot to the frontier region
$\mathbb{F}_{t}$ or visibility region $\mathbb{V}_{t}$, for exploration or re-
observation, we define two reward functions accordingly.

####  V-B1 Reward function for reaching $\mathbb{F}_{t}$

The reward function $R(s,a,s^{\prime})$ is designed as:

$R(:,:,s^{\prime})=P(\mathbf{x}\in e_{j}\mid s^{\prime})\cdot
P(c_{T}\mid\mathbb{E},r_{i})\cdot\lvert e_{j}\rvert,$ (6)

where $P(\mathbf{x}\in e_{j}\mid s^{\prime})$ is the probability of the robot
being at frontier edge $e_{j}$ if its mean position is $s^{\prime}$.
$P(c_{T}\mid\mathbb{E},r_{i})$ is the probability to find target object
instance $c_{T}$ in geometric room $r_{i}$ where edge $e_{j}$ lies given the
current evidence $\mathbb{E}$. $\lvert e_{j}\rvert$ is the size of the
frontier edge, representing the possible information gain by exploring
$e_{j}$. $P(\mathbf{x}\in e_{j}\mid s^{\prime})$ can be calculated by first
discretizing the robot’s Gaussian position distribution (with mean at
$s^{\prime}$) based on $\mathbf{G}_{t}$ and then summing up the probability of
the robot at each cell that belongs to $e_{j}$. $P(c_{T}\mid\mathbb{E},r_{i})$
is calculated using the Bayesian network, as discussed in Section IV-C.

####  V-B2 Reward function for reaching $\mathbb{V}_{t}$

The reward function $R(s,a,s^{\prime})$ is designed as:

$R(:,:,s^{\prime})=P(\mathbf{x}\in\mathbb{V}_{t}\mid s^{\prime}),$ (7)

which is the probability of the robot being in visibility region
$\mathbb{V}_{t}$ if its mean position is $s^{\prime}$.

###  V-C Goal Determination

We use an optimistic approach in determining the intermediate goal. If the
probability of the object of interest $o_{I}$ being in the target object
category $c_{T}$ exceeds a threshold $\tau$, i.e., $p_{I}(c_{T})>\tau$, then
the intermediate goal is to re-observe the object of interest $o_{I}$, and the
reward function is as defined in (7). Otherwise, the intermediate goal is to
explore the frontier region, and the reward function is defined as (6).

###  V-D Planner

The MDP $\mathbf{M}_{t}$ and the selected reward function $R$ are fed into a
planner based on the Real Time Dynamic Programming (RTDP) algorithm [35] to
compute an optimal policy $\pi^{*}$ that maximizes the expected sum of
rewards, i.e., value function $\mathcal{V}$. A value function $\mathcal{V}$
starting at state $s\in S$ following policy $\pi$ is defined as follows:

$\displaystyle\mathcal{V}^{\pi}(s)=\operatorname{E}_{\pi}[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t},s_{t+1})],$

where $\pi\colon S\to A$ is a deterministic policy over $\mathbf{M}_{t}$
mapping the state into an action, and $\gamma\in[0,1)$ is a discounting
factor. The optimal policy $\pi^{\ast}$ is computed as follows: for all $s\in
S$,

$\displaystyle\pi^{\ast}(s)=\operatorname*{arg\,max}_{\pi\in\Pi}\mathcal{V}^{\pi}(s).$

The RTDP algorithm allows us to compute a semi-optimal policy in a short
time111Unlike a more traditional approach such as value iteration [36].. As
the robot carries out the semi-optimal policy, the policy will be continuously
improved by the RTDP algorithm with the current robot mean position as the
initial state $s_{0}$ and converges to the optimal policy.

###  V-E Adaptation

The fused map $E_{t}$, frontier region $\mathbb{F}_{t}$, and visibility region
$\mathbb{V}_{t}$ are updated at every time instance $t$ based on the ever-
improving semantic SLAM results. Consequently, once the robot reaches an
intermediate goal state, the MDP model $\text{M}_{t}$ needs to be updated
based on the new fused map $E_{t}$. We call this process the adaptation of the
MDP model. Next, the corresponding policy $\pi$ also needs to be updated.

Specifically, the following components are adapted: (a) the discrete state
space $S$ to match the changing grid map $\mathbf{G}_{t}$, (b) the transition
probability function $P$, (c) the reward function $R$ based on Eqs. (6) and
(7), and (d) the set of intermediate goal states $F$ as $\mathbb{F}_{t}$ and
$\mathbb{V}_{t}$ change. The RTDP planner takes the updated MDP model
$\text{M}_{t}$ to generate a new policy.

##  VI EXPERIMENTS

We have performed experiments on the Matterport3D (MP3D) [37] dataset using
the Habitat [38] simulator. MP3D dataset contains 3D scenes of a common indoor
environment, and the Habitat simulator allows the robot to navigate the
virtual 3D scene. Given the towel as the target object category, the robot’s
objective is to find any instance of the target with a confidence level
greater than $1-\epsilon=0.99$. The action space of the robot is continuous,
constituting its angular and linear velocity. An episode is only successful if
the agent stops its motion when it has identified the target within a specific
time budget (1K seconds). Five episodes are run for each method, with the
robot placed at a random position at the beginning of each episode. Two shots
of the MP3D scene are given in Fig. 7. This particular scene is $6.4m\times
8.4m$ in size, and has one level, ten rooms, and 187 objects. The robot start
positions and the target object instances are visualized in Fig. 8,
represented as blue boxes and yellow diamonds.

The accompanying video shows the robot’s operations to find target objects
with different starting locations.

Figure 7: Two snap shots of the MP3D scene. Figure 8: Target objects (yellow
diamonds) and robot start positions (blue boxes).

###  VI-A Semantic SLAM results

We present the semantic SLAM results obtained during one episode. Our
evaluation focuses on the accuracy and uncertainty of the collected results.

####  VI-A1 Accuracy

We calculate the mean and the median of the error between the predicted
objects’ position and the ground-truth objects’ position:

$\text{Mean}=\frac{\sum_{i=1}^{n}\lVert{\hat{p}}_{i}-p_{i}\rVert}{n},\hskip
5.69054pt\text{Median}=\operatorname{median}(\lVert{\hat{p}}_{i}-p_{i}\rVert),$

where $n$ is the current number of objects, $\hat{p}_{i}$ is the estimated
object position and $p_{i}$ is the ground truth object position. Their
variations with respect to time are plotted in Fig. 9. For reference, the
number of identified objects at each time instance is also plotted in Fig. 10.
We can see that the error increases for the first few seconds as new objects
are identified. Nonetheless, as more observations come in, the error decreases
and converges. We can also see that the calculated average error appears
larger than the median value. This is because some objects only receive one
observation. As a result, their positions are not updated, contributing to a
large error. For this reason, the median error is considered a more sensible
metric in our case, which is kept at a reasonable level.

In the same spirit, we also calculate the cross entropy between the predicted
objects’ classes and the ground-truth objects’ classes:
$-\frac{1}{n}\sum_{i=1}^{n}\sum_{c\in{\mathbb{C}}}p^{gt}_{i}(c)\,\log
p_{i}(c)$. $p_{i}(\cdot)$ is the predicted object class distribution,
$p_{i}^{gt}(\cdot)$ is the ground truth of object class distribution, taking
the value one at the corresponding object class and zero elsewhere. The
results are plotted in Fig. 11. We can see that the cross entropy gradually
decreases with time, proving that the predicted objects’ classes would
converge to the correct results.

####  VI-A2 Uncertainty

Though we do not claim our method to be an active SLAM method, we observe a
decrease in semantic map uncertainty as the robot progresses. The average
A-opt (sum of the covariance matrix eigenvalues), D-opt (product of covariance
matrix eigenvalues), and E-opt (largest covariance matrix eigenvalue) of the
map object position covariance are calculated. Their evolution over time is
plotted in Fig. 12. The spikes in the graph indicate the identification of new
objects, hence the increased position uncertainty. However, as time goes by
and more observations come in, we can see that all three metrics are kept at a
low level. This shows that the robot can estimate the objects’ position fairly
confidently.

Fig. 13 gives a more intuitive representation. In Fig. 13, we plot the
Gaussian functions with their means and covariances set as the estimated
object position means and covariances. Therefore, each “bell” in the plot
represents one object. Comparing the results we obtained at time instants
$t=8s$ and $t=70s$. We can see that at $t=70s$, the bell’s peak increases, and
the base decreases, indicating a more certain estimation of the object’s
position.

The entropy of the predicted object class is also calculated:
$-\frac{1}{n}\sum_{i=1}^{n}\sum_{c\in{\mathbb{C}}}p_{i}(c)\,\log p_{i}(c)$ and
visualized in Fig. 14. The result suggests that as time progresses, the robot
is more and more certain about the object class that it predicted.

Figure 9: Mean and median of the error between the predicted objects’ position
and the ground-truth objects’ position. Figure 10: Number of identified
objects with respect to time. Figure 11: Cross entropy between the predicted
objects’ classes and the ground-truth objects’ classes. Figure 12: The
evolution of the object position covariance with respect to time.

(a) $t=8s$.

(b) $t=70s$.

Figure 13: Object position covariance at time instant $t=8s$ and time instant
$t=70s$ Figure 14: The evolution of the predicted object class entropy with
respect to time

###  VI-B Planning results

We evaluate the performance of our planning method vs. other navigation
strategies: FE-SS: a frontier exploration method [39] with rewards defined by
(6), and equipped with our custom Semantic SLAM, and Ours-NS: ablation of our
method without semantic prior knowledge and using a uniform reward. To
evaluate all methods, we report the following metrics:
Success: percentage of successful episodes
Average path length: average length of the path taken by the agent in an
episode.
Success weighted by path length (SPL) [40]:
$\frac{1}{N}\sum_{i=1}^{N}S_{i}\frac{l_{i}}{\max(p_{i},l_{i})}$, where
$l_{i}$$=$length of the shortest path between goal and the visibility region
of target instance for an episode, $p_{i}$$=$length of the path taken by the
agent in an episode, $S_{i}$$=$ binary indicator of success in episode $i$.
Average planning time: average time spent on planning (excluding the time in
action).

The testing results are summarized in Table I. Our method outperforms other
methods in success rate, SPL, and path length by a large margin. Although our
method does not guarantee dominant performance in planning time, it still
exhibits advantages with a shorter average planning time for all episodes.

The ablation study is conducted by denying access to the semantic prior
knowledge in our method. A significant performance drop is observed on all
metrics after that. This proves the efficacy of using semantic prior knowledge
to guide our search for the target object.

Table I: Comparison study Method | Success | Path length (m) | SPL | Planning time (s)
---|---|---|---|---
Ours | 0.96 | 4.984 | 0.46 | 80.338
FE-SS | 0.80 | 6.796 | 0.39 | 105.514
Ours-NS | 0.68 | 8.726 | 0.41 | 97.716

##  VII Conclusions

We presented a novel approach to tackle the open problem of enabling a robot
to search for a semantic object in an unknown and GPS-denied environment. Our
approach combines semantic SLAM, Bayesian Networks, Markov Decision Process,
and real-time dynamic planning. The testing results on Matterport 3D dataset
demonstrate both the effectiveness and efficiency of our approach. Moreover,
while our approach is unique in incorporating semantic object information to
search for semantic targets, to evaluate its motion planning performance, we
compared it to a non-semantic baseline planning method and conducted an
ablation study. The results show that our approach has a higher success rate,
shorter path length, and less planning time. In the next step, we will
consider extending our approach to more complex, compound semantic tasks and
tasks that require the robot to interact with objects.

## References

  * [1] D. Gálvez-López, M. Salas, J. D. Tardós, and J. Montiel, “Real-time monocular object slam,” _Rob. Auton. Syst._ , vol. 75, pp. 435–449, 2016.
  * [2] L. Nicholson, M. Milford, and N. Sünderhauf, “Quadricslam: Dual quadrics from object detections as landmarks in object-oriented slam,” _IEEE Robot. Autom. Lett. (RA-L)_ , vol. 4, no. 1, pp. 1–8, 2018.
  * [3] Z. Qian, K. Patath, J. Fu, and J. Xiao, “Semantic slam with autonomous object-level data association,” in _IEEE Int. Conf. Robot. Autom. (ICRA)_ , 2021, pp. 11 203–11 209.
  * [4] S. Yang and S. Scherer, “Cubeslam: Monocular 3-d object slam,” _IEEE Trans. Robot. (T-RO)_ , vol. 35, no. 4, pp. 925–938, 2019.
  * [5] L. Zhang, L. Wei, P. Shen, W. Wei, G. Zhu, and J. Song, “Semantic slam based on object detection and improved octomap,” _IEEE Access_ , vol. 6, pp. 75 545–75 559, 2018.
  * [6] C. Leung, S. Huang, and G. Dissanayake, “Active slam using model predictive control and attractor based exploration,” in _IEEE Int. Conf. Intell. Robots Syst. (IROS)_. IEEE, 2006, pp. 5026–5031.
  * [7] T. Kollar and N. Roy, “Trajectory optimization using reinforcement learning for map exploration,” _Int. J. Robot. Res. (IJRR)_ , vol. 27, no. 2, pp. 175–196, 2008.
  * [8] A. Kim and R. M. Eustice, “Perception-driven navigation: Active visual slam for robotic area coverage,” in _ICRA_. IEEE, 2013, pp. 3196–3203.
  * [9] S. Ehrenfeld, “On the efficiency of experimental designs,” _Ann. Math. Stat._ , vol. 26, no. 2, pp. 247–255, 1955.
  * [10] C. Stachniss, G. Grisetti, and W. Burgard, “Information gain-based exploration using rao-blackwellized particle filters.” in _Robotics: Science and systems_ , vol. 2, 2005, pp. 65–72.
  * [11] J.-L. Blanco, J.-A. Fernandez-Madrigal, and J. González, “A novel measure of uncertainty for mobile robot slam with rao—blackwellized particle filters,” _IJRR_ , vol. 27, no. 1, pp. 73–89, 2008.
  * [12] S. M. LaValle, _Planning algorithms_. Cambridge university press, 2006.
  * [13] R. Alterovitz, S. Koenig, and M. Likhachev, “Robot planning in the real world: Research challenges and opportunities,” _Ai Magazine_ , vol. 37, no. 2, pp. 76–84, 2016.
  * [14] A. Stentz, “Optimal and efficient path planning for partially known environments,” in _Intelligent unmanned ground vehicles_. Springer, 1997, pp. 203–220.
  * [15] S. Koenig and M. Likhachev, “Fast replanning for navigation in unknown terrain,” _T-RO_ , vol. 21, no. 3, pp. 354–363, 2005.
  * [16] J. Bruce and M. M. Veloso, “Real-time randomized path planning for robot navigation,” in _Robot soccer world cup_. Springer, 2002, pp. 288–295.
  * [17] D. Ferguson, N. Kalra, and A. Stentz, “Replanning with rrts,” in _ICRA_. IEEE, 2006, pp. 1243–1248.
  * [18] J. Vannoy and J. Xiao, “Real-time adaptive motion planning (ramp) of mobile manipulators in dynamic environments with unforeseen changes,” _T-RO_ , vol. 24, no. 5, pp. 1199–1212, 2008.
  * [19] Z. Wang and G. Tian, “Hybrid offline and online task planning for service robot using object-level semantic map and probabilistic inference,” _Information Sciences_ , vol. 593, pp. 78–98, 2022.
  * [20] T. S. Veiga, M. Silva, R. Ventura, and P. U. Lima, “A hierarchical approach to active semantic mapping using probabilistic logic and information reward pomdps,” in _Int. Conf. Automated Planning Scheduling_ , vol. 29, 2019, pp. 773–781.
  * [21] L. Burks, I. Loefgren, and N. R. Ahmed, “Optimal continuous state pomdp planning with semantic observations: A variational approach,” _T-RO_ , vol. 35, no. 6, pp. 1488–1507, 2019.
  * [22] D. S. Chaplot, D. P. Gandhi, A. Gupta, and R. R. Salakhutdinov, “Object goal navigation using goal-oriented semantic exploration,” _Adv. Neural. Inf. Process. Syst._ , vol. 33, pp. 4247–4258, 2020.
  * [23] G. Georgakis, B. Bucher, K. Schmeckpeper, S. Singh, and K. Daniilidis, “Learning to map for active semantic goal navigation,” _arXiv preprint arXiv:2106.15648_ , 2021.
  * [24] R. Zeng, Y. Wen, W. Zhao, and Y.-J. Liu, “View planning in robot active vision: A survey of systems, algorithms, and applications,” _Comput. Vis. Media._ , vol. 6, no. 3, pp. 225–245, 2020.
  * [25] Z. Meng, H. Sun, H. Qin, Z. Chen, C. Zhou, and M. H. Ang, “Intelligent robotic system for autonomous exploration and active slam in unknown environments,” in _Int. Symp. Syst. Integr. (SII)_. IEEE, 2017, pp. 651–656.
  * [26] M. Selin, M. Tiger, D. Duberg, F. Heintz, and P. Jensfelt, “Efficient autonomous exploration planning of large-scale 3-d environments,” _RA-L_ , vol. 4, no. 2, pp. 1699–1706, 2019.
  * [27] A. Bircher, M. Kamel, K. Alexis, H. Oleynikova, and R. Siegwart, “Receding horizon” next-best-view” planner for 3d exploration,” in _ICRA_. IEEE, 2016, pp. 1462–1468.
  * [28] S. J. Russell, _Artificial intelligence a modern approach_. Pearson Education, Inc., 2010.
  * [29] M. Labbé and F. Michaud, “Rtab-map as an open-source lidar and visual simultaneous localization and mapping library for large-scale and long-term online operation,” _J. Field Robot._ , vol. 36, no. 2, pp. 416–446, 2019\.
  * [30] R. Bormann, F. Jordan, J. Hampp, and M. Hägele, “Indoor coverage path planning: Survey, implementation, analysis,” in _ICRA_. IEEE, 2018, pp. 1718–1725.
  * [31] Z. Qian, K. Patath, J. Fu, and J. Xiao, “Semantic slam with autonomous object-level data association,” in _ICRA_. IEEE, 2021, pp. 11 203–11 209.
  * [32] J. Redmon and A. Farhadi, “Yolov3: An incremental improvement,” _arXiv preprint arXiv:1804.02767_ , 2018.
  * [33] J. Canny, “A computational approach to edge detection,” _IEEE Trans. Pattern Anal. Mach. Intell._ , no. 6, pp. 679–698, 1986.
  * [34] H. Schütze, C. D. Manning, and P. Raghavan, _Introduction to information retrieval_. Cambridge University Press Cambridge, 2008, vol. 39.
  * [35] T. Smith and R. Simmons, “Focused real-time dynamic programming for mdps: Squeezing more out of a heuristic,” in _AAAI_ , 2006, pp. 1227–1232.
  * [36] R. Bellman, “A markovian decision process,” _J. math. mech._ , pp. 679–684, 1957.
  * [37] A. Chang, A. Dai, T. Funkhouser, M. Halber, M. Niessner, M. Savva, S. Song, A. Zeng, and Y. Zhang, “Matterport3d: Learning from rgb-d data in indoor environments,” _arXiv preprint arXiv:1709.06158_ , 2017.
  * [38] M. Savva, A. Kadian, O. Maksymets, Y. Zhao, E. Wijmans, B. Jain, J. Straub, J. Liu, V. Koltun, J. Malik _et al._ , “Habitat: A platform for embodied ai research,” in _IEEE Int. Conf. Comput. Vis._ , 2019, pp. 9339–9347.
  * [39] B. Yamauchi, “A frontier-based approach for autonomous exploration,” in _IEEE Int. Symp. Comput. Intell. Robot. Autom._ , 1997, pp. 146–151.
  * [40] P. Anderson, A. Chang, D. S. Chaplot, A. Dosovitskiy, S. Gupta, V. Koltun, J. Kosecka, J. Malik, R. Mottaghi, M. Savva _et al._ , “On evaluation of embodied navigation agents,” _arXiv preprint arXiv:1807.06757_ , 2018.


# Neighborhood-based Pooling for Population-level Label Distribution Learning
111This is a pre-print version of a paper that was accepted for publication at
European Conference on Artificial Intelligence 2020

Tharindu Cyril Weerasooriya222Rochester Institute of Technology, USA, email:
<EMAIL_ADDRESS>Appen Machine Learning Team, USA, email:
<EMAIL_ADDRESS>Institute of Technology, USA, email<EMAIL_ADDRESS>Tong Liu Appen Machine Learning Team, USA, email<EMAIL_ADDRESS>Institute of Technology, USA, email<EMAIL_ADDRESS>Christopher M. Homan
Rochester Institute of Technology, USA, email<EMAIL_ADDRESS>
###### Abstract

Supervised machine learning often requires human-annotated data. While
annotator disagreement is typically interpreted as evidence of noise,
population-level label distribution learning (PLDL) treats the collection of
annotations for each data item as a sample of the opinions of a population of
human annotators, among whom disagreement may be proper and expected, even
with no noise present. From this perspective, a typical training set may
contain a large number of very small-sized samples, one for each data item,
none of which, by itself, is large enough to be considered representative of
the underlying population’s beliefs about that item. We propose an algorithmic
framework and new statistical tests for PLDL that account for sampling size.
We apply them to previously proposed methods for sharing labels across similar
data items. We also propose new approaches for label sharing, which we call
_neighborhood-based pooling_.

##  1 Introduction

In supervised learning, the labels provided by a group of annotators are
typically aggregated into a single label, which is regarded as ground truth.
The underlying assumption that one label fits all is rarely questioned.
However, the process of labeling is often subjective, i.e., based on the
personal experiences of the humans who label the data [1], such as when the
task is to predict beauty in images or rate movies [9]. Genuine disagreement
is also common in seemingly “more objective” tasks, for instance, in assessing
the mental state, beliefs, or other hidden states based on observable data
[19, 13]. Nevertheless, the negative impacts of AI systems trained on too
narrow a segment of a population are increasingly felt [23, 28, 30, 4, 26].

Label distribution learning (LDL) seeks to predict, for each data item, a
probability distribution over the set of labels [8]. LDL can capture for each
data item the diversity of opinions among the human annotators. In contrast,
almost all of the prior work in LDL has taken the label distributions found in
the training data to be accurate, when in fact annotations obtained from
crowdsourcing sites or social media—a common though certainly not exclusive
source of label distributions—are most often samples of a larger pool of
annotators, who may not themselves be representative of the actual target
populations’ opinions. Furthermore, outside of a limited number of cases—such
as movie ratings, where annotations are abundant and convenient—the sample
size of annotations for each data item is far too small (often as small as
five annotations per item) to reliably represent the true distributions of the
annotator pool’s beliefs and opinions.

Figure 1: The neighborhood-based pooling strategy explored in this paper. The
black dots represent data items. The human annotators are represented below
each dot and the color of the person represents the label choice. In this
example, five humans annotate each data item. $D$ represents the information
theoretic divergence in each neighboring data item from the central data item
and $r$ is the radius of the neighborhood. We explore the usefulness of
refining the labels of the central data item for PLDL by pooling the labels of
neighboring items with the central item’s labels.

Liu et al. [19] propose a method for sharing labels among items with similar
label distributions, under the assumption that, relative to a specific
labeling task, there are only a small number of possible interpretations of
any data item, even at the population level. A goal in their work was to
address the resource bottleneck of human annotation from a large sample by
sharing the existing labels. They introduce the concept of population-level
label distribution learning (PLDL), i.e., LDL that explicitly models label
distributions as population samples. They explored PLDL by using different
methods of clustering in the label space. However, they do not use population
models to evaluate their algorithm’s performance or select models.

Our main contribution is to introduce a new model selection techniques based
on population-level hypothesis tests. These techniques use traditional
frequentist statistical approaches to hypothesize that items are similar if
their labels can be regarded as samples from a common source. We use these
methods to explore, from a sampling perspective, the clustering approach of
Liu et al [19]. Additionally, we consider a new, bottom-up approach, called
_neighborhood-based pooling_ (NBP) (Figure 1), for improving the ground truth
estimates of labels for PLDL. Our approach is based on the idea that items
with very similar labels may have essentially the same meaning, relative to an
annotation task, and thus may be shared, but that the space of label
distribution is less clustered and smoother, rather than clustered, as Liu et
al. assume.

##  2 Related Work

Disagreement during labeling tasks is a well studied problem [21, 22, 1]. Snow
et al. [27] observed using multiple crowdsourced workers that individuals
(even experts) had personal biases when labeling. This can contribute to
diversity among labels through disagreement, which nondistributional learning
cannot account for. Aroyo [2] observed that when the human annotators agree
with one another, they perform at a level comparable to experts, and when they
disagree, it is often for a good reason. In conventional single label learning
applications, researchers consider the majority label as the ground truth,
disregarding previously discussed disagreements.

Geng [8] introduced label distribution learning, a learning paradigm where
probability distributions are objects to be predicted. LDL takes into account
the diversity, disagreement, ambiguity, and uncertainty between annotators for
its approaches including, predictions. He and colleagues studied LDL using a
variety of different learning algorithms, problem transformation, algorithm
adaptation, and a specialized algorithm. The algorithm for LDL shares some
similarities with learning over a probability distribution, which has a long
history of research [25, 11, 6]. Both use probability distributions; LDL
interprets them as ground truth while the others use them to model
uncertainty. Geng and other researchers studied the applications of LDL in
various settings such as predicting population level labels [9, 10, 24] while
some do not [7, 17]. These studies acknowledge the need for a large number of
labels to train on for improving their distributions. We use the natural scene
and facial expressions datasets used by Geng [10] for our experiments (see
Section 4).

In contrast to supervised learning, semi-supervised learning (SSL) is a
combination of supervised and unsupervised learning [5]. SSL uses both labeled
and unlabeled data to improve learning. SSL [14, 32] has a long history with a
variety of methods of learning. Clustering is another semi-supervised learning
method in which if two items belong to the same cluster, they are believed to
share the same label [5].

Liu et al. [19] use a similar approach for PLDL (they also formally introduce
the PLDL problem). They explored clustering as an unsupervised learning method
to improve the quality of ground truth estimation. They [19] collected a
crowdsourced dataset in which five-to-ten human annotators labeled each data
item. Then they “[clustered] together semantic similar data items, and then
[pooled] together all the labels in each cluster into a single, larger sample”
[19], under the assumption that this sample represented the population-level
beliefs about each item in the cluster. They compared and contrasted the
performance of a variety of clustering methods. Their approach is more
typically applied to items with no or unreliable labels, where similarity
between data items is necessarily determined in the feature space of the data
items, not in the label space. However, Liu et al. [19] observe that, if all
the items already have labels, one can determine similarity in the label space
alone. Their work has two limitations: (1) though their approach was based on
statistical principles, they do not exploit this connection in their analysis
and (2) they consider only a relatively small number of clusters per learning
problem (under the assumption that for classification problems the number of
distinct answer distributions is necessarily limited).

Zhang [31] introduces multi-instance-multi-learning (MIML)-$k$-NN as a non-
parametric learning method that used the k-nearest neighbor for multiple
labels. However, $k$-NN selects the closest $k$ neighbors around the item
regardless of how close or further away they are from the data point. The
drawback of this approach is not taking into account the similarity between
the item and its neighbors.

##  3 Methods

###  3.1 Label Distribution Learning

Wang and Geng [29] developed a theory for label distribution learning, proving
a number of theorems about error functions for LDL. Their theory presents
label distributions as ground truth objects, without considering that they may
be merely estimates of an underlying ground distribution. Here, we present a
theory for LDL for the special case of when the label distribution is a sample
of an underlying population, which explicitly accounts for this population,
along with noise in the sampling process and level of reliability of the
annotators. First, we introduce some notation. For any probability
distribution $\mathcal{D}$, and any set $\mathcal{X}$ let $X_{\mathcal{D}}$
denote a random variable in $\mathcal{X}$ over $\mathcal{D}$. If context is
clear we will drop the “$\mathcal{D}$” subscript. Let $\mathcal{D}|X$ denote
the distribution conditioned on $X$, and similarly for $x\in\mathcal{X}$ and
$\mathcal{D}|x$. Thus, $Y_{\mathcal{D}|x}$ is a random variable in
$\mathcal{Y}$ over the distribution $\mathcal{D}|x$. Finally, for any set
$\mathcal{X}$, let $\mathcal{P}_{\mathcal{X}}$ denote the space of all
probability distributions over $\mathcal{X}$.

1$S\leftarrow()$

2 for  _$i\leftarrow 1$ to $n$_ do

3 choose $x_{i}\sim X_{\mathcal{D}}$

4 for  _$j\leftarrow 1$ to $m(x_{i})$_ do

5 choose $a_{i,j}\sim P_{\mathcal{D}}$

6 choose $y_{i,j}\sim Y_{\mathcal{D}}~{}|~{}x_{i},a_{i,j}$

7 add $(x_{i},a_{i,j},y_{i,j})$ to $S$

8

return _S_

Algorithm 1 Sampling procedure.

Now, to formally define PLDL, let $\mathcal{D}$ be a probability distribution
over $\mathcal{X}\times\mathcal{A}\times\mathcal{Y}$, where $\mathcal{X}$ is
the _feature space_ of a data set of interest, $\mathcal{A}$ is the _agent (or
annotator) space_ , and $\mathcal{Y}$ is a _label space_. Let
$X_{\mathcal{D}}$, $A_{\mathcal{D}}$, and $Y_{\mathcal{D}}$ be random
variables representing the marginal distributions of $\mathcal{X}$,
$\mathcal{A}$, and $\mathcal{Y}$ respectively. We assume that
$X_{\mathcal{D}}$ is independent from $A_{\mathcal{D}}$.

Let $\mathcal{S}$ be a sample from $\mathcal{D}$, drawn according to Figure 1.
We can thus consider the indexed set $(x_{i})_{p(X_{\mathcal{S}}=x_{i})>0}$.
and let $\mathcal{H}$ be a _hypothesis space_ , where each $h\in\mathcal{H}$
is a function $h:\mathcal{X}\rightarrow\mathcal{P}_{\mathcal{Y}}$. The
_empirical risk minimization (ERM) problem_ for PLDL is to find a hypothesis
$h_{\mathcal{S}}\in\mathcal{H}$ that minimizes $L_{\mathcal{S}}$, the _loss
function_ applied to $\mathcal{S}$ on $h$:

$\displaystyle h_{\mathcal{S}}$ $\displaystyle\in$
$\displaystyle\arg\min_{h\in\mathcal{H}}L_{\mathcal{S}}(h)$ (1)

(Digression: in the multi-label setting one can take
$\mathcal{Y^{\prime}}=2^{\mathcal{Y}}$ and treat it as a single label learning
problem; however, it is often beneficial to exploit the set structure of the
multi-label setting in designing a machine learning solution.)
$L_{\mathcal{S}}$ is a function that is small when each $h(x_{i})$ is close to
$Y_{\mathcal{S}|x_{i}}$ and zero whenever $h(x_{i})=Y_{\mathcal{S}|x_{i}}$.
For the sake of discussion, we will take $L_{\mathcal{S}}$ to be the expected
Kullback-Liebler (KL) divergence,
$E_{\mathcal{S}}[\mathrm{KL}(h(x_{i})||Y_{\mathcal{S}|x_{i}})]$, where for any
two probability distributions $\mathcal{P}$ and $\mathcal{Q}$ with random
variables over $\mathcal{Y}$,

$\displaystyle\mathrm{KL}(P||Q)$ $\displaystyle=$
$\displaystyle\sum_{y\in\mathcal{Y}}P(y)\log\left(\frac{P(y)}{Q(y)}\right)$
(2)

KL divergence is widely used in machine learning, especially in belief
modeling, and as a loss function in many settings. Here, it can be roughly
interpreted as the expected number of bits per item needed to correct whenever
a sample from $P$ is mistaken for a sample from $Q$, and this seems to capture
intuitively the notion of error when comparing two probability distributions.

###  3.2 Estimating Ground Truth via Label Pooling

A common problem that occurs in population-based label distribution is that
datasets frequently only have a small number of annotations per data item,
i.e., each $x$ occurs at most $m$ times in $\mathcal{S}$, where $m$ is
typically too small to estimate the ground truth sample $f(x)$. For
simplicity’s sake we will assume hereafter that each item occurs exactly $m$
times.

Liu et al. [19] explore the idea that similarly-labeled data items may have
similar meanings at the population level and could thus be seen as samples of
a common underlying source. We generalize the idea of pooling and extend it to
neighborhood-based approaches, but first we need to formally define pooling: A
_pooling_ is: an integer $p\in\mathbb{N}$, a collection of sets
$K_{1},\ldots,K_{p}\subseteq\mathcal{X}$ such that $K_{1}\cup\cdots\cup
K_{p}=\mathcal{X}$, and a mapping $k:\mathcal{X}\rightarrow\\{1,\ldots p\\}$.
After learning a model $(p,\\{K_{1},\ldots,K_{p}\\},k)$ that best fits the
data, each data item $x\in\mathcal{X}$ is then associated with the marginal
label distribution $Y_{K_{k(x)}}$ (which Liu et al. call the _refined label
distribution_) of $x$’s cluster $K_{k(x)}$.

####  3.2.1 Cluster-Based Pooling

Liu et al. [19] introduce pooling methods based on generative hierarchical
probabilistic models. Each of these models assumes that the empirical label
distributions were generated by choosing a cluster according to a distribution
$\pi$ (or in the case of latent Dirichlet allocation (LDA) [3], each data item
$x_{i}$ has its own distribution $\pi_{i}$) over the pools, and then choosing
the labels via a distribution $\phi_{j}$ associated with the chosen cluster
(or in the case of LDA, choosing a new “pool” for each label).

For comparison purposes, we consider four of the models used by Liu et al.
[19]: a (finite) multinomial mixture model (F) with a Dirichlet prior over
$\pi\sim\mbox{Dir}(p,\gamma=75)$, where each cluster distribution $\pi_{j}$ is
a multinomial distribution with Dirichlet priors $\mbox{Dir}(d,\gamma=0.1)$, a
Gaussian mixture model (G) without Dirichlet priors, k-means (K) and LDA (L).

####  3.2.2 Neighborhood-based Pooling

Neighborhood based pooling (NBP) creates for each data item $x\in\mathcal{S}$
one pool
$K_{x}=\\{x^{\prime}~{}|~{}D_{KL}(Y_{\mathcal{S}|x}||Y_{\mathcal{S}|x^{\prime}})<r\\}$,
where $r>0$ is a hyperparameter called the _neighborhood radius_ (see
Algorithm 2).

We also considered Euclidean distance, Chebyshev distance, and the Canberra
metric, however our results using these methods were similar enough to our
results with KL divergence (Figure 2). Additionally, KL divergence has a
meaningful interpretation in the context of statistical estimation. It is the
expected number of bits per item needed to make a multinomial sample from one
distribution appear to be from the other.

Figure 2: The KL-divergence for each $r$ value for the _JQ1_ dataset with
various distance/divergence measures.

1 Inputs:

2 Empirical label distributions
$(Y_{\mathcal{S}|x_{i}})_{i\in\\{1,\ldots,n\\}}$

3 Radius of the neighborhood $r$

4 Information theoretic measure $D$

5 Output:

6 A pooling $(p,(K_{1},\ldots,K_{n}),k)$

7 Function   _Neighborhood Based Pooling_

8 forall  _$i\in\\{1,\ldots,n\\}$_ do

9 let
$K_{i}=\\{x\in\mathcal{X}_{\mathcal{S}}~{}|~{}D(Y_{\mathcal{S}|x}||Y_{\mathcal{S}|x_{i}})\leq
r\\}$

10 let $k(x_{i})=i$

11 end forall

12 return $(p,(K_{1},\ldots,K_{n}),k)$

13 end

Algorithm 2 Neighborhood based pooling (NBP)

###  3.3 Hyperparameter Selection for (and Evaluation of) Pooling Models

To evaluate our label pooling methods and select hyperparameters (the number
of pools $p$ for the clustering or the neighborhood radius $r$ for the NBP
methods), we consider two loss functions: first, we use the mean KL divergence
between the empirical and label distributions of each item the evaluation set.

$\displaystyle\mathcal{L}_{S}(p,(K_{1},\ldots,K_{p}),k)=\sum_{i\in\\{1,\ldots,n\\}}D_{KL}(Y_{K_{k(x_{i})}}||Y_{\mathcal{S}|x_{i}})/n$
(3)

Second, we consider the probability of the given label set, given the pools.
Additionally, the clustering methods all rely on stochastic optimization. To
avoid overfitting, for a range of cluster sizes $p\in\\{1,\ldots 40\\}$ (based
on the range selected by Liu et al. [19]), we ran 100 trials on the training
set (since we are using clustering here for sample estimation and not
prediction, it is valid and proper to test on the training set) picked the
model for each value of $p$ with the median loss. Table 2 shows the number of
clusters selected on each label set.

Selecting the best hyperparameter by the raw loss function (Eq 3) may not be
the best choice here, in part because it only measures which hyperparameter
fits the model best, but also because ground truth is for us unobservable.
Sometimes, even the best models are still not adequate. In unsupervised
problems such as pooling, there are few settings where widely agreed-upon
numerical measures are sufficient to judge the quality of a model [12].

However, in the case of PLDL we have a population of annotators $\mathcal{A}$
to work with. This enables us to use frequentist statistical methods such as
hypothesis testing to assess the quality of our pooling models. The basic idea
is to generate from each given model random samples that are the same size as
our training sample. If the model is a good fit for our training sample, then
statistics from the training sample should be in line with those generated
directly by the model.

So for each model, we run two simulation-based statistical tests. First we
generate 1000 synthetic label sets, each the size of our training set, based
on the pooling model we are testing, we then compare the loss function on our
test data to the distribution of loss functions on the synthetic sets. As an
additional test, we compare these to another sample of 1000 synthetic label
sets based on a bootstrap sample from the actual data. See Algorithms 3–4.

$\displaystyle L_{\mathcal{S}}(p,(K_{1},\ldots,K_{p}),k)$ $\displaystyle=$
$\displaystyle\log
n!+\sum_{i=1}^{n}\sum_{y\in\mathcal{Y}}y_{\mathcal{S}|x_{i}}^{\\#}\log
y_{K_{k(x_{i})}}-\log y_{\mathcal{S}|x_{i}}^{\\#}!,$

where $y_{\mathcal{S}|x_{i}}^{\\#}$ denotes $|\\{y\in\mathcal{Y}~{}|~{}\exists
x,a((x,a,y)\in\mathcal{S}\\}|$.

We consider a range of reasonable values for $r$ based on our NBP and
bootstrap sampler. Table 3 shows the neighborhood sizes ($r$) selected on each
of the label sets. The selected $r$ is the elbow point of a piecewise linear
regression line (See Figure 7 and Figure 7).

1 Inputs: A sample of data items and empirical label distributions
$\mathcal{S}$

2 A pooling of the data $(p,(K_{1},\ldots,K_{p}),k)$

3 A stochastic sample generator $G$ for random label samples

4 A statistic $L$ defined over labeled data items and poolings of data

5 The number votes $m$ per item.

6 The number $b$ of samples used for testing

7 Output: The fraction of samples $\mathcal{B}$ such that
$L_{\mathcal{B}}(p,(K_{1},\ldots,K_{p}),k)>L_{\mathcal{S}}(p,(K_{1},\ldots,K_{p}),k)$

8 Function   _Model Evaluation_

9 $count\leftarrow 0$

10 for  _$i\in\\{1,\ldots,b\\}$_ do

11 generate $\mathcal{B}\sim G((p,(K_{1},\ldots,K_{p}),k),n,m)$ according to

12 one of the sampling procedures from Algorithm 1

13 if  _$L_{\mathcal{B}}(p,(K_{1},\ldots,K_{p}),k)
>L_{\mathcal{S}}(p,(K_{1},\ldots,K_{p}),k)$_ then

14 $count\leftarrow count+1$

15 end if

16

17 end for

18 return $count/n$

19 end

Algorithm 3 Model Selection/Evaluation for Pooling

1 $G=$ cluster sampler

2 for  _$i\in\\{1,\ldots,n\\}$_ do

3 choose a cluster $K_{j}\sim\pi$

4 choose $Y_{\mathcal{B}|x_{i}}\sim\mathcal{M}(Y_{K_{j}},m)$ where
$\mathcal{M}(Y_{K_{j}},m)$ denotes the multinomial distribution over all size
$m$ i.i.d. samples of $Y_{K_{j}}$

5

6 end for

7

8 $G=$ NBP sampler

9 for  _$i\in\\{1,\ldots,n\\}$_ do

10 choose $j\in\\{1,\ldots n\\}$ uniformly at random

11 choose $Y_{\mathcal{B}|x_{i}}\sim\mathcal{M}(Y_{K_{j}},m)$

12

13 end for

14

15 $G=$ Bootstrap sampler

16 for  _$i\in\\{1,\ldots,n\\}$_ do

17 choose $j\in\\{1,\ldots n\\}$ uniformly at random

18 choose $Y_{\mathcal{B}|x_{i}}\sim\mathcal{M}(Y_{\mathcal{S}|x_{j}},m)$

19 end for

Algorithm 4 Sampling approaches

##  4 Experiments

###  4.1 Data and Labels

All of the datasets we consider have labels that were produced by humans, and
in many cases so was the data, we consulted with our institutional review
board (IRB), who determined that the data was both secondary and publicly
available, and thus exempt from IRB review. For each dataset, we used a
50/25/25 train/dev/test split. These datasets have been used in prior LDL
related research [19, 9].

Jobs dataset - JQ1, JQ2, and JQ3 We used a set of 2,000 job-related annotated
tweets data set collected by Liu et al. [18] for this research. The dataset
contains responses from three annotation tasks. Originally five crowdsourced
annotators each from Mechanical Turk and FigureEight (10 annotators total)
labelled the data. The task for JQ1 was to identify the point of view of the
tweet (i.e., 1st person, 2nd person, 3rd person, unclear, or not job related).
JQ2 was to capture the employment status of the subject in the tweet (i.e.,
employed, not in labor force, not employed, unclear, and not job-related). The
final task was to identify if there was any mention of a employment transition
event in the tweet (i.e., getting hired/job seeking, getting fired, quitting a
job, losing job some other way, getting promoted/raised, getting cut in hours,
complaining about work, offering support, going to work, coming home from
work, none of the above but job related, and not job-related).

Natural Scenes (NS) dataset333The datasets are to download on the website
http://ldl.herokuapp.com/download We also use the natural scenes dataset by
[8]. This set contains 2,000 images of natural scenes (NS). Each image has a
label distribution over nine labels (i.e., plant, sky, cloud, snow, building,
desert, mountain, water, and sun) and with labels collected from ten human
annotators. These images have 36 features associated with them.

BU-3DFE Facial Expression (FE) dataset This dataset contains 2,500 facial
expression images, each of these images are associated with a label
distribution over 6 label categories (i.e., happiness, sadness, surprise,
fear, anger, and disgust). The dataset was collected by Yin et al [16]. For
each image, the labels come from 23 human annotators.

###  4.2 Experiments on Label Pooling

In evaluating our pooling results according to the simulation-based methods
described in Section 3.3 we noticed that, frequently, the values of the loss
function on the synthetic data were either all greater or all less than their
corresponding values in the training data (recall that we evaluated the model
on the training data because, given its purpose to estimate population
statistics from samples, rather than predict individual values on new items,
held-out data was not necessary). This made our test defined by Algorithm 3
meaningless. Thus, rather than use it, we instead, for each parameter value
$\phi$ to be tested, and corresponding pooling $(p,(K_{1},\ldots,K_{p}),k)$
subtract the loss on the training data
$\mathcal{L}_{\mathcal{S}}(p,(K_{1},\ldots,K_{p}),k)$ from the mean loss on
the synthetic data $\mathcal{L}_{\mathcal{B}}(p,(K_{1},\ldots,K_{p}),k)$,
divided by the standard deviation of the synthetic data loss:

$\displaystyle\frac{\mu(\mathcal{L}_{\mathcal{B}}(p,(K_{1},\ldots,K_{p}),k))-\mathcal{L}_{\mathcal{S}}(p,(K_{1},\ldots,K_{p}),k)}{\sigma(\mathcal{L}_{\mathcal{B}}(p,(K_{1},\ldots,K_{p}),k))}$
(4)

and seek the parameter $\phi$ that minimizes this quantity. The optimal number
of clusters ($p$) based on the observation for $\phi$ is given in Table 1 and
Table 2. For the JQ1, JQ2, and JQ3 datasets, F clustering models outperformed
other clustering methods based on these results. It was followed by L
clustering for the same set of labels. As expected, K and G come last. Figure
7 shows the histograms of the loss functions on the JQ1 dataset for L
clustering. While the standard difference for the value in Eq. 4, is shown in
Figure 7 and Figure 7 for bootstrap and cluster samplers. In contrast to the
jobs dataset (JQ1, JQ2, and JQ3), for NS and FE, G outperformed other models
and it was followed by either F (for NS) or K (for FE). These results are
related to the structure of the label distributions of the dataset.

The hyperparameter for NBP is the neighborhood size ($r$). To build the
synthetic dataset for NBP, we use the bootstrap and NBP based samplers defined
in Algorithms 3–4. Figure 7 and Figure 7 shows the standard difference with
linear piecewise fitting for bootstrap and NBP samplers. Table 3 gives the
optimum neighborhood sizes ($r$) based on each sampling method. Due to the
nature of NBP, we also report $N_{Median}$, the median of all the neighborhood
sizes. The $r$ sizes identified using the NBP sampler outperformed the sizes
identified using the bootstrap sampler. In FE, both the values identified
utilized the entire dataset which was available for pooling, while in contrast
other datasets utilized approximately a quarter of the entire set.

Table 1: We achieve optimal label aggregation models on each label set with the presented number of clusters ($p$) and KL-divergence for the datasets using the cluster sampler with Multinational distribution as the loss function. The lowest KL per dataset is highlighted in blue. Model |  | JQ1 | JQ2 | JQ3 | NS | FE
---|---|---|---|---|---|---
FMM | $p$ | 29 | 12 | 11 | 36 | 16
| $D_{KL}$ | 0.201 | 0.151 | 0.347 | 0.340 | 0.080
GMM | $p$ | 2 | 3 | 5 | 6 | 37
| $D_{KL}$ | 0.700 | 0.639 | 1.416 | 0.215 | 0.008
K-Means | $p$ | 5 | 16 | 36 | 6 | 22
| $D{KL}$ | 0.716 | 0.809 | 1.215 | 0.654 | 0.049
LDA | $p$ | 2 | 12 | 7 | 4 | 35
| $D_{KL}$ | 0.428 | 0.201 | 0.587 | 0.443 | 0.064
Table 2: We achieve optimal label aggregation models on each label set with the presented number of clusters ($p$) and KL-divergence for the datasets using the cluster sampler with KL-divergence as the loss function. The lowest KL per dataset is highlighted in blue. Model |  | JQ1 | JQ2 | JQ3 | NS | FE
---|---|---|---|---|---|---
FMM | $p$ | 14 | 7 | 35 | 7 | 16
| $D_{KL}$ | 0.193 | 0.170 | 0.269 | 0.935 | 0.080
GMM | $p$ | 4 | 2 | 6 | 17 | 37
| $D_{KL}$ | 0.819 | 0.777 | 1.225 | 0.285 | 0.008
K-Means | $p$ | 10 | 15 | 33 | 12 | 22
| $D{KL}$ | 0.712 | 0.797 | 1.126 | 0.675 | 0.049
LDA | $p$ | 7 | 5 | 5 | 4 | 35
| $D_{KL}$ | 0.243 | 0.237 | 0.625 | 0.602 | 0.064
Table 3: We achieve optimal neighborhood size for NBP on each label set with the given KL-divergence and the median neighborhood size at each level. The lowest KL per dataset is highlighted in blue. | JQ1 | JQ2 | JQ3 | NS | FE
---|---|---|---|---|---
$r_{B}$ | 5 | 6 | 8 | 4 | 4.5
$D_{KL}$ | 0.358 | 0.358 | 0.704 | 0.568 | 0.080
$N_{Median}$ | 967 | 922 | 863.5 | 548.5 | 1,250
$N_{Maximum}$ | 1,000 | 1,000 | 1,000 | 1,000 | 1,250
$r_{NBP}$ | 3 | 2 | 2 | 2 | 3
$D_{KL}$ | 0.317 | 0.257 | 0.409 | 0.444 | 0.080
$N_{Median}$ | 875 | 645 | 293 | 265 | 1,250
$N_{Maximum}$ | 1,000 | 1,000 | 1,000 | 1,000 | 1,250

###  4.3 Supervised Learning Experiments

Following the same experimental process as Liu et al [19] we use the refined
labels to train and test supervised learning models. Here, we tested our held-
out data on two supervised learning models (CNN on Table 4 and LSTM on Table
5) from Liu et al., with the goal of predicting the pooled label distribution
of each data item. Note that the features for the supervised learning models
to learn were different among the datasets. The JQ1, JQ2, and JQ3 datasets are
text-based [19] and the NS and FE features are the vectorized representations
used by Geng [9]. We evaluated the predictions against the refined labels
generated from the clustering and NBP. We evaluated them: (1) as a traditional
supervised learning problem by measuring the accuracy (using
$argmax(Y_{K_{k(x)}})$), (2) as a probability distribution problem using the
KL-divergence.

####  4.3.1 Results from Label Clustering

Looking at the KL-divergence results, the CNNs in Table 4 outperformed the
LSTM models. In all the instances, the labels refined through clustering
outperformed the baseline. The labels refined using the G models outperformed
the other models for the JQ1 and JQ2 datasets while for JQ3 and NS, K
outperformed the others. For the FE dataset, the labels refined by the F model
performed better than the other models. These results could be related to the
size of the label spaces. JQ3 had the largest label space, while others were
within a similar range. Moreover, in JQ3, human annotators were allowed to
provide multiple labels per data item, in contrast to others where only one
label choice was allowed per item. In the LSTMs, the observations from the
CNNs were common, in contrast to JQ1, where L outperformed other models.

####  4.3.2 Results from Label Pooling

In our experiments, we used the two radii picked using bootstrap and NBP
sampling. Looking at the mean KL-divergence, for the CNNs, the NBP
outperformed the clustering models. The accuracy results obtained did
supplement the results obtained through the KL test in majority of the cases
other than FE dataset. Similar to the clustering approaches, the results from
CNNs outperformed the results obtained through the LSTMs. These observations
will be discussed further in the next section.

Figure 3: Comparison of the
$\mathcal{L}_{\mathcal{B}}(p,(K_{1},\ldots,K_{p}),k)$ (synthetic dataset)
distributions obtained from the sampling techniques and clustering methods on
the JQ1 dataset for LDA. Reference line:
$\mathcal{L}_{\mathcal{S}}(p,(K_{1},\ldots,K_{p}),k)$ value of the training
dataset. Top: Cluster sampler in green. Bottom: Bootstrap sampler in blue.

Figure 4: The difference between the average KL-divergence of the sample
generated by the bootstrap sampler and the predicted data for the JQ1 dataset
with the bootstrap sampler.

Figure 5: The difference between the average KL-divergence of the sample
generated by the cluster sampler and the predicted data JQ1 dataset with the
cluster sampler.

Figure 6: The difference between the average KL-divergence of the sample
generated by the bootstrap sampler and the predicted data for the JQ1 dataset
with the bootstrap sampler for NBP. We included for reference the piece-wise
linear regression line.

Figure 7: The variation of the standard difference between the average KL-
divergence of the sample generated by the NBP sampler and the predicted data
JQ1 dataset with the NBP sampler. We included for reference the piecewise
linear regression line.

Table 4: The predictions with KL-divergence ($\mathbf{D_{KL}}$) when used with supervised learning (CNN) and unsupervised learning (clustering and NBP). The lowest KL and the highest accuracy for NBP and clustering is highlighted in blue. KL-divergence | Accuracy
---|---
Dataset | Raw | Clustering |  NBP \- KL | Raw | Clustering |  NBP \- KL
| Labels | F | G | K | L | $r_{B}$ | $r_{NBP}$ | Labels | F | G | K | L | $r_{B}$ | $r_{NBP}$
Jobs dataset - Supervised Learning Classification (CNN)
JQ1 | 1.088 | 0.346 | 0.265 | 0.270 | 0.370 | 0.021 | 0.028 | 0.537 | 0.747 | 0.575 | 0.677 | 0.727 | 1.000 | 0.974
JQ2 | 1.072 | 0.483 | 0.148 | 0.306 | 0.738 | 0.064 | 0.032 | 0.477 | 0.720 | 1.000 | 0.652 | 0.648 | 0.916 | 1.000
JQ3 | 1.440 | 0.772 | 0.366 | 0.341 | 1.033 | 0.206 | 0.117 | 0.271 | 0.313 | 0.467 | 0.553 | 0.330 | 0.528 | 0.600
Natural Scenes dataset - Supervised Learning Classification (CNN)
NS | 0.985 | 0.589 | 0.469 | 0.235 | 0.551 | 0.117 | 0.192 | 0.282 | 0.816 | 0.186 | 0.340 | 0.828 | 0.529 | 0.044
Facial Expressions dataset - Supervised Learning Classification (CNN)
FE | 0.081 | 0.0009 | 0.071 | 0.081 | 0.081 | 2.927 | 1.045 | 0.259 | 0.353 | 0.315 | 0.259 | 0.227 | 1.000 | 1.000
Table 5: The predictions with KL-divergence ($\mathbf{D_{KL}}$) when used with supervised learning (LSTM) and unsupervised learning (clustering and NBP). The lowest KL and the highest accuracy for NBP and clustering is highlighted in blue. KL-divergence | Accuracy
---|---
Dataset | Raw | Clustering |  NBP \- KL | Raw | Clustering |  NBP \- KL
| Labels | F | G | K | L | $r_{B}$ | $r_{NBP}$ | Labels | F | G | K | L | $r_{B}$ | $r_{NBP}$
Jobs dataset - Supervised Learning Classification (LSTM)
JQ1 | 0.907 | 0.874 | 0.918 | 0.788 | 0.770 | 0.550 | 0.533 | 0.865 | 0.874 | 0.794 | 0.861 | 0.844 | 0.987 | 1.000
JQ2 | 0.989 | 1.038 | 0.624 | 0.746 | 1.084 | 0.659 | 0.669 | 0.841 | 0.861 | 1.000 | 0.855 | 0.832 | 0.964 | 1.000
JQ3 | 1.567 | 1.358 | 1.003 | 0.910 | 1.456 | 0.789 | 0.748 | 0.643 | 0.621 | 0.642 | 0.718 | 0.612 | 0.782 | 0.821

##  5 Discussion

Discrepancies in the results obtained from different clustering models
correspond to discrepancies in the label distributions in different datasets
and in the behaviors of different clustering models. For instance, the label
distributions in the jobs dataset (Figure 10) tend to be skewed towards one
label choice, while this was not the case for NS (Figure 10) and FE (Figure
10). This skewing in the jobs dataset label distributions may be due to the
nature of human annotation with respect to human interpretations of the
questions asked about the data.

In contrast to the clustering methods, NBP as a whole showed promising results
throughout the experiments. On the NS and FE datasets, it showed a pattern of
increasing KL divergence as the radius increased. This behavior seems to
depend on how the label distributions are structured. For instance, the skewed
label distributions in the jobs dataset results in some items having no
neighbors at smaller radii.

The jobs dataset by Liu et al. [19] contains labels obtained from from two
crowdsourcing platforms. Manual inspection suggests there exist population-
level disparities in the distributions provided by each. This phenomenon could
be studied more rigorously by modeling user behaviors and traits to improve
PLDL. One approach, for instance, could involve inter-annotator agreement
using measures such as Cohen’s Kappa [15] to either resolve conflicts during
annotation or use them for refining the distribution estimates. However, a
challenge would be to acquire a dataset that contains annotator information,
as they are generally removed in publicly available datasets.

Table 3 raises questions about hyperparameter selection for NBP. As our main
goal is to share labels between neighbors, looking at the median number of
neighbors per each data item ($N_{Median}$) presents some insights. All the
datasets had a $N_{Median}$ of at least a quarter of the entire dataset except
for FE. One reason could be that FE is, among the datasets we consider, the
one that has the largest population of annotators.

While single label learning has a number of established performance measures,
such measures are not so well-established in label distribution learning. Geng
[9] analyzed 41 different measures and identified five (KL-divergence,
Chebyshev, Clark, Canberra, Cosine similarity, and Intersection) as most
effective. In our work, we used KL-divergence (one of the five measures
identified). KL-divergence is used to measure information loss specifically
for probability distributions. The use of our sampling techniques to evaluate
the models and hyperparameter selection contributes to the establishment of
standard procedures for LDL evaluation.

##  6 Conclusion

Gathering labeled data is an evident resource bottleneck for population-based
label distribution learning (PLDL). We introduced and studied new methods for
refining the label distributions of data items for PLDL based on the labels of
their neighbors. Neighborhood-based pooling (NBP) is semi-supervised learning
approach that uses information theoretic measures to pool similar label
distributions. We compared NBP as a pooling technique for supervised learning
to clustering methods introduced in prior research. We also introduced new
methods based on population hypothesis testing for selecting models for label
refinement. Our results show that NBP is a feasible approach for refining
label distribution estimates.

##  7 Acknowledgments

We thank the anonymous reviewers for their helpful feedback and suggestions.
Many thanks to Ifeoma Nwogu, Cecilia O. Alm, Victoria Maung, James Spann, and
Nandula Perera for their contributions and conversations.

## References

  * [1] Cecilia Ovesdotter Alm, ‘Subjective Natural Language Problems: Motivations, Applications, Characterizations, and Implications’, in Proceedings of the 49th Annual Meeting of the ACL : Human Language Technologies, pp. 107–112, (jun 2011).
  * [2] Lora Aroyo and Chris Welty, ‘The Three Sides of CrowdTruth’, in Journal of Human Computation, volume 1, pp. 31–34, (2014).
  * [3] David M Blei, Andrew Y Ng, and Michael I Jordan, ‘Latent dirichlet allocation’, Journal of machine Learning research, (2003).
  * [4] Joy Buolamwini and Timnit Gebru, ‘Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification’, in Proceedings of the 1st Conference on Fairness, Accountability and Transparency, (2018).
  * [5] Olivier Chapelle, Bernhard Schlkopf, and Alexander Zien, Semi-Supervised Learning, The MIT Press, 1st edn., 2010.
  * [6] A. P. Dawid and A. M. Skene, ‘Maximum likelihood estimation of observer error-rates using the em algorithm’, 28(1), 20–28, (1979).
  * [7] Bin-Bin Gao, Chao Xing, Chen-Wei Xie, Jianxin Wu, and Xin Geng, ‘Deep label distribution learning with label ambiguity’, volume 26, pp. 2825–2838. IEEE Press, (June 2017).
  * [8] Xin Geng, ‘Label Distribution Learning’, in IEEE Transactions on Knowledge and Data Engineering, volume 28, pp. 1734–1748, (2016).
  * [9] Xin Geng and Peng Hou, ‘Pre-release prediction of crowd opinion on movies by label distribution learning’, in Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15, (2015).
  * [10] Xin Geng, Qin Wang, and Yu Xia, ‘Facial age estimation by adaptive label distribution learning’, in Proceedings - International Conference on Pattern Recognition, (2014).
  * [11] Tanya Goyal, Tyler Mcdonnell, Mucahid Kutlu, Tamer Elsayed, and Matthew Lease, ‘Your Behavior Signals Your Reliability: Modeling Crowd Behavioral Traces to Ensure Quality Relevance Annotations’, in Sixth AAAI Conference on Human Computation and Crowdsourcing, (2018).
  * [12] Maria Halkidi, Yannis Batistakis, and Michalis Vazirgiannis, ‘On Clustering Validation Techniques’, Journal of Intelligent Information Systems, 17(2), 107–145, (2001).
  * [13] Christopher Homan, Ravdeep Johar, Tong Liu, Megan Lytle, Vincent Silenzio, and Cecilia Ovesdotter Alm, ‘Toward macro-insights for suicide prevention: Analyzing fine-grained distress at scale’, in Proceedings of the Workshop on Computational Linguistics and Clinical Psychology: From Linguistic Signal to Clinical Reality, pp. 107–117. Association for Computational Linguistics, (June 2014).
  * [14] Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum, ‘Label propagation for deep semi-supervised learning’, (June 2019).
  * [15] Jonathan Lazar, Jinjuan Heidi Feng, and Harry Hochheiser, ‘Chapter 11 - analyzing qualitative data’, in Research Methods in Human Computer Interaction (Second Edition), eds., Jonathan Lazar, Jinjuan Heidi Feng, and Harry Hochheiser, 317 – 319, Morgan Kaufmann, Boston, second edition edn., (2017).
  * [16] Lijun Yin, Xiaozhou Wei, Yi Sun, Jun Wang, and M. J. Rosato, ‘A 3d facial expression database for facial behavior research’, in 7th International Conference on Automatic Face and Gesture Recognition (FGR06), pp. 211–216, (April 2006).
  * [17] Miaogen Ling and Xin Geng, ‘Soft video parsing by label distribution learning’, in Frontiers of Computer Science, pp. 1331–1337, (2018).
  * [18] Tong Liu, Christopher Homan, Cecilia Ovesdotter Alm, Megan Lytle, Ann Marie White, and Henry Kautz, ‘Understanding discourse on work and job-related well-being in public social media’, in Proceedings of the 54th Annual Meeting of the ACL, (2016).
  * [19] Tong Liu, Akash Venkatachalam, Pratik Sanjay Bongale, and Christopher M. Homan, ‘Learning to Predict Population-Level Label Distributions’, in Seventh AAAI Conference on Human Computation and Crowdsourcing, volume 7, pp. 68–76, (2019).  A preliminary version appears in [20].
  * [20] Tong Liu, Akash Venkatachalam, Pratik Sanjay Bongale, and Christopher Homan, ‘Learning to predict population-level label distributions’, in Companion Proceedings of The 2019 World Wide Web Conference, WWW ’19, pp. 1111–1120. ACM, (2019).
  * [21] Andrea Malossini, Enrico Blanzieri, and Raymond T. Ng, ‘Detecting potential labeling errors in microarrays by data perturbation’, volume 22, pp. 2114–2121, (2006).
  * [22] Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz, ‘Building a large annotated corpus of English: The Penn Treebank’, volume 19, pp. 313–330, (1993).
  * [23] Gina Neff and Peter Nagy, ‘Talking to bots: Symbiotic agency and the case of Tay’, in International Journal of Communication, volume 10, pp. 4915–4931, (2016).
  * [24] Yi Ren and Xin Geng, ‘Sense beauty by label distribution learning’, in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, (2017).
  * [25] Victor S. Sheng, Foster Provost, and Panagiotis G. Ipeirotis, ‘Get another label? improving data quality and data mining using multiple, noisy labelers’, in Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pp. 614–622. ACM, (2008).
  * [26] Tom Simonite, ‘When it comes to gorillas, google photos remains blind’, (Jan 2018).  https://bit.ly/2FzeNM7.
  * [27] Rion Snow, Brendan O’Connor, Daniel Jurafsky, and Andrew Y. Ng, ‘Cheap and fast—but is it good?: Evaluating non-expert annotations for natural language tasks’, in Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP ’08, Stroudsburg, PA, USA, (2008). Association for Computational Linguistics.
  * [28] James Vincent.  Twitter taught Microsoft’s friendly AI chatbot to be a racist asshole in less than a day, 2016.  https://bit.ly/2u8m6qB.
  * [29] Jing Wang and Xin Geng, ‘Theoretical analysis of label distribution learning’, 5256–5263, (2019).
  * [30] Yingzhi Yang, ‘China chatbot goes rogue: ’do you love the communist party?’ ’no”, (Aug 2017).  https://on.ft.com/2vp8Qi5.
  * [31] M. Zhang, ‘A k-nearest neighbor based multi-instance multi-label learning algorithm’, in 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, volume 2, pp. 207–212, (Oct 2010).
  * [32] Xiaojin Zhu, ‘Semi-supervised learning literature survey’, Technical Report 1530, Computer Sciences, University of Wisconsin-Madison, (2005).

##  Appendix A Appendix

Figure 8: Overall label distribution of the JQ1 dataset [19].

Figure 9: Overall label distribution of the NS dataset [9].

Figure 10: Overall label distribution of the FE dataset [16].