# On the exponent of cyclic codes

A. K. Bhagat, R. Sarma

###### Abstract

We propose an algorithm to find a lower bound for the number of cyclic codes
over any finite field with any given exponent. Besides, we give a formula to
find the exponent of BCH codes.

Department of Mathematics,
Indian Institute of Technology Delhi,
Hauz Khas, New Delhi-110016, India1.

11footnotetext: E-mail addresses<EMAIL_ADDRESS>(Anuj Kumar
Bhagat<EMAIL_ADDRESS>
(Ritumoni Sarma).

MSC 2010 : 94B05, 94B25, 94B60,11T71.
Keywords: cyclic code; BCH code; exponent.

##  1 Introduction

For a prime power $q$, denote by $\mathbb{F}_{q}$ the field that has exactly
$q$ elements. Every finite field $\mathbb{F}_{q}$ has at least one element
$\beta$ that satisfies $\mathbb{F}_{q}\setminus\\{0\\}=<\beta>$; such elements
are called _primitive elements_ of $\mathbb{F}_{q}$. Let gcd$(n,q)=1$. Then
$C_{i}:=\\{(i.q^{j}(\text{mod}\
n)\in\mathbb{Z}_{n}:j=\mathbb{N}\cup\\{0\\}\\}$ is called the _cyclotomic
cosets_ of $q$ in $\mathbb{Z}_{n}$ containing $i$. A _minimal polynomial_ of
$\beta\in\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$ is a non-zero monic
polynomial $f(x)\in\mathbb{F}_{q}[x]$ of least degree such that $f(\beta)=0$.
The minimal polynomial of an element of $\mathbb{F}_{q^{m}}$ over
$\mathbb{F}_{q}$ is irreducible and is unique. The following theorem
determines the minimal polynomial of any element in a finite field:

######  Theorem 1.1.

[3] Let $\beta\in\mathbb{F}_{q^{m}}$ be a primitive element. If $C_{i}$ is the
cyclotomic coset of $q$ in $\mathbb{Z}_{q^{m}-1}$ containing $i$. Then
$M^{(i)}(x):=\prod_{j\in C_{i}}(x-\beta^{j})$ is the minimal polynomial of
$\beta^{i}$ over $\mathbb{F}_{q}$.

######  Corollary 1.2.

[3] Let $\beta\in\mathbb{F}_{q^{m}}$ be a primitive element. Denote by
$M^{(s)}(x)$ the minimal polynomial of $\beta^{s}$ over $\mathbb{F}_{q}$. Then
$M^{(s)}(x)=M^{(t)}(x)$ iff $s$ and $t$ are in the same cyclotomic coset of
$q$ in $\mathbb{Z}_{q^{m}-1}$.

######  Lemma 1.3.

[2] Let $g(x)\in\mathbb{F}_{q}[x]$ be a polynomial of positive degree $m$ such
that $x\nmid g(x)$. Then for some integer $e$ with $1\leq e\leq q^{m}-1$,
$g(x)$ divides $x^{e}-1$.

Lemma 1.3 motivates the following definition.

######  Definition 1.4.

[2] Let $g(x)\in\mathbb{F}_{q}[x]\setminus\\{0\\}$. If $x\nmid g(x)$, then the
least natural number $e$ such that $g(x)$ divides $x^{e}-1$ is called the
_order_ of $g$ and it is denoted by ord$(g)$ or ord$(g(x))$. If
$g(x)=x^{r}f(x)$ for some $r\in\mathbb{N}$ and $f\in\mathbb{F}_{q}[x]$ with
$x\nmid f(x)$, then ord$(g)$ is ord$(f)$.

The following theorems give some properties of the order of irreducible
polynomials, their products and their powers:

######  Theorem 1.5.

[2] Let $g(x)\in\mathbb{F}_{q}[x]$ be an irreducible polynomial over
$\mathbb{F}_{q}$ of degree $m$ such that $x\nmid g(x)$. Then ord$(g)$ is equal
to the order of any root of $g$ in the multiplicative group
$\mathbb{F}_{q^{m}}^{*}$.

######  Theorem 1.6.

[2] Suppose $d$ is the order of $q$ in $\mathbb{Z}_{e}^{*}$. Then the degree
of an irreducible polynomial in $\mathbb{F}_{q}[x]$ of order $e$ must be equal
to $d$.

######  Theorem 1.7.

[2] Let char$(\mathbb{F}_{q})=p$. Suppose $g(x)\in\mathbb{F}_{q}[x]$ is
irreducible such that $x|g(x)$ and ord$(g)=e$. Then ord$(g^{k})=ep^{t}$, where
$t$ is the least positive integer with $p^{t}\geq k$.

######  Theorem 1.8.

[2] Let $g_{1},g_{2},...,g_{k}\in\mathbb{F}_{q}[x]$ be pairwise co-prime non-
zero polynomials. Then

$\text{ord}(g_{1}g_{2}...g_{k})=\text{lcm}(\text{ord}(g_{1}),\text{ord}(g_{2}),...,\text{ord}(g_{k})).$

In [1], the order of the generator polynomial of a cyclic code $C$ is termed
as the exponent of $C$, denoted by exp$(C)$. The authors posed the problem of
determining bounds for the number of cyclic codes of given exponent and
finding the exponent of BCH and Reed-Solomon codes.

The remaining sections are as follows. In Section 2, we give bounds for the
number of cyclic codes of given exponent. In Section 3, we determine a formula
to find the exponent of BCH code and RS code. In Section 4, we conclude the
article.

##  2 Cyclic codes of given exponent

Suppose $g(x)$ is a polynomial over $\mathbb{F}_{q}[x]$. If $n$ is the length
of a cyclic code $C$ that $g(x)$ generates, then $g(x)\mid x^{n}-1$. Note that
there are infinitely many choices of $n$. The exponent of such a code depends
upon the choice of $g(x)$ and it divides $n$. Conversely, each monic divisor
$g(x)$ of $x^{n}-1\in\mathbb{F}_{q}[x]$ generates a unique $[n,k]_{q}$ cyclic
code with $k=n-deg(g(x))$.
Thus, if $e\in\mathbb{N}$ does not divide $n$, then no cyclic code of length
$n$ can have exponent $e$. Suppose $e,n\in\mathbb{N}$ are such that $e|n$.
Then cyclic codes of exponent $e$ and length $n$ is generated by a divisor of
$x^{e}-1$ of order $e$. Note that not every divisor of $x^{e}-1$ is of order
$e$, for instance, the divisor $(x+1)$ of $x^{2}-1\in\mathbb{F}_{2}[x]$ has
order $1$. Thus, if $e$ divides $n$, then to find the number of cyclic codes
of exponent $e$ and length $n$, it is sufficient to consider the factorization
of $x^{e}-1$ over $\mathbb{F}_{q}$. From this discussion, the following remark
is clear.

######  Remark 1.

The number of cyclic codes of exponent $e$ and length $n$ where $e\mid n$, is
independent of choice of $n$.

Throughout the section, we assume that char$(\mathbb{F}_{q})=p$ and $e\mid n$.
Suppose $x^{e}-1=\prod_{i=1}^{r}p_{i}(x)^{f_{i}}$ is the prime factorization
in $\mathbb{F}_{q}[x]$. Now, with this notation, the obvious upper bound for
the number of cyclic codes of exponent $e$ is $\prod_{i=1}^{r}(f_{i}+1)$.

######  Lemma 2.1.

Let $x^{e}-1=\prod_{i=1}^{r}p_{i}(x)^{f_{i}}$ where each
$p_{i}(x)\in\mathbb{F}_{q}[x]$ is irreducible.. If $f_{i}>1$, then
ord$(p_{i}(x))<e$.

Proof. Suppose ord$(p_{i}(x))=e$. Then by theorem 1.7,
ord$(p_{i}(x)^{f_{i}})=ep^{t}$, where $t$ is the smallest natural number
satisfying $p^{t}\geq f_{i}$.
But ord$(p_{i}(x)^{f_{i}})\leq e$ as $p_{i}(x)^{f_{i}}$ divides $x^{e}-1$.
Thus we have,

$\displaystyle ep^{t}$ $\displaystyle\leq e$ $\displaystyle\implies p^{t}$
$\displaystyle\leq 1$ $\displaystyle\implies f_{i}$ $\displaystyle\leq 1$

which contradicts the hypothesis. $\square$

######  Lemma 2.2.

Let $x^{e}-1=\prod_{i=1}^{r}p_{i}(x)^{f_{i}}$ where each
$p_{i}(x)\in\mathbb{F}_{q}[x]$ is irreducible. Suppose $d$ is the order of $q$
in $\mathbb{Z}_{e}^{*}$ and $f_{i}=1$. Then ord$(p_{i}(x))=e$
$\Longleftrightarrow$ deg$(p_{i}(x))=d$.

Proof. Follows directly from Theorem 1.6 . $\square$

######  Lemma 2.3.

Let $x^{e}-1=\prod_{i=1}^{r}p_{i}(x)^{f_{i}}$ where each
$p_{i}(x)\in\mathbb{F}_{q}[x]$ is irreducible. Suppose $f_{i}>1$. Then for
some $a>1,$ ord$(p_{i}(x)^{a})=e$ $\Longleftrightarrow$ $p$ is the only prime
divisor of $\frac{e}{\text{ord}(p_{i}(x))}$. Furthermore, if $p$ is the only
prime divisor of $\frac{e}{\text{ord}(p_{i}(x))}$, then ord$(p_{i}(x)^{a})=e$
whenever $p^{t-1}<a\leq p^{t}$, where
$t=\log_{p}{\frac{e}{\text{ord}(p_{i}(x))}}$.

Proof. By Lemma 2.1, ord$(p_{i}(x))<e$. So, ord$(p_{i}(x))=d$, where $d\neq e$
and $d\mid e$.
For any $a>1$, we have, $e\geq$ord$(p_{i}(x)^{a})=dp^{t}$ where $t$ is the
smallest natural number satisfying $p^{t}\geq a$.
Suppose ord$(p_{i}(x)^{a})=e$ for some $a>1$. Then $\frac{e}{d}=p^{t}$.
Conversely, suppose $\frac{e}{d}$ is a $p$-power, that is, $\frac{e}{d}=p^{t}$
for some $t\in\mathbb{N}$. Choose $a$ such that $p^{t-1}<a\leq p^{t}$. Then
ord$(p_{i}(x)^{a})=dp^{t}=e$.
This also justifies the second part. $\square$

We now give an algorithm to compute a lower bound for the number of cyclic
codes of exponent $e$.

Algotithm.

Step 1: Factorize $x^{e}-1$ over $\mathbb{F}_{q}$.
Suppose

$x^{e}-1=\prod_{i=1}^{r}p_{i}(x)^{f_{i}}.$

where each $p_{i}(x)$ is irreducible over $\mathbb{F}_{q}[x]$.

Step 2: If gcd$(q,e)=1$, find $m$=ord$(q)$ in $\mathbb{Z}_{e}^{*}$; otherwise
go to Step 6.

Step 3: Set $M=\\{p_{i}(x):1\leq i\leq r,f_{i}=1,\text{deg}(p_{i}(x))=m\\}$
and $t=\\#M$.

Step 4: There are at least
$\sum_{j=0}^{r-t}\sum_{i=1}^{t}\binom{t}{i}\binom{r-t}{j}$ cyclic codes of
exponent $e$.

Step 5: STOP.

Step 6: Set $N=\\{p_{i}(x):1\leq i\leq r,f_{i}>1\\}$.

Step 7: $\forall p_{i}(x)\in N$, find $k_{i}=\frac{e}{\text{ord}(p_{i}(x))}$.

Step 8: Set $S=\\{p_{i}(x)\in N:k_{i}\ \text{is a}\ p\text{-power}\\}$

Step 9: $\forall p_{i}(x)\in S$, find $t_{i}=\log_{p}{k_{i}}$.

Step 10: There are at least $\sum_{i=1}^{\\#S}\sum_{j\neq
i}(f_{j}+1)\phi(p^{t_{i}})$ cyclic codes of exponent $e$.

Step 11: STOP.

To prove the algorithm, it it sufficient to prove Step 4 and Step 10 of the
algorithm.
To prove Step 4, we show that $e$ is the order of
$\prod_{i=1}^{l}p_{i}(x)\prod_{j={l+1}}^{k}p_{j}(x)$, where $p_{i}(x)\in M$
and $p_{j}(x)\notin M$. In fact,

$\displaystyle\text{ord}\left(\prod_{i=1}^{l}p_{i}(x)\right)$
$\displaystyle=\text{lcm}\\{\text{ord}(p_{i}(x)):1\leq i\leq l\\}\hskip
56.9055pt(\text{by Theorem \ref{orderproduct}})$
$\displaystyle=\text{lcm}\\{e:1\leq i\leq l\\}\hskip 99.58464pt(\text{by Lemma
\ref{qmodm}})$ $\displaystyle=e.$

Thus,

$\displaystyle\text{ord}\left(\prod_{i=1}^{l}p_{i}(x)\prod_{j={l+1}}^{k}p_{j}(x)\right)$
$\displaystyle=\text{lcm}\left(\text{ord}\left(\prod_{i=1}^{l}p_{i}(x)\right),\text{ord}\left(\prod_{j={l+1}}^{k}p_{j}\left(x\right)\right)\right)\hskip
2.84544pt(\text{by Theorem \ref{orderproduct}}).$ $\displaystyle=e,\ \text{as
ord}\left(\prod_{i=1}^{l}p_{i}(x)\right)=e.$

Noting that there are exactly $t$ elements in $M$, the number of products of
the form
$\prod_{i=1}^{l}p_{i}(x)\prod_{j={l+1}}^{k}p_{j}(x)$ is
$\sum_{j=0}^{r-t}\sum_{i=1}^{t}\binom{t}{i}\binom{r-t}{j}$.

To prove Step 10, we show that for each $1\leq i\leq\\#S$ that,
ord$\left(p_{i}(x)^{a_{i}}\prod_{j\neq i}p_{j}(x)^{a_{j}}\right)=e$, where
$p^{t_{i}-1}<a_{i}\leq p^{t}_{i}\
\left(t_{i}=\log_{p}{\frac{e}{\text{ord}(p_{i}(x))}}\right)$ and $0\leq
a_{j}\leq f_{j}$.

$\displaystyle\text{ord}\left(p_{i}(x)^{a_{i}}\prod_{j\neq
i}p_{j}(x)^{a_{j}}\right)$
$\displaystyle=\text{lcm}\left(\text{ord}\left(p_{i}(x)^{a_{i}}\right),\text{ord}\left(\prod_{j\neq
i}p_{j}(x)^{a_{j}}\right)\right)\ \hskip 28.45274pt(\text{by Theorem
\ref{orderproduct}})$ $\displaystyle=e.\hskip 213.39566pt(\text{by Lemma
\ref{for what powers exponent is e}})$ The number of polynomials of the above
form is $\displaystyle\sum_{i=1}^{\\#S}\sum_{j\neq
i}(f_{j}+1)(p^{t_{i}}-p^{t_{i}-1})$
$\displaystyle=\sum_{i=1}^{\\#S}\sum_{j\neq i}(f_{j}+1)\phi(p^{t_{i}}).\hskip
56.9055pt\square$

######  Example 1.

There are exactly $4$ ternary cyclic codes of exponent $4$. In this case, the
bound suggested by the algorithm is also $4$. In fact, $q=3,e=4$ and in
$\mathbb{F}_{3}[x]$, $x^{4}-1=(x^{2}+1)(x+2)(x+1)$ so that $r=3,t=1$ and
$\binom{2}{0}+\binom{2}{1}+\binom{2}{2}=4$.

######  Example 2.

To find a lower bound for number of cyclic codes of exponent $12$ over
$\mathbb{F}_{3}$. We factorize $x^{12}-1$ over $\mathbb{F}_{3}[x]$.
$x^{12}-1=(x+1)^{3}(x+2)^{3}(x^{2}+1)^{3}$.
Since gcd$(12,3)\neq 1$, we go to step 6 of the algorithm.
$N=\\{p_{1}(x)=x+1,p_{2}(x)=x+2,p_{3}(x)=x^{2}+1\\}$.

ord$(p_{1}(x))=2$, ord$(p_{2}(x))=1$, ord$(p_{3}(x))=4$

$k_{1}=\frac{12}{2}=6$, $k_{2}=\frac{12}{1}=12$, $k_{3}=\frac{12}{4}=3$

$S=\\{p_{3}(x)\\}$ and $t_{3}=\log_{3}{3}=1$.
Hence, the number of cyclic codes of exponent $12$ over $\mathbb{F}_{3}$ is
atleast $(3+1)(3+1)\phi(3^{1})=32$.

##  3 Exponent of BCH codes

######  Definition 3.1.

[3] Fix a primitive element $\beta$ in $\mathbb{F}_{q^{m}}$ and suppose
$M^{(i)}(x)$ is the minimal polynomial of $\beta^{i}$ over $\mathbb{F}_{q}$.
Let $a\in\mathbb{N}\cup\\{0\\}$ and let $\delta\leq q^{m}-1$. Denote by
$g_{a,\delta}(x)$, the lcm of $M^{(i)}(x):a\leq i\leq a+\delta-2$. The cyclic
code $C(a,\delta)$ generated by $g_{a,\delta}(x)$ over $\mathbb{F}_{q}$ is
called the _BCH code_ of length $q^{m}-1$ with designed distance $\delta$.
$g_{a,\delta}(x)$ will be simply denoted by $g(x)$ if $a$ and $\delta$ are
clear from the context.

######  Lemma 3.2.

Suppose $C_{r}$ denote the cyclotomic coset of $q$ in $\mathbb{Z}_{q^{m}-1}$
that contains $r$. If $C_{r}=C_{s}$, then ord$(\beta^{s})=$ord$(\beta^{r})$
for any primitive element $\beta$ of $\mathbb{F}_{q^{m}}$.

Proof. Suppose $s\in C_{r}$. Then, $s=rq^{j}(\text{mod\ }q^{m}-1)$ for some
$j\in\mathbb{N}\cup\\{0\\}$.
gcd$(s,q^{m}-1)=$gcd$(rq^{j},q^{m}-1)=$gcd$(r,q^{m}-1)$ as
gcd($q^{j},q^{m}-1)=1.$
ord$(\beta^{s})=\frac{q^{m}-1}{gcd(s,q^{m}-1)}=\frac{q^{m}-1}{gcd(r,q^{m}-1)}=$ord$(\beta^{r})$.
$\square$

We now give a formula for the exp$(C)$ in terms of the orders of $\beta^{i}$
in $\mathbb{F}_{q^{m}}^{*}$.

######  Theorem 3.3.

The exponent of the BCH code $C$ with its parameters as in Definition 3.1 is
given by

$exp(C)=\text{lcm}\\{\text{ord}(\beta^{i}):a\leq i\leq a+\delta-2\text{\\}},$

where ord$(\beta^{i})$ denotes the order of $\beta^{i}$ in
$\mathbb{F}_{q^{m}}^{*}$.

Proof. Let $n$ be the length of the BCH code. We have, $M^{(s)}(x)=M^{(t)}(x)$
iff $s$ and $t$ are in the same cyclotomic cosets of $q$ in $\mathbb{Z}_{n}$
by Corollary 1.2. Also $M^{(s)}(x)$ are irreducible over $\mathbb{F}_{q}$.
Then the generator polynomial is

$\displaystyle g(x)=$ $\displaystyle\prod\\{M^{(i)}(x):a\leq i\leq a+\delta-2\
\text{and}\ i\ \text{belongs to distinct cyclotomic cosets of}$ $\displaystyle
q\ \text{in}\ \mathbb{Z}_{n}\\}$

Therefore,

$\displaystyle\text{exp}(C)=$ $\displaystyle\text{ord}(g(x))$ $\displaystyle=$
$\displaystyle\text{ord}(\prod\\{M^{(i)}(x):a\leq i\leq a+\delta-2\
\text{and}\ i\ \text{belongs to distinct cyclotomic cosets of}$ $\displaystyle
q$ $\displaystyle\ \text{in}\ \mathbb{Z}_{n}\\})$ $\displaystyle=$
$\displaystyle\text{lcm}\\{\text{ord}(M^{(i)}(x)):a\leq i\leq a+\delta-2\
\text{and}\ i\ \text{belongs to distinct cyclotomic cosets of}$ $\displaystyle
q$ $\displaystyle\ \text{in}\ \mathbb{Z}_{n}\\}\hskip 142.26378pt(\text{by
Theorem \ref{orderproduct}})$ $\displaystyle=$
$\displaystyle\text{lcm}\\{\text{ord}(\beta^{i}):a\leq i\leq a+\delta-2\
\text{and}\ i\ \text{belongs to distinct cyclotomic cosets of}$ $\displaystyle
q$ $\displaystyle\ \text{in}\ \mathbb{Z}_{n}\\}\hskip 142.26378pt(\text{by
Theorem \ref{orderirr}})$ $\displaystyle=$
$\displaystyle\text{lcm}\\{\text{ord}(\beta^{i}):a\leq i\leq a+\delta-2\
\text{\\}}\hskip 19.91684pt(\text{by Lemma \ref{orderalpha}})$

$\square$

######  Corollary 3.4.

Let $\alpha,\beta\in\mathbb{F}_{q^{m}}$ be primitive elements. Denote by
$M_{1}^{(i)}(x)$ and $M_{2}^{(i)}(x)$, the minimal polynomials of $\alpha^{i}$
and $\beta^{i}$ respectively over $\mathbb{F}_{q}$. Fix
$a\in\mathbb{N}\cup\\{0\\}$ and designed distance $\delta$. Suppose
$f(x)=lcm\\{M_{1}^{(i)}(x):a\leq i\leq a+\delta-2\\}$ and
$g(x)=lcm\\{M_{2}^{(i)}(x):a\leq i\leq a+\delta-2\\}$. Let $C_{\alpha}$ and
$C_{\beta}$ be the BCH codes of length $q^{m}-1$ generated by $f(x)$ and
$g(x)$ respectively. Then $exp(C_{\alpha})=exp(C_{\beta})$.

Proof. Since $\alpha$ and $\beta$ are two primitive elements of
$\mathbb{F}_{q^{m}}$, therefore ord$(\alpha^{i})$=ord$(\beta^{i})$ $\forall
i\in\mathbb{N}$. Then by the above theorem,

$\displaystyle\text{exp}(C_{\alpha})$
$\displaystyle=\text{lcm}\\{\text{ord}(\alpha^{i}):a\leq i\leq
a+\delta-2\text{\\}}$ $\displaystyle=\text{lcm}\\{\text{ord}(\beta^{i}):a\leq
i\leq a+\delta-2\text{\\}}$ $\displaystyle=\text{exp}(C_{\beta})$

$\square$

######  Example 3.

Let $\beta$ be a root of $x^{4}+x+1=f(x)\in\mathbb{F}_{2}[x]$. Since $f(x)$ is
irreducible in $\mathbb{F}_{2}[x]$, $\beta$ is a primitive element of
$\mathbb{F}_{16}\cong\frac{\mathbb{F}_{2}[x]}{<f(x)>}$.

  1. (i)

Denote by $C$, the $2$-ary $[15,9]$-BCH code generated by the lcm of
$M^{(5)}(x)$ and $M^{(6)}(x)$ that is $(1+x+x^{2})(1+x+x^{2}+x^{3}+x^{4})$
whose designed distance is $3$. Then

$\displaystyle\text{exp}(C)=\text{lcm}(\text{ord}(\alpha^{5}),\text{ord}(\alpha^{6}))=\text{lcm}(3,5)=15.$

  2. (ii)

Denote by $D$, the $2$-ary $[15,13]$-BCH code generated by
$M^{(5)}(x)=1+x+x^{2}$ and designed distance $2$. Then

$\displaystyle\text{exp}(D)=\text{lcm}(\text{ord}(\alpha^{5}))=3.$

######  Example 4.

Let $f(x)=2+x+x^{2}\in\mathbb{F}_{3}[x]$ and let $\beta$ be its root. Since
$f(x)$ is irreducible in $\mathbb{F}_{3}[x]$, $\beta$ is a primitive element
of $\mathbb{F}_{9}\cong\frac{\mathbb{F}_{3}[x]}{<f(x)>}$.
The cyclotomic cosets of $3$ in $\mathbb{Z}_{8}$ are:
$C_{0}=\\{0\\}\hskip 85.35826ptC_{1}=\\{1,3\\}\hskip
85.35826ptC_{2}=\\{2,6\\}$
$C_{4}=\\{4\\}\hskip 85.35826ptC_{5}=\\{5,7\\}$

  1. (i)

Denote by $C$, the $3$-ary narrow-sense $[8,4]$-BCH code which is generated by
$g(x),$ the least common multiple of $M^{(1)}(x)$, $M^{(2)}(x)$ and
$M^{(3)}(x)$ that is $(2+x+x^{2})(1+x^{2})$ whose designed distance is $4$.
Then

$\displaystyle\text{exp}(C)=\text{lcm}(\text{ord}(\alpha^{1}),\text{ord}(\alpha^{2}),\text{ord}(\alpha^{3}))=\text{lcm}(8,4,8)=8.$

One may verify that $g(x)$ divides $x^{8}-1$ but does not divide $x^{r}-1$ for
any $r<8$. Hence, exp($C$)=ord($g(x))=8$.

  2. (ii)

Denote by $D$, the $3$-ary $[8,6]$-BCH code which is generated by
$g(x)=M^{(2)}(x)=(1+x^{2})$ and designed distance $2$. Then

$\displaystyle\text{exp}(D)=\text{lcm}(\text{ord}(\alpha^{2}))=4.$

One may verify that $g(x)$ divides $x^{4}-1$ but does not divide $x^{r}-1$ for
any $r<4$. Hence, exp($D$)=ord($g(x))=4$.

From the above examples, one can observe that the exponent of BCH codes with
designed distance greater than $2$ is equal to the length of the code. It is
not an accident. In fact, we have:

######  Corollary 3.5.

The exponent of a BCH code with designed distance greater than $2$ over
$\mathbb{F}_{q}$ is equal to its length, namely, $q^{m}-1$.

Proof. Since $\delta>2$, $\\{\text{ord}(\alpha^{i}):a\leq i\leq a+\delta-2\\}$
contains at least two elements $\text{ord}(\alpha^{a})$ and
$\text{ord}(\alpha^{a+1})$. Set $n=q^{m}-1,s=\gcd(n,a)$ and $r=\gcd(n,a+1)$ so
that $\gcd(s,r)=1$. Then

$\displaystyle\text{exp}(C)$
$\displaystyle=\text{lcm}\\{\text{ord}(\alpha^{i}):a\leq i\leq
a+\delta-2\text{\\}}$
$\displaystyle\geq\text{lcm}(\text{ord}(\alpha^{a}),\text{ord}(\alpha^{a+1}))$
$\displaystyle=\text{lcm}(\frac{n}{s},\frac{n}{r})$
$\displaystyle=\frac{n}{\gcd(s,r)}$ $\displaystyle=n.$

Thus, exp$(C)\geq n$. But by definition exp$(C)\leq n$, proving that
exp$(C)=n=q^{m}-1$. $\square$

###  3.1 Exponent of Reed-Solomon code

######  Definition 3.6.

[3] The BCH code generated by
$(x-\beta^{a+1})(x-\beta^{a+2})...(x-\beta^{a+\delta-1})\in\mathbb{F}_{q}[x]$,
where $a\in\mathbb{N}\cup\\{0\\},2\leq\delta\leq q-1$, and
$\beta\in\mathbb{F}_{q}$ is primitive, is called a $q$-ary _Reed-Solomon code_
(RS code).

As RS codes are BCH codes, Theorem 3.3 can be rephrased as follows:

######  Theorem 3.7.

The exponent of the RS code $C$ with its parameters as in Definition 3.6 is
given by

$\text{exp}(C)=\text{lcm}\\{\text{ord}(\beta^{i}):a+1\leq i\leq
a+\delta-1\text{\\}},$

where ord$(\beta^{i})$ denotes the order of $\beta^{i}$ in
$\mathbb{F}_{q}^{*}$.

######  Corollary 3.8.

The exponent of a RS code with designed distance greater than $2$ over
$\mathbb{F}_{q}$ is equal to its length, namely, $q-1$.

##  4 Conclusion

In this article, we find bounds for the number of cyclic codes of given
exponent over every finite field. We also determine a formula for the exponent
of the BCH code and RS code and conclude that their exponent is same as the
length of the code, if the designed distance is greater than $2$. For a cyclic
code, the exponent is believed to have certain significance to the code, so in
future one can study the importance of the exponent of a cyclic code.

## References

  * [1] N. Annamalai and C. Durairajan.  Exponent of cyclic codes over.  Journal of Discrete Mathematical Sciences and Cryptography, 0(0):1–6, 2021.
  * [2] R. Lidl and H. Niederreiter.  Introduction to finite fields and their applications.  Cambridge University Press, Cambridge, first edition, 1994.
  * [3] S. Ling and C. Xing.  Coding theory.  Cambridge University Press, Cambridge, 2004.  A first course.


# A Generalized Unbiased Risk Estimator for Learning with Augmented Classes

Senlin Shu1, Shuo He2, Haobo Wang3, Hongxin Wei4, Tao Xiang1, Lei Feng4
1Chongqing University, China
2University of Electronic Science and Technology of China, China
3Zhejiang University, China
4Nanyang Technological University, Singapore
Corresponding author: Lei Feng<EMAIL_ADDRESS>
###### Abstract

In contrast to the standard learning paradigm where all classes can be
observed in training data, _learning with augmented classes_ (LAC) tackles the
problem where augmented classes unobserved in the training data may emerge in
the test phase. Previous research showed that given unlabeled data, an
_unbiased risk estimator_ (URE) can be derived, which can be minimized for LAC
with theoretical guarantees. However, this URE is only restricted to the
specific type of one-versus-rest loss functions for multi-class
classification, making it not flexible enough when the loss needs to be
changed with the dataset in practice. In this paper, we propose a
_generalized_ URE that can be equipped with arbitrary loss functions while
maintaining the theoretical guarantees, given unlabeled data for LAC. To
alleviate the issue of negative empirical risk commonly encountered by
previous studies, we further propose a novel risk-penalty regularization term.
Experiments demonstrate the effectiveness of our proposed method.

##  1 Introduction

Machine learning approaches have achieved great performance on a variety of
tasks, and most of them focus on the stationary learning environment. However,
the learning environment in many real-world scenarios could be open and change
gradually, which requires the learning approaches to have the ability of
handling the distribution change in the non-stationary environment [1, 2, 3,
4].

This paper considers a specific problem where the class distribution changes
from the training phase to the test phase, called _learning with augmented
classes_ (LAC). In LAC, some augmented classes unobserved in the training
phase might emerge in the test phase. In order to make accurate and reliable
predictions, the learning model is required to distinguish augmented classes
and keep good generalization performance over the test distribution.

The major difficulty in LAC is how to exploit the relationships between known
and augmented classes. To overcome this difficulty, various learning methods
have been proposed. For example, by learning a compact geometric description
of known classes to distinguish augmented classes that are far away from the
description, the anomaly detection or novelty detection methods can be used
(e.g., iForest [5], one-class SVM [6, 7], and kernel density estimation [8,
9]). By exploiting unlabeled data with the low-density separation assumption
to adjust the classification decision boundary [10], the performance of LAC
can be empirically improved.

A recent study [4] showed that by exploiting unlabeled data, an _unbiased risk
estimator_ (URE) for LAC over the test distribution can be constructed under
the _class shift condition_. The motivation of this study stems from that
although the instances from augmented classes cannot be observed in labeled
data, their distribution information may be contained in unlabeled data and
estimated by differentiating the distribution of known classes from unlabeled
data. Such an URE is advantageous for the learning task, since it can lead to
a theoretically grounded method based on empirical risk minimization. However,
the URE for LAC derived by the previous study [4] is only restricted to the
specific type of one-versus-rest loss functions, making it not flexible enough
when the loss needs to be changed with the dataset in practice.

To address the above issue, we make the following contributions in this paper:

  * •

we propose a _generalized_ unbiased risk estimator that can be equipped with
_arbitrary_ loss functions while maintaining the theoretical guarantees, given
unlabeled data for learning with augmented classes.

  * •

We provide a theoretical analysis on the estimation error bound, which
guarantees that the convergence of the empirical risk minimizer to the true
risk minimizer.

  * •

We propose a novel risk-penalty regularization term that can be used to
alleviate the issue of negative empirical risk commonly encountered by
previous studies.

  * •

We conduct extensive experiments with different base models on widely used
benchmark datasets to demonstrate the effectiveness of our proposed method.

##  2 Preliminaries

In this section, we introduce some preliminary knowledge.

#### Learning with augmented classes.

In the training phase of LAC, we are given a labeled training set
$\mathcal{D}_{\mathrm{L}}=\\{\bm{x}_{i},y_{i}\\}_{i=1}^{n}$ independently
sampled from a distribution of known classes $P_{\mathrm{kc}}$ over
$\mathcal{X}\times\mathcal{Y}^{\prime}$, where $\mathcal{X}$ is the feature
space and $\mathcal{Y}^{\prime}=\\{1,2,\ldots,k\\}$ is the label space of $k$
known classes. However, in the test phase, we need to predict unlabeled data
sampled from the test distribution $P_{\mathrm{te}}$, where augmented classes
unobserved in the training phase may emerge. Since the specific partition of
augmented classes is unknown, they are normally predicted as a single class.
In this way, the label space of the test distribution $P_{\mathrm{te}}$ is
$\mathcal{Y}=\\{1,2,\ldots,k,\mathtt{ac}\\}$ where $\mathtt{ac}$ denotes the
class grouped by augmented classes. The _class shift condition_ [4] was
introduced to describe the relationship between the distributions of known and
augmented classes:

$\displaystyle P_{\mathrm{te}}=\theta\cdot P_{\mathrm{kc}}+(1-\theta)\cdot
P_{\mathrm{ac}},$ (1)

where $\theta\in[0,1]$ indicates the mixture proportion. In addition, a set of
unlabeled data $\mathcal{D}_{\mathrm{U}}=\\{\bm{x}_{i}\\}_{i=1}^{m}$ sampled
from the test distribution is provided and will be used for model training.
This learning scenario of available unlabeled data is conceivable since we can
easily collect a large amount of unlabeled data from current environments.
Such unlabeled data can be used to enrich the information of unobservable
classes in the training phase, despite no revealed supervision information on
the unlabeled data.

#### Unbiased risk estimator for LAC.

Under the class shift condition in LAC, the expected classification risk over
the test distribution can be formulated as

$\displaystyle R(f)$ $\displaystyle=\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{te}}}[\mathcal{L}(f(\bm{x}),y)]$
$\displaystyle=\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),y)]+(1-\theta)\mathbb{E}_{(\bm{x},y=\mathtt{ac})\sim
P_{\mathrm{ac}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})].$ (2)

The recent study [4] only considered the _one-versus-rest_ (OVR) loss function
as the classification loss in Eq. (2), which takes the following form for
$k$-class classification:

$\displaystyle\mathcal{L}_{\mathrm{OVR}}(f(\bm{x}),y)=\psi(f_{y}(\bm{x}))+\sum\nolimits_{i=1,i\neq
y}^{k}\psi(-f_{i}(\bm{x})),$

where $\psi(\cdot):\mathbb{R}\mapsto\mathbb{R}_{+}$ denotes a binary loss
function. By substituting the OVR loss $\mathcal{L}_{\mathrm{OVR}}$ into the
classification risk, we have $R^{\mathrm{OVR}}(f)=\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{te}}}[\mathcal{L}_{\mathrm{OVR}}(f(\bm{x}),y)]$. The previous study
[4] showed that an equivalent expression of $R^{\mathrm{OVR}}(f)$ in the
setting of LAC with unlabeled data drawn from the test distribution can be
derived:

$\displaystyle R_{\mathrm{LAC}}^{\mathrm{OVR}}(f)$
$\displaystyle=\theta\cdot\mathbb{E}_{p_{\mathrm{kc}}(\bm{x},y)}[\psi(f_{y}(\bm{x}))-\psi(-f_{y}(\bm{x}))+\psi(-f_{\mathtt{ac}}(\bm{x}))-\psi(f_{\mathtt{ac}}(\bm{x}))]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\mathbb{E}_{\bm{x}\sim
P_{\mathrm{te}}}[\psi(f_{\mathrm{ac}}(\bm{x}))+\sum\nolimits_{i=1}^{k}\psi(-f_{k}(\bm{x}))].$

As can be verified, $R^{\mathrm{OVR}}_{\mathrm{LAC}}(f)=R^{\mathrm{OVR}}(f)$,
and thus its empirical version $\widehat{R}^{\mathrm{OVR}}_{\mathrm{LAC}}(f)$
is an _unbiased risk estimator_ (URE). As we can see, this URE is only
restricted to the OVR loss for multi-class classification, making it not
flexible enough when the loss needs to be changed with the dataset in
practice.

##  3 The Proposed Method

In this section, we first propose a generalized URE and provide a theoretical
analysis for the derived URE. Then, we propose a novel risk-penalty
regularization term that can be used to alleviate the issue of negative
empirical risk.

###  3.1 A Generalized Unbiased Risk Estimator

######  Theorem 1.

Under the class shift condition in Eq. (1), the classification risk $R(f)$ can
be equivalently expressed as:

$\displaystyle R_{\mathrm{LAC}}(f)$
$\displaystyle=\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),y)-\mathcal{L}(f(\bm{x}),\mathtt{ac})]+\mathbb{E}_{\bm{x}\sim
P_{\mathrm{te}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]=R(f).$ (3)

The proof of Theorem 1 is provided in Appendix A. Theorem 1 shows that we are
able to learn a classifier from labeled data from the distribution of known
classes and unlabeled data from the test distribution, without any
restrictions on the loss function $\mathcal{L}$ for multi-class
classification.

######  Corollary 1.

If the one-versus-rest (OVR) loss $\mathcal{L}_{\mathrm{OVR}}$ is used as the
classification loss in our derived risk $R_{\mathrm{LAC}}(f)$, then we can
exactly recover the risk $R_{\mathrm{LAC}}^{\mathrm{OVR}}(f)$ derived by the
previous study [4].

The proof of Corollary 1 is omitted here, since it is quite straightforward to
verify that by directly inserting $\mathcal{L}_{\mathrm{OVR}}$ into
$R_{\mathrm{LAC}}(f)$. Corollary 1 shows that our proposed URE is a
generalization of the URE proposed by Zhang et al. [4] and can be compatible
with arbitrary loss functions.

Given a set of labeled data
$\mathcal{D}_{\mathrm{L}}=\\{\bm{x}_{i},y_{i}\\}_{i=1}^{n}$ drawn from the
distribution of known classes $P_{\mathrm{kc}}$ and a set of unlabeled data
$\mathcal{D}_{\mathrm{U}}=\\{\bm{x}_{i}\\}_{i=1}^{m}$ drawn from the test
distribution $P_{\mathrm{te}}$, we can obtain the following URE, which is the
empirical approximation of ${R}_{\mathrm{LAC}}$:

$\displaystyle\widehat{R}_{\mathrm{LAC}}(f)$
$\displaystyle=\frac{\theta}{n}\sum\nolimits_{i=1}^{n}\Big{(}\mathcal{L}(f(\bm{x}_{i}),y_{i})-\mathcal{L}(f(\bm{x}_{i}),\mathtt{ac})\Big{)}+\frac{1}{m}\sum\nolimits_{j=1}^{m}\mathcal{L}(f(\bm{x}_{j}),\mathtt{ac}).$
(4)

In this way, we are able to learn an effective multi-class classifier by
directly minimizing $\widehat{R}_{\mathrm{LAC}}(f)$. Since there are no
restrictions on the loss function $\mathcal{L}$ and the model $f$, we can use
any loss and any model for LAC with unlabeled data.

###  3.2 Theoretical Analysis

Here, we establish an estimation error bound for our proposed URE based on the
widely used _Rademacher complexity_ [11].

######  Definition 1 (Rademacher Complexity).

Let $n$ be a positive integer, $\bm{x}_{1},\ldots,\bm{x}_{n}$ be independent
and identically distributed random variables drawn from a probability
distribution with density $\mu$,
$\mathcal{G}={g:\mathcal{X}\mapsto\mathbb{R}}$ be a class of measurable
functions, and $\bm{\sigma}=(\sigma_{1},\ldots,\sigma_{n})$ be Rademacher
variables that take value from $\\{+1,-1\\}$ with even probabilities. Then,
the Rademacher complexity of $\mathcal{G}$ is defined as

$\displaystyle\mathfrak{R}_{n}(\mathcal{G}):=\mathbb{E}_{\bm{x}_{1},\ldots,\bm{x}_{n}\overset{\mathrm{i.i.d.}}{\sim}\mu}\mathbb{E}_{\bm{\sigma}}\Big{[}\sup\nolimits_{g\in\mathcal{G}}\frac{1}{n}\sum\nolimits_{i=1}^{n}\sigma_{i}g(\bm{x}_{i})\Big{]}.$

Let us represent $\mathcal{F}$ by
$\mathcal{F}=\mathcal{F}_{1}\times\mathcal{F}_{2}\cdots\mathcal{F}_{k+1}$
where $\mathcal{F}_{i}=\\{\bm{x}\mapsto f_{i}(\bm{x})\mid f\in\mathcal{F}\\}$
and $\mathcal{F}_{k+1}$ is specially for the augmented class $\mathtt{ac}$.
Thus we can denote by $\mathfrak{R}_{n}(\mathcal{F}_{y})$ the Rademacher
complexity of $\mathcal{F}_{y}$ for the $y$-th class, given the sample size
$n$ over the test distribution $P_{\mathrm{te}}$. It is commonly assumed that
$\mathfrak{R}_{n}(\mathcal{F}_{y})\leq C_{\mathcal{F}}/\sqrt{n}$ for all
$y\in\mathcal{Y}$ [12], where $C_{\mathcal{F}}$ is a positive constant. Let
the learned classifier by our URE be
$\widehat{f}=\mathop{\arg\min}_{f\in\mathcal{F}}\widehat{R}_{\mathrm{LAC}}(f)$
and the optimal classifier learned by minimizing the true classification risk
be $f^{\star}=\mathop{\arg\min}_{f\in\mathcal{F}}R(f)$. Then we have the
following theorem.

######  Theorem 2.

Assume the multi-class loss $\mathcal{L}(f(\bm{x}),y)$ is $\rho$-Lipschitz
($0<\rho<\infty$) with respect to $f(\bm{x})$ for all $y\in\mathcal{Y}$ and
upper bounded by a positive constant $C_{\mathcal{L}}$, i.e.,
$C_{\mathcal{L}}=\sup_{\bm{x}\in\mathcal{X},y\in\mathcal{Y},f\in\mathcal{F}}\mathcal{L}(f(\bm{x}),y)$.
Then, for any $\delta>0$, with probability at least $1-\delta$,

$\displaystyle R(\widehat{f})-R(f^{\star})$ $\displaystyle\leq
C_{k,\rho,\delta}(\frac{2\theta}{\sqrt{n}}+\frac{1}{\sqrt{m}}),$

where
$C_{k,\rho,\delta}=(4\sqrt{2}\rho(k+1)C_{\mathcal{F}}+2C_{\mathcal{L}}\sqrt{\frac{\log\frac{4}{\delta}}{2}})$.

The proof of Theorem 2 is provided in Appendix B. Theorem 2 shows that our
proposed method is consistent, i.e., $R(\widehat{f})\rightarrow R(f^{\star})$
as $n\rightarrow\infty$ and $m\rightarrow\infty$. The convergence rate is
$\mathcal{O}_{p}(1/\sqrt{n}+1/\sqrt{m})$, where $\mathcal{O}_{p}$ denotes the
order in probability. This order is the optimal parametric rate for the
empirical risk minimization without additional assumptions (Mendelson, 2008).

###  3.3 Risk-Penalty Regularization

As shown in Eq. (4), there exist negative terms in the URE
$\widehat{R}_{\mathrm{LAC}}(f)$. Since the widely used classification loss
(i.e., the cross entropy loss) is unbounded above,
$\widehat{R}_{\mathrm{LAC}}(f)$ could be unbounded below, which causes the
overfitting issue, and this issue becomes especially terrible when deep models
are employed. Such an issue was encountered and demonstrated by many previous
studies [13, 14, 4, 15]. To alleviate this issue, these studies normally
wrapped the terms that could make empirical risk negative by certain
correction functions, such as the _rectified linear unit_ (ReLU) function
$g(z)=\max(0,z)$ and the _absolute value_ (ABS) function $g(z)=|z|$. Despite
the effectiveness of the correction functions used by previous studies [14],
using a correction function could make the empirical risk not unbiased
anymore. Motivated by this, we aim to keep the original URE unchanged and
impose a regularization term to alleviate the issue of negative empirical
risk.

We note that the above issue in our work comes from the use of equality:
$(1-\theta)\mathbb{E}_{(\bm{x},y=\mathtt{ac})\sim
P_{\mathrm{ac}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]=\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{te}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]-\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]$. Let us denote by
$\widehat{R}_{\mathrm{PAC}}$ the empirical version of the expected risk on the
left hand side of the above equality:

$\displaystyle\widehat{R}_{\mathrm{PAC}}(f)=\frac{1}{m}\sum_{j=1}^{m}\mathcal{L}(f(\bm{x}_{j}),\mathtt{ac})-\frac{\theta}{n}\sum_{i=1}^{n}\mathcal{L}(f(\bm{x}_{i}),\mathtt{ac}).$

Our goal is to prevent the whole training objective from going to be unbounded
below in the training process. Therefore, we choose to add an regularization
term on the training objective, which could incur a cost when
$\widehat{R}_{\mathrm{PAC}}(f)$ goes to be negative. In this way, the whole
training objective would not be unbounded below, because there is always a
positive cost incurred if $\widehat{R}_{\mathrm{PAC}}(f)$ goes to be negative.
Our proposed regularization term is presented as follows:

$\displaystyle\Omega(f)=\left\\{\begin{matrix}(-\widehat{R}_{\mathrm{PAC}}(f))^{t},&\mathrm{if}\
\widehat{R}_{\mathrm{PAC}}(f)<0,\\\ 0,&\mathrm{otherwise},\\\
\end{matrix}\right.$ (5)

where $t\geq 0$ is a hyper-parameter. We plot the above regularization
function in Figure 1. Using this regularization, our final training objective
becomes $\widehat{R}_{\mathrm{LAC}}(f)+\lambda\Omega(f)$, where
$\widehat{R}_{\mathrm{LAC}}(f)$ is our derived URE defined in Eq. (4) and
$\lambda$ is a hyper-parameter that controls the importance of the
regularization term. As can be seen from Figure 1, when the empirical risk
becomes negative, an extra loss will be generated, thereby alleviating the
issue of the negative empirical risk during training. Additionally, the widely
used correction functions ReLU and ABS can be considered as spacial cases of
our proposed negative risk penalty regularization. Specifically, when $t=1$
and $\lambda=1$, we obtain a formulation by using ReLU as the correction
function. When $t=1$ and $\lambda=2$, we obtain a formulation by using ABS as
the correction function. Therefore, our proposed risk-penalty regularization
could be considered as a generalized solution to the issue of negative
empirical risk.

Figure 1: The function curve of our proposed risk-penalty regularization.

###  3.4 Handling Class Prior Shift

The class shift condition in Eq. (1) describes the relationship between the
distributions of known classes and augmented classes, with the assumption that
the distribution of known classes keeps identical in both the training phase
and the test phase. However, the learning environment could dynamically change
in real-world scenarios, and thus the prior of each class could also vary from
the training phase and the test phase. As shown by Zhang et al. [4], the
following generalized class shift condition can be obtained:

$\displaystyle
P_{\mathrm{te}}=\sum\nolimits_{i=1}^{k}\theta_{\mathrm{te}}^{i}\cdot
P_{i}+(1-\sum\nolimits_{i=1}^{k}\theta_{\mathrm{te}}^{i})\cdot
P_{\mathrm{ac}},$ (6)

where $P_{i}$ denotes the data distribution of the $i$-th known class and
$\theta_{\mathrm{te}}^{i}$ denotes the class prior of the $i$-th known class
in the test phase. Given the generalized class shift condition in Eq. (6), we
can still obtain an equivalent representation of the classification risk
$R(f)$.

######  Theorem 3.

Under the generalized class shift condition in Eq. (6), the classification
risk $R(f)$ can be equivalently expressed as follows:

$\displaystyle
R_{\mathrm{LAC}}^{\mathrm{shift}}(f)=\sum\nolimits_{i=1}^{k}\theta_{\mathrm{te}}^{i}\cdot\mathbb{E}_{(\bm{x},y)\sim
P_{i}}[\mathcal{L}(f(\bm{x}),y)-\mathcal{L}(f(\bm{x}),\mathtt{ac})]+\mathbb{E}_{\bm{x}\sim
P_{\mathrm{te}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]=R(f).$ (7)

We omitted the proof of Theorem 3, since it is quite straightforward by
following the proof of Theorem 1. Theorem 3 shows that we can learn a
classifier for LAC with unlabeled data under the class prior shift condition
of known classes by empirically minimizing
$R_{\mathrm{LAC}}^{\mathrm{shift}}(f)$.

##  4 Experiments

In this section, we conduct extensive experiments to evaluate the performance
of our proposed method on various datasets using different models.

###  4.1 Expermental Setup

#### Datasets.

We use six regular-scale datasets downloaded from the UCI Machine Learning
Repository111https://archive.ics.uci.edu [16], including Har, Msplice, Normal,
Optdigits, Texture, and Usps. Since they are not large-scale datasets, we
train a linear model on these datasets. We also use four widely large-scale
benchmark datasets, including MNIST222http://yann.lecun.com/exdb/mnist/ [17],
Fashion-MNIST333https://github.com/zalandoresearch/fashion-mnist [18],
Kuzushiji-MNIST444http://codh.rois.ac.jp/kmnist/ [19], and
SVHN555http://ufldl.stanford.edu/housenumbers/ [20]. For MINST, Fashion-MNIST,
and Kuzushiji-MNIST, we train a multilayer perceptron (MLP) model with three
layers ($d-500-k$) and the ReLU activation function is used. For the SVHN
dataset, we train a VGG16 model [21]. The brief characteristics of all the
used datasets are reported in Table 1. For each regular-scale dataset, half of
the classes are selected as augmented classes and the remaining classes are
considered as known classes. Besides, the number of labeled, unlabeled, and
test examples set to 500, 1000, and 1000, respectively. For large-scale
datasets, we select six classes as known classes and other classes are
regarded as augmented classes. For MNIST, Fashion-MNIST, and Kuzushiji-MNIST,
the number of the labeled, unlabeled, and test examples is set to 24000 (4000
per known class), 10000 (1000 per class), and 1000 (100 per class),
respectively. For SVHN, the number of the labeled, unlabeled, and test
examples is set to 24000 (4000 per known class), 25000 (2500 per class), and
1000 (100 per class), respectively. To comprehensively evaluate the
performance of our proposed method, we report the mean value with standard
deviation over 10 trials, in terms of the evaluation metrics including
accuracy, Macro-F1, and AUC.

Dataset |  # Examples |  # Features |  # Classes
---|---|---|---
Har |  10,699 |  561 |  6
Msplice |  3,175 |  240 |  3
Normal |  7,000 |  2 |  7
Optdigits |  5,620 |  62 |  10
Texture |  5,500 |  40 |  11
Usps |  9,298 |  256 |  10
MNIST |  70,000 |  784 |  10
Fashion |  70,000 |  784 |  10
Kuzushiji |  70,000 |  784 |  10
SVHN |  99,268 |  3,072 |  10

Table 1: Brief characteristics of the used datasets.

Datasets |  Accuracy
---|---
OVR |  EVM |  LACU |  iForest |  EULAC |  NRPR
Har |  0.452$\pm$0.012 |  0.413$\pm$0.007 |  0.542$\pm$0.077 |  0.958$\pm$0.005 |  0.967$\pm$0.009 |  0.986$\pm$0.007
Msplice |  0.725$\pm$0.008 |  0.658$\pm$0.005 |  0.664$\pm$0.015 |  0.716$\pm$0.007 |  0.781$\pm$0.032 |  0.785$\pm$0.020
Normal |  0.570$\pm$0.001 |  0.567$\pm$0.003 |  0.567$\pm$0.050 |  0.775$\pm$0.036 |  0.755$\pm$0.051 |  0.851$\pm$0.009
Optdigits |  0.533$\pm$0.014 |  0.460$\pm$0.009 |  0.724$\pm$0.068 |  0.728$\pm$0.020 |  0.791$\pm$0.047 |  0.863$\pm$0.037
Texture |  0.570$\pm$0.010 |  0.474$\pm$0.018 |  0.520$\pm$0.062 |  0.601$\pm$0.029 |  0.732$\pm$0.109 |  0.930$\pm$0.009
Usps |  0.631$\pm$0.026 |  0.547$\pm$0.007 |  0.572$\pm$0.057 |  0.551$\pm$0.005 |  0.874$\pm$0.023 |  0.878$\pm$0.012
Datasets |  Macro-F1
OVR |  EVM |  LACU |  iForest |  EULAC |  NRPR
Har |  0.526$\pm$0.014 |  0.530$\pm$0.008 |  0.277$\pm$0.020 |  0.950$\pm$0.006 |  0.950$\pm$0.011 |  0.980$\pm$0.009
Msplice |  0.549$\pm$0.007 |  0.490$\pm$0.005 |  0.537$\pm$0.049 |  0.537$\pm$0.007 |  0.759$\pm$0.034 |  0.767$\pm$0.021
Normal |  0.679$\pm$0.001 |  0.658$\pm$0.028 |  0.405$\pm$0.221 |  0.747$\pm$0.050 |  0.586$\pm$0.103 |  0.762$\pm$0.013
Optdigits |  0.606$\pm$0.012 |  0.572$\pm$0.014 |  0.745$\pm$0.069 |  0.708$\pm$0.025 |  0.690$\pm$0.103 |  0.859$\pm$0.026
Texture |  0.709$\pm$0.008 |  0.561$\pm$0.026 |  0.294$\pm$0.194 |  0.696$\pm$0.019 |  0.540$\pm$0.192 |  0.927$\pm$0.011
Usps |  0.667$\pm$0.026 |  0.579$\pm$0.008 |  0.370$\pm$0.111 |  0.590$\pm$0.010 |  0.853$\pm$0.038 |  0.867$\pm$0.012
Datasets |  AUC
OVR |  EVM |  LACU |  iForest |  EULAC |  NRPR
Har |  0.789$\pm$0.006 |  0.754$\pm$0.007 |  0.695$\pm$0.051 |  0.953$\pm$0.005 |  0.998$\pm$0.001 |  0.999$\pm$0.001
Msplice |  0.737$\pm$0.007 |  0.652$\pm$0.006 |  0.748$\pm$0.011 |  0.733$\pm$0.006 |  0.924$\pm$0.013 |  0.917$\pm$0.010
Normal |  0.849$\pm$0.001 |  0.847$\pm$0.002 |  0.748$\pm$0.029 |  0.803$\pm$0.031 |  0.976$\pm$0.026 |  0.999$\pm$0.000
Optdigits |  0.866$\pm$0.005 |  0.836$\pm$0.008 |  0.834$\pm$0.041 |  0.798$\pm$0.021 |  0.907$\pm$0.053 |  0.987$\pm$0.002
Texture |  0.894$\pm$0.004 |  0.831$\pm$0.016 |  0.720$\pm$0.036 |  0.828$\pm$0.012 |  0.756$\pm$0.126 |  0.995$\pm$0.001
Usps |  0.870$\pm$0.007 |  0.846$\pm$0.007 |  0.743$\pm$0.034 |  0.843$\pm$0.004 |  0.979$\pm$0.005 |  0.981$\pm$0.002

Table 2: Test performance (mean$\pm$std) of each method on UCI datasets. The
best performance is highlighted in bold.

Datasets |  Accuracy
---|---
OVR |  Softmax |  Softmax-T |  Openmax |  EULAC |  NRPR
MNIST |  0.743$\pm$0.018 |  0.592$\pm$0.002 |  0.883$\pm$0.009 |  0.882$\pm$0.007 |  0.952$\pm$0.006 |  0.960$\pm$0.006
Fashion |  0.587$\pm$0.009 |  0.559$\pm$0.007 |  0.595$\pm$0.011 |  0.601$\pm$0.011 |  0.840$\pm$0.034 |  0.875$\pm$0.010
Kuzushiji |  0.696$\pm$0.017 |  0.578$\pm$0.004 |  0.828$\pm$0.009 |  0.835$\pm$0.012 |  0.881$\pm$0.016 |  0.927$\pm$0.009
SVHN |  0.595$\pm$0.022 |  0.564$\pm$0.006 |  0.720$\pm$0.037 |  0.786$\pm$0.013 |  0.835$\pm$0.021 |  0.873$\pm$0.012
Datasets |  Macro-F1
OVR |  Softmax |  Softmax-T |  Openmax |  EULAC |  NRPR
MNIST |  0.794$\pm$0.015 |  0.653$\pm$0.004 |  0.898$\pm$0.007 |  0.898$\pm$0.006 |  0.951$\pm$0.007 |  0.960$\pm$0.006
Fashion |  0.667$\pm$0.010 |  0.637$\pm$0.007 |  0.685$\pm$0.009 |  0.688$\pm$0.008 |  0.813$\pm$0.070 |  0.872$\pm$0.010
Kuzushiji |  0.746$\pm$0.014 |  0.630$\pm$0.005 |  0.847$\pm$0.009 |  0.851$\pm$0.011 |  0.877$\pm$0.021 |  0.926$\pm$0.008
SVHN |  0.640$\pm$0.020 |  0.614$\pm$0.007 |  0.760$\pm$0.029 |  0.801$\pm$0.014 |  0.831$\pm$0.021 |  0.876$\pm$0.011
Datasets |  AUC
OVR |  Softmax |  Softmax-T |  Openmax |  EULAC |  NRPR
MNIST |  0.929$\pm$0.005 |  0.890$\pm$0.002 |  0.939$\pm$0.005 |  0.939$\pm$0.005 |  0.996$\pm$0.002 |  0.998$\pm$0.001
Fashion |  0.868$\pm$0.004 |  0.864$\pm$0.005 |  0.822$\pm$0.005 |  0.820$\pm$0.004 |  0.953$\pm$0.039 |  0.985$\pm$0.002
Kuzushiji |  0.908$\pm$0.005 |  0.880$\pm$0.003 |  0.909$\pm$0.008 |  0.905$\pm$0.008 |  0.981$\pm$0.009 |  0.994$\pm$0.001
SVHN |  0.835$\pm$0.011 |  0.868$\pm$0.005 |  0.889$\pm$0.012 |  0.865$\pm$0.018 |  0.931$\pm$0.019 |  0.984$\pm$0.003

Table 3: Test performance (mean$\pm$std) of each method on benchmark datasets.
The best performance is highlighted in bold.

#### Methods.

For the experiments on regular-scale datasets, we compare with the following
five methods:

  * •

OVR [22], which uses the one-versus-reset loss for training a multi-class
classifier. For the LAC problem, OVR predicts the augmented class if
$\mathrm{max}_{y\in\mathcal{Y}^{\prime}}f_{y}(\bm{x})<0$, otherwise it makes
normal predictions $\mathop{\arg\max}_{y\in\mathcal{Y}}f_{y}$ in known
classes.

  * •

EVM [23], which uses the extreme value machine to perform nonlinear kernel-
free variable bandwidth incremental learning.

  * •

LACU [10], which exploits unlabeled data with the low-density separation
assumption to adjust the classification decision boundary.

  * •

iForest [5], which first uses iForest to detect augmented classes and then
uses the OVR method [22] to make normal predictions for known classes.

  * •

EULAC [4], which derives an unbiased risk estimator for LAC with unlabeled
data.

For the experiments on large-scale datasets, we compare with OVR, EULAC, and
following three methods:

  * •

Softmax, which directly trains a multi-class classifier by using the softmax
cross entropy loss and only makes normal predictions for known classes.

  * •

Softmax-T, which denotes the Softmax method with a threshold set for
predicting the augmented class. It predicts the augmented class if
$\mathrm{max}_{y\in\mathcal{Y}^{\prime}}g_{y}(\bm{x})$ is less than a given
threshold, where $g_{y}(\bm{x})$ is a softmax score of the class $y$ for the
instance $\bm{x}$. The threshold is set to 0.95.

  * •

Openmax [24], which can be considered as a calibrated version of the Softmax-T
method. In Openmax, Weibull calibration is implemented as an augment to the
SoftMax method while replacing the Softmax layer with a new OpenMax layer.

For the compared methods, we adopt the hyper-parameter settings suggested by
respective papers. For our proposed method, we utilize the _generalized cross
entropy_ (GCE) loss [25] as the multi-class loss function, since it is a
generalized version of the widely used cross entropy loss. We use the Adam
optimization method [26], with the number of training epochs set to 1500 on
regular-scale datasets and 200 on large-scale datasets respectively. We set
the mini-batch size to 500 on large-scale datasets and use the full batch size
on regular-scale datasets. For regular-scale datasets, learning rate and
weight decay are selected in $\\{10^{-2},10^{-3},10^{-4}\\}$. For large-scale
datasets, learning rate and weight decay are selected in
$\\{10^{-3},10^{-4},10^{-5}\\}$. For our method, $t$ and $\lambda$ are
selected in $\\{1,2,3\\}$ and $\\{0.2,0.4,\ldots,1.8,2\\}$, respectively.
Since our method uses a URE with negave-risk penalty regularization, we name
it NRPR. All the experiments are conducted on GeForce GTX 3090 GPUs.

Datasets |  Accuracy
---|---
ReLU |  ABS |  NRPR
MNIST |  0.865$\pm$0.034 |  0.776$\pm$0.014 |  0.960$\pm$0.006
Fashion |  0.809$\pm$0.021 |  0.747$\pm$0.019 |  0.870$\pm$0.009
Kuzushiji |  0.853$\pm$0.029 |  0.757$\pm$0.027 |  0.927$\pm$0.009
SVHN |  0.734$\pm$0.018 |  0.695$\pm$0.007 |  0.865$\pm$0.010
Datasets |  Macro-F1
ReLU |  ABS |  NRPR
MNIST |  0.883$\pm$0.027 |  0.813$\pm$0.011 |  0.960$\pm$0.006
Fashion |  0.825$\pm$0.017 |  0.782$\pm$0.015 |  0.868$\pm$0.009
Kuzushiji |  0.868$\pm$0.024 |  0.790$\pm$0.023 |  0.926$\pm$0.008
SVHN |  0.767$\pm$0.015 |  0.736$\pm$0.006 |  0.867$\pm$0.011
Datasets |  AUC
ReLU |  ABS |  NRPR
MNIST |  0.997$\pm$0.001 |  0.996$\pm$0.001 |  0.998$\pm$0.001
Fashion |  0.974$\pm$0.001 |  0.966$\pm$0.002 |  0.985$\pm$0.002
Kuzushiji |  0.992$\pm$0.002 |  0.984$\pm$0.004 |  0.994$\pm$0.001
SVHN |  0.983$\pm$0.003 |  0.980$\pm$0.002 |  0.981$\pm$0.003

Table 4: Performance comparison between our proposed risk-penalty
regularization and risk-correction functions.

Figure 2: Classification accuracy with different values of the regularization
parameter $\lambda$.

###  4.2 Experimental Results

#### Results on regular-scale datasets.

Table 2 records the accuracy, Macro-F1, and AUC of each method on the six
regular-scale UCI datasets trained with a linear model. From Table 2, we can
observe that our proposed method achieves the best performance in all the
cases, which validates the effectiveness of our proposed method. Besides, the
superiority of our method (using a generalized URE) over the EULAC method
(using a URE relying on the OVR loss) is also clearly demonstrated, which
indicates that our method is not only more flexible on the choice of used loss
functions but also is more effective by substituting other loss functions
rather than the OVR loss.

#### Results on large-scale datasets.

Table 3 records the accuracy, Macro-F1, and AUC of each method on the four
large-scale benchmark datasets. As can be observed from Table 3, our proposed
method also achieves the best performance in all the cases. In addition, the
performance gap between the EULAC method and our proposed method is also
considerably evident. These positive experimental results also support our
proposed method.

###  4.3 Further Analysis

#### Effectiveness of the risk-penalty regularization.

In order to verify the effectiveness of our proposed risk-penalty
regularization, we further compare it with the widely used risk-correction
functions [13, 14] including the _rectified linear unit_ (ReLU) function
$g(z)=\max(0,z)$ and the _absolute value_ (ABS) function $g(z)=|z|$. We
conduct experiments on the four large-scale benchmark datasets and report the
accuracy, Macro-F1, and AUC of each method in Table 4. As can be seen from
Table 4, our proposed risk-penalty regularization significantly outperforms
ReLU and ABS, which demonstrates the superiority of our proposed risk-penalty
regularization over the risk correction scheme.

Figure 3: (a)-(b): Influence of the mixture proportion $\theta$ ($\lozenge$
denotes the empirically estimated mixture proportion $\hat{\theta}$); (c)-(d):
Ability to handle class prior shift.

Figure 4: Test performance on four regular-scale datasets when the number of
unlabeled examples increases.

#### Regularization parameter analysis.

To show the concrete effect of our risk-penalty regularization, we further
conduct parameter sensitivity analysis of the regularization parameter
$\lambda$ on four datasets. Specifically, $\lambda$ is varied in
$\\{0,0.2,0.4,\dots,1.8,2\\}$ ($\lambda=0$ means that the risk-penalty
regularization is not used). From Figure 2, we can find that the risk-penalty
regularization indeed improves the learning performance and the best
performance is achieved at some intermediate value of $\lambda$, which
suggests that the regularization plays an important role.

#### Influence of the mixture proportion.

For the mixture parameter $\theta$, we follow Zhang et al. [4] to empirically
estimate $\theta$ by using the kernel mean embedding method [27] on regular
datasets. To show the influence of the mixture proportion $\theta$, we conduct
experiments on the Usps and Optdigits datasets by varying the preseted mixture
proportion $\hat{\theta}$ from 0.1 to 1 under different values of the true
mixture proportion $\theta$. As shown in Figure 3 (a)-(b), the true mixture
proportion can be accurately estimated in most cases.

#### Handling class prior shift.

In order to verify the ability of our proposed method to handle more complex
learning environments, we further conduct experiments on Usps and Optdigits
with class prior shift. Specifically, we select $\\{1,2,3,4,5\\}$ as known
classes with prior 0.2 per class in labeled data and $\\{6,7,8,9,10\\}$ as
augmented classes with prior 0.1 per class in test and unlabeled data. As for
the prior shift in the test distribution, we reset the prior of five known
classes to
$\\{1-\alpha,1-\frac{\alpha}{2},1,1+\frac{\alpha}{2},1+\frac{\alpha}{2}\\}\times
0.1$, where $\alpha$ controls shift intensity and is selected in
$\\{0,0.3,0.5,0.7,0.9\\}$. Figure 3 (c)-(d) reports the accuracy for NRPR
(ignoring class prior shift) and NRPR-shift (considering class prior shift in
model training according to our derived Theorem 3). As shown in Figure 3
(c)-(d), when the shift intensity increases, performance of NRPR rapidly
decreases while NRPR-shift retains satisfactory performance even with a high
shift intensity. This observation suggests that our proposed NRPR-shift method
could well handle changing learning environments.

#### Performance of increasing unlabeled examples.

As shown in Theorem 2, the performance of our NRPR method is expected to be
improved if more unlabeled examples are provided. To empirically validate such
a theoretical finding, we conduct experiments on four regular-scale datasets
by changing the number of unlabeled examples from 100 to 1200. As shown in
Figure 4, the accuracy, Macro-F1, and AUC of our NRPR method generally
increases given more unlabeled examples. This observation clearly supports the
derived estimation error bound in Theorem 2.

##  5 Related Work

In this section, we discuss some research topics and studies that are relevant
to our work.

#### Class-incremental learning.

As many practical machine learning systems require the ability to continually
learn new knowledge, _class-incremental learning_ (CIL) [28, 29] was proposed
to handling the increasing number of classes. _Learning with augmented
classes_ (LAC) [10, 4, 30], the problem studied in this paper, is a main task
in CIL. The previous research on LAC [10] showed that unlabeled data can be
exploited to enhance the performance of LAC. Furthermore, Zhang et al. [4]
showed that given unlabeled data, an unbiased risk estimator (URE) can be
derived, which can be minimized for LAC with theoretical guarantees.

#### Open-set recognition.

In _open-set recognition_ (OSR) [31], new classes unseen in training the phase
could appear in the test phase, and the learned classifier is required to not
only accurately classify known classes but also effectively deal with unknown
classes. Therefore, OSR can be seen as a cousin of the LAC problem in the
computer vision and pattern recognition communities. Most studies on OSR aim
to explore the relationship between known and augmented classes by using
specific techniques, such as the open space risk [32], nearest neighbor
approach [33], and extreme value theory [23]. It is noteworthy that many OSR
methods utilized the domain knowledge, while our work focuses on a general
setting without additional information.

#### Multi-class positive-unlabeled learning.

Learning from multi-class positive-unlabeled data [34, 35] is similar to the
LAC problem with unlabeled data, by taking the known classes as the multi-
class positive. Although our work shares similarity with the two studies [34,
35], our LAC risk derived in a different context brings novel understandings
for the LAC and can handle more complex environments (i.e., class prior
shift), while they assumed the class priors to be known.

##  6 Conclusion

In this paper, we studied the problem of _learning with augmented classes_
(LAC). To solve this problem, we proposed a generalized _unbiased risk
estimator_ (URE) that can be equipped with arbitrary loss functions while
maintaining the theoretical guarantees, given unlabeled data for LAC. We
showed that our generalized URE can recover the URE proposed by the previous
study [4]. We also established an estimation error bound, which achieves the
optimal parametric convergence rate. To alleviate the issue of negative
empirical risk commonly encountered by previous studies, we further proposed a
novel risk-penalty regularization term. Comprehensive experimental results
clearly verified the effectiveness of our proposed method. In future work, it
would be interesting to develop more powerful regularization techniques for
further improving the performance of our proposed method.

##  7 Acknowledgments

This work is supported by the National Natural Science Foundation of China
(Grant No. 62106028), Chongqing Overseas Chinese Entrepreneurship and
Innovation Support Program, and CAAI-Huawei MindSpore Open Fund.

## References

  * [1] M. Sugiyama and M. Kawanabe, Machine learning in non-stationary environments: Introduction to covariate shift adaptation.  MIT press, 2012.
  * [2] J. Gama, I. Žliobaitė, A. Bifet, M. Pechenizkiy, and A. Bouchachia, “A survey on concept drift adaptation,” ACM Computing Surveys, vol. 46, no. 4, pp. 1–37, 2014.
  * [3] P. Zhao, X. Wang, S. Xie, L. Guo, and Z.-H. Zhou, “Distribution-free one-pass learning,” IEEE Transactions on Knowledge and Data Engineering, vol. 33, no. 3, pp. 951–963, 2019.
  * [4] Y.-J. Zhang, P. Zhao, L. Ma, and Z.-H. Zhou, “An unbiased risk estimator for learning with augmented classes,” in NeurIPS, pp. 10247–10258, 2020.
  * [5] F. T. Liu, K. M. Ting, and Z.-H. Zhou, “Isolation forest,” in ICDM, pp. 413–422, 2008.
  * [6] B. Schölkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson, “Estimating the support of a high-dimensional distribution,” Neural Computation, vol. 13, no. 7, pp. 1443–1471, 2001.
  * [7] D. M. Tax and R. P. Duin, “Support vector data description,” Machine Learning, vol. 54, no. 1, pp. 45–66, 2004.
  * [8] E. Parzen, “On estimation of a probability density function and mode,” The Annals of Mathematical Statistics, vol. 33, no. 3, pp. 1065–1076, 1962.
  * [9] J. Kim and C. D. Scott, “Robust kernel density estimation,” Journal of Machine Learning Research, vol. 13, no. 1, pp. 2529–2565, 2012.
  * [10] Q. Da, Y. Yu, and Z.-H. Zhou, “Learning with augmented class by exploiting unlabeled data,” in AAAI, 2014.
  * [11] P. L. Bartlett and S. Mendelson, “Rademacher and gaussian complexities: Risk bounds and structural results,” Journal of Machine Learning Research, vol. 3, no. 11, pp. 463–482, 2002.
  * [12] H. Bao, G. Niu, and M. Sugiyama, “Classification from pairwise similarity and unlabeled data,” in ICML, pp. 452–461, 2018.
  * [13] R. Kiryo, G. Niu, M. C. Du Plessis, and M. Sugiyama, “Positive-unlabeled learning with non-negative risk estimator,” in NeurIPS, pp. 1675–1685, 2017.
  * [14] N. Lu, T. Zhang, G. Niu, and M. Sugiyama, “Mitigating overfitting in supervised classification from two unlabeled datasets: A consistent risk correction approach,” in AISTATS, pp. 1115–1125, 2020.
  * [15] L. Feng, S. Shu, N. Lu, B. Han, M. Xu, G. Niu, B. An, and M. Sugiyama, “Pointwise binary classification with pairwise confidence comparisons,” in ICML, 2021.
  * [16] D. Dua, C. Graff, et al., “Uci machine learning repository,” URL http://archive. ics. uci. edu/ml, vol. 7, no. 1, 2017.
  * [17] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
  * [18] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017.
  * [19] T. Clanuwat, M. Bober-Irizar, A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha, “Deep learning for classical japanese literature,” arXiv preprint arXiv:1812.01718, 2018.
  * [20] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng, “Reading digits in natural images with unsupervised feature learning,” in NeurIPS Workshop, 2011.
  * [21] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” in ICLR, May 2015.
  * [22] R. Rifkin and A. Klautau, “In defense of one-vs-all classification,” Journal of Machine Learning Research, vol. 5, pp. 101–141, 2004.
  * [23] E. M. Rudd, L. P. Jain, W. J. Scheirer, and T. E. Boult, “The extreme value machine,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 3, pp. 762–768, 2017.
  * [24] A. Bendale and T. E. Boult, “Towards open set deep networks,” in CVPR, pp. 1563–1572, 2016.
  * [25] Z. Zhang and M. Sabuncu, “Generalized cross entropy loss for training deep neural networks with noisy labels,” in NeurIPS, 2018.
  * [26] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in ICLR, 2015.
  * [27] H. Ramaswamy, C. Scott, and A. Tewari, “Mixture proportion estimation via kernel embeddings of distributions,” in ICML, pp. 2052–2060, 2016.
  * [28] Z.-H. Zhou and Z.-Q. Chen, “Hybrid decision tree,” Knowledge-based systems, vol. 15, no. 8, pp. 515–528, 2002.
  * [29] X. Tao, X. Hong, X. Chang, S. Dong, X. Wei, and Y. Gong, “Few-shot class-incremental learning,” in CVPR, June 2020.
  * [30] S.-Y. Ding, X.-Y. Liu, and M.-L. Zhang, “Imbalanced augmented class learning with unlabeled data by label confidence propagation,” in ICDM, pp. 79–88, IEEE, 2018.
  * [31] C. Geng, S.-j. Huang, and S. Chen, “Recent advances in open set recognition: A survey,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 43, no. 10, pp. 3614–3631, 2020.
  * [32] W. J. Scheirer, L. P. Jain, and T. E. Boult, “Probability models for open set recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 36, no. 11, pp. 2317–2324, 2014.
  * [33] P. R. Mendes Júnior, R. M. De Souza, R. d. O. Werneck, B. V. Stein, D. V. Pazinato, W. R. de Almeida, O. A. Penatti, R. d. S. Torres, and A. Rocha, “Nearest neighbors distance ratio open-set classifier,” Machine Learning, vol. 106, no. 3, pp. 359–386, 2017.
  * [34] Y. Xu, C. Xu, C. Xu, and D. Tao, “Multi-positive and unlabeled learning.,” in IJCAI, pp. 3182–3188, 2017.
  * [35] S. Shu, Z. Lin, Y. Yan, and L. Li, “Learning from multi-class positive and unlabeled data,” in ICDM, pp. 1256–1261, 2020.
  * [36] C. McDiarmid, “On the method of bounded differences,” Surveys in Combinatorics, vol. 141, no. 1, pp. 148–188, 1989.
  * [37] M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning.  MIT Press, 2012.
  * [38] A. Maurer, “A vector-contraction inequality for rademacher complexities,” in International Conference on Algorithmic Learning Theory, pp. 3–17, Springer, 2016.

##  Appendix A Proof of Theorem 1

Recall that

$\displaystyle R(f)=\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),y)]+(1-\theta)\mathbb{E}_{(\bm{x},y=\mathtt{ac})\sim
P_{\mathrm{ac}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})],$

we can observe that there are two parts in the classification risk $R(f)$,
including the risk of know classes $R_{\mathrm{kc}}=\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),y)]$ and the risk of the augmented
class $R_{\mathrm{ac}}=\mathbb{E}_{(\bm{x},y=\mathtt{ac})\sim
P_{\mathrm{ac}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]$. Then $R(f)$ can be
represented by $R(f)=\theta R_{\mathrm{kc}}(f)+(1-\theta)R_{\mathrm{ac}}(f)$.

According to $P_{\mathrm{te}}=\theta\cdot P_{\mathrm{kc}}+(1-\theta)\cdot
P_{\mathrm{ac}}$, we have $(1-\theta)P_{\mathrm{ac}}=P_{\mathrm{te}}-\theta
P_{\mathrm{kc}}$. Thus we can express $(1-\theta)R_{\mathrm{ac}}(f)$ by

$\displaystyle(1-\theta)\mathbb{E}_{(\bm{x},y=\mathtt{ac})\sim
P_{\mathrm{ac}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]=\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{te}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]-\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})].$

By substituting the above equality into $R(f)$, we have

$\displaystyle R(f)$ $\displaystyle=\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),y)]+\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{te}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]-\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]$
$\displaystyle=\theta\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}[\mathcal{L}(f(\bm{x}),y)-\mathcal{L}(f(\bm{x}),\mathtt{ac})]+\mathbb{E}_{\bm{x}\sim
P_{\mathrm{te}}}[\mathcal{L}(f(\bm{x}),\mathtt{ac})]$
$\displaystyle=R_{\mathrm{LAC}}(f),$

which completes the proof of Theorem 1.∎

##  Appendix B Proof of Theorem 2

Recall that the unbiased risk estimator we derived is represented as follows:

$\displaystyle\widehat{R}_{\mathrm{LAC}}(f)$
$\displaystyle=\frac{\theta}{n}\sum\nolimits_{i=1}^{n}\Big{(}\mathcal{L}(f(\bm{x}_{i}),y_{i})-\mathcal{L}(f(\bm{x}_{i}),\mathtt{ac})\Big{)}+\frac{1}{m}\sum\nolimits_{j=1}^{m}\mathcal{L}(f(\bm{x}_{j}),\mathtt{ac}).$

Let us further introduce

$\displaystyle\widehat{R}_{\mathrm{kac}}(f)$
$\displaystyle=\frac{\theta}{n}\sum\nolimits_{i=1}^{n}\Big{(}\mathcal{L}(f(\bm{x}_{i}),y_{i})-\mathcal{L}(f(\bm{x}_{i}),\mathtt{ac})\Big{)},$
$\displaystyle\widehat{R}_{\mathrm{tac}}(f)$
$\displaystyle=\frac{1}{m}\sum\nolimits_{j=1}^{m}\mathcal{L}(f(\bm{x}_{j}),\mathtt{ac}),$
$\displaystyle{R}_{\mathrm{kac}}(f)$ $\displaystyle=\mathbb{E}_{(\bm{x},y)\sim
P_{\mathrm{kc}}}\big{[}\mathcal{L}(f(\bm{x}),y)-\mathcal{L}(f(\bm{x}),\mathtt{ac})\big{]},$
$\displaystyle{R}_{\mathrm{tac}}(f)$ $\displaystyle=\mathbb{E}_{\bm{x}\sim
P_{\mathrm{te}}}\big{[}\mathcal{L}(f(\bm{x}),\mathtt{ac})\big{]}.$

Therefore, we have

$\displaystyle\widehat{R}_{\mathrm{LAC}}(f)$
$\displaystyle=\theta\cdot\widehat{R}_{\mathrm{kac}}(f)+\widehat{R}_{\mathrm{tac}},$
$\displaystyle{R}_{\mathrm{LAC}}(f)$
$\displaystyle=\theta\cdot{R}_{\mathrm{kac}}(f)+{R}_{\mathrm{tac}}.$

Thus we obtain

$\displaystyle\sup_{f\in\mathcal{F}}\left|{R}_{\mathrm{LAC}}(f)-\widehat{R}_{\mathrm{LAC}}(f)\right|$
$\displaystyle\leq\theta\cdot\sup_{f\in\mathcal{F}}\left|{R}_{\mathrm{kac}}(f)-\widehat{R}_{\mathrm{kac}}(f)\right|+\sup_{f\in\mathcal{F}}\left|{R}_{\mathrm{tac}}(f)-\widehat{R}_{\mathrm{tac}}(f)\right|.$

Hence the problem becomes how to find an upper bound of each term in the right
hand side of the above inequality.

######  Lemma 1.

Assume the multi-class loss function $\mathcal{L}(f(\bm{x}),y)$ is
$\rho$-Lipschitz ($0<\rho<\infty$) with respect to $f(\bm{x})$ for all
$y\in\mathcal{Y}$ and upper bounded by a constant $C_{\mathcal{L}}$, i.e.,
$C_{\mathcal{L}}=\sup_{\bm{x}\in\mathcal{X},y\in\mathcal{Y},f\in\mathcal{F}}\mathcal{L}(f(\bm{x}),y)$.
Then, for any $\delta>0$, with probability at least $1-\delta$, we have

$\displaystyle\sup_{f\in\mathcal{F}}\left|{R}_{\mathrm{kac}}(f)\\!-\\!\widehat{R}_{\mathrm{kac}}(f)\right|\\!\leq\\!4\sqrt{2}\rho(k+1)\frac{C_{\mathcal{F}}}{n}\\!+\\!2C_{\mathcal{L}}\sqrt{\frac{\log\frac{2}{\delta}}{2n}}.$

###### Proof.

Suppose an example in $\widehat{R}_{\mathrm{kac}}(f)$ is replaced by another
arbitrary example, then the change of
$\sup_{f\in\mathcal{F}}\big{(}{R}_{\mathrm{kac}}(f)-\widehat{R}_{\mathrm{kac}}(f)\big{)}$
is no greater than $\frac{2C_{\mathcal{L}}}{n}$. Then, by applying the
Diarmid’s inequality [36], for any $\delta>0$, with probability at least
$1-\frac{\delta}{2}$,

$\displaystyle\sup\nolimits_{f\in\mathcal{F}}\big{(}{R}_{\mathrm{kac}}(f)-\widehat{R}_{\mathrm{kac}}(f)\big{)}$
$\displaystyle\leq\mathbb{E}\Big{[}\sup\nolimits_{f\in\mathcal{F}}\big{(}{R}_{\mathrm{kac}}(f)-\widehat{R}_{\mathrm{kac}}(f)\big{)}\Big{]}+2C_{\mathcal{L}}\sqrt{\frac{\log\frac{2}{\delta}}{2n}}.$

Besides, it is routine [37] to show

$\displaystyle\mathbb{E}\Big{[}\sup\nolimits_{f\in\mathcal{F}}\big{(}{R}_{\mathrm{kac}}(f)-\widehat{R}_{\mathrm{kac}}(f)\big{)}\Big{]}\leq
4\mathfrak{R}_{n}(\mathcal{L}\circ\mathcal{F}).$

Then, we need to upper bound
${\mathfrak{R}}_{n}(\mathcal{L}\circ\mathcal{F})$. Since $\mathcal{L}$ is
$\rho$-Lipschitz with respect to $f(\bm{x})$, according to the _Rademacher
vector contraction inequality_ [38], we have

$\displaystyle\widehat{\mathfrak{R}}_{n}(\mathcal{L}\circ\mathcal{F})\leq\sqrt{2}\rho\sum\nolimits_{y=1}^{k+1}\widehat{\mathfrak{R}}_{n}(\mathcal{F}_{y}).$

By taking the expectation of
$\widehat{\mathfrak{R}}_{n}(\mathcal{L}\circ\mathcal{F})$ and
$\widehat{\mathfrak{R}}_{n}(\mathcal{F}_{y})$ over $p(\bm{x})$, we have
${\mathfrak{R}}_{n}(\mathcal{L}\circ\mathcal{F})\leq\sqrt{2}\rho\sum_{y=1}^{k+1}{\mathfrak{R}}_{n}(\mathcal{F}_{y})$.
By further considering $\mathfrak{R}_{n}(\mathcal{F}_{y})\leq
C_{\mathcal{F}}/\sqrt{n}$, then we have for any $\delta>0$, with probability
at least $1-\frac{\delta}{2}$,

$\displaystyle\sup_{f\in\mathcal{F}}\\!\big{(}{R}_{\mathrm{kac}}(f)\\!-\\!\widehat{R}_{\mathrm{kac}}(f)\big{)}\\!\leq\\!4\sqrt{2}\rho(k+1)\frac{C_{\mathcal{F}}}{\sqrt{n}}\\!+\\!2C_{\mathcal{L}}\sqrt{\frac{\log\frac{2}{\delta}}{2n}}.$

By further considering the other side
$\sup_{f\in\mathcal{F}}\big{(}\widehat{R}_{\mathrm{kac}}(f)-{R}_{\mathrm{kac}}(f)\big{)}$,
we have for $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\sup_{f\in\mathcal{F}}\left|{R}_{\mathrm{kac}}(f)\\!-\\!\widehat{R}_{\mathrm{kac}}(f)\right|\\!\leq\\!\
4\sqrt{2}\rho(k\\!+\\!1)\frac{C_{\mathcal{F}}}{\sqrt{n}}\\!+\\!2C_{\mathcal{L}}\sqrt{\frac{\log\frac{2}{\delta}}{2n}},$

which completes the proof of Lemma 1. ∎

######  Lemma 2.

Assume the multi-class loss function $\mathcal{L}(f(\bm{x}),y)$ is
$\rho$-Lipschitz ($0<\rho<\infty$) with respect to $f(\bm{x})$ for all
$y\in\mathcal{Y}$ and upper bounded by a constant $C_{\mathcal{L}}$, i.e.,
$C_{\mathcal{L}}=\sup_{\bm{x}\in\mathcal{X},y\in\mathcal{Y},f\in\mathcal{F}}\mathcal{L}(f(\bm{x}),y)$.
Then, for any $\delta>0$, with probability at least $1-\delta$, we have

$\displaystyle\sup_{f\in\mathcal{F}}\left|{R}_{\mathrm{tac}}(f)-\widehat{R}_{\mathrm{tac}}(f)\right|\\!\leq\\!2\sqrt{2}\rho(k+1)\frac{C_{\mathcal{F}}}{\sqrt{m}}+C_{\mathcal{L}}\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$

###### Proof.

Lemma 2 can be proved similarly as Lemma 1, hence we omit the proof. ∎

By combining Lemma 1 and Lemma 2 together, for $\delta>0$, with probability at
least $1-\delta$, we have

$\displaystyle\sup\nolimits_{f\in\mathcal{F}}\left|R_{\mathrm{LAC}}(f)-\widehat{R}_{\mathrm{LAC}}(f)\right|$
$\displaystyle\leq
C_{k,\rho,\delta}(\frac{2\theta}{\sqrt{n}}+\frac{1}{\sqrt{m}}),$

where
$C_{k,\rho,\delta}=(2\sqrt{2}\rho(k+1)C_{\mathcal{F}}+C_{\mathcal{L}}\sqrt{\frac{\log\frac{4}{\delta}}{2}})$.

In addition, we can obtain

$\displaystyle R(\widehat{f})-R(f^{\star})$
$\displaystyle=R_{\mathrm{LAC}}(\widehat{f})-R_{\mathrm{LAC}}(f^{\star})$
$\displaystyle=R_{\mathrm{LAC}}(\widehat{f})-\widehat{R}_{\mathrm{LAC}}(\widehat{f})+\widehat{R}_{\mathrm{LAC}}(\widehat{f})-R_{\mathrm{LAC}}({f}^{\star})$
$\displaystyle\leq
R_{\mathrm{LAC}}(\widehat{f})-\widehat{R}_{\mathrm{LAC}}(\widehat{f})+R_{\mathrm{LAC}}(\widehat{f})-R_{\mathrm{LAC}}({f}^{\star})$
$\displaystyle\leq
2\sup\nolimits_{f\in\mathcal{F}}\left|R_{\mathrm{LAC}}(f)-\widehat{R}_{\mathrm{LAC}}(f)\right|.$

Therefore, for $\delta>0$, with probability at least $1-\delta$, we have

$\displaystyle R(\widehat{f})-R(f^{\star})$ $\displaystyle\leq
C_{k,\rho,\delta}(\frac{2\theta}{\sqrt{n}}+\frac{1}{\sqrt{m}}),$

where
$C_{k,\rho,\delta}=(4\sqrt{2}\rho(k+1)C_{\mathcal{F}}+2C_{\mathcal{L}}\sqrt{\frac{\log\frac{4}{\delta}}{2}})$.
∎