# TACR: A Table-alignment-based Cell-selection and Reasoning Model for Hybrid
Question-Answering

Jian Wu1111indicates equal contribution. , Yicheng Xu2111indicates equal
contribution. , Yan Gao3, Jian-Guang Lou3
Börje F. Karlsson4, Manabu Okumura1
1Tokyo Institute of Technology 2Nanyang Technological University
3Microsoft Research Asia 4Beijing Academy of Artificial Intelligence
<EMAIL_ADDRESS><EMAIL_ADDRESS>
{yan.gao<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Hybrid Question-Answering (HQA), which targets reasoning over tables and
passages linked from table cells, has witnessed significant research in recent
years. A common challenge in HQA and other passage-table QA datasets is that
it is generally unrealistic to iterate over all table rows, columns, and
linked passages to retrieve evidence. Such a challenge made it difficult for
previous studies to show their reasoning ability in retrieving answers. To
bridge this gap, we propose a novel Table-alignment-based Cell-selection and
Reasoning model (TACR) for hybrid text and table QA, evaluated on the HybridQA
and WikiTableQuestions datasets. In evidence retrieval, we design a table-
question-alignment enhanced cell-selection method to retrieve fine-grained
evidence. In answer reasoning, we incorporate a QA module that treats the row
containing selected cells as context. Experimental results over the HybridQA
and WikiTableQuestions (WTQ) datasets show that TACR achieves state-of-the-art
results on cell selection and outperforms fine-grained evidence retrieval
baselines on HybridQA, while achieving competitive performance on WTQ. We also
conducted a detailed analysis to demonstrate that being able to align
questions to tables in the cell-selection stage can result in important gains
from experiments of over 90% table row and column selection accuracy,
meanwhile also improving output explainability. 111 Code is publicly available
at https://github.com/WuJian1995/QAP

##  1 Introduction

Figure 1: Example from the HybridQA dataset. The top sentence is the original
question, and words in different colors show different parts of questions
required for reasoning in different modalities. the two headers in blue-dashed
boxes are column names aligned with the given question. TACR first uses a
method based on table-question-alignment to align the original question with
table columns to help obtain golden table cells and then retrieve the final
answer based on linked passages.

Text-based question-answering datasets derive answers based on reasoning over
given passages Rajpurkar et al. (2016); Chen et al. (2017); Joshi et al.
(2017); Yang et al. (2018), while table-based QA datasets collect tables from
sources such as WikiTables Pasupat and Liang (2015a); Zhong et al. (2017);
Chen et al. (2019). However, datasets combining textual passages and tables,
like HybridQA Chen et al. (2020b), OTT-QA Chen et al. (2020a), and TAT-QA Zhu
et al. (2021) are more realistic benchmarks. As the answer to a given question
may come from either table cells or linked passages, current hybrid QA models
usually consist of two components, a retriever to learn evidence and a
reasoner to leverage the evidence to derive answers. Such models retrieve
evidence from different granularities, coarse-grained (e.g., row or column) or
fine-grained (e.g., cell), and directly use a span-based reading comprehension
model to reason the answer.

Kumar et al. (2021), for example, chooses coarse-grained regions as evidence,
e.g., a table row. Chen et al. (2020b) and Eisenschlos et al. (2021), however,
focus on fine-grained units, table cells and linked passages. To preserve the
advantages and eliminate the disadvantages of different-granularity evidence,
Sun et al. (2021a) propose MuGER,2 which performs multi-granularity evidence
retrieval and answer reasoning.

Wang et al. (2022) conducts extensive experiments to prove that a coarse-
grained retriever contributes less than a fine-grained retriever. Moreover,
fine-grained methods, although giving an exact position of candidate cells,
fail to illustrate why the selected cells are chosen, while our method is
based on row and column selection probabilities. We thus further extend the
fine-grained method by aligning questions with tables, letting our approach
know which parts of questions are accounted for by which modalities.
Intuitively, multi-hop questions in the text-table QA task usually contain two
pieces of information from different modalities, tables and passages.
Moreover, tables and passages are connected with evidence contained in tabular
data. Our method implicitly decomposes the questions for different modalities
to locate evidence and improve cell-selection accuracy.

As illustrated in Figure 1, an example from the HybridQA dataset shows how
humans work on multi-hop and multi-modal QA tasks. The original question
_"What is the middle name of the player with the second most National Football
League career rushing yards ?"_ can be divided into two parts, _"What is the
middle name of"_ and _"the player with the second most National Football
League career rushing yards?"_ for passages and tables, respectively. Such
sub-questions are connected with the evidence of a cell ( _"Walter Payton"_).
For humans, we first locate who was the player in the second rank, which
requires information from two columns: _"Rank"_ and _"Player"_. After locating
the cell, we can finally determine Walter Payton’s middle name from the
passage. Such reasoning process inspired us to develop TACR, a Table-
alignment-based Cell-selection and Reasoning model, which incorporates a fine-
grained evidence-retrieval module that utilizes table-question-alignment to
learn which parts of the question are used for retrieving evidence from
different modalities and reasoning towards answers.

To explicitly and correctly show the reasoning process in the text-table QA
task, in the evidence retrieval stage, TACR first selects the golden cells and
avoids redundant information in multi-granularity evidence that would lower
the performance of the answer-reasoning module. The table-cell-selection
module of TACR is designed to navigate the fine-grained evidence for the
reader by fusing well-learned information from the table-question-alignment
module. Compared with current fine-grained retrievers, the table-question-
alignment module of TACR can help our model learn which parts of questions are
used for reasoning in which modality, and which parts of tables contain
candidate cells. Together with the alignment module, TACR preserves both high
golden cell-selection accuracy and shows competitive performance on the
HybridQA and WikiTableQuestions (WTQ) datasets, while providing improved
explainability.

Our contributions are as follows: (1) TACR is the first model able to
explicitly show its reasoning process in the passage-table QA task; (2) We
jointly train the cell-selection and table-question alignment modules to
improve golden cell selection performance and preserve the QA reader’s
performance; and (3) We conduct extensive experiments on the HybridQA and WTQ
datasets to demonstrate the effectiveness of TACR.

##  2 Related Work

###  2.1 Table Question Answering

Table QA has gained much attention, as shown by benchmark datasets such as
WikiTableQuestions Pasupat and Liang (2015b), WikiSQL Zhong et al. (2018),
SPIDER Yu et al. (2018), and TABFACT Chen et al. (2019). However, these
datasets mainly focus on reasoning on tables and ignore important knowledge
stored in the textual corpus. Consequently, QA covering both tabular and
textual knowledge has gained increasing interest. Chen et al. (2020b)
pioneered a passage-table QA benchmark, HybridQA, with Wikipedia tables linked
to relevant free-form text passages (e.g., Wikipedia entity-definition pages).
The OTT-QA Chen et al. (2020a) benchmark extended HybridQA to the open domain
setting, where a system needs to retrieve a relevant set of tables and
passages first before trying to answer questions. Moreover, the links from the
table and passage are not provided explicitly.

###  2.2 Table-Question Alignment

There are several table-question-alignment methods. Schema-linking-based
methods, such as RAT-SQL Wang et al. (2019), introduce a relation-aware
transformer encoder to improve the joint encoding of a question and schema.
Liu et al. (2022) propose a similarity learning-based question-schema-
alignment method to obtain a semantic schema-linking graph and observed how
the pre-trained language model (PLM) embeddings for the schema items are
affected. Zhao and Yang (2022) use the same words that appear in both the
natural language statement and the table as weak supervised key points and
design an interaction network to explore the correlation between the
representations of the natural language statements and tables.

###  2.3 Hybrid QA

Studies on hybrid QA usually retrieve different granularities of evidence from
heterogeneous data to retrieve the final answer. Hybrider, proposed by Chen et
al. (2020b), is a two-phase pipeline framework to retrieve gold table cells as
evidence and input their values and linked passages into a QA model to extract
the final answer. Sun et al. (2021b) proposes Dochopper, an end-to-end multi-
hop retrieval model that directly concatenates rows with related textual
evidence as its inputs. Pan et al. (2020) explores an unsupervised multi-hop
QA model, called MQA-QG, which can generate human-like multi-hop questions by
building a reasoning graph from heterogeneous data resources. Kumar et al.
(2021) propose MITQA, which applies multiple-instance training objectives to
retrieve coarse-grained evidence. On the contrary, Eisenschlos et al. (2021)
introduce a transformer-based model with row- and column-wise attentions for
fine-grained evidence retrieval, e.g., table cells. Wang et al. (2022) propose
a unified retriever that tries to preserve the advantages and eliminates the
disadvantages of different-granularity evidence retrieval methods.

TACR differs from the above models mainly in two aspects: (1) TACR focuses on
providing an explicit reasoning process by aligning multi-hop questions to
tables, so it learns which parts of multi-hop questions are accounted for by
retrieving evidence from which modality; and (2) The table-question alignment
can enhance the reasoning ability of the table cell selection module with the
help of our generated hybrid alignment dataset. TACR shows competitive
performance to that of other table QA models on the HybridQA and WTQ datasets
on the basis of high row, column, and cell selection accuracy. To the best of
our knowledge, no text-table QA system handles the challenge of explicitly
showing its reasoning process and multi-hop question table alignment.

###  2.4 Table Cell Retrieval

Jauhar et al. (2016) construct a multiple-choice table QA benchmark that
includes over 9000 question-table pairs via crowd-sourcing and proposed a
table-cell search model based on calculating all relevance scores between each
cell and question. Such a model is reasonable and intuitive but time-
consuming. TACR selects gold cells based on row and column selection. Suppose
that a table contains $n$ rows and $m$ columns; the table cell search method
must calculate $n*m$ scores for each cell, while TACR needs to calculates only
$n+m$ scores for each row and column, and selects the gold cell in the row and
column with the highest score. Sun et al. (2016) focus on extracting entities
from questions and building a row graph and then mapping the question to the
pair of cells in the same row of a table. However, some entities may not
appear in both questions and table cells, e.g., an entity of the question in
Figure 1 that should be extracted is _National Football League_ , but it
cannot be mapped into any cells.

##  3 Framework

As described in the previous section, both coarse- and fine-grained approaches
fail to provide a reasoning process showing which parts of multi-hop questions
map to which modality and evidence. Here we describe the details of TACR and
its three main components: (1) data augmentation for training the table-
question alignment module; (2) a multi-task learning module for table-question
alignment and table-cell-selection; and (3) a text-based multi-hop QA module
for retrieving answers. Figure 2 shows the overall architecture of TACR.

Figure 2: TACR model architecture. From left to right, we first construct a
hybrid alignment dataset to jointly train the table-question-alignment and
table-cell-selection modules. We then concatenate filtered linked passages
with selected top-k candidate cells as paragraphs and feed them into a text-
based multi-hop QA module to retrieve answers.

###  3.1 Task Definition

Given a question $Q$ (a sequence of tokens) and $N$ rows of table $T$ together
with linked passages $P$, where each table column has a header $h_{i=1}^{i=M}$
($M$ is the number of table headers), the task is to find a candidate cell
$c_{i,j}$ that contains the answer $\alpha$.

###  3.2 Data Construction

We generate multi-hop questions from tables and linked passages, as well as
table-question alignment labels from questions and table columns for training
the table-question-alignment module. However, such supervision information is
not offered in the HybridQA dataset and other text-table QA datasets, which
makes the alignment task difficult. We use an unsupervised text-table QA-
generation method to generate questions as well as alignment labels.

##### Alignment Generation.

We follow the settings of the MQA-QG method Pan et al. (2020), using a pre-
trained Google T5 Raffel et al. (2019), fine-tuned on the SQuAD dataset
Rajpurkar et al. (2018), to generate multi-hop questions from tables and
passages based on a bridge entity, a table cell that contains the bridge
entity, and a linked passage that describes the bridge entity. The bridge
entity is critical in reasoning because it connects the tables and passages,
which are difficult to locate in the original HybridQA dataset.

Such bridge entity provides us with additional information to align table
headers with generated questions based on the column containing golden cells
and the column containing the bridge entity. We align the columns which
contain bridge entities and answers to questions following two schema-linking
alignment rules:

Name-based Linking. This rule refers to exact or partial occurrences of the
column/table names in the question, such as the occurrences of “player” in the
question in Figure 1. Textual matches are the most explicit evidence of table-
question alignment and, as such, one might expect them to be directly
beneficial to the table-question alignment module.

Value-based Linking. Table-question alignment also occurs when the question
mentions any values that occur in the table and consequently participate in
the table-cell selection, such as “the second most” in Figure 1. While it is
common for examples to make the alignment explicit by mentioning the column
name (e.g., “Rank”), many real-world questions do not (like in the example).
Consequently, linking a value mentioned in the question to the corresponding
column also requires background knowledge.

Figure 3: The table-question-alignment module of TACR. We treat the alignment
objective as a similarity learning task.

###  3.3 Passage Filtering

In this stage, we aim to filter out linked passages unrelated to a question,
namely keeping almost noise-free passages for the following modules. Moreover,
the total number of tokens in passages linked to table cells can be large,
exceeding the maximum input sequence length of current LMs. Thus, we utilize
Sentence-BERT Reimers and Gurevych (2019) to obtain question and passage
embeddings and rank the top-k sentences based on their text similarities. We
expand the cells with the filtered top k-related sentences to both fit in the
max input length of language models and to preserve the useful information
from passages. More details on this stage are provided in Appendix A.

###  3.4 Table Alignment & Cell Selection

In this stage, we jointly train a multi-task model with the objectives of
selecting the expanded cell that contains the answer and table-question
alignment to different modalities to enhance the previous objective. TACR
accepts the full table as inputs and outputs the probabilities of selected
cells based on the probabilities of row and column selection.

####  3.4.1 Table-Question Alignment

Given a natural language question
$Q=\left\\{q_{1},....q_{\left|Q\right|}\right\\}$, a table consisting of
several column headers $C=\left\\{c_{1}....c_{\left|C\right|}\right\\}$, and
the corresponding table-question alignment labels
$L=\left\\{l_{1},...l_{\left|C\right|}\right\\}$ where $l_{i}\in[0,1]$ (0
meaning the column header is unrelated to the question $Q$ and 1 meaning the
column header is related to $Q$). The goal of our table-question alignment
module is to learn the relevance between table-column headers and questions.
Table-question relations aid TACR by aligning column references in the
question to the corresponding table columns.

We first feed the questions and table columns into the pre-trained model and
map them into hidden representations. The question and table-column headers
can be denoted as $\left\\{q_{1},....q_{\left|Q\right|}\right\\}$ and
$\left\\{c_{1}....c_{\left|C\right|}\right\\}$, respectively. Our goal is to
induce a function $f(q_{i},c_{j})$ to capture the relevance of a question word
$q_{i}$ has on the representation of column header $c_{j}$. Figure 3 shows the
structure of the alignment module.

Specifically, we use ALBERT Lan et al. (2019) as the encoder to learn the
representations of tables and column headers. Here we concatenate column
headers as a pseudo sentence. The representations of the question ($h_{q}$)
and the column headers sequence ($h_{c}$) are first computed independently.
The relevance where each column header $c_{i}$ is the target of the question
is then given by using softmax. The respective equations are as follows:

$\displaystyle h_{q}$ $\displaystyle=\texttt{BERT(Q)},$ (1) $\displaystyle
h_{c}$ $\displaystyle=\texttt{BERT(C)},$ (2) $\displaystyle p(C_{i}\in C)$
$\displaystyle=\texttt{softmax}(W(h_{q}*h_{c})+b).$ (3)

####  3.4.2 Table-Cell Selection

Inspired by the previous idea of modeling the attention on rows and columns
Eisenschlos et al. (2021), we design a cell-selection module based on row and
column selection. The probabilities of each row and column are given and the
cells with the top-k highest scores are returned as the candidate answers, or
to aid in locating the relevant passage. However, unlike in MATE Eisenschlos
et al. (2021), we can derive probabilities of candidate cells from the
probabilities of row and column.

We utilize the Row-Column-Intersection (RCI) model, designed for the single-
hop table-QA task Glass et al. (2021) (based on ALBERT Lan et al. (2019)), as
our backbone and decompose the table QA task into two subtasks: projection -
corresponding to identifying columns; and selection - identifying rows. Every
row and column identification is a binary sequence pair classification. We
concatenate the question as the first sequence and the row or column as the
second sequence. We feed concatenated two sequences, with standard separator
tokens $[CLS]$ and $[SEP]$, as the input to the model. The representation of
the final hidden state is sent to the linear layer, followed by a softmax to
classify whether the column or row contains the answer or not. Each row and
column is assigned a probability of containing the answer. This module finally
outputs the top-k cells with the sum of row and column probabilities.
Therefore, given a table $T$ with $N$ rows and $M$ columns, we can obtain two
sets of scores produced from the RCI model: $P_{r}={p_{1},....p_{N}}$ for rows
and $P_{c}={p_{1},....p_{M}}$ for columns. We then calculate the overall
probability score for each cell.

The final training loss is the summation of table-question-alignment loss,
table-row-selection loss, and table-column-selection loss:

$\displaystyle\begin{split}L&=\texttt{L\\_{row}}+\texttt{L\\_{column}}\\\
&+\sigma\times\texttt{BCE}(pred\\_{headers},target\\_{headers}),\end{split}$
(4)

where $\sigma$ is a hyper-parameter to balance cell-selection training and
table-question-alignment training. The details of choosing the best $\sigma$
are provided in Appendix C.

###  3.5 Passage Question-Answering

Previous research often simply treat the answer-reasoning task as a span-
extraction task, considered the first span matching the answer text as the
gold span, and use that for training. Such consideration is incorrect because
the answer text may appear in multiple passages, but only one of them is
right. Therefore, using all text matches for training span extraction may
introduce a large amount of training noise. As not all instances are the gold
answer text that has relations with questions, after obtaining the top-k cells
from the cell-selection module, we train the text-based QA module to predict
the final answer that also takes into account the cell-selection scores.

Specifically, we select clean training instances where the gold answer text
appears only once and train an initial QA model. In this stage, we use RoBERTa
Liu et al. (2019) as our backbone model. Other BERT variants, e.g., either
SpanBERT Joshi et al. (2019) or DeBERTa He et al. (2020), could be also used
in this module. Our goal is to obtain a span $s$ in a given expanded table
cell $c$ with its filtered passage $p$ and the input question $q$. We compute
a span representation as follows:

$\displaystyle h_{start}=\texttt{RoBERTa}_{r}(q,c)[\texttt{START}(s)],$ (5)
$\displaystyle h_{end}=\texttt{RoBERTa}_{r}(q,c)[\texttt{END}(s)],$ (6)
$\displaystyle S_{span}(q,p)=\texttt{MLP}([h\\_{start},h\\_{end}]).$ (7)

We also consider other cells in the same row as the retrieved candidate gold
cells as the necessary context. We linearize and concatenate the row into a
passage with the designed template: "The <column header> is <cell content>".
We retrieve the top-k cells and thus have k samples. Since not all selected
cells contain the gold answer text, we treat one sample as positive and the
others as negative samples. For each data point, we generate $k$ samples and
match these with the answer text. Let
$K=\\{q_{i},A_{i},P^{+}_{i},P^{-}_{i,1},···,P^{-}_{i,k-1}\\}^{k}_{i=1}$ be the
training data that consist of $k$ instances, where $k$ is the number of
selected candidate cells. Each instance contains one question $q_{i}$, the
gold answer text $A_{i}$, and one correct (positive) passage text $P^{+}_{i}$,
along with $k-1$ wrong passages $P^{-}_{i,j}$. For positive samples, the
answer is the text span of the passage, while for negative samples, the
answers are -1.

##  4 Experiments

###  4.1 Datasets

HybridQA Chen et al. (2020b) is the first large-scale multi-hop QA dataset
that requires reasoning over hybrid knowledge, including tables and linked
Wikipedia passages. The dataset contains 62,682 instances in the training set,
3,466 instances in the development set, and 3,463 instances in the test set.

WikiTableQuestions Pasupat and Liang (2015a), WTQ for short, consists of 22033
complex questions and 2108 semi-structured Wikipedia tables. The questions are
designed by crowd-sourcing to contain a wide range of domains. The answers are
derived from several operations such as table lookup, aggregation,
superlatives, arithmetic operations, joins, and unions.

Split | Train | Dev. | Test | Total
---|---|---|---|---
In-Passage | 35215 | 2025 | 2045 | 39285
In-Table | 26803 | 1349 | 1346 | 29498
Compute | 664 | 92 | 72 | 864
Total | 62682 | 3466 | 3463 | 69611
Table 1: Statistics of HybridQA dataset

To verify the performance of TACR, we first conduct experiments on HybridQA
Chen et al. (2020b), a dataset of multi-hop question-answering over tabular
and textual data. The basic statistics of HybridQA are listed in Table 1. The
dataset contains three partitions: ‘In-Table’, where the answer derives from
table cell values; ‘In-Passage’, where the answer exists in a linked passage;
and ‘Compute’, where the answer should be computed by executing numerical
operations. We mainly focus on the first two types. We also provide results
over WTQ to illustrate TACR’s capabilities in table-focused QA.

###  4.2 Baselines

MQA-QG, proposed by Pan et al. (2020), is an unsupervised question-generation
framework that generates multi-hop questions from tables and linked passages,
and uses the generated questions to train an HQA model.
Table-Only Chen et al. (2020b) only retrieves the tabular information to find
an answer by parsing the question into a symbolic form and executing it.
Passage-Only Chen et al. (2020b) only retrieves answers from the table-linked
passages.
Hybrider Chen et al. (2020b) addresses HQA using a two-stage pipeline
framework to retrieve the gold table cell and extract an answer in its value
or linked passages.
Dochopper Sun et al. (2021b) first converts a table with its hyperlinked
passages into a long document then concatenates column headers, cell text, and
linked passages in each row of tables as a paragraph.
MATE Eisenschlos et al. (2021) applies sparse attention to rows and columns in
a table. To apply it to the HybridQA dataset, the authors propose a PointR
module, which expands a cell using the description of its entities, selects
the golden cells, then retrieves answers from them.
MITQA Kumar et al. (2021) designs a multi-instance training method based on
distant supervision to filter the noisy information from multiple answer
spans.

###  4.3 Quantitative Analysis

We use exact match (EM) and F1 scores as evaluation metrics on the HybridQA
dataset to compare the performance of TACR with that of previous baselines. As
shown in Table 2, TACR outperforms most baselines and achieved competitive
performance to state-of-the-art (SOTA) models (e.g., MITQA) in both EM and F1
scores over the HybridQA dataset. Table 3 reports the accuracy performance on
WTQ. Though TACR is trained on a base model, it presents comparable accuracy
to the large SOTA models and outperforms other base models. It is important to
note that, besides both using much larger LMs than TACR (GPT-3 and BART-large
respectively, versus RoBERTa-base), neither Binder nor Omnitab-large provide
explainability. With the help of the table-question-alignment module, TACR
boosts relative accuracy by $+18.5\%$ on the test set compared with RCI Glass
et al. (2021), which is also based on cell selection. This competitive
performance is mainly based on the high cell selection along with table-
question alignment. We further verified the effectiveness of the table-
question-alignment module in an ablation study discussed in Section 4.5.

###  4.4 Qualitative Analysis

We compare the cell-selection accuracy of TACR and baseline models, as shown
in Table 4. The high cell selection accuracy is based on the high row- and
column-selection accuracies shown in Table 6. On the HybirdQA dataset, TACR
shows SOTA performance and 0.4% higher than that of MATE Eisenschlos et al.
(2021) in the top 3 cell-selection accuracies due to its 89.3% row-selection
accuracy and 98.3% column-selection accuracy, as shown in Table 6. Moreover,
by achieving soft question decomposition (i.e., showing which parts of
questions are connected to reasoning in the different modalities), TACR both
improves the explainability of its results and provides valuable signals for
future improvements.

Model | Dev. | Test
---|---|---
| In-Table | In-Passage | Total | In-Table | In-Passage | Total
| EM | F1 | EM | F1 | EM | F1 | EM | F1 | EM | F1 | EM | F1
Table-Only | 14.7 | 19.1 | 2.4 | 4.5 | 8.4 | 12.1 | 14.2 | 18.8 | 2.6 | 4.7 | 8.3 | 11.7
Passage-Only | 9.2 | 13.5 | 26.1 | 32.4 | 19.5 | 25.1 | 8.9 | 13.8 | 25.5 | 32.0 | 19.1 | 25.0
Hybrider ($\tau$=0.8) | 54.3 | 61.4 | 39.1 | 45.7 | 44.0 | 50.7 | 56.2 | 63.3 | 37.5 | 44.4 | 43.8 | 50.6
PointR + SAT | 66.5 | 71.8 | 60.3 | 69.2 | 61.2 | 68.7 | 64.6 | 70.1 | 59.6 | 68.5 | 60.1 | 67.4
PointR + TAPAS | 68.1 | 73.9 | 62.9 | 72.0 | 63.3 | 70.8 | 67.8 | 73.2 | 62.0 | 70.9 | 62.7 | 70.0
PointR + TABLEETC | 36.0 | 42.4 | 37.8 | 45.3 | 36.1 | 42.9 | 35.8 | 40.7 | 38.8 | 45.7 | 36.6 | 42.6
PointR + LINFORMER | 65.5 | 71.1 | 59.4 | 69.0 | 60.8 | 68.4 | 66.1 | 71.7 | 58.9 | 67.8 | 60.2 | 67.6
PointR + MATE | 68.6 | 74.2 | 62.8 | 71.9 | 63.4 | 71.0 | 66.9 | 72.3 | 62.8 | 71.9 | 62.8 | 70.2
MQA-QG (unsupervised) | – | – | – | – | – | – | 36.2 | 40.6 | 19.8 | 25.0 | 25.7 | 30.5
Dochopper | – | – | – | – | 47.7 | 55.0 | – | – | – | – | 46.3 | 53.3
MITQA | 68.1 | 73.3 | 66.7 | 75.6 | 65.5 | 72.7 | 68.5 | 74.4 | 64.3 | 73.3 | 64.3 | 71.9
MuGER2 | 58.2 | 66.1 | 52.9 | 64.6 | 53.7 | 63.6 | 56.7 | 64.0 | 52.3 | 63.9 | 52.8 | 62.5
TACR (ours) | 66.7 | 70.3 | 63.4 | 72.5 | 64.5 | 71.6 | 64.1 | 69.6 | 65.4 | 70.7 | 66.2 | 70.2
Human |  |  |  |  |  |  |  |  |  |  | 88.2 | 93.5

Table 2: EM and F1 results of models on the HybridQA dataset. In-Table and In-
Passage subsets refer to the location of answers.

Model | Dev | Test
---|---|---
| Acc | Acc
TAPEX-Large Liu et al. (2021) | 57.0 | 57.5
Binder Cheng et al. (2022) | 65.0 | 64.6
OmniTab-Large Jiang et al. (2022) | 62.5 | 63.3
TAPAS_base (pre-trained on SQA) Herzig et al. (2020) | - | 48.8
UnifiedSKG Xie et al. (2022) | 50.7 | 49.3
TaBERT_base Yin et al. (2020) | 51.6 | 51.4
RCI Glass et al. (2021) | 45.3 | 41.7
TACR_RoBERTa-base (ours) | 58.9 | 60.2

Table 3: Execution-accuracy results of models on WTQ

Model | Hits@1 | Hits@3 | Hits@5
---|---|---|---
TABLEETC Ainslie et al. (2020) | 51.1 | 72.0 | 78.9
LINFORMER Wang et al. (2020) | 77.1 | 86.5 | 90.0
MATE Eisenschlos et al. (2021) | 80.1 | 86.2 | 90.5
TACR (ours) | 83.3 | 87.8 | 91.2

Table 4:  Comparison of cell-retrieval results on HybridQA dataset (dev set)

###  4.5 Ablation Study

To evaluate the impact of the table-question-alignment module, we conduct an
ablation study, shown in Table 5. We test DeBERTa-base, ALBERT-base, and
RoBERTa-base models as TACR backbones for generality. Different top-k results
show that the alignment module consistently significantly improves results;
with the best model based on ALBERT improving cell-selection accuracy by 2.5,
3.9, and 4.3% in top 1, 3, and 5 cell selection respectively; and mean
reciprocal rank (MRR) improving by 3.7%. The results indicate that the table-
question-alignment module has an important role in the table-question-
reasoning stage to select the most related cells that support the answer to
the question.

Model | MRR | Hits@1 | Hits@3 | Hits@5
---|---|---|---|---
TACR-DeBERT_base w/o alignment | 78.9 | 74.9 | 79.4 | 83.7
TACR-Roberta_base w/o alignment | 80.7 | 74.3 | 82.6 | 84.4
TACR-ALBERT_base w/o alignment | 80.1 | 77.1 | 82.8 | 85.4
TACR-DeBERTa_base w/ alignment | 82.4 | 78.3 | 83.4 | 86.2
TACR-RoBERTa_base w/ alignment | 82.5 | 76.5 | 85.5 | 88.9
TACR-ALBERT_base w/ alignment | 83.8 | 79.6 | 86.7 | 89.7

Table 5: Ablation study of table-question-alignment module impact. Experiment
results of cell-retrieval on HybridDQA (dev set) show the effectiveness of
this module in the table-cell-selection stage.

Model | HybridQA | WTQ
---|---|---
Row | Col | Row | Col
top 1
TACR_DeBERTa_base | 85.1 | 95.3 | 53.2 | 93.9
TACR_ALBERT_base | 86.7 | 96.1 | 56.8 | 94.4
TACR_RoBERTa_base | 86.0 | 96.2 | 52.3 | 94.7
top 3
TACR_DeBERTa_base | 86.2 | 96.2 | 57.6 | 94.2
TACR_ALBERT_base | 88.3 | 97.1 | 62.4 | 95.1
TACR_RoBERTa_base | 87.9 | 97.3 | 59.3 | 94.9
top 5
TACR_DeBERTa_base | 87.5 | 97.8 | 59.1 | 94.8
TACR_ALBERT_base | 89.9 | 98.3 | 68.1 | 95.4
TACR_RoBERTa_base | 89.3 | 98.4 | 64.5 | 95.2

Table 6: Performance of TACR with different backbone models. Top-k rows and
columns selection accuracies on HybridQA and WTQ datasets, where k=1, 3, 5.
Results demonstrate the effectiveness of TACR.

###  4.6 Case Study

To illustrate TACR can successfully learn which parts of tables contain golden
cells and which parts of questions are required for reasoning in the different
modalities, we choose two examples from the HybridQA development set. Appendix
B includes Figures 4 and 5 showing their word relevances heatmap and analysis.

The question in Case 1 is "Who is the athlete in a city located on the
Mississippi River ?". The concatenated table headers string for the
corresponding table is "Year Score Athlete Place". The table-question-
alignment module helps TACR learn that header terms "Athlete" and "Place" have
higher relevance to the question than the headers of other columns, thus
guiding cell-selection. Figure 4 shows its relevance heatmap. TACR again
learns which parts of the question account for retrieving evidence in tables.

The question in Case 2 is "What is the middle name of the player with the
second most National Football League career rushing yards ?". The concatenated
table headers string for it is "Rank Player Team(s) by season Carries Yards
Average". The table-question-alignment module helps TACR learn that the sub-
question "the player with the second most National Football League career
rushing yards" has a higher relevance to the table headers than that of other
parts of the original question, thus guiding modality relevance. Figure 5
shows its relevance heatmap.

###  4.7 Error Analysis

To further analyze TACR, we also calculate statistics for error cases in the
model predictions. The error statistics are based on the development set of
HybridQA. Through the cell-selection accuracy statistics in Table 4, we find
there are 347 tables whose cells are incorrectly selected.

To better understand the advantages and disadvantages of table-question
alignment-based cell selection, we manually sample and examined 20 such error
cases (i.e., where TACR does not provide the correct answer in the correct
row, column, and cell position). Out of the 20 samples, we find that five
error cases (25%) are due to requiring numerical reasoning operations that
cross several cells (which is out of scope for TACR). The majority of errors,
13 of the remaining incorrect cases, are in the same column with a correct
answer while in the wrong row. Only one case is from a different row but the
same column with the correct answer and only one incorrect case is in a
completely different row and column to the correct answer.

##  5 Conclusion

This paper presents TACR, a Table question Alignment-based cell selection and
Reasoning model for hybrid text and table QA, evaluated on the HybridQA and
WikiTableQuestions datasets. When answering questions given retrieved table
cells and passages, TACR attempts to align multi-hop questions to different
modalities for correct evidence retrieval. To enhance the QA module with
better table cell-selection and table-question-alignment ability, we construct
a hybrid alignment dataset generated from the HybridQA dataset. TACR shows
state-of-the-art performance in retrieving intermediate gold table cells and
competitive performance on the HybridQA and WikiTableQuestions datasets, while
improving output explainability.

##  6 Limitations

In this paper, we focus on the hybrid QA task, where the answers to most
questions can be extracted from cell values in tables and linked passages
using a reading comprehension model. Although TACR performs well in cell
selection, one of its limitations is that it lacks numerical reasoning ability
across different cells, such as counting and comparing. To enable TACR to
answer numerical questions, we will further develop its numerical reasoning
capabilities in future work. Another limitation of TACR is that it shows a
strong ability in column selection while performing relatively worse in row
selection. For future work, we plan to try to improve its row-selection
accuracy.

## References

  * Ainslie et al. (2020) Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. 2020.  ETC: Encoding long and structured inputs in transformers.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 268–284, Online. Association for Computational Linguistics.
  * Chen et al. (2017) Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017.  Reading Wikipedia to answer open-domain questions.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1870–1879, Vancouver, Canada. Association for Computational Linguistics.
  * Chen et al. (2020a) Wenhu Chen, Ming-Wei Chang, Eva Schlinger, William Yang Wang, and William W. Cohen. 2020a.  Open question answering over tables and text.  _ArXiv_ , abs/2010.10439.
  * Chen et al. (2019) Wenhu Chen, Hongmin Wang, Jianshu Chen, Yunkai Zhang, Hong Wang, Shiyang Li, Xiyou Zhou, and William Yang Wang. 2019.  Tabfact: A large-scale dataset for table-based fact verification.  _arXiv preprint arXiv:1909.02164_.
  * Chen et al. (2020b) Wenhu Chen, Hanwen Zha, Zhiyu Chen, Wenhan Xiong, Hong Wang, and William Wang. 2020b.  HybridQA: A dataset of multi-hop question answering over tabular and textual data.  _arXiv preprint arXiv:2004.07347_.
  * Cheng et al. (2022) Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, R.K. Nadkarni, Yushi Hu, Caiming Xiong, Dragomir R. Radev, Marilyn Ostendorf, Luke Zettlemoyer, Noah A. Smith, and Tao Yu. 2022.  Binding language models in symbolic languages.  _ArXiv_ , abs/2210.02875.
  * Eisenschlos et al. (2021) Julian Martin Eisenschlos, Maharshi Gor, Thomas Müller, and William W. Cohen. 2021.  MATE: Multi-view attention for table transformer efficiency.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Glass et al. (2021) Michael R. Glass, Mustafa Canim, A. Gliozzo, Saneem A. Chemmengath, Rishav Chakravarti, Avirup Sil, Feifei Pan, Samarth Bharadwaj, and Nicolas Rodolfo Fauceglia. 2021.  Capturing row and column semantics in transformer based question answering over tables.  In _North American Chapter of the Association for Computational Linguistics_.
  * He et al. (2020) Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2020.  DeBERTa: Decoding-enhanced BERT with disentangled attention.  _ArXiv_ , abs/2006.03654.
  * Herzig et al. (2020) Jonathan Herzig, Pawel Krzysztof Nowak, Thomas Müller, Francesco Piccinno, and Julian Martin Eisenschlos. 2020.  TaPas: Weakly supervised table parsing via pre-training.  _ArXiv_ , abs/2004.02349.
  * Jauhar et al. (2016) Sujay Kumar Jauhar, Peter Turney, and Eduard Hovy. 2016.  Tables as semi-structured knowledge for question answering.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 474–483, Berlin, Germany. Association for Computational Linguistics.
  * Jiang et al. (2022) Zhengbao Jiang, Yi Mao, Pengcheng He, Graham Neubig, and Weizhu Chen. 2022.  Omnitab: Pretraining with natural and synthetic data for few-shot table-based question answering.  In _NAACL_.
  * Joshi et al. (2019) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S. Weld, Luke Zettlemoyer, and Omer Levy. 2019.  SpanBERT: Improving pre-training by representing and predicting spans.  _Transactions of the Association for Computational Linguistics_ , 8:64–77.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer. 2017.  Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Kumar et al. (2021) Vishwajeet Kumar, Saneem A. Chemmengath, Yash Gupta, Jaydeep Sen, Samarth Bharadwaj, and Soumen Chakrabarti. 2021.  Multi-instance training for question answering across table and linked text.  _ArXiv_ , abs/2112.07337.
  * Lan et al. (2019) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2019.  ALBERT: A lite BERT for self-supervised learning of language representations.  _ArXiv_ , abs/1909.11942.
  * Liu et al. (2022) Aiwei Liu, Xuming Hu, Li Lin, and Lijie Wen. 2022.  Semantic enhanced text-to-sql parsing via iteratively learning schema linking graph.  _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_.
  * Liu et al. (2021) Qian Liu, Bei Chen, Jiaqi Guo, Zeqi Lin, and Jian-Guang Lou. 2021.  TAPEX: Table pre-training via learning a neural SQL executor.  _ArXiv_ , abs/2107.07653.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A robustly optimized BERT pretraining approach.  _ArXiv_ , abs/1907.11692.
  * Pan et al. (2020) Liangming Pan, Wenhu Chen, Wenhan Xiong, Min-Yen Kan, and William Yang Wang. 2020\.  Unsupervised multi-hop question answering by question generation.  In _North American Chapter of the Association for Computational Linguistics_.
  * Pasupat and Liang (2015a) Panupong Pasupat and Percy Liang. 2015a.  Compositional semantic parsing on semi-structured tables.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1470–1480, Beijing, China. Association for Computational Linguistics.
  * Pasupat and Liang (2015b) Panupong Pasupat and Percy Liang. 2015b.  Compositional semantic parsing on semi-structured tables.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Raffel et al. (2019) Colin Raffel, Noam M. Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2019.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _ArXiv_ , abs/1910.10683.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know what you don’t know: Unanswerable questions for squad.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  Squad: 100,000+ questions for machine comprehension of text.  _arXiv preprint arXiv:1606.05250_.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  _ArXiv_ , abs/1908.10084.
  * Sun et al. (2021a) Haitian Sun, William W. Cohen, and Ruslan Salakhutdinov. 2021a.  End-to-end multihop retrieval for compositional question answering over long documents.  _ArXiv_ , abs/2106.00200.
  * Sun et al. (2021b) Haitian Sun, William W. Cohen, and Ruslan Salakhutdinov. 2021b.  Iterative hierarchical attention for answering complex questions over long documents.
  * Sun et al. (2016) Huan Sun, Hao Ma, Xiaodong He, Wen tau Yih, Yu Su, and Xifeng Yan. 2016.  Table cell search for question answering.  _Proceedings of the 25th International Conference on World Wide Web_.
  * Wang et al. (2019) Bailin Wang, Richard Shin, Xiaodong Liu, Oleksandr Polozov, and Matthew Richardson. 2019.  Rat-sql: Relation-aware schema encoding and linking for text-to-sql parsers.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Wang et al. (2020) Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. 2020.  Linformer: Self-attention with linear complexity.  _ArXiv_ , abs/2006.04768.
  * Wang et al. (2022) Yingyao Wang, Junwei Bao, Chaoqun Duan, Youzheng Wu, Xiaodong He, and Tiejun Zhao. 2022.  MuGER2: Multi-granularity evidence retrieval and reasoning for hybrid question answering.  _ArXiv_ , abs/2210.10350.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Xie et al. (2022) Tianbao Xie, Chen Henry Wu, Peng Shi, Ruiqi Zhong, Torsten Scholak, Michihiro Yasunaga, Chien-Sheng Wu, Ming Zhong, Pengcheng Yin, Sida I. Wang, Victor Zhong, Bailin Wang, Chengzu Li, Connor Boyle, Ansong Ni, Ziyu Yao, Dragomir R. Radev, Caiming Xiong, Lingpeng Kong, Rui Zhang, Noah A. Smith, Luke Zettlemoyer, and Tao Yu. 2022.  UnifiedSKG: Unifying and multi-tasking structured knowledge grounding with text-to-text language models.  _ArXiv_ , abs/2201.05966.
  * Yang et al. (2018) Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018.  HotpotQA: A dataset for diverse, explainable multi-hop question answering.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2369–2380, Brussels, Belgium. Association for Computational Linguistics.
  * Yin et al. (2020) Pengcheng Yin, Graham Neubig, Wen tau Yih, and Sebastian Riedel. 2020.  TaBERT: Pretraining for joint understanding of textual and tabular data.  _ArXiv_ , abs/2005.08314.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai-Chou Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Z Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir R. Radev. 2018.  Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-sql task.  In _Conference on Empirical Methods in Natural Language Processing_.
  * Zhao and Yang (2022) Guangzhen Zhao and Peng Yang. 2022.  Table-based fact verification with self-labeled keypoint alignment.  In _International Conference on Computational Linguistics_.
  * Zhong et al. (2017) Victor Zhong, Caiming Xiong, and Richard Socher. 2017.  Seq2sql: Generating structured queries from natural language using reinforcement learning.  _arXiv preprint arXiv:1709.00103_.
  * Zhong et al. (2018) Victor Zhong, Caiming Xiong, and Richard Socher. 2018.  Seq2sql: Generating structured queries from natural language using reinforcement learning.  _ArXiv_ , abs/1709.00103.
  * Zhu et al. (2021) Fengbin Zhu, Wenqiang Lei, Youcheng Huang, Chao Wang, Shuo Zhang, Jiancheng Lv, Fuli Feng, and Tat-Seng Chua. 2021.  TAT-QA: A question answering benchmark on a hybrid of tabular and textual content in finance.  _arXiv preprint arXiv:2105.07624_.

##  Appendix A Passage Filtering

Passage filtering plays an important role in cell selection as well as answer
extraction. Pre-trained language models such as BERT, RoBERTa, and LLMs have
the limitation of max input sequence length. Passage filtering ensures that it
is unlikely to lose information relevant to the questions, while fitting model
input limits. We used the well-trained DistilBert-based model to obtain
question and passage embeddings to rank and filter relevant
passages.222https://huggingface.co/sebastian-hofstaetter/distilbert-dot-
tas_b-b256-msmarco

##  Appendix B Alignment Analysis

Figure 4: Heatmap of question and table-header relevance - Case 1

Here we provide example heatmaps showing the relevance of questions and table
headers. The relevance is in the [0,1] range, where the higher relevance
between words from questions and column headers is shown in the warmer colors
and vice versa. Figure 4 shows that the column headers "athlete" and "place"
have more relevance to the question, which helps TACR identify which columns
contain potential gold cells. In Figure 5, the words "player with second most
national football league" from the question have more relevance to columns,
which help TACR learn which parts of the question better use to retrieve gold
cells.

##  Appendix C Implementation Details of Cell Selection and Alignment

TACR is implemented using Pytorch version 1.13 and the Huggingface
transformers Wolf et al. (2020) library. We trained TACR using two NVIDIA
A6000 GPUs. The cell selection and table–question-alignment modules are
trained for four epochs and we selected the best model based on the dev fold
performance. AdamW is used as optimizer algorithm with a learning rate of
5×10-5 and a batch size of 32. We set the per-GPU train batch size to 16 while
training the span-based QA model. Final answers are evaluated using EM and F1
scores. We also automatically iterated through increments of 0.1 in the range
[0, 1] to select the best $\sigma$ to balance the multi-task training.

##### Hyper-parameter Details:

We tune hyper-parameters based on the loss on the development set and use the
following range of values for selecting the best hyper-parameters:
• Batch size: [8, 16, 32, 64]
• Learning rate: [1e-3, 1e-4, 1e-5, 1e-6, 3e-3, 3e-4, 3e-5, 3e-6, 5e-3, 5e-4,
5e-5, 5e-6]
• $\sigma$ : [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]

Figure 5: Heatmap of question and table header relevance - Case 2


# Enhancing Label Sharing Efficiency in Complementary-Label Learning with
Label Augmentation

Wei-I Lin<EMAIL_ADDRESS>National Taiwan University  RIKEN  Gang
Niu<EMAIL_ADDRESS>RIKEN  Hsuan-Tien Lin<EMAIL_ADDRESS>National Taiwan University  Masashi Sugiyama<EMAIL_ADDRESS>RIKEN
The University of Tokyo

###### Abstract

Complementary-label Learning (CLL) is a form of weakly supervised learning
that trains an ordinary classifier using only complementary labels, which are
the classes that certain instances do not belong to. While existing CLL
studies typically use novel loss functions or training techniques to solve
this problem, few studies focus on how complementary labels collectively
provide information to train the ordinary classifier. In this paper, we fill
the gap by analyzing the implicit sharing of complementary labels on nearby
instances during training. Our analysis reveals that the efficiency of
implicit label sharing is closely related to the performance of existing CLL
models. Based on this analysis, we propose a novel technique that enhances the
sharing efficiency via complementary-label augmentation, which explicitly
propagates additional complementary labels to each instance. We carefully
design the augmentation process to enrich the data with new and accurate
complementary labels, which provide CLL models with fresh and valuable
information to enhance the sharing efficiency. We then verify our proposed
technique by conducting thorough experiments on both synthetic and real-world
datasets. Our results confirm that complementary-label augmentation can
systematically improve empirical performance over state-of-the-art CLL models.

##  1 Introduction

Ordinary supervised learning relies on labeled data to train a classifier.
However, obtaining high-quality labels can be expensive or impractical in
real-world scenarios. To overcome the challenge, various types of weakly
supervised learning (WSL) tasks have been studied in recent years which focus
on learning from weaker information than high-quality ordinary labels. Those
includes but not limited to noisy-label learning, partial-label learning, and
positive-unlabeled learning [19, 16]. Studies on WSL can potentially make a
real-world classification task possible when only weak information is
provided.

In this paper, we focus on complementary-label learning (CLL), a very weak
type of WSL [9]. Complementary labels refer to the classes to which a given
instance does not belong to. CLL aims to learn from only complementary labels
during training, while correctly predicting the ordinary labels of unseen
instances. Pioneering CLL researchers believe that studies on CLL could
potentially make multi-class classification more realistic when ordinary
labels are costly to obtain [9, 10]. Although there is no real-world dataset
that demonstrates that CLL is a practical learning paradigm, studies on CLL
still help understand the weakly supervised learning. For instance, Chou et
al. [2] revealed that the unbiased risk estimator, a popular method in weakly
supervised learning, could be misleading due to the large variance in the
gradient. Lin and Lin [14] found that CLL could be reduced to the problem of
probability estimates. Deng et al. [4] utilized the information of pseudo
complementary labels to improve the performance of semi-supervised learning.
These examples demonstrate the significance of fundamental studies on CLL.
inline,color=cyan!20]WL: I’m still unsure whether this revision is better than
the original one. Could HT help check the paragraph again?

Ishida et al. [9] initiated the study of CLL by rewriting the loss functions
for ordinary classification with its unbiased risk estimate (URE) that depends
only on complementary labels. Despite the unbiasedness property, Ishida et al.
[10] and Chou et al. [2] discovered that the URE approach is prone to
overfitting. To conquer the URE’s tendency to overfit, Ishida et al. [10]
argued that the issue arises because URE are not lower bounded. They proposed
two tricks, non-negative correction and gradient ascent, to effectively keep
the URE loss non-negative during training. Chou et al. [2] addressed the issue
by proposing an alternative loss function, the surrogate complementary loss,
that is bounded below by zero. Despite its empirical effectiveness, Chou et
al. [2] did not provide theoretical guarantees on the surrogate complementary
loss. To fill the gap, Gao and Zhang [6] modeled the posterior distribution of
complementary labels, leading to a non-negative loss function, and proved the
statistical consistency of the estimator. Liu et al. [15] proposed the order-
preserving loss, enabling training from a family of loss functions on the CLL
problem with statistical consistency guarantees while preventing the
overfitting issue. The analysis or the benchmark experiments of the methods
mentioned above, however, rely on the assumption that the complementary labels
are generated uniformly. To accommodate biased complementary-label generation,
Yu et al. [17] proposed a forward-correction loss that directly uses the
transition matrix to model the non-uniform generation. This allows learning
from CLs with biased generation.

In this paper, we first find that the success of the loss-based methods for
CLL relies on the _implicit_ shares of complementary labels through the
smoothness of neural networks. Specifically, we observe a strong correlation
between the efficiency of the implicit label sharing and the model
performance. Based on the result, we propose a novel technique that explicitly
shares the complementary labels between neighboring instances. The proposed
technique provides two advantages. First, it is compatible with most previous
approaches on CLL. As the proposed complementary-label augmentation generates
a soft complementary label for each instance, it becomes compatible with any
CLL algorithm that can take soft complementary labels as input. Second, the
compatibility suggests that the proposed method has the potential to provide
conceptually orthogonal benefits to the existing methods. We confirm through
the experiments on the real-world and synthetic complementary datasets that
the proposed complementary-label augmentation does enhance the existing CLL
algorithms. Our contribution can be summarized as follows.

  1. 1.

We proposed _complementary-label augmentation_ , a technique that explicitly
shares the complementary labels between neighboring instances before training.
In addition, the method is compatible with the existing CLL algorithms and can
provide conceptually orthogonal benefits to them.

  2. 2.

The proposed method is based on our empirical observation that (a) the success
of the previous loss-based CLL algorithms can be attributed to the implicit
shares of the labeling information between data instances, (b) a strong
relationship between the implicit label sharing efficiency and model
performance, and (c) explicitly sharing the complementary labels can enhance
the sharing efficiency, leading to improved classification accuracy.

  3. 3.

Extensive experiments on both real-world and synthetic complementary datasets
confirm that the proposed method improves the existing loss-based CLL
algorithms.

##  2 Problem Setting

In this section, we first introduce the problem of Complementary-Label
Learning (CLL) in Section 2.1, and then discuss some common assumptions on how
the complementary labels are generated in Section 2.2.

###  2.1 Complementary-Label Learning

CLL is a weakly-supervised learning problem on multi-class classification.
Typical multi-class classification assumes that the feature vector $x_{i}$’s
and the corresponding labels $y_{i}$’s in the training dataset
$D=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ are i.i.d. sampled from an unknown
distribution. In CLL, $D$ is not accessible to the learning algorithm.
Instead, a complementary dataset $\bar{D}=\\{(x_{i},\bar{y}_{i})\\}_{i=1}^{N}$
is provided to the learner, where $\bar{y}_{i}$ denotes a complementary label,
a class to which the instance $x_{i}$ does not belong. The goal of the
complementary learning algorithm is to find a classifier $f$ that can predict
unseen instances correctly. Typically, classifier $f$ is implemented by a
decision function $g:\mathbb{R}^{d}\to\mathbb{R}^{K}$ and taking argmax on
$g$, i.e., $f(x)=\operatorname*{arg\,max}_{k\in[K]}g(x)_{k}$, where $g(x)_{k}$
denote the $k$-th element of $g(x)$ and $[K]=\\{1,\dotsc,K\\}$ denote the set
of labels.

###  2.2 Generation of Complementary Labels

In the CLL literature, some assumptions on the generation of complementary
labels (CL) are made. The most simple one is called _uniform generation_.
Firstly proposed in the pioneering work [9], it assumes that each
complementary label $\bar{y}_{i}$ is independently and uniformly selected from
all the labels except the correct one. This assumption is also utilized in
some subsequent works [10, 2].

A further generalization to the uniform case is called class-conditional
assumption. It assumes that the generation process of the CLs depends only on
their underlying ordinary labels, i.e., there is $T_{ij}=P(\bar{y}=j\mid y=i)$
for each ordinary label $i$ and complementary label $j$. When
$T_{ij}=\tfrac{1}{K-1}$ for each $i\neq j$, this falls back to the uniform
generation. CLL under such assumption is further analyzed in [17]. This type
of generation is also called _biased generation_ when $T_{ij}$ is not always
$\frac{1}{K-1}$ whenever $i\neq j$ to distinguish it from the uniform one. The
generation process mentioned above is noiseless, meaning there are no CLs that
actually belong to the ordinary class. In the noiseless case, $T_{ii}=0$ holds
for each $i\in[K]$, whereas in noisy CLL [11], the diagonal elements of the
transition matrix $T_{ii}$ are a small positive number.

In our work, the augmented CLs using the proposed method are not generated
with respect to the class-conditional assumption. Nevertheless, we will show
in the experimental section that the proposed method still improves the
learning algorithms that rely on them.

##  3 Proposed Method

In this section, we first establish the relationship between the implicit
label sharing and model performance for the CLL algorithms in Section 3.1.
Then, we demonstrate that the implicit sharing efficiency could be enhanced by
explicitly sharing the complementary labels through the illustrative
experiments in Section 3.2. Finally, we describe the proposed _label
augmentation_ , a practical way to explicitly share the complementary labels,
and discuss some crucial components when performing label augmentation in
Section 3.3.

###  3.1 Implicit Label Sharing and Model Performance

#### Implicit Label Sharing

We first take a closer look at the training process of the CLL algorithms. Let
us consider a $K$-class CLL problem with a single complementary label per
instance. Intuitively, if a model is able to recognize only one complementary
label per instance, then the accuracy for the model is at best $\frac{1}{K-1}$
by randomly guessing from the remaining labels. However, previous CLL methods
can attain much higher accuracies than $\frac{1}{K-1}$ [9, 10, 2, 6, 14, 15].
That leads us to conjecture that one of the mechanisms behind the current CLL
algorithms is the implicit sharing of the complementary labels through the
smoothness of the neural networks. Intuitively, if two instances are near in
the feature space learned by the neural network, then they will have similar
probability outputs. This smoothness can potentially let the complementary
labels be shared implicitly to their neighbors in the feature space.

To verify the conjecture, we performed a toy experiment. First, we divided the
labels into three types: (a) Seen complementary labels, which are the labels
provided in the complementary dataset (b) Ordinary labels, and (c) Unseen
complementary labels, which are the remaining labels. These labels are the
complementary labels that are not provided to the learning algorithms. Then,
we investigated how much confidence the model allocates to the seen and unseen
complementary labels during training. Specifically, for a model $f$ with a
probabilistic output, we checked (a) $f_{\bar{y}}(x)$ for seen complementary
labels and (b)
$\frac{1}{K-2}\sum_{y^{\prime}\notin\\{y,\bar{y}\\}}f_{y^{\prime}}(x)$ for
unseen complementary labels. We trained the models with the SCL-NL loss
function [2] and reported the results in Figure 1. Other experimental details
are left in Appendix A.1.

We drew the following observations from Figure 1. First, the blue lines,
indicating the mean confidence on the given complementary labels, are
minimized to zero in all the datasets. This implies that the learning
algorithm is able to memorize and fit the given complementary labels
perfectly. Second, the green lines, indicating the mean confidence on the
unseen complementary labels, become smaller but do not reach zero in all the
datasets. This phenomenon suggests that somehow the learning algorithm
implicitly shares the information of the given complementary labels to other
data instances; otherwise, the confidence on the unseen complementary labels
will remain unchanged during the whole training process.

Figure 1:  Comparison of the complementary label confidence during training
with the original complementary datasets. The black horizontal lines indicate
the zero confidence. The colored numbers indicate the corresponding
confidences in the last epoch.

Figure 2:  Relationship between the implicit sharing efficiency and model
performance. Each dot represents a result with certain dataset size and model
architecture. Solid markers ($\bullet/\filleddiamond$) refer to the training
accuracy while empty markers ($\circ/\diamond$) refer to the testing accuracy.
Circles ($\bullet/\circ$) and diamonds ($\filleddiamond/\diamond$) refer to
the experiments with the AdamW and the SGD optimizers, respetively.

#### Relationship between Implicit Label Sharing and Performance

Now that we confirmed that the implicit sharing occurs during the training
process of CLL algorithms, we wonder whether the _efficiency_ of the implicit
sharing is related to the model performance. To clarify their relationship, we
first define the implicit sharing efficiency as follows:

$\text{Implicit sharing
efficiency}=1-\frac{1}{N}\sum_{i=1}^{N}\frac{K-1}{K-2}\sum_{\bar{y}^{\prime}\notin\\{y_{i},\bar{y}_{i}\\}}f_{\bar{y}^{\prime}}(x_{i}).$

This metric measures the magnitude of the reduction in the model’s confidence
on the unseen CLs. If the implicit sharing helps identify all the
complementary labels, then $f_{\bar{y}^{\prime}}(x_{i})$ will become zero,
making the implicit sharing efficiency becomes one. If there is no implicit
sharing between the instances, then $f_{\bar{y}^{\prime}}(x_{i})$ will become
$\frac{1}{K-1}$ on average. In this case, implicit sharing efficiency becomes
zero. For instance, in the MNIST experiment in Figure 1, if there is no
implicit label sharing, the mean confidence on unseen CLs is $1/9$. We observe
that empirically the mean confidence on unseen CLs after training is actually
$0.0073$, suggesting that the mean confidence on unseen CLs reduce by
$1-0.0073/\tfrac{1}{9}$, which is 93.43%. Hence, the implicit sharing
efficiency is 93.43% in this case.

To vary the implicit sharing efficiency, we performed the same experiment with
different dataset sizes, model architectures, and optimizers. We reported the
relationship between the implicit sharing efficiency and the model performance
in Figure 2

As we can observe from the figure, there is a near-linear relationship between
the implicit sharing efficiency and the model’s training accuracy. This
relationship is strong and independent of the network architectures, dataset
size, and optimizers. The higher the implicit sharing is, the higher the
model’s training accuracy is. The improved training accuracy indicates that
the model becomes better at recognizing the true labels in the training
dataset, leading to better testing accuracy. The result highlights the
importance of improving the implicit sharing efficiency when designing
algorithms for CLL. We also performed experiments with other CLL algorithms
and reported the results in Appendix B.1. This relationship also holds for
other CLL algorithms.

###  3.2 Illustrative Experiments on Explicit Label Sharing

Figure 3:  Comparison of the complementary label confidence during training
with the explicit shares of complementary labels.  Table 1:  The performance
(in %) and noise rate (in %) on the illustrative toy experiments with
different datasets and with different settings: original, or with explicit
shares. The numbers before the arrow is from the original setting whereas the
numbers after the arrow are from the setting with explicit shares. (original
$\Rightarrow$ with explicit shares)

Dataset | Training Accuracy | Testing Accuracy | Neighboring Noise Rate
---|---|---|---
MNIST |  94.24 $\pm$ 0.09 $\Rightarrow$ 98.32 $\pm$ 0.06 |  94.34 $\pm$ 0.21 $\Rightarrow$ 97.26 $\pm$ 0.07 |  0.73 $\pm$ 0.02 $\Rightarrow$ 0.64 $\pm$ 0.02
KMNIST |  92.95 $\pm$ 0.99 $\Rightarrow$ 98.09 $\pm$ 0.17 |  81.63 $\pm$ 0.89 $\Rightarrow$ 91.38 $\pm$ 0.65 |  0.73 $\pm$ 0.08 $\Rightarrow$ 0.28 $\pm$ 0.02
CIFAR10 |  50.07 $\pm$ 1.79 $\Rightarrow$ 86.96 $\pm$ 0.32 |  47.93 $\pm$ 1.90 $\Rightarrow$ 78.07 $\pm$ 1.68 |  4.51 $\pm$ 0.20 $\Rightarrow$ 1.21 $\pm$ 0.13

#### Explicit Complementary Label Sharing

Although the previous CLL algorithms are able to implicitly share
complementary labels, there is still room for improvement in the sharing
efficiency. To analyze why the previous CLL algorithms could not attain
perfect implicit label sharing, we inspected the learned representation space
at the end of training. To be specific, we checked the noise rate of the
complementary labels from the neighboring 128 instances on the learned
representation space. A complementary label from the neighboring instances is
considered noisy if it is actually the ordinary label. The results are
reported in Table 1. As we can see, the complementary labels from the
neighboring instances are not always correct. The phenomenon of the incorrect
label sharing may explain why the implicit sharing efficiency could not attain
one.

Based on the results, we wonder whether it is possible to learn a better
representation space and thereby improve the implicit sharing efficiency
through _explicitly_ sharing complementary labels. To answer the question, for
each data instance, we first randomly added half of the unseen complementary
labels to the complementary dataset, and then trained a model using both the
original complementary labels and the augmented ones. The rest of the settings
is the same as the previous experiment, and we reported the results in Figure
3 and Table 3.

From the results, we observe that the benefits of explicitly adding more
complementary labels are three-fold. First, the mean confidence on the
augmented complementary labels also goes down to near zero at the end of the
training, suggesting that the learning algorithm is able to memorize more
complementary labels. Second, we see a reduction in the neighboring noise rate
in the learned representation space, indicating that the explicit sharing
helps learn a less noisy representation space. Third, the mean confidence on
the unseen complementary labels is smaller in the experiments with the
explicit sharing than the original experiments without the explicit label
sharing. This phenomenon suggests that the explicit sharing helps improve the
implicit label sharing efficiency. This efficiency improvement leads to
improved accuracies on both the training and testing datasets, as shown in
Table 1.

#### Challenges in Explicitly Sharing Complementary Labels

Although the previous experiments demonstrated the potential benefits of
explicitly adding more complementary labels, it remains challenging in
practice to do so without incurring extra label collection costs. Besides,
obtaining new complementary labels from the existing dataset may introduce
noise to the complementary dataset. How to share informative complementary
labels while keeping the noise rate low becomes the main challenge in the
explicit label sharing.

###  3.3 Complementary-Label Augmentation

Algorithm 1 Complementary-Label Augmentation

1:Input: Complementary Labels $\bar{Y}$, Affinity Matrix $W$, Number of
training samples $N$, Hyperparameters $T$, $\alpha$

2:Output: Augmented Complementary Labels $Z$

3:$Z=\bar{Y}$

4:for $i=1$ to $N$ do

5: $W_{i}=W_{i}/\sum_{j=1}^{N}W_{i,j}$ $\triangleright$ normalizing the
weights

6:end for

7:for $t=1$ to $T$ do

8: $Z=\alpha\bar{Y}+(1-\alpha)WZ$

9:end for

10:for $i=1$ to $N$ do

11: $Z_{i}=Z_{i}/\sum_{j=1}^{N}Z_{i,j}$ $\triangleright$ normalizing the soft
labels

12:end for

Table 2:  A summary of different label augmentation schemes.

Schemes |  Affinity Matrix $W$ |  Round $T$
---|---|---
Traditional | None | 0
Rank-weighted Single Step | $W_{i,j}=\begin{cases*}\tfrac{1}{k}&\text{if $v_{j}$ is $v_{i}$'s $k$th neighbor ($k\leq N_{K}$)}\\\ 0&\text{otherwise}\end{cases*}$ | 1
Rank-weighted Multi Steps | 100
Distance-weighted Single Step | $W_{i,j}=\begin{cases*}\exp(-\gamma\lVert v_{i}-v_{j}\rVert^{2})&\text{if $v_{j}\in\operatorname*{NN}_{N_{K}}(v_{i})$}\\\ 0&\text{otherwise}\end{cases*}$ | 1
Distance-weighted Multi Steps | 100

In this section, we proposed _complementary-label augmentation_ for the
existing loss-based complementary learning algorithms. The main idea of the
complementary-label augmentation is to add new complementary labels from a
data instance’s neighbors. The idea utilizes the smoothness of the
representation space, i.e., if two instances have similar features, then they
are likely to belong to the same class. That implies that the complementary
labels from the neighboring instances can be shared to each other.

To do so, given a feature extractor $v(\cdot)$, let $v_{i}=v(x_{i})$ denote
the feature of the $i$th instance in the complementary dataset, and let
$V=\\{v_{i}\\}_{i=1}^{N}$ denote the collection of extracted features. For
each data instance $x_{i}$ in $\\{x_{i}\\}_{i=1}^{N}$, let $\bar{y}_{i,k}$
denote the complementary label from $v_{i}$’s $k$th nearest neighbor in
$V\backslash\\{v_{i}\\}$.

In a loss-based complementary learning algorithm, there is a loss function
$\ell:[K]\times\mathbb{R}^{K}\to\mathbb{R}$ that takes a complementary label
$\bar{y}_{i}$ and the model’s prediction $g(x_{i})$ as input. The learning
algorithm minimizes the loss function $\ell$ with respect to the complementary
dataset $\bar{D}$, i.e., the learning algorithm optimizes $g$ with respect to
the following empirical risk:

$R(g;\ell)=\frac{1}{N}\sum_{i=1}^{N}\ell(\bar{y}_{i},g(x_{i})).$ (1)

A naive way to utilize the augmented labels is to directly add them to the
loss function as follows:

$R^{\prime}(g;\ell)=\frac{\alpha}{N}\sum_{i=1}^{N}\ell(\bar{y}_{i},g(x_{i}))+\frac{1-\alpha}{N}\sum_{i=1}^{N}\sum_{k=1}^{N_{K}}\ell(\bar{y}_{i,k},g(x_{i})),$
(2)

where $\alpha$ is a hyperparameter that controls how much weight to put on the
augmented labels and $N_{K}$ is the hyperparameter that denotes the number of
neighbors to consider. This simple approach, however, neglects the fact that
the complementary labels augmented from the neighboring instances are noisy.
To overcome the issue, traditional $k$NN methods typically associate a weight
to the neighbors [5]. We follow the idea, and propose to use a weight
$w_{i,k}$ for the pair $(x_{i},\bar{y}_{i,k})$ when training with a
complementary learning algorithm. The loss function then becomes:

$R^{\prime}(g;\ell)=\frac{\alpha}{N}\sum_{i=1}^{N}\ell(\bar{y}_{i},g(x_{i}))+\frac{1-\alpha}{N}\sum_{i=1}^{N}\sum_{k=1}^{N_{K}}w_{i,k}\ell(\bar{y}_{i,k},g(x_{i})).$
(3)

The above loss function can be interpreted as training with respect to soft
complementary labels as follows. Let $z_{i}=\alpha
e_{\bar{y}_{i}}+(1-\alpha)\sum_{i=1}^{N_{k}}w_{i,k}e_{\bar{y}_{i,k}}$, where
$e_{k}$ denotes the one-hot vector of label $k$, then the loss function is
equivalent to

$R_{\text{LA}}(g;\ell)=\frac{1}{N}\sum_{i=1}^{N}\sum_{k=1}^{K}z_{i,k}\ell(k,g(x_{i})).$
(4)

To simplify the notations, we use an $N\times N$ matrix $W$ to denote the
weight, where $W_{i,j}$ is the weight from instance $j$ to instance $i$. In
addition, we define $N\times K$ matrices $Y$ and $Z$ by setting the $i$th row
of $Y$ to the one-hot vector of $\bar{y}_{i}$, i.e., $Y_{i}=e_{\bar{y}_{i}}$
and setting the $i$th row of $Z$ to $z_{i}$, i.e., $Z_{i}=z_{i}$, for each
$i$. Then, the process of complementary-label augmentation can be simplified
to calculating the matrix $Z$ with the following equation:
$Z=\alpha\bar{Y}+(1-\alpha)W\bar{Y}$, then optimize the model $g$ with respect
to the loss function $R_{\text{LA}}$ defined in Equation 4.

#### Weight and multi-step augmentation

Intuitively, the complementary labels from far neighbors are noisier than the
ones from near neighbors. To ensure that the augmented complementary labels
are not dominated by the noisy ones, the weights on the farther neighbors
should be smaller than the weights on the nearer ones. As a result, we
consider two ways to set the affinity matrix $W$:

  1. 1.

Rank-based approach: weight based on the rank of the neighbors. Specifically,
$W_{i,j}=\frac{1}{k}$ if $v_{j}$ is $v_{i}$’s $k$th neighbor with $k\leq
N_{K}$.

  2. 2.

Distance-based approach: weight based on the distance from the neighbors.
Specifically, $W_{i,j}=\exp(-\gamma\lVert v_{i}-v_{j}\rVert^{2})$ if $v_{j}$
is within the $N_{K}$th nearest neighbor of $v_{i}$.

The augmentation process proposed above can be performed multiple times. By
augmenting the labels multiple times, the label information could potentially
be shared to more distant neighbors. We call this technique multi-step label
augmentation. The pseudocode for the label augmentation is presented in
Algorithm 1, where we use $T$ to control the number of times to perform the
complementary-label augmentation. Different affinity matrix $W$ and the number
of augmentation $T$ produce different augmented complementary labels. We
summarized in Table 2 the different schemes to perform the augmentation.

###  3.4 Relation to other methods

Label Propagation [20, 18] is a method in semi-supervised learning that also
leverages the smoothness assumption. The proposed multi-step complementary-
label augmentation shares a similar form to the label propagation method;
however, complementary-label augmentation is different from label propagation
in two aspects. First, label propagation in semi-supervised learning and
complementary-label augmentation propagates different labeling information and
for different goals. The former propagates the _ordinary_ labels to the
unlabeled data with the goal of obtaining pseudo labels for the unlabeled
instances. On the other hand, the latter propagates the _complementary_ labels
to the neighboring instances in order to enrich the complementary labels of
all the instances in the dataset. Second, the two methods are different in
their roles in the training process. Label propagation is typically part of a
training process [8], where the labels and the model parameters are updated in
an alternating manner. In contrast, complementary-label augmentation is a
technique to enrich the labeling information that is independent of the
training process and is applied before the whole training process.

##  4 Experiments

To verify the efficacy of the proposed method, we conducted experiments on
various benchmarks, including some synthetic datasets, where the complementary
labels were generated uniformly, and some real-world datasets, where the
complementary labels were annotated by humans. The synthetic datasets in the
benchmark include CIFAR10 and CIFAR20. Both datasets contain 50,000 training
samples and 10,000 testing samples, while CIFAR10 contains 10 classes and
CIFAR20 contains 20 superclasses from CIFAR100. We consider the setting of a
single complementary label per data instance, where the complementary labels
were generated uniformly. We do not benchmark on CIFAR100 as we found that no
previous CLL algorithms can learn a meaningful classifier in this dataset,
provided only one complementary label per data instance, even with the
proposed label augmentation. The real-world datasets in the benchmark include
CLCIFAR10 and CLCIFAR20, which contain the images in CIFAR10 and CIFAR20,
respectively. Each image in the datasets is annotated with three complementary
labels by different human annotators.

#### Baseline Methods

Four SOTA methods were considered in our experiments: (a) PC [9]: the pairwise
comparison loss, (b) URE-GA [10]: the unbiased risk estimator on cross-entropy
loss with the gradient ascent trick, (c) SCL-NL [2]: the surrogate
complementary loss with the negative log loss, and (d) L-W [6]: the weighted
loss derived from the discriminative modeling of the complementary labels. We
did not include the forward correction method [17] as it is equivalent to SCL-
NL when the transition matrix is uniform. Each baseline method was trained
directly without label augmentation, and trained with four configurations of
label augmentation as in Table 2. Other implementation details, including
hyperparameter selection through a validation process, are left in Appendix
A.2.

Table 3:  Effects of label augmentation applied on different complementary learning algorithms on CIFAR10 and CIFAR20. The mean and standard deviation of the testing accuracies over five random trials are reported. RSS, RMS, DSS and DMS refer to rank-weighted single-step, rank-weighted multi-step, distance-weighted single-step and distance-weighted multi-step, respectively.  | CIFAR10 | CIFAR20 | CLCIFAR10 | CLCIFAR20
---|---|---|---|---
PC |  35.59 $\pm$ 0.44 |  11.01 $\pm$ 1.79 |  40.69 $\pm$ 1.98 |  13.79 $\pm$ 0.38
PC+RSS |  73.50 $\pm$ 0.54 |  34.11 $\pm$ 0.46 |  65.47 $\pm$ 0.61 |  19.30 $\pm$ 2.12
PC+RMS |  83.47 $\pm$ 0.17 |  55.00 $\pm$ 0.26 |  74.83 $\pm$ 0.80 |  23.26 $\pm$ 1.39
PC+DSS |  80.86 $\pm$ 0.25 |  43.38 $\pm$ 0.50 |  72.10 $\pm$ 0.54 |  22.05 $\pm$ 0.44
PC+DMS | 83.90 $\pm$ 0.25 | 57.62 $\pm$ 0.49 | 75.13 $\pm$ 0.49 | 26.43 $\pm$ 2.02
URE-GA |  58.23 $\pm$ 1.45 |  12.03 $\pm$ 0.49 |  23.98 $\pm$ 2.91 |  9.00 $\pm$ 0.38
URE-GA+RSS |  72.72 $\pm$ 1.83 |  23.93 $\pm$ 3.25 | 28.66 $\pm$ 1.17 |  11.52 $\pm$ 0.51
URE-GA+RMS |  73.33 $\pm$ 2.60 |  25.36 $\pm$ 2.12 |  25.03 $\pm$ 1.35 |  12.32 $\pm$ 0.14
URE-GA+DSS |  72.97 $\pm$ 1.89 |  27.13 $\pm$ 2.74 |  25.42 $\pm$ 0.31 |  12.49 $\pm$ 0.53
URE-GA+DMS | 75.06 $\pm$ 3.01 | 29.73 $\pm$ 3.09 |  20.76 $\pm$ 1.66 | 13.19 $\pm$ 0.30
SCL-NL |  73.95 $\pm$ 0.86 |  23.24 $\pm$ 1.54 |  44.12 $\pm$ 1.49 |  8.09 $\pm$ 0.13
SCL-NL+RSS |  85.77 $\pm$ 0.78 |  54.71 $\pm$ 2.05 |  56.52 $\pm$ 0.54 |  14.33 $\pm$ 1.20
SCL-NL+RMS |  88.67 $\pm$ 0.09 |  64.48 $\pm$ 0.58 |  73.30 $\pm$ 2.12 |  19.74 $\pm$ 1.66
SCL-NL+DSS |  87.00 $\pm$ 0.32 |  55.08 $\pm$ 1.51 |  67.86 $\pm$ 1.87 |  17.19 $\pm$ 1.51
SCL-NL+DMS | 88.72 $\pm$ 0.15 | 66.33 $\pm$ 0.42 | 74.87 $\pm$ 2.25 | 24.44 $\pm$ 2.88
L-W |  50.26 $\pm$ 0.37 |  15.64 $\pm$ 2.85 |  38.38 $\pm$ 0.63 |  7.35 $\pm$ 0.80
L-W+RSS |  83.13 $\pm$ 0.22 |  42.35 $\pm$ 2.67 |  54.58 $\pm$ 0.65 |  13.18 $\pm$ 0.90
L-W+RMS |  88.27 $\pm$ 0.24 |  63.28 $\pm$ 0.51 |  73.25 $\pm$ 0.61 |  20.05 $\pm$ 2.49
L-W+DSS |  86.45 $\pm$ 0.25 |  47.43 $\pm$ 1.57 |  67.84 $\pm$ 0.62 |  17.49 $\pm$ 0.69
L-W+DMS | 88.45 $\pm$ 0.24 | 65.68 $\pm$ 0.24 | 74.76 $\pm$ 0.68 | 22.09 $\pm$ 1.86

#### Results and Discussion

The benchmark results are reported in Table 3. As shown in the table,
complementary-label augmentation improved all the baseline methods on all the
datasets. Taking a closer look, we found a general trend that the distance-
based weighting performed better than the rank-based weighting. The reason
could be that the rank-based weighting could not distinguish between a high-
density neighborhood and low-density neighborhood. In low-density region, the
first few neighbors could already be noisy, but rank-based weighting did not
take this into consideration and reduce their weights. In contrast, the
weight-based weighting reduced their weights in this case. On the other hand,
another observation from Table 3 was that the multi-step augmentation
outperformed the single-step augmentation. This echoes our previous conjecture
that multi-step augmentation could lead to better performance by further
propagating the information of complementary labels to more distant instances.

##  5 Ablation and Further Discussions

###  5.1 Effects on the Number of Neighbors

In this subsection, we discuss how the number of neighbors, the hyperparameter
$K$ in Algorithm 1, affects the testing accuracy. To do so, for each baseline
method, we fix the training hyperparameters, including the learning rate and
weight decay, to the best one in Section 4 and vary the number of neighbors
only. The results are reported in Figure 4. From the figure, we first observe
that the best number of neighbors for the multi-step augmentation is smaller
than the best number of neighbors for the single-step augmentation. The
results distinguished the label sharing mechanism between the single-step and
multi-step augmentation. The former propagates the label information to
distant instances by performing augmentation _multiple_ times, whereas the
single-step augmentation propagates the label information to more instances by
_increasing_ the number of neighbors. Hence, the multi-step augmentation
requires less number of neighbors while the single-step augmentation requires
more. Despite the single-step augmentation can be improved by augmenting with
more neighboring instances, we still observe that the multi-step augmentation
outperforms the single-step augmentation if the number of neighbors can be
tuned.

###  5.2 Comparison with Alternative Baselines

Besides the proposed complementary-label augmentation, there are some
alternative ways to utilize the information from the feature space:

  1. 1.

Fine-tuning from a self-supervised model with the loss-based CLL algorithms is
also a way to utilize the feature space of the self-supervised models. Fine-
tuning from a pretrained model can be faster or have better accuracy than
training from scratch for some downstream tasks. It could potentially be
useful for CLL as well.

  2. 2.

Using a $k$NN method to obtain a local estimate of the distribution of the
complementary labels, then decoding the results by predicting the target label
with the least-likely complementary labels. This method follows the intuition
that the least-likely complementary labels should correspond to the most-
likely ordinary labels. It corresponds to the decoding methods proposed by Lin
and Lin [14] when the transition matrix is uniform.

The results are reported in Table 4. As we can see from the table, fine-tuning
from a self-supervised model improved the testing accuracies of the models in
three of the datasets. Nevertheless, label augmentation still improved the
fine-tuning method. This implies that label augmentation can provide an
orthogonal benefit to fine-tuning. On the other hand, as suggested in the
table, $k$NN is a strong baseline for utilizing the information from the self-
supervised models, with superior performance to training from scratch and
fine-tuning. Still, fine-tuning the self-supervised model with label
augmentation outperforms the baseline across all the datasets we consider.

Figure 4:  Comparison of the testing accuracies with different number of neighbors.  Table 4:  Comparison of the testing accuracy compared with two other baselines: (a) Fine-tuned with pretrained self-supervised models, and (b) $k$ nearest neighbor models. In this table, FT indicates fine-tuning from a self-supervised model, and LA refers to training with complementary label augmentation.  | CIFAR10 | CIFAR20 | CLCIFAR10 | CLCIFAR20
---|---|---|---|---
SCL-NL |  73.95 $\pm$ 0.86 |  23.24 $\pm$ 1.54 |  44.12 $\pm$ 1.49 |  8.09 $\pm$ 0.13
SCL-NL+FT |  84.07 $\pm$ 0.16 |  15.31 $\pm$ 2.46 |  53.10 $\pm$ 0.74 |  10.94 $\pm$ 1.59
SCL-NL+FT+LA | 89.21 $\pm$ 0.20 | 66.19 $\pm$ 0.59 | 78.68 $\pm$ 0.50 | 29.36 $\pm$ 1.31
$k$NN |  86.77 $\pm$ 0.14 |  53.12 $\pm$ 0.80 |  75.65 $\pm$ 0.41 |  27.59 $\pm$ 1.12

##  6 Conclusion and Future Works

In this paper, we first observe a strong linear correlation between the
implicit sharing efficiency and the performance of the CLL algorithms. This
relationship is strong in the sense that it appears for different network
architectures, datasets, optimizers, and loss functions. Based on the
observation, we propose _complementary-label augmentation_ , a technique that
explicitly shares the labeling information between neighboring instances. The
proposed method is compatible with and can be synergistic with the previous
CLL algorithms. Empirical experiments confirm that the proposed method
enhances the implicit sharing efficiency and leads to improved performance for
previous CLL algorithms on both synthetic and real-world datasets.

The near-linear relationship between the implicit sharing efficiency and the
training accuracy leads us to conjecture that there is a theoretical
foundation that bridges these two properties. On the other hand, the proposed
methods are limited by the fact that it improves the sharing efficiency in an
indirect way. We leave it to future work to discover the theoretical
connection between the implicit sharing efficiency and the training accuracy,
and a way to directly enhance the sharing efficiency.

## References

  * Chen and He [2021] X. Chen and K. He.  Exploring simple siamese representation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15750–15758, 2021.
  * Chou et al. [2020] Y.-T. Chou, G. Niu, H.-T. Lin, and M. Sugiyama.  Unbiased risk estimators can mislead: A case study of learning with complementary labels.  In _International Conference on Machine Learning_ , pages 1929–1938. PMLR, 2020.
  * Clanuwat et al. [2018] T. Clanuwat, M. Bober-Irizar, A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha.  Deep learning for classical japanese literature, 2018.
  * Deng et al. [2022] Q. Deng, Y. Guo, Z. Yang, H. Pan, and J. Chen.  Boosting semi-supervised learning with contrastive complementary labeling.  _arXiv preprint arXiv:2212.06643_ , 2022.
  * Dudani [1976] S. A. Dudani.  The distance-weighted k-nearest-neighbor rule.  _IEEE Transactions on Systems, Man, and Cybernetics_ , (4):325–327, 1976.
  * Gao and Zhang [2021] Y. Gao and M.-L. Zhang.  Discriminative complementary-label learning with weighted loss.  In _International Conference on Machine Learning_ , pages 3587–3597. PMLR, 2021.
  * He et al. [2016] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Iscen et al. [2019] A. Iscen, G. Tolias, Y. Avrithis, and O. Chum.  Label propagation for deep semi-supervised learning.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 5070–5079, 2019.
  * Ishida et al. [2017] T. Ishida, G. Niu, W. Hu, and M. Sugiyama.  Learning from complementary labels.  _Advances in neural information processing systems_ , 30, 2017.
  * Ishida et al. [2019] T. Ishida, G. Niu, A. Menon, and M. Sugiyama.  Complementary-label learning for arbitrary losses and models.  In _International Conference on Machine Learning_ , pages 2971–2980. PMLR, 2019.
  * Ishiguro et al. [2022] H. Ishiguro, T. Ishida, and M. Sugiyama.  Learning from noisy complementary labels with robust loss functions.  _IEICE TRANSACTIONS on Information and Systems_ , 105(2):364–376, 2022.
  * Krizhevsky et al. [2009] A. Krizhevsky, G. Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * LeCun et al. [1998] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lin and Lin [2023] W.-I. Lin and H.-T. Lin.  Reduction from complementary-label learning to probability estimates.  In _Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)_ , May 2023.
  * Liu et al. [2023] S. Liu, Y. Cao, Q. Zhang, L. Feng, and B. An.  Consistent complementary-label learning via order-preserving losses.  In _International Conference on Artificial Intelligence and Statistics_ , pages 8734–8748. PMLR, 2023.
  * Sugiyama et al. [2022] M. Sugiyama, H. Bao, T. Ishida, N. Lu, T. Sakai, and G. Niu.  _Machine learning from weak supervision: An empirical risk minimization approach_.  MIT Press, 2022.
  * Yu et al. [2018] X. Yu, T. Liu, M. Gong, and D. Tao.  Learning with biased complementary labels.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 68–83, 2018.
  * Zhou et al. [2003] D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schölkopf.  Learning with local and global consistency.  _Advances in neural information processing systems_ , 16, 2003.
  * Zhou [2018] Z.-H. Zhou.  A brief introduction to weakly supervised learning.  _National science review_ , 5(1):44–53, 2018\.
  * Zhu and Ghahramani [2002] X. Zhu and Z. Ghahramani.  Learning from labeled and unlabeled data with label propagation.  2002\.

##  Appendix A Implementation Details of the Experiments

###  A.1 Implementation Details of the experiments in Section 3

#### Implicit Label Sharing Experiment

In this experiment, we trained the model with SCL-NL [2] loss using the AdamW
optimizer with learning rate of $10^{-3}$, weight decay of $10^{-5}$, and
batch size of 256 for 100 epochs. No learning rate scheduling and data
augmentation was applied during the training. Three datasets, MNIST[13],
KuzushijiMNIST[3], and CIFAR10[12] were utilized in this experiment. The
network architectures were a one-layer MLP (784-256-10) for MNIST, LeNet [13]
for Kuzushiji-MNIST, and ResNet-18 [7] for CIFAR10. Each trial was repeated
five times, and the mean results with standard deviations are reported. All
the experiments in Section 3 were run with NVIDIA RTX 2070.

#### Implicit Label Sharing Experiment with varying parameters

In this experiment, all the settings are the same as the above except

  1. 1.

Model architectures: we also performed the experiments using one-layer MLP for
Kuzushiji-MNIST and LeNet for CIFAR10.

  2. 2.

Dataset sizes: we also performed the experiments using only a subset of the
dataset. For MNIST and Kuzushiji-MNIST, we additionally trained with size of
40000, 20000, 10000, 8000, 6000, 4000, 2000, 1000, 800, and 600 examples. For
CIFAR10, we additionally trained with size of 25000, 10000, 5000, 2500, and
1000 examples.

  3. 3.

Optimizers: we also performed the experiments using the SGD optimizer with a
momentum of $0.9$, learning rate of $10^{-1}$ and weight decay of $10^{-4}$.

Each trial was repeated five times, and the mean results are reported. Varying
these different training settings produces the figures in Figure 2.

#### Explicit Label Sharing Experiment

The training settings in this experiment are the same as the settings in the
implicit label sharing experiment.

###  A.2 Implementation Details of the Experiments in Section 4

We used ResNet-18 as the base model, and trained the SimSiam [1] as the
feature extractor to find the neighboring instances. For SimSiam, we followed
the suggested training setting and model architecture (ResNet-18) in the
paper. CLL algorithms were trained using the AdamW optimizer for 200 epochs.
The learning rate was warmed up linearly for the first five epochs, then
decayed with cosine annealling for the rest epochs. The number of neighbors in
the proposed label augmentation was fixed to 64, and we set the parameter
$\alpha$ to 0.1. We used standard data augmentation techniques,
RandomHorizontalFlip, RandomCrop, and normalization for all training images.
10% of the data instances in the training datasets were left out as the
validation datasets. The learning rate was selected from
$\\{10^{-3},10^{-4},10^{-5}\\}$ while the weight decay was selected from
$\\{10^{-4},10^{-5}\\}$ using URE on the 0-1 loss on the validation dataset.
It is worth mentioning that the validation dataset consists of only
complementary labels. This protocol is different from some previous works,
where the validation dataset consists of ordinary labels. We argue that our
protocol is more practical because ordinary labels may not be obtainable or
costly to collect in real world.

For the experiments in Section 5.2, the training settings were the same as
above, except that the number of epochs was reduced to 50. The hyperparameter
$k$ for the $k$NN was selected from $\\{4,8,16,32,64,128,256,512,1024\\}$.

We completed five trials for each experiment with NVIDIA V100.

##  Appendix B Additional Results of the Experiments

###  B.1 Additional Results of the Experiments in Section 3

In this section, we repeated the experiments with two additional CLL
algorithms: (a) PC [9]: the pairwise comparison loss, (b) L-W [6]: the
weighted loss derived from the discriminative modeling of the complementary
labels. The results between the implicit sharing efficiency and model
performance are reported in Figure 5. As we can observe, the positive
correlation between those two properties still hold even if we train the model
with different methods.

###  B.2 Additional Results of the Experiments in Section 4

In the standard benchmark in Section 4, we assessed the models’ performance
using the model in the last epoch. As the CLL algorithms are known to have a
tendency to overfit, some previous studies selected the best epoch using the
validation dataset instead of selecting the last epoch. For instance, Ishida
et al. [10] selected the best epoch on the validation dataset while Yu et al.
[17] employed early-stopping. For completeness, we report the results on the
standard benchmark where we selected the model based on the best epoch on the
validation dataset using the URE of the 0-1 loss. The results are reported in
Table 5. As we can observe, the proposed label augmentation still improves the
previous methods in this training setting, demonstrating the broad
applicability of the proposed method.

Figure 5:  Relationship between the implicit sharing efficiency and model
performance. Each dot represents a result of the last epoch in training with a
certain CLL algorithm. Specifically, solid markers ($\bullet$) refer to the
training accuracy while empty markers ($\circ$) refer to the testing accuracy.
Table 5:  Effects of label augmentation applied on different complementary
learning algorithms on CIFAR10 and CIFAR20, where the best epoch selected
using the validation dataset is evaluated. The mean and standard deviation of
the testing accuracies over five random trials are reported.
| CIFAR10 | CIFAR20 | CLCIFAR10 | CLCIFAR20
---|---|---|---|---
PC |  40.11 $\pm$ 2.36 |  12.89 $\pm$ 1.82 |  44.32 $\pm$ 1.69 |  15.20 $\pm$ 1.54
PC+RSS |  72.52 $\pm$ 0.80 |  33.53 $\pm$ 0.73 |  66.12 $\pm$ 1.48 |  26.25 $\pm$ 1.13
PC+RMS |  83.27 $\pm$ 0.52 |  53.29 $\pm$ 1.14 |  73.52 $\pm$ 1.35 |  26.15 $\pm$ 2.40
PC+DSS |  80.99 $\pm$ 0.27 |  43.74 $\pm$ 0.46 |  72.67 $\pm$ 0.77 |  26.80 $\pm$ 3.12
PC+DMS | 83.61 $\pm$ 0.59 | 55.59 $\pm$ 1.58 | 74.09 $\pm$ 1.59 | 30.94 $\pm$ 1.89
URE-GA |  56.88 $\pm$ 1.59 |  11.41 $\pm$ 1.47 |  25.84 $\pm$ 1.12 |  9.12 $\pm$ 0.39
URE-GA+RSS |  72.58 $\pm$ 1.42 |  23.81 $\pm$ 3.18 | 28.36 $\pm$ 1.00 |  11.37 $\pm$ 0.47
URE-GA+RMS |  72.91 $\pm$ 2.59 |  24.43 $\pm$ 1.42 |  24.52 $\pm$ 2.64 |  12.11 $\pm$ 0.43
URE-GA+DSS |  73.32 $\pm$ 1.75 |  25.64 $\pm$ 2.69 |  26.35 $\pm$ 1.30 |  12.50 $\pm$ 0.47
URE-GA+DMS | 75.40 $\pm$ 2.39 | 27.64 $\pm$ 3.43 |  20.44 $\pm$ 1.66 | 13.01 $\pm$ 0.49
SCL-NL |  72.80 $\pm$ 1.21 |  22.37 $\pm$ 1.77 |  48.38 $\pm$ 2.18 |  8.08 $\pm$ 0.51
SCL-NL+RSS |  86.35 $\pm$ 0.12 |  56.70 $\pm$ 0.82 |  65.53 $\pm$ 1.59 |  13.09 $\pm$ 1.33
SCL-NL+RMS |  88.35 $\pm$ 0.22 | 63.87 $\pm$ 1.09 |  74.17 $\pm$ 2.66 |  19.84 $\pm$ 1.16
SCL-NL+DSS |  86.91 $\pm$ 0.27 |  56.79 $\pm$ 1.35 |  70.11 $\pm$ 1.55 |  18.58 $\pm$ 1.92
SCL-NL+DMS | 88.49 $\pm$ 0.37 |  63.85 $\pm$ 2.73 | 77.80 $\pm$ 1.87 | 23.49 $\pm$ 1.93
L-W |  64.82 $\pm$ 0.39 |  16.20 $\pm$ 1.69 |  47.22 $\pm$ 2.09 |  7.98 $\pm$ 0.41
L-W+RSS |  85.46 $\pm$ 0.37 |  50.11 $\pm$ 0.59 |  65.26 $\pm$ 1.58 |  15.01 $\pm$ 1.09
L-W+RMS |  87.70 $\pm$ 0.18 |  62.76 $\pm$ 0.69 |  73.49 $\pm$ 2.58 |  19.52 $\pm$ 2.52
L-W+DSS |  86.44 $\pm$ 0.24 |  54.50 $\pm$ 1.23 |  71.48 $\pm$ 2.06 |  18.92 $\pm$ 1.10
L-W+DMS | 87.83 $\pm$ 0.47 | 65.08 $\pm$ 0.70 | 77.46 $\pm$ 1.46 | 23.52 $\pm$ 1.42