# Weakly Separated Bessel Systems of Model Spaces

Alberto Dayan  Department of Mathematics
Washington University in St. Louis,
One Brookings Drive, St. Louis, MO 63130, USA<EMAIL_ADDRESS>
###### Abstract.

We show that any weakly separated Bessel system of model spaces in the Hardy
space on the unit disc is a Riesz system and we highlight some applications to
interpolating sequences of matrices. This will be done without using the
recent solution of the Feichtinger conjecture, whose natural generalization to
multi-dimensional model sub-spaces of $\mathrm{H}^{2}$ turns out to be false.

The author was partially supported by National Science Foundation Grant DMS
1565243

##  1\. Introduction

Let $\mathrm{H}^{2}$ be the Hardy space on the unit disc $\mathbb{D}$, that
is, the reproducing kernel Hilbert space of those power series centered at the
origin with square-summable Taylor coefficients. Its kernel $s$ is the well-
studied _Szegö kernel_

$s_{w}(z):=\frac{1}{1-\overline{w}z}\qquad w,z\in\mathbb{D}$

and its multiplier algebra can be identified isometrically with
$\mathrm{H}^{\infty}$, the algebra of bounded holomorphic functions on
$\mathbb{D}$. A key role for the study of the function theory and the
hyperbolic geometry of the unit disc is played by _inner functions_ , which
are those bounded analytic functions on the unit disc with an unimodular
radial limit almost everywhere on the unit circle. Given an inner function
$\Theta$, one can define the associated _model space_

$H_{\Theta}:=\mathrm{H}^{2}\ominus\Theta\mathrm{H}^{2}$

as the orthogonal complement in the Hardy space of all multiples of $\Theta$
in $\mathrm{H}^{2}$. A great treatment of the main properties of model spaces,
together with their interactions with operator theory on spaces of analytic
functions, can be found in [8].
Any function in $\mathrm{H}^{2}$ that vanishes with multiplicity $m$ at a
point $\lambda$ in $\mathbb{D}$ is divisible in $\mathrm{H}^{2}$ by a
_Blaschke factor_ , i.e., an inner function of the form $b_{\lambda}^{m}$,
where

$b_{\lambda}(z):=\frac{\lambda-z}{1-\overline{\lambda}z}\qquad
z\in\mathbb{D}.$

Therefore the model space associated to $b_{\lambda}^{m}$ is $m$-dimensional
and it is spanned by the kernels at $\lambda$ that represent up to $m-1$
derivatives of any $\mathrm{H}^{2}$ function at $\lambda$, that is,

(1.1)
$H_{b_{\lambda}^{m}}=\mathrm{span}\left\\{s_{\lambda},\frac{\partial\leavevmode\nobreak\
s_{\lambda}}{\partial\overline{w}},\dots,\frac{\partial^{m-1}\leavevmode\nobreak\
s_{\lambda}}{\partial\overline{w}^{m-1}}\right\\}.$

Since a model space is a subspace of $\mathrm{H}^{2}$ generated by an inner
function, it comes natural to ask whether function theoretical properties of a
sequence of inner functions $(\Theta_{n})_{n\in\mathbb{N}}$ translate to
Euclidean properties for the sequence $(H_{\Theta_{n}})_{n\in\mathbb{N}}$. Out
of the many results that constitute such a valuable dictionary between
operator theory and function theory, one of the most significant for the
purposes of this note can be found in [10, Th. 3.2.14]:

######  Theorem 1.1.

Let $(\Theta_{n})_{n\in\mathbb{N}}$ be a sequence of inner functions such that
$\Theta:=\prod_{n=1}^{\infty}\Theta_{n}$ converges uniformly on any compact
subset of $\mathbb{D}$. The following are equivalent:

(i):

For any bounded sequence $(\phi_{n})_{n\in\mathbb{N}}$ in
$\mathrm{H}^{\infty}$ there exists a function $\phi$ in $\mathrm{H}^{\infty}$
such that

(1.2) $\phi-\phi_{n}\in\Theta_{n}\mathrm{H}^{2},\qquad n\in\mathbb{N};$

(ii):

There exists a $C\geq 1$ such that, for any sequence
$(h_{n})_{n\in\mathbb{N}}$ of unit vectors in $\mathrm{H}^{2}$ such that
$h_{n}$ belongs to $H_{\Theta_{n}}$ for any $n$ in $\mathbb{N}$ and for any
$(a_{n})_{n\in\mathbb{N}}$ in $l^{2}$,

(1.3) $\frac{1}{C^{2}}\leavevmode\nobreak\
\sum_{n\in\mathbb{N}}|a_{n}|^{2}\leq\left|\left|\sum_{n\in\mathbb{N}}a_{n}h_{n}\right|\right|^{2}\leq
C^{2}\leavevmode\nobreak\ \sum_{n\in\mathbb{N}}|a_{n}|^{2};$

(iii):

There exists a positive $\delta$ such that, for any $z$ in $\mathbb{D}$,

$|\Theta(z)|\geq\delta\leavevmode\nobreak\
\inf_{n\in\mathbb{N}}|\Theta_{n}(z)|.$

Note that (1.2) is stated in [10, Th. 3.2.14] as

$\phi-\phi_{n}\in\Theta_{n}\mathrm{H}^{\infty},\qquad n\in\mathbb{N}.$

This is equivalent to (1.2), since $\mathrm{H}^{\infty}$ is contained in
$\mathrm{H}^{2}$ and since, if for any $n$ there exists a $g$ in
$\mathrm{H}^{2}$ such that

$\theta_{n}\leavevmode\nobreak\ g=\phi-\phi_{n}\in\mathrm{H}^{\infty},$

then the radial limit of $|g|$ on the unit circle must be bounded by
$|\phi-\phi_{n}|$, since $\Theta_{n}$ is inner, and therefore $g$ is actually
in $\mathrm{H}^{\infty}$. A sequence of closed subspaces
$(H_{n})_{n\in\mathbb{N}}$ of a Hilbert space $\mathcal{H}$ that satisfies
(ii) is called a Riesz system, and the least $C$ for which (1.3) holds is the
_Riesz bound_ of the sequence. If the least $C$ such that the right hand side
of (1.3) holds is finite then $(H_{n})_{n\in\mathbb{N}}$ is a Bessel systems
with _Bessel bound_ $C$. On the other hand, condition (iii) is equivalent to

(1.4) $\sup_{n\in\mathbb{N}}\prod_{j\neq n}|\Theta_{j}(z)|\geq\delta,$

to hold uniformly in $z$. Indeed, condition (iii) above states that there
exists a positive $\delta$ such that, for any $z$ in $\mathbb{D}$ and for any
$0<\varepsilon<\delta$ there exists a $n$ in $\mathbb{N}$ such that

$|\Theta_{n}(z)|\leq\frac{|\Theta(z)|}{\delta-\varepsilon},$

or, equivalently, such that

$\prod_{j\neq n}|\Theta_{j}(z)|\geq\delta-\varepsilon,$

which yields (1.4) (in case $\Theta_{n}(z)=0$, take a limit for $w$ going to
$z$ and then use continuity).
Moreover, condition (iii) is related in [11, Lec. IX] to separation conditions
on the subspaces in $(H_{\Theta_{n}})_{n\in\mathbb{N}}$, being equivalent to
asserting that the sine of the angle between any model space and the closure
of the linear span of all the others is uniformly bounded below:

(1.5) $\inf_{n\in\mathbb{N}}\sin\left(H_{\Theta_{n}},\overline{\underset{j\neq
n}{\mathrm{span}}}\\{H_{\Theta_{j}}\\}\right)>0.$

Here the sine between two closed sub-spaces $K_{1}$ and $K_{2}$ of a Hilbert
space $\mathcal{H}$ is the least sine of the angle between two vectors chosen
in $K_{1}$ and $K_{2}$ or, equivalently,

$\sin(K_{1},K_{2})=||T||^{-1},$

where

$\begin{split}T\colon\mathrm{span}\\{K_{1},K_{2}\\}&\mapsto\mathrm{span}\\{K_{1},K_{2}\\}\\\
T_{|K_{1}}=Id_{K_{1}}&\qquad T_{|K_{2}}=0.\end{split}$

If (1.5) holds, we say that $(H_{\Theta_{n}})_{n\in\mathbb{N}}$ is strongly
separated, whereas weak separation will correspond to an uniform bound from
below for the angle between any pair of distinct model spaces:

(1.6) $\inf_{n\neq j}\sin(H_{\Theta_{n}},H_{\Theta_{j}})>0.$

Suppose now that $\Theta_{n}=b_{\lambda_{n}}^{m_{n}}$, for some sequence
$(\lambda_{n})_{n\in\mathbb{N}}$ in the unit disc and some sequence
$(m_{n})_{n\in\mathbb{N}}$ of positive integers. Condition (i) of Theorem 1.1
becomes then an _interpolation property_ : for any bounded sequence
$(\phi_{n})_{n\in\mathbb{N}}$ in $\mathrm{H}^{\infty}$ there exists a bounded
analytic function $\phi$ that, for any $n$ in $\mathbb{N}$, agrees with
$\phi_{n}$ at $\lambda_{n}$ up to its $m_{n}-1^{\text{st}}$ derivative.
Theorem 1.1 is therefore a great example of how the deep interconnection
between operator theory and function theory greatly helps the studying and the
understanding of _interpolating sequences_.

Let $\mathcal{H}_{k}$ be a reproducing kernel Hilbert space of analytic
functions on a domain $D$ of $\mathbb{C}^{d}$, and let $\mathcal{M}_{k}$ be
its multiplier algebra. A sequence $Z=(z_{n})_{n\in\mathbb{N}}$ in $D$ is
interpolating for $\mathcal{M}_{k}$ if for any bounded sequence
$(w_{n})_{n\in\mathbb{N}}$ in $\mathbb{C}$ there exists a function $\phi$ in
$\mathcal{M}_{k}$ such that $\phi(z_{n})=w_{n}$ for any $n$ in $\mathbb{N}$.
Intuitively, an interpolating sequence is a separated sequence, as we need to
be able to specify the values of $\phi$ _arbitrarily_ at the nodes
$(z_{n})_{n\in\mathbb{N}}$. It is also not surprising that the separation
conditions we will look at depend on the kernel $k$: $Z$ is a weakly separated
sequence if there exists a positive $M$ such that, for any $n\neq j$ in
$\mathbb{N}$, there exists a function $\phi_{n,j}$ whose norm in
$\mathcal{M}_{k}$ doesn’t exceed $M$ and that separates $z_{n}$ and $z_{j}$,
that is,

$\phi_{n,j}(z_{n})=1\qquad\phi_{n,j}(z_{j})=0.$

A celebrated work of Carleson,[4], characterized interpolating sequences for
$\mathrm{H}^{\infty}$:

######  Theorem 1.2.

A sequence $\Lambda=(\lambda_{n})_{n\in\mathbb{N}}$ is interpolating for
$\mathrm{H}^{\infty}$ if and only if it is weakly separated and the measure

$\mu_{\Lambda}:=\sum_{n\in\mathbb{N}}(1-|\lambda_{n}|^{2})\delta_{\lambda_{n}}$

satisfies the embedding condition

(1.7) $||f||_{L^{2}(\mathbb{D},\mu_{\Lambda})}\leq
C_{\Lambda}\leavevmode\nobreak\ ||f||_{\mathrm{H}^{2}}\qquad
f\in\mathrm{H}^{2}.$

A measure $\mu$ on a domain $D$ that embeds continuously a reproducing kernel
Hilbert space $\mathcal{H}_{k}$ on $D$ into $L^{2}(D,\mu)$ is called a
Carleson measure for $\mathcal{H}_{k}$. One can find in [4] a characterization
of Carleson measures for $\mathrm{H}^{2}$ that involves a one-box condition,
and hence the hyperbolic geometry of the unit disc. It turns out that (1.7)
holds if and only if the sequence of all lines through the kernels
$(s_{\lambda_{n}})_{n\in\mathbb{N}}$ (that is, the sequence one dimensional
sub-spaces spanned by the kernels $s_{\lambda_{n}}$) is a Bessel system,[1,
Prop. 9.5], highlighting once again a correspondence between the hyperbolic
geometry of the unit disc and the Euclidean geometry of the Hardy space.
Moreover, such a characterization of Carleson measures in terms of Bessel
systems allows to extend Theorem 1.2 to some multiplier algebra other than
$\mathrm{H}^{\infty}$. For example, a class of multiplier algebras for which
an analogous of Theorem 1.2 holds is the one associated with _complete Pick
kernels_. One of the most important properties that connects interpolating
sequence to the study of related Hilbert spaces is the fact that, for any
multiplier $\phi$ in $\mathcal{M}_{k}$, any kernel function $k_{z}$ in
$\mathcal{H}_{k}$ is an eigenfunction of the adjoint of the multiplication
operator $M_{\phi}$:

(1.8) $M^{*}_{\phi}(k_{z})=\overline{\phi(z)}\leavevmode\nobreak\ k_{z}\qquad
z\in D,$

as a straightforward computation using the property of adjoints shows. In
particular, if $M_{\phi}$ is a contraction and $\phi(z_{n})=w_{n}$ for any $n$
in $\mathbb{N}$, then the linear map $T$ from
$S_{Z}:=\overline{\underset{n\in\mathbb{N}}{\mathrm{span}}}\\{k_{z_{n}}\\}$ to
itself given by

(1.9) $T(k_{z_{n}}):=\overline{w_{n}}\leavevmode\nobreak\ k_{z_{n}}\qquad
n\in\mathbb{N}$

is a contraction. A reproducing kernel Hilbert space is said to have the Pick
property if the existence of such a contraction $T$ is also a sufficient
condition for the existence of a function $\phi$ in the unit ball of
$\mathcal{M}_{k}$ such that $\phi(z_{n})=w_{n}$. In particular, this says that
$M^{*}_{\phi}$ is an extension of $T$ to $\mathcal{H}_{k}$ and
$||M^{*}_{\phi}||=||T||$, which implies that any two disjoint sets of points
$Z_{1}$ and $Z_{2}$ can be separated by a function in $\mathcal{M}_{k}$ of
norm at most $M$ if and only if the angle between $S_{Z_{1}}$ and $S_{Z_{2}}$
in $\mathcal{H}_{k}$ is bounded below by $1/M$:

(1.10)
$\sup\left\\{||\phi||_{\mathcal{M}_{k}}\,\big{|}\,\phi_{|Z_{1}}=1,\,\phi_{|Z_{2}}=0\right\\}=\frac{1}{\sin(S_{Z_{1}},S_{Z_{2}})}.$

Moreover,[1, Th. 9.19], this implies that $Z$ is interpolating if and only if
the sequence of lines through the kernels $(k_{z_{n}})_{n\in\mathbb{N}}$ is a
Riesz system.
Since (1.9) being a contraction is equivalent to the infinite matrix

$(1-\overline{w_{n}}w_{j})k_{z_{j}}(z_{n})\qquad n,j\in\mathbb{N}$

being positive semi-definite (i.e., all its finite principal minors are
positive semi-definite), one can extend the Pick property to the case of
_matrix-valued_ functions in $\mathcal{H}_{k}$, by defining $\mathcal{H}_{k}$
to have the _$s\times t$ Pick property_ if whenever $z_{1},\dots,z_{N}$ are
points in $D$ and $W_{1},\dots,W_{N}$ are $s\times t$ matrices such that

$(Id-W_{n}^{*}W_{j})k_{z_{j}}(z_{n})\geq 0$

then there exists a multiplier $\phi$ in the closed unit ball of

$\mathcal{M}(\mathcal{H}_{k}\otimes\mathbb{C}^{t},\mathcal{H}_{k}\otimes\mathbb{C}^{s}):=\left\\{{\bf\phi}=(\phi_{l,r})\,|\,l=1,\dots,s,\,r=1,\dots
t,\,\sup_{{\bf f}\neq 0}\frac{||\phi{\bf
f}||_{\mathcal{H}_{k}\otimes\mathbb{C}^{s}}}{||{\bf
f}||_{\mathcal{H}_{k}\otimes\mathbb{C}^{t}}}<\infty\right\\}$

such that $\phi(z_{i})=W_{i}$, for $i=1,\dots,N$. We say that
$\mathcal{H}_{k}$ has the complete Pick property if it has the $s\times t$
Pick property for any positive integers $s$ and $t$. The Hardy space
$\mathrm{H}^{2}$ has the complete Pick property, as well as some of its
natural generalizations, such as the reproducing kernel Hilbert spaces
$\mathcal{H}_{s}$ on $\mathbb{D}$, $-1\leq s\leq 0$, defined by the kernels

$k^{s}_{w}(z):=\sum_{n=0}^{\infty}(n+1)^{s}(\overline{w}z)^{n}\qquad
z,w\in\mathbb{D}$

and the _Drury-Arveson space_ $\mathrm{H}^{2}_{d}$ on the $d$-dimensional unit
ball $\mathbb{B}_{d}$ defined by the kernel

$b_{w}(z):=\frac{1}{1-\braket{z,w}},\qquad z,w\in\mathbb{B}_{d}.$

For instance, see [1, Ch. 7]. In a recent work, [2], Aleman, Hartz,
M${}^{\text{c}}$Carthy and Richter extended Theorem 1.2 by showing that any
weakly separated sequence $Z$ on a domain $D$ such that the sequence of lines
through the kernels $(k_{z_{n}})_{n\in\mathbb{N}}$ is a Bessel system is an
interpolating sequence for $\mathcal{M}_{k}$, provided that $\mathcal{H}_{k}$
has the complete Pick property. This is done by using the recent positive
answer to the _Feichtinger conjecture_ , which states that any Bessel system
of one-dimensional subspaces is the disjoint union of finitely many Riesz
systems. It has been shown, [5] [13], that the Feichtinger conjecture is
equivalent to many other conjectures in operator theory, including the Paving
conjecture, who had been proved by the well-known work of Marcus, Spielmann
and Srivastava [7].

In [6], the author asked whether the positive answer to the Feichtinger
conjecture can be extended to multi-dimensional model spaces of
$\mathrm{H}^{2}$, that is, if any Bessel system of model spaces is the
disjoint union of finitely many Riesz systems. We show in Section 3.2 that
this is not the case, though any Bessel systems of model spaces satisfying
(1.6) is in fact a Riesz system:

######  Theorem 1.3.

Any weakly separated Bessel system of model spaces in $\mathrm{H}^{2}$ is a
Riesz system.

The motivation for Theorem 1.3 is the study of _interpolating sequences of
matrices_ introduced by the author in [6]. As Section 3 explains in details,
we say that a sequence of square matrices $A=(A_{n})_{n\in\mathbb{N}}$ with
eigenvalues in $\mathbb{D}$ is interpolating if, for any bounded sequence
$(w_{n})_{n\in\mathbb{N}}$ in $\mathbb{C}$, there exists a bounded holomophic
function $\phi$ such that

$\phi(A_{n})=w_{n}\leavevmode\nobreak\ Id.$

If $P_{n}$ is, for any $n$ in $\mathbb{N}$, the minimal polynomial of $A_{n}$,
then

(1.11)
$B_{n}(z):=\frac{P_{n}(z)}{\overline{P_{n}}\left(\frac{1}{\overline{z}}\right)}\qquad
z\in\mathbb{D}$

is a Blaschke product with zeros at the eigenvalues of $A$, and any
$\mathrm{H}^{2}$ function that vanishes at $A_{n}$ is a multiple of $B_{n}$.
Let $H=(H_{n})_{n\in\mathbb{N}}$ be the sequence of model spaces associated to
$(B_{n})_{n\in\mathbb{N}}$. The author extended in [6, Th. 6.6] Theorem 1.2 to
sequences of matrices of uniformly bounded dimensions, by showing that $A$ is
interpolating if and only if $H$ is a weakly separated Bessel system. Theorem
1.3 can be rephrased to drop the extra assumption on the sizes of the matrices
in $A$:

######  Theorem 1.4.

$A$ is interpolating if and only if the sequence $H$ is a weakly separated
Bessel system.

Section 2 deals with the proof of Theorem 1.3. Section 3 provides a brief
summary of the content of [6] and gives an argument for Theorem 1.4, together
with an explicit example of an interpolating sequence of matrices. We also
give in Section 3.2 an example of a sequence of matrices whose associated
sequence of model spaces $(H_{n})_{n\in\mathbb{N}}$ is a Bessel system which
can not be written as the disjoint union of finitely many Riesz systems,
giving a negative answer to a question posed by the author in [6].

The author would like to thank John M${}^{\text{c}}$Carthy for the valuable
suggestions given during all the conversations that led to this work. The
author is also indebted to the reviewer for some extremely important remarks
and suggestions.

##  2\. The Proof of the Main Result

The first main tool for the proof of Theorem 1.3 can be found in [11, Lec.
IX], and relates the sine of the angle between two model spaces
$H_{\Theta_{1}}$ and $H_{\Theta_{2}}$ with the constant in Carleson corona
Theorem:

######  Theorem 2.1.

There exists a constant $c\geq 1$ such that, for any $\Theta_{1}$ and
$\Theta_{2}$ inner functions on $\mathbb{D}$ such that

$\inf_{z\in\mathbb{D}}\max\\{|\Theta_{1}(z)|,|\Theta_{2}(z)|\\}=\delta\geq 0$

then

$\frac{\delta^{3}}{c}\leq\sin(H_{\Theta_{1}},H_{\Theta_{2}})\leq c\delta.$

We are also going to use the following re-statement of the Bessel system
condition:

######  Proposition 2.2.

A sequence $(H_{n})_{n\in\mathbb{N}}$ of closed sub-spaces of a Hilbert space
$\mathcal{H}$ is a Bessel system with Bessel bound $M$ if and only if, for any
sequence $(h_{n})_{n\in\mathbb{N}}$ of unit vectors such that $h_{n}$ belongs
to $H_{n}$ for any $n$ in $\mathbb{N}$,

(2.1) $\sup_{||x||=1}\sum_{n\in\mathbb{N}}|\braket{x,h_{n}}|^{2}=M^{2}.$

###### Proof.

The idea of the proof comes from [1, Prop. 9.5]. Choose for any $n$ in
$\mathbb{N}$ a unit vector $h_{n}$ in $H_{n}$, and suppose first that (2.1)
holds. Then, for any finitely supported $(a_{n})_{n\in\mathbb{N}}$,

$\begin{split}\left|\left|\sum_{n\in\mathbb{N}}a_{n}h_{n}\right|\right|^{2}&=\sup_{||x||=1}\left|\braket{x,\sum_{n\in\mathbb{N}}a_{n}h_{n}}\right|^{2}\\\
&=\sup_{||x||=1}\left|\sum_{n\in\mathbb{N}}\braket{x,h_{n}}\leavevmode\nobreak\
\overline{a_{n}}\right|^{2}\\\ &\leq
M^{2}\sum_{n\in\mathbb{N}}|a_{n}|^{2},\end{split}$

thanks to (2.1) and Cauchy-Schwartz’s inequality. The case of infinitely
supported sequences $(a_{n})_{n\in\mathbb{N}}$ in $l^{2}$ follows by
considering the limit case of finitely supported sequences.
Conversely, let $M$ be the Bessel bound for the sequence
$(H_{n})_{n\in\mathbb{N}}$, and fix a unit vector $x$ in $\mathcal{H}$ . Then
set $a_{n}=\braket{x,h_{n}}$, and observe that

$\begin{split}\sum_{n\in\mathbb{N}}|\braket{x,h_{n}}|^{2}=&\braket{x,\sum_{n\in\mathbb{N}}a_{n}h_{n}}\\\
\leq&\left|\left|\sum_{n\in\mathbb{N}}a_{n}h_{n}\right|\right|\\\
\leq&M\left(\sum_{n\in\mathbb{N}}|a_{n}|^{2}\right)^{\frac{1}{2}}\\\
=&M\left(\sum_{n\in\mathbb{N}}|\braket{x,h_{n}}|^{2}\right)^{\frac{1}{2}}.\end{split}$

By truncating the sum $\underset{n\in\mathbb{N}}{\sum}|\braket{x,h_{n}}|^{2}$,
one sees that this implies that $(a_{n})_{n\in\mathbb{N}}$ must be square
summable, and this concludes the proof. ∎

######  Remark 2.3.

Fixed $x$ in $\mathcal{H}$, we can choose $(h_{n})_{n\in\mathbb{N}}$ so that
the sum in (2.1) attains its maximum. We can actually maximizes each term of
the sum, by setting $h_{n}$ to be the orthogonal projection onto $H_{n}$ of
$x$, divided by its norm:

$f_{n}(x):=\frac{P_{H_{n}}(x)}{\left|\left|P_{H_{n}}(x)\right|\right|}.$

Proposition 2.2 then says that $(H_{n})_{n\in\mathbb{N}}$ has a finite Bessel
bound $M$ if and only if

(2.2)
$\sup_{||x||=1}\sum_{n\in\mathbb{N}}(1-\mathrm{dist}_{\mathrm{H}^{2}}^{2}(x,H_{n}))=\sup_{||x||=1}\sum_{n\in\mathbb{N}}|\braket{x,f_{n}(x)}|^{2}=M^{2}$

Lastly, we are going to use the one dimensional case of [6, Th. 5.1]. For any
$x$ in a Hilbert space $\mathcal{H}$ let $\hat{x}$ denote its normalization
$x/||x||$.

######  Theorem 2.4.

For any inner function $\Theta$ on $\mathbb{D}$,

$\mathrm{dist}_{\mathrm{H}^{2}}(\hat{s_{z}},H_{\Theta})=|\Theta(z)|\qquad
z\in\mathbb{D}.$

###### Proof.

Since the orthogonal projection onto
$\Theta\mathrm{H}^{2}=\mathrm{H}^{2}\ominus H_{\Theta}$ is
$M_{\Theta}M_{\Theta}^{*}$ one gets

$\mathrm{dist}_{\mathrm{H}^{2}}(\hat{s}_{z},H_{\Theta})=||M_{\Theta}M^{*}_{\Theta}(\hat{s}_{z})||=||M^{*}_{\Theta}(\hat{s}_{z})||=|\Theta(z)|.$

∎

We are now ready to prove Theorem 1.3:

###### Proof of Theorem 1.3.

Let $(H_{\Theta_{n}})_{n\in\mathbb{N}}$ be a weakly separated Bessel system.
We will show that (1.4) holds, and Theorem 1.1 will conclude the proof. Thanks
to (2.2), for any fixed $z$ in $\mathbb{D}$ there exists a positive integer
$n_{z}$ that minimizes the distance between $\hat{s_{z}}$ and $H_{n}$:

$\mathrm{dist}_{\mathrm{H}^{2}}(\hat{s_{z}},H_{n_{z}})=\min_{n\in\mathbb{N}}\mathrm{dist}_{\mathrm{H}^{2}}(\hat{s_{z}},H_{n}),$

which thanks to Theorem 2.4 becomes

$|\Theta_{n_{z}}(z)|=\min_{n\in\mathbb{N}}|\Theta_{n}(z)|.$

Therefore, by Theorem 2.1 and weak separation we have that

$\inf_{z\in\mathbb{D}}\inf_{n\neq n_{z}}|\Theta_{n}(z)|>0,$

which implies that

$\prod_{n\neq n_{z}}|\Theta_{n}(z)|=\sup_{n\in\mathbb{N}}\prod_{j\neq
n}|\Theta_{j}(z)|$

is bounded below uniformly on $z$ if and only if

$\sum_{n\neq n_{z}}(1-|\Theta_{n}(z)|^{2})=\sum_{n\neq
n_{z}}(1-\mathrm{dist}_{\mathrm{H}^{2}}^{2}(\hat{s_{z}},H_{\Theta_{n}}))$

is uniformly bounded on $z$, which is true thanks to Remark 2.3. ∎

Observe that the proof of Theorem 1.3 used a weaker version of the Bessel
system condition, in which the sup in (2.1) is taken only on normalized kernel
functions, rather than on all unit vectors in $\mathrm{H}^{2}$. It remains
open for us whether such a weaker condition is enough to characterize Bessel
systems of model spaces, and a positive answer for the special case in which
each $\Theta_{n}$ is a Blaschke product would be of great interest for us, as
this is the case that we consider when we apply Theorem 1.3 to interpolating
sequences of matrices, as we will see in Section 3:

######  Question 2.5.

Is any sequence of model spaces $(H_{\Theta_{n}})_{n\in\mathbb{N}}$ in
$\mathrm{H}^{2}$ satisfying

(2.3) $\sup_{z\in\mathbb{D}}\sum_{n\in\mathbb{N}}1-|\Theta_{n}(z)|^{2}<\infty$

a Bessel system? Is it true if $\Theta_{n}$ is, for any positive integer $n$,
a Blaschke product?

######  Remark 2.6.

Question 2.5 has a positive answer whenever $\Theta_{n}=b_{\lambda_{n}}$ is,
for any positive integer $n$, a degree-one Blaschke factor at a point
$\lambda_{n}$, and therefore whenever $H_{\Theta_{n}}$ is the line spanned by
the Szegö kernel at $\lambda_{n}$, [9, Ch. VI, Lemma 3.3].

##  3\. Interpolating Matrices

The motivation for Theorem 1.3 is the study of _interpolating sequences of
matrices_. The author asked in [6] whether some well known characterizations
for interpolating sequences for $\mathrm{H}^{\infty}$ such as Theorem 1.2
extend to sequences of square matrices $A=(A_{n})_{n\in\mathbb{N}}$, without
assuming any restriction on the sequence of their dimensions. The fact that a
square matrix might have a non trivial algebraic structure invariant under
holomorphic functions (its eigenspaces, for example), makes an interpolation
problem using matrices a bit trickier than the classic one: given two points
$\lambda$ and $w$ in $\mathbb{D}$ there is no function $\phi$ in
$\mathrm{H}^{\infty}$ that maps

$A=\begin{bmatrix}\lambda&0\\\ 0&\lambda\end{bmatrix}$

to

$W=\begin{bmatrix}w&1\\\ 0&w\end{bmatrix},$

although both $A$ and $W$ are bounded in the operator norm and the constant
function $w$ is a contraction in $\mathrm{H}^{\infty}$ that sends the spectrum
of $A$ to the spectrum of $W$. Since choosing bounded targets in the operator
norm makes even a one-point interpolation problem impossible to solve via
bounded analytic functions, in order to define interpolating matrices one has
to identify a target with a bounded sequence in $\mathrm{H}^{\infty}$, [6,
Def. 1.1]:

######  Definition 3.1 (Interpolating Matrices).

A sequence $A=(A_{n})_{n\in\mathbb{N}}$ of square matrices with spectra in the
open unit disc is interpolating for $\mathrm{H}^{\infty}$ if for any bounded
sequence $(\phi_{n})_{n\in\mathbb{N}}$ in $\mathrm{H}^{\infty}$ there exists a
$\phi$ in $\mathrm{H}^{\infty}$ such that

$\phi(A_{n})=\phi_{n}(A_{n}),\qquad n\in\mathbb{N}.$

Equivalently, [6, Th. 4.1], one can choose diagonal targets, and define $A$ to
be interpolating if for any bounded sequence $(w_{n})_{n\in\mathbb{N}}$ in
$\mathbb{C}$ there exists a bounded analytic function $\phi$ such that

$\phi(A_{n})=w_{n}\leavevmode\nobreak\ Id,\qquad n\in\mathbb{N}.$

Here an analytic function on the unit disc is applied to a square matrix via
the Riesz-Dunford functional calculus, hence the assumption on the spectra of
the matrices in $A$. In order to characterize interpolating sequences of
matrices, a rather trivial yet important observation is that, for any pair of
similar matrices $M$ and $N$ with spectra in $\mathbb{D}$ and for any
holomorphic function $f$ on the unit disc then $f(M)$ and $f(N)$ are similar
as well, and the matrix that performs both similarities is the same,

$M=P^{-1}NP\implies f(M)=P^{-1}f(N)P,$

as an elementary computation using the power series of $f$ shows. As a
consequence, we can assume without loss of generality that each matrix of the
sequence $A$ is in its _Jordan canonical form_ : if, for any positive integer
$n$, $\lambda_{n,1},\dots,\lambda_{n,k_{n}}$ are the eigenvalues of $A_{n}$,
then

$A_{n}=\mathrm{diag}(J_{n,1},\dots,J_{n,k_{n}}),$

where $J_{n,j}$ is a Jordan block of size $m_{n,j}$

$J_{n,j}=\begin{bmatrix}\lambda_{n,j}&1&0&\dots&0\\\
0&\lambda_{n,j}&1&\dots&0\\\ \vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&\dots&\lambda_{n,j}&1\\\ 0&0&0&0&\lambda_{n,j}\end{bmatrix}.$

Since, for any function $f$ holomorphic in $\mathbb{D}$,

$f(A_{n})=\mathrm{diag}(f(J_{n,1}),\dots,f(J_{n,k_{n}})),$

where

$f(J_{n,j})=\begin{bmatrix}f(\lambda_{n,j})&f^{\prime}(\lambda_{n,j})&\frac{f^{\prime\prime}(\lambda_{n,j})}{2}&\dots&\frac{f^{(m_{n,j}-1)}(\lambda_{n,j})}{(m_{n,j}-1)!}\\\
0&f(\lambda_{n,j})&f^{\prime}(\lambda_{n,j})&\dots&\frac{f^{(m_{n,j}-2)}(\lambda_{n,j})}{(m_{n,j}-2)!}\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&\dots&f(\lambda_{n,j})&f^{\prime}(\lambda_{n,j})\\\
0&0&0&0&f(\lambda_{n,j})\end{bmatrix},$

one realizes that a holomorphic function vanishes at $A_{n}$ if and only if it
vanishes at its eigenvalues with the right multiplicity. Specifically, the
multiplicity of $\lambda_{n,j}$ as a zero of $f$ must be the maximal size of a
Jordan block of $A_{n}$ associated to $\lambda_{n,j}$. In particular, any
function in $\mathrm{H}^{2}$ that vanishes at $A_{n}$ is a multiple of the
Blaschke product and the function in (1.11) can be re-written as

$B_{n}=\prod_{j=1}^{k_{n}}b_{\lambda_{n,j}}^{m_{n,j}}.$

Hence, for any $n$ in $\mathbb{N}$, the subspace

(3.1)
$\begin{split}H_{n}:=&\mathrm{H}^{2}\ominus\\{f\in\mathrm{H}^{2}\,|\,f(A_{n})=0\\}\\\
=&\mathrm{span}\left\\{s_{\lambda_{n,j}},\frac{\partial\leavevmode\nobreak\
s_{\lambda_{n,j}}}{\partial\overline{w}},\dots,\frac{\partial^{m_{n,j}-1}\leavevmode\nobreak\
s_{\lambda_{n,j}}}{\partial\overline{w}^{m_{n,j}-1}}\,\bigg{|}\,j=1,\dots,k_{n}\right\\}\end{split}$

containing all the interpolation information of the matrix $A_{n}$ is in fact
a model space:

$H_{n}=H_{B_{n}}\qquad n\in\mathbb{N}.$

Each $H_{n}$ can be seen also as a _kernel at the matrix $A_{n}$_. More
precisely, let $M$ be a $m\times m$ square matrix with eigenvalues in the unit
disc, and let $H_{M}$ be the associated model space in $\mathrm{H}^{2}$. Let
us define, for any $u$ and $v$ in $\mathbb{C}^{m}$, the $\mathrm{H}^{2}$
function

$K_{M}(u,v)(z):=\sum_{n\in\mathbb{N}}\braket{v,M^{n}u}_{\mathbb{C}^{m}}z^{n}\qquad
z\in\mathbb{D}.$

Then, thanks to the definition of the inner product in $\mathrm{H}^{2}$,

(3.2)
$\braket{f,K_{M}(u,v)}_{\mathrm{H}^{2}}=\braket{f(M)u,v}_{\mathbb{C}^{m}}\qquad
f\in\mathrm{H}^{2}.$

Equation 3.2 works as a _reproducing property_ for the collection

$X_{M}:=\\{K_{M}(u,v)\,|\,u,v\in\mathbb{C}^{m}\\}.$

In particular, since $f(M)=0$ if and only if the right hand side of (3.2)
vanishes for any $u$ and $v$, we have that $X_{M}$ coincides with the model
space $H_{M}$. Moreover, (3.2) implies that the collection of function in
$X_{M}$ is linear in $v$ and conjugate-linear in $u$, and that for any $\phi$
in $\mathrm{H}^{\infty}$

(3.3) $M_{\phi}^{*}(K_{M}(u,v))=K_{M}(u,\phi(M)^{*}v)\qquad
u,v\in\mathbb{C}^{m},$

extending (1.8) to this matrix setting. Another analogy with the scalar case
comes from separation: thanks to (3.3) and the commutant lifting Theorem, [1,
case $s=1$ of Corollary 10.30], (1.10) extends by saying that $A$ is weakly
separated if the sequence $(H_{n})_{n\in\mathbb{N}}$ is weakly separated or,
equivalently, if there exists a positive $M$ such that, for any pair of
distinct positive integers $n$ and $j$, there exists a bounded analytic
function $\phi_{n,j}$ whose $\mathrm{H}^{\infty}$ norm doesn’t exceed $M$ and
that separates $A_{n}$ and $A_{j}$, that is,

$\phi_{n,j}(A_{n})=Id\qquad\phi_{n,j}(A_{j})=0.$

Following the same idea, if $(H_{n})_{n\in\mathbb{N}}$ is strongly separated
we say that $A$ is strongly separated, and the commutant lifting Theorem,
together with (3.3), makes it equivalent to asserting the existence of a
bounded sequence $(\phi_{n})_{n\in\mathbb{N}}$ in $\mathrm{H}^{\infty}$ that
separates each $A_{n}$ with the rest of the sequence, i.e.,

$\phi_{n}(A_{j})=\delta_{n,j}\leavevmode\nobreak\ Id.$

The scalar case has an even more geometric viewpoint on separation via bounded
analytic functions: given two points $z$ and $w$ in the unit disc there exists
a function $\phi$ whose $\mathrm{H}^{\infty}$ norm doesn’t exceed $M$ that
separates $z$ and $w$ (and hence the sine of the angle between $s_{z}$ and
$s_{w}$ is bounded below by $1/M$) if and only if their _pseudo-hyperbolic
distance_

$\rho(z,w):=|b_{w}(z)|$

is bounded below by $1/M$. This extends to the matrix case by looking at the
action of the adjoint of the multiplication by a Blaschke product on different
model spaces:

######  Lemma 3.2.

Let $A_{1}$ and $A_{2}$ be two square matrices corresponding to the Blaschke
products $B_{1}$ and $B_{2}$, and let $H_{1}$ and $H_{2}$ be the associated
model spaces. Then the sine of the angle between $H_{1}$ and $H_{2}$ is equal
to $\delta>0$ if and only if the restriction of $M^{*}_{B_{1}}$ to $H_{2}$ is
bounded below by $\delta$, that is,

$\inf_{x\in H_{2}}||M_{B_{1}}^{*}(\hat{x})||=\sin(H_{1},H_{2}).$

###### Proof.

Since the orthogonal projection onto
$B_{1}\mathrm{H}^{2}=\mathrm{H}^{2}\ominus H_{1}$ is $M_{B_{1}}M^{*}_{B_{1}}$,
one gets

$\sin(H_{1},H_{2})=\inf_{x\in
H_{2}\setminus\\{0\\}}||M_{B_{1}}M_{B_{1}}^{*}(\hat{x})||=\inf_{x\in
H_{2}\setminus\\{0\\}}||M_{B_{1}}^{*}(\hat{x})||,$

since $M_{B_{1}}$ is an isometry. ∎

The author extended in [6] Carleson’s characterizations, [4] and [3], of
interpolating sequences to sequences of square matrices, together with the
characterization of interpolating sequences in terms of Riesz systems
conditions from [12]. Nevertheless, the analogous of Theorem 1.2 was proven
with the additional assumption that the dimensions of the matrices in $A$ are
uniformly bounded, and used the solution of the Feichtinger conjecture:

######  Theorem 3.3.

Let $A=(A_{n})_{n\in\mathbb{N}}$ be a sequence of matrices with spectra in the
unit disc, and let $H=(H_{n})_{n\in\mathbb{N}}$ be the associated sequence of
model spaces defined in (3.1). The following are equivalent:

(i):

$A$ is interpolating for $\mathrm{H}^{\infty}$;

(ii):

$A$ is strongly separated;

(iii):

$H$ is a Riesz system.

Moreover, if the dimensions of the matrices in $A$ are uniformly bounded, (i)
(and hence also all the conditions above) is equivalent to

(iv):

$A$ is weakly separated and $H$ is a Bessel system.

Thanks to equivalence between conditions (i), (ii) and (iii) in Theorem 3.3,
Theorem 1.3 applied to the sequence of model spaces $(H_{n})_{n\in\mathbb{N}}$
says, together with Theorem 1.1, that the extra assumption on the dimensions
of the matrices in $A$ in condition (iv) of Theorem 3.3 can be dropped.
Therefore Theorem 1.2 extends to sequences of matrices of any sizes:

######  Theorem 3.4.

$A$ is interpolating if and only if it is weakly separated and $H$ is a Bessel
system.

In particular, Theorem 1.4 follows from Theorem 1.3.

We present below two examples of sequences of matrices having equidistributed
eigenvalues. Section 3.1 will give an example of an interpolating sequence of
matrices, together with some useful tool to estimate the angle between model
spaces arising from Blaschke products. Section 3.2 will use a similar
construction in order to exhibit a Bessel system of model spaces which is not
the disjoint union of finitely many weakly separated sequences, and hence not
the finite union of finitely many Riesz systems. This will give a negative
answer to a question posed by the author in [6], where it was asked whether
the positive answer to the Feichtinger conjecture can be extended to multi-
dimensional model sub-spaces of the Hardy space.

###  3.1. Interpolating Matrices with Equidistributed Eigenvalues

Let, for any positive integer $n$,

$\omega_{n}:=e^{\frac{2\pi i}{2^{n}}}$

be a primitive $2^{n}$-root of unity, and let

$W_{n}:=\mathrm{diag}(1,\omega_{n},\dots,\omega_{n}^{2^{n}-1})$

be a $2^{n}\times 2^{n}$ diagonal matrix having $2^{n}$ equi-distributed
points on the unit circle as its eigenvalues. Let $(r_{n})_{n\in\mathbb{N}}$
be a sequence in $(0,1)$ that re-scales the sequence
$(W_{n})_{n\in\mathbb{N}}$ so that its spectra belong to $\mathbb{D}$:

(3.4) $A_{n}:=r_{n}\leavevmode\nobreak\ W_{n},\qquad n\in\mathbb{N}.$

We will discuss here how fast must $(r_{n})_{n\in\mathbb{N}}$ go to $1$ in
order for $A:=(A_{n})_{n\in\mathbb{N}}$ to be interpolating. Thanks to
Definition 3.1, if $(A_{n})_{n\in\mathbb{N}}$ is interpolating, then so is the
sequence of radii $(r_{n})_{n\in\mathbb{N}}$. Moreover, if $A$ is
interpolating it is trivially a _zero sequence_ , that is, there exists
bounded analytic function on $\mathbb{D}$ that vanishes on $A$ and that
doesn’t vanish outside the spectra of the matrices in $A$. It turns out that
those two conditions are enough to characterize interpolating sequences of
matrices that look like (3.4):

######  Theorem 3.5.

The sequence of matrices defined in (3.4) is interpolating if and only if it
is a zero sequence and $(r_{n})_{n\in\mathbb{N}}$ is interpolating.

######  Remark 3.6.

Since $(r_{n})_{n\in\mathbb{N}}$ approaches the unit circle radially, asking
that it is interpolating is actually the same as asking that it is just weakly
separated [11][Lec. X, Cor. 5].

The proof of Theorem 3.5 requires that we are able to estimate (from below)
the angle between two model spaces arising from Blaschke products. Such a tool
is the content of Lemma 3.7 below. Let $(B_{n})_{n\in\mathbb{N}}$ be a
sequence of Blaschke products such that $B=\prod_{n\in\mathbb{N}}B_{n}$
converges uniformly on any compact subset of $\mathbb{D}$ to a non zero inner
function, and let $(H_{n})_{n\in\mathbb{N}}$ be the associated sequence of
model spaces in $\mathrm{H}^{2}$. For any subset $\sigma$ of $\mathbb{N}$ we
will define, for the sake of brevity,

$H_{\sigma}:=\overline{\underset{i\in\sigma}{\mathrm{span}}}\\{H_{i}\\}$

and

$B_{\sigma}=\prod_{i\in\sigma}B_{i}.$

######  Lemma 3.7.

Let $\sigma$ and $\tau$ be two disjoint subsets of $\mathbb{N}$, and suppose
that $(H_{i})_{i\in\sigma}$ is a Riesz system with Riesz bound $\gamma$. Then

$\sin(H_{\sigma},H_{\tau})\geq\frac{1}{\gamma^{2}}\leavevmode\nobreak\
\inf_{i\in\sigma}\sin(H_{i},H_{\tau}).$

###### Proof.

For any $i$ in $\sigma$ let $\delta_{i}:=\sin(H_{i},H_{\tau})$, and let
$\delta:=\inf_{i\in\sigma}\delta_{i}$. It suffices to show that

$T\colon H_{\sigma\cup\tau}\to H_{\sigma\cup\tau}$

such that

$T_{|H_{\sigma}}=\delta\leavevmode\nobreak\ Id_{|H_{\sigma}}\qquad
T_{|H_{\tau}}=0$

is bounded by $\gamma^{2}$. Let $T_{i}$ be, for any $i$ in $\sigma$, the
restriction to $H_{i}$ of $M^{*}_{B_{\tau}}$. Thanks to Lemma 3.2, each
$T_{i}$ is bounded below by $\delta_{i}$. Fix then a vector $x=u+v$ in
$H_{\sigma\cup\tau}$, where $u$ is in $H_{\sigma}$ and $v$ is in $H_{\tau}$.
There exists a sequence $(h_{i})_{i\in\sigma}$ of unit vectors such that
$h_{i}$ is in $H_{i}$ for any $i$ in $\sigma$ so that $u$ can be written as a
linear combination of $(h_{i})_{i\in\sigma}$:

$u=\sum_{i\in\sigma}\alpha_{i}h_{i}.$

Since each $T_{i}$ is a contraction and it is bounded below by $\delta$, the
sequence $(T_{i}(h_{i}))_{i\in\mathbb{N}}$ is bounded above and below.
Moreover, $T_{i}(h_{i})$ belongs to $H_{i}$, since each $H_{i}$ is invariant
under $M_{B_{\tau}}$, and therefore

$\begin{split}||T(x)||^{2}&=||T(u)||^{2}=\left|\left|\sum_{i\in\sigma}\delta\alpha_{i}h_{i}\right|\right|^{2}\\\
&\leq\gamma^{2}\delta^{2}\sum_{i\in\sigma}|\alpha_{i}|^{2}\leq\gamma^{2}\sum_{i\in\sigma}\delta_{i}^{2}|\alpha_{i}|^{2}\\\
&\leq\gamma^{2}\sum_{i\in\sigma}|\alpha_{i}|^{2}||T_{i}(h_{i})||^{2}\leq\gamma^{4}\left|\left|\sum_{i\in\sigma}\alpha_{i}T_{i}(h_{i})\right|\right|^{2}\\\
&=\gamma^{4}||M^{*}_{B_{\tau}}(u)||^{2}=\gamma^{4}||M^{*}_{B_{\tau}}(x)||^{2}.\end{split}$

Since $M^{*}_{B_{\tau}}$ is a contraction, this shows that the norm of $T$
doesn’t exceed $\gamma^{2}$, as we claimed. ∎

######  Remark 3.8.

Suppose that also $(H_{j})_{j\in\tau}$ is a Riesz system. Then a double
application of Lemma 3.7 implies that the distance between $H_{\sigma}$ and
$H_{\tau}$ is comparable with the minimal distance attained by a model space
labeled by an index in $\sigma$ and one with a label in $\tau$. If the
sequence $(H_{n})_{n\in\mathbb{N}}$ is weakly separated, this says roughly
speaking that the set of _sparse subsequences_ of $(H_{n})_{n\in\mathbb{N}}$
is a separated set as well.

We are now ready to prove Theorem 3.5. Here $(B_{n})_{n\in\mathbb{N}}$ and
$(H_{n})_{n\in\mathbb{N}}$ arise from the sequence of matrices $A$ defined in
(3.4). We need to show that $A$ is interpolating, provided that it is a zero
sequence and that $(r_{n})_{n\in\mathbb{N}}$ is weakly separated, thanks to
Remark 3.6.

###### Proof of Theorem 3.5.

Let, for any positive integer $n$,

(3.5) $r_{n}=1-\alpha_{n}2^{-n}.$

Since $A$ is a zero sequence, then the spectra of the matrices in $A$ form a
zero sequence and therefore

$\sum_{n\in\mathbb{N}}\alpha_{n}<\infty.$

Let $\gamma_{n}$ be the Riesz bound of the basis
$\\{\hat{s}_{r_{n}},\dots,\hat{s}_{r_{n}\omega_{n}^{2^{n}-1}}\\}$ of $H_{n}$.
Then $(\gamma_{n})_{n\in\mathbb{N}}$ is uniformly bounded if and only if the
strong separation constants

$\prod_{l=1}^{2^{n}-1}|b_{r_{n}\omega_{n}^{l}}(r_{n})|^{2}$

are uniformly bounded below. Let, for any $j$ and $n$ in $\mathbb{N}$,

(3.6)
$\begin{split}M_{j}(n):=&\sum_{l=1}^{2^{j}}|\braket{\hat{s}_{r_{j}\omega_{j}^{l}},\hat{s}_{r_{n}}}|^{2}\\\
=&\sum_{l=1}^{2^{j}}\frac{(1-r_{n}^{2})(1-r_{j}^{2})}{|1-r_{n}r_{j}\omega_{j}^{l}|^{2}}.\end{split}$

Since $(\alpha_{n})_{n\in\mathbb{N}}$ is bounded, then the weak separation
constant of the set $\\{r_{n},\dots,r_{n}\omega^{2^{n}-1}\\}$ is uniformly
bounded below in $n$. Since also

$|b_{w}(z)|^{2}=1-|\braket{\hat{s}_{w},\hat{s}_{z}}|^{2}\qquad
w,z\in\mathbb{D},$

then $(\gamma_{n})_{n\in\mathbb{N}}$ is bounded if and only if
$(M_{n}(n))_{n\in\mathbb{N}}$ is, which is the case, thanks to Lemma 3.9
below, because $(\alpha_{n})_{n\in\mathbb{N}}$ is bounded. We want to show
that $(H_{n})_{n\in\mathbb{N}}$ is strongly separated:

$\inf_{n\in\mathbb{N}}\sin\left(H_{n},\underset{j\neq
n}{\overline{\mathrm{span}}}\\{H_{j}\\}\right)>0.$

Since $(\gamma_{n})_{n\in\mathbb{N}}$ is bounded, thanks to Lemma 3.7 the sine
between $H_{n}$ and $\underset{j\neq n}{\overline{\mathrm{span}}}\\{H_{j}\\}$
is comparable to

$\sin\left(\hat{s}_{r_{n}},\underset{j\neq
n}{\overline{\mathrm{span}}}\\{H_{j}\\}\right)=\prod_{j\neq n}|B_{j}(r_{n})|.$

In fact, the sine between $H_{n}$ and $\underset{j\neq
n}{\overline{\mathrm{span}}}\\{H_{j}\\}$ is comparable to

$\underset{l=0,\dots,2^{n}-1}{\min}\sin\left(s_{r_{n}\omega_{n}^{l}},\underset{j\neq
n}{\overline{\mathrm{span}}}\\{H_{j}\\}\right)=\underset{l=0,\dots,2^{n}-1}{\min}|B_{j}(r_{n}\omega_{n}^{l})|.$

Nevertheless, the minimum is attained at $l=0$, since

$B_{j}(z)=\frac{r_{j}^{2^{j}}-z^{2^{j}}}{1-r_{j}^{2^{j}}z^{2^{j}}}=b_{r_{j}^{2^{j}}}(z^{2^{j}})$

and the point on the circle of radius $r_{n}$ which is closest (with respect
the pseudo-hyperbolic distance) to $r_{j}^{2^{j}}$ is precisely $r_{n}$.
We are then left to show that

(3.7) $\inf_{n\in\mathbb{N}}\prod_{j\neq n}|B_{j}(r_{n})|>0.$

This is true if and only if each term on the product is uniformly bounded
below and

$\sup_{n\in\mathbb{N}}\sum_{j\in\mathbb{N}}M_{j}(n)<\infty.$

Such sum converges thanks to Lemma 3.9, since $(\alpha_{n})_{n\in\mathbb{N}}$
is summable. Moreover, each term on the product in 3.7 is uniformly bounded
below, since $(r_{n})_{n\in\mathbb{N}}$ is weakly separated and since, thanks
to Lemma 3.7, the pseudo-hyperbolic distance between $r_{n}$ and $r_{j}$ is,
for any $n\neq j$, comparable to $\sin(\hat{s}_{r_{n}},H_{j})=|B_{j}(r_{n})|$.
∎

A technical tool for the proof of Theorem 3.5 is the following computation,
which relates the quantity $M_{j}(n)$ to the parameters
$(\alpha_{n})_{n\in\mathbb{N}}$ defined in (3.5):

######  Lemma 3.9.

Let

$r_{n}:=1-\alpha_{n}2^{-n}\qquad n\in\mathbb{N}$

be a sequence in $(0,1)$ and let $M_{j}(n)$ be defined as in (3.6). Then, for
any $j$ and $n$ positive integers,

$M_{j}(n)\simeq\frac{\alpha_{n}\alpha_{j}}{\alpha_{n}+\alpha_{j}2^{n-j}-\alpha_{n}\alpha_{j}2^{-j}}.$

###### Proof.

Let, for any $j$ in $\mathbb{N}$ and for any $l=-2^{j-1},\dots,2^{j-1}$,

$\theta^{j}_{l}:=\arg{\omega_{j}^{l}}=\frac{2\pi l}{2^{j}}.$

Then

$1-\cos(\theta^{j}_{l})\simeq\frac{(\theta^{j}_{l})^{2}}{2}\simeq\frac{l^{2}}{2^{2j+1}}\qquad
l=-2^{j-1},\dots,2^{j-1}$

and therefore

$\begin{split}M_{j}(n)&\simeq(1-r_{j})(1-r_{n})\sum_{l=-2^{j-1}}^{2^{j-1}}\frac{1}{|1-r_{n}r_{j}\omega_{j}^{l}|^{2}}\\\
&=(1-r_{j})(1-r_{n})\sum_{l=-2^{j-1}}^{2^{j-1}}\frac{1}{(1-r_{n}r_{j})^{2}+2((1-\cos(\theta^{j}_{l})))r_{n}r_{j}}\\\
&\simeq\frac{(1-r_{j})(1-r_{n})}{(1-r_{j}r_{n})^{2}}\sum_{l=1}^{2^{j-1}}\frac{1}{1+\left(\frac{\sqrt{r_{n}r_{j}}}{2^{j}(1-r_{n}r_{j})}\leavevmode\nobreak\
l\right)^{2}}\\\
&\simeq\frac{(1-r_{j})(1-r_{n})}{(1-r_{j}r_{n})^{2}}\int_{1}^{2^{j-1}}\frac{1}{1+\left(\frac{\sqrt{r_{n}r_{j}}}{2^{j}(1-r_{n}r_{j})}\leavevmode\nobreak\
x\right)^{2}}\,dx\\\
&=\frac{2^{j}(1-r_{j})(1-r_{n})}{(1-r_{j}r_{n})\sqrt{r_{j}r_{n}}}\int_{\frac{\sqrt{r_{j}r_{n}}}{2^{j}(1-r_{j}r_{n})}}^{\frac{\sqrt{r_{j}r_{n}}}{(1-r_{j}r_{n})}}\frac{1}{1+x^{2}}\,dx\\\
&\simeq\frac{2^{j}(1-r_{j})(1-r_{n})}{1-r_{j}r_{n}}\\\
&=\frac{\alpha_{n}\alpha_{j}}{\alpha_{n}+\alpha_{j}2^{n-j}-\alpha_{n}\alpha_{j}2^{-j}}.\end{split}$

∎

###  3.2. Bessel Systems of Model Spaces

Thanks to the positive answer to the Feichtinger conjecture, any Bessel system
of lines in a Hilbert space is the disjoint union of finitely many Riesz
systems. We show here that this is not the case for multi-dimensional model
spaces in $\mathrm{H}^{2}$, as we will construct a sequence of matrices $A$
which can not be written as the disjoint union of finitely many weakly
separated sequences and whose associated sequence of model spaces is a Bessel
system. This implies that [1, Th. 9.11] doesn’t extend to multi-dimensional
model spaces, and since any Riesz system is weakly separated it will show that
the positive answer to the Feichtinger conjecture doesn’t extend to multi-
dimensional model spaces whose dimensions are not uniformly bounded.
Pick a divergent sequence $(m_{n})_{n\in\mathbb{N}}$, and let
$(r_{n})_{n\in\mathbb{N}}$ be a sequence of radii that converges to $1$, and
whose rate of convergence will be determined later. For any such a sequence,
there exists a second sequence of radii $(s_{n})_{n\in\mathbb{N}}$ such that

(3.8) $\rho(r_{n},s_{n})\leq\frac{1}{n+1}\qquad n\in\mathbb{N}.$

For each $n$ in $\mathbb{N}$, consider $m_{n}$ diagonal matrices,
$A_{n,1},\dots,A_{n,m_{n}}$, each one of size $m_{n}-1$, and whose eigenvalues
are placed as follows: if $\omega_{n}$ is a $\binom{m_{n}}{2}$-th primitive
root of unity, the set of all eigenvalues of $A_{n,1},\dots,A_{n,m_{n}}$ is

(3.9)
$\left\\{r_{n},r_{n}\omega_{n},\dots,r_{n}\omega_{n}^{\binom{m_{n}}{2}-1}\right\\}\cup\left\\{s_{n},s_{n}\omega_{n},\dots,s_{n}\omega_{n}^{\binom{m_{n}}{2}-1}\right\\}.$

We now need to assign each of those $m_{n}(m_{n}-1)$ eigenvalues to the
matrices $A_{n,1},\dots,A_{n,m_{n}}$ so that

(3.10) $\sin\left(H_{A_{n,i}},H_{A_{n,j}}\right)\leq\frac{1}{n+1}\qquad
i,j=1,\dots,m_{n},$

where $H_{n,i}$ is the model space in $\mathrm{H}^{2}$ associated to the
matrix $A_{n,i}$. Observe that this would imply that the sequence

$A:=\left\\{A_{n,j}\,|\,n\in\mathbb{N},j=1,\dots,m_{n}\right\\}$

can not be written as the disjoint union of finitely many weakly separated
sub-sequences, since $(m_{n})_{n\in\mathbb{N}}$ is divergent. More
importantly, this would hold for any choice of $(r_{n})_{n\in\mathbb{N}}$. In
order to achieve (3.10), we assign the eigenvalues in (3.9) to the matrices
$A_{n,1},\dots,A_{n,m_{n}}$ so that the set of non-ordered pairs

$\left\\{\left(r_{n}\omega_{n}^{l},s_{n}\omega_{n}^{l}\right)\,|\,l=1,\dots,\binom{m_{n}}{2}\right\\}$

coincide with the set of non-ordered pairs

$\\{(\lambda,\gamma)\,|\,\lambda\in\sigma(A_{n,i}),\gamma\in\sigma(A_{n,j}),\,i\neq
j\\}.$

Thus (3.10) follows from the fact that, for any $i\neq j=1,\dots,m_{n}$, there
exists an eigenvalue $\lambda$ of $A_{n,i}$ and an eigenvalue $\gamma$ of
$A_{n,j}$ so that

$\rho(\lambda,\gamma)\leq\frac{1}{n+1},$

thanks to (3.8).

######  Example 3.10.

In order to have an explicit example in mind, let $m_{1}=4$, and let then
$\omega_{1}$ be a primitive $6$-th root of unity. One can then choose

$\begin{split}r_{1}\in\sigma(A_{1,1})\quad&s_{1}\in\sigma(A_{1,2})\\\
r_{1}\omega\in\sigma(A_{1,1})\quad&s_{1}\omega\in\sigma(A_{1,3})\\\
r_{1}\omega^{2}\in\sigma(A_{1,1})\quad&s_{1}\omega^{2}\in\sigma(A_{1,4})\\\
r_{1}\omega^{3}\in\sigma(A_{1,2})\quad&s_{1}\omega^{3}\in\sigma(A_{1,3})\\\
r_{1}\omega^{4}\in\sigma(A_{1,2})\quad&s_{1}\omega^{4}\in\sigma(A_{1,4})\\\
r_{1}\omega^{5}\in\sigma(A_{1,3})\quad&s_{1}\omega^{5}\in\sigma(A_{1,4}).\end{split}$

In general, the idea is to assign, for all $n$, the $m_{n}(m_{n}-1)$ points on
the two very close circle of radius $r_{n}$ and $s_{n}$ in a way so that the
$\binom{m_{n}}{2}$ pairs of points very close to each other correspond to the
set of pairs $\\{(A_{n,i},A_{n,j})\\}$.

What is left now to show is that, if $(r_{n})_{n\in\mathbb{N}}$ is chosen to
be converging to $1$ adequately fast, the sequence of model spaces associated
with the sequence $A$ is a Bessel system. Let
$A^{\prime}=(z_{j})_{j\in\mathbb{N}}$ be the (scalar) sequence of all the
eigenvalues of the matrices in $A$. Observe that we can recursively choose the
sequence $(r_{n})_{n\in\mathbb{N}}$ to approach $1$ fast enough so that

(3.11)
$\sup_{z\in\mathbb{D}}\sum_{j\in\mathbb{N}}1-|b_{z_{j}}(z)|^{2}<\infty.$

Indeed, one can use the same idea of [6][Th. 2.2] and add the contribution of
the eigenvalues in (3.9) once at a time in the sum in (3.11). More precisely,
let $A_{n}^{\prime}$ be the set in (3.9), and let

$Q_{n}(z):=\sum_{j=1}^{n}\sum_{z_{l}\in A^{\prime}_{j}}1-|b_{z_{l}}(z)|^{2}.$

Then, once we choose $r_{1},\dots,r_{n}$, there exists a radius $t_{n}$ such
that

$\sup_{t_{n}\leq|z|<1}Q_{n}(z)\leq\frac{1}{2^{n}},$

and it suffices then to choose $r_{n+1}$ so that

$\sum_{z_{l}\in
A^{\prime}_{n+1}}1-|b_{z_{l}}(z)|^{2}\leq\frac{1}{2^{n}}\qquad|z|\leq t_{n}$

and so that the Riesz bound of the set of normalized kernels at the points in
$A^{\prime}_{n+1}\cap\\{|z|=r_{n+1}\\}$ is uniformly bounded (in fact, since
$m_{n+1}$ is fixed one can make such Riesz bound arbitrarily close to $1$, by
choosing $r_{n+1}$ close enough to $1$ ).
Thanks to (3.11) and Remark 2.6 the sequence of lines spanned by the Szegö
kernels at the point of $A^{\prime}$ is a Bessel system. This, together with
an extra separation condition on the eigenvalues of the matrices in $A$,
implies that the model spaces associated with the sequence $A$ forms a Bessel
system:

######  Lemma 3.11.

Let $(H_{n})_{n\in\mathbb{N}}$ be a sequence of closed sub-spaces of a Hilbert
space $\mathcal{H}$, and let, for any $n$ in $\mathbb{N}$,
$\\{x_{n}^{1},\dots,x_{n}^{m_{n}}\\}$ be a basis of $H_{n}$ made of unit
vectors such that

(3.12) $\sum_{l=1}^{m_{n}}|c_{l}|^{2}\leq C_{n}^{2}\leavevmode\nobreak\
\left|\left|\sum_{l=1}^{m_{n}}c_{l}x_{n}^{l}\right|\right|^{2},\qquad
c_{1},\dots,c_{m_{n}}\in\mathbb{C}.$

If

(3.13) $C:=\sup_{n\in\mathbb{N}}C_{n}<\infty$

and $(x_{n}^{l})$ is a Bessel system with bound $M$, then
$(H_{n})_{n\in\mathbb{N}}$ is a Bessel system with bound $CM$.

###### Proof.

Let $(h_{n})_{n\in\mathbb{N}}$ be a sequence of unit vectors in $\mathcal{H}$
such that $h_{n}$ belongs to $H_{n}$ for any $n$ in $\mathbb{N}$, and let
$(a_{n})_{n\in\mathbb{N}}$ be an $l^{2}$ sequence. Write
$h_{n}=\sum_{l=1}^{m_{n}}b_{n}^{l}x_{n}^{l}$, and observe that

$\begin{split}\left|\left|\sum_{n\in\mathbb{N}}a_{n}h_{n}\right|\right|^{2}=&\left|\left|\sum_{n\in\mathbb{N}}\sum_{l=1}^{m_{n}}a_{n}b_{n}^{l}x_{n}^{l}\right|\right|^{2}\\\
\leq&M^{2}\sum_{n\in\mathbb{N}}|a_{n}|^{2}\sum_{l=1}^{m_{n}}|b_{n}^{l}|^{2}\\\
\leq&C^{2}M^{2}\sum_{n\in\mathbb{N}}|a_{n}|^{2},\end{split}$

thanks to (3.12) and (3.13). ∎

Since the sequence $(m_{n})_{n\in\mathbb{N}}$ is fixed, by eventually
increasing the rate of convergence of $(r_{n})_{n\in\mathbb{N}}$ to $1$ we can
assume that the Reisz bound of the kernels basis of each $H_{A_{n}}$ is
uniformly bounded in $n$, thus in particular condition (3.12) holds. Indeed,
although the eigenvalues of a given matrix $A_{n}$ might belong to two circle
very close to each other, our construction ensures that their arguments are
separated by at least an angle of $\frac{2\pi}{\binom{m_{n}}{2}}$. Therefore,
thanks to Lemma 3.11, the sequence of model spaces associated to the sequence
$A$ is a Bessel system.

## References

  * [1] Agler, J and M${}^{\text{c}}$Carthy, J. E.: _Pick Interpolation and Hilbert Function Spaces_ , Graduate Studies in Mathematics, vol 44, American Mathematical Society, 2002.
  * [2] Aleman, A., Hartz, M., M${}^{\text{c}}$Carthy, J. E. and Richter, S.: Interpolating sequences in spaces with the Pick property, _Int. Math. Res. Not. IMRN_ (2019), no. 12, 3832-3854.
  * [3] Carleson, L.: An Interpolation Problem for Bounded Analytic Functions, _American Journal of Mathematics_ , Vol. 80, No. 4 (Oct. 1958), pp. 921-930.
  * [4] Carleson, L.: Interpolation by Bounded Analytic Functions and the Corona Problem, _Annals of Mathematics_ , Second Series, Vol. 76, No. 3 (Nov. 1962), pp. 547-559.
  * [5] Casazza, P. G., Christensen, O., Lindner, A. M. and Verhsynin, R.: Frames and the Feichtinger Conjecture, _Proceedings of the American Mathematical Society_ , Vol. 133, No. 4, pp. 1025-1033.
  * [6] Dayan, A.: Interpolating Matrices, _Integral Equations and Operator Theory 92_ , 49 (2020).
  * [7] Marcus, A. W., Spielman, D. A. and Srivastava, N.: Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem, _Annals of Mathematics_ , Second Series, Vol. 182, No. 1 (July 2015), pp. 327-350.
  * [8] Garcia, R. S., Mashreghi, J. and Ross, W. T.: _Introduction to Model Spaces and their Operators_ , Cambridge Studies in Advanced Mathematics 148, 2016.
  * [9] Garnett, J., B.: _Bounded Analytic Functions_ , Revised First Edition, Graduate Texts in Mathematics 236, Springer.
  * [10] Nikol’skiĭ, N., K.: _Operators, Functions and Systems: an Easy Reading_ , Volume 2: _Model Operators and Systems_ , Mathematical Surveys and Monographs, Volume 93, American Mathematical Society.
  * [11] Nikol’skiĭ, N. K.: _Treatise on the Shift Operator: Spectral Function Theory_ , Springer Series in Soviet Mathematics, 1985
  * [12] Shapiro, H. S. and Shields, A. L.: On some interpolation problems for analytic functions, _Amer. J. Math._ 83 (1961) 513-532.
  * [13] Weaver, N.: The Kadison-Singer Problem in Discrepancy Theory, _Discrete Mathematics_ 278 (2004), pp. 227-239.


# Selecting a number of voters for a voting ensemble

Eric Bax<EMAIL_ADDRESS><EMAIL_ADDRESS>
Verizon Media, Playa Vista, CA, USA

###### Abstract

For a voting ensemble that selects an odd-sized subset of the ensemble
classifiers at random for each example, applies them to the example, and
returns the majority vote, we show that any number of voters may minimize the
error rate over an out-of-sample distribution. The optimal number of voters
depends on the out-of-sample distribution of the number of classifiers in
error. To select a number of voters to use, estimating that distribution then
inferring error rates for numbers of voters gives lower-variance estimates
than directly estimating those error rates.

††journal: Pattern Recognition Letters

##  1 Introduction

Voting ensembles of classifiers are a staple of machine learning, including
bagging (Breiman, 1996), boosting (Schapire, 1990; Freund and Schapire, 1997),
forests of decision trees (Ho, 1995, 1998; Breiman, 2001), and stacking
(Wolpert, 1992). Comparative studies show that ensemble classifiers are often
the best types of out-of-the-box classifiers (Li, 2010), they win many machine
learning competitions (Bennett and Lanning, 2007; Chen and Guestrin, 2016),
and they continue to solve practical problems (Zheng et al., 2019; Shahzad and
Lavesson, 2013). For a compelling explanation why ensemble classifiers produce
good performance, refer to (Dietterich, 2000). For more on selecting ensemble
classifiers and ensemble size, refer to (Bonab and Can, 2019; Jackowski, 2018;
Gomes et al., 2017; Hernández-Lobato et al., 2013; Oshiro et al., 2012; Yang,
2011; Rokach, 2010, 2009; Tsoumakas et al., 2008; Kuncheva, 2004; Kuncheva et
al., 2003; Liu et al., 2004; Hu, 2001; Bax, 1998; Lam and Suen, 1997).

This paper focuses on equally-weighted voting. One extreme is to use all
classifiers as voters for every classification. The other is to select a
single classifier at random for each classifier. This is sometimes called
Gibbs classification. PAC-Bayes error bounds (McAllester, 1999; Langford et
al., 2001; Begin et al., 2016) indicate why Gibbs classification can be
effective – selecting a Gibbs ensemble that includes 1% of the hypothesis
classifiers produces error bounds that are similar to selecting a classifier
from a hypothesis set with only 100 classifiers, even if the actual hypothesis
set has an arbitrarily large number of classifiers.

Similar to Esposito and Saitta (2004), this paper explores how to select a
number of voters for a majority-vote ensemble classifier. That paper shows
that the distribution of the number of classifier errors can vary widely over
examples in empirical datasets, motivating our analysis of the influence of
ensemble size on error rates in such situations. That paper focuses on
ensembles of classifiers selected with replacement, allowing a potentially
unlimited number of voters. In contrast, this paper focuses on ensembles of
classifiers selected without replacement, leading to a different conclusion
about the optimal ensemble size, and a statistical method to select the
ensemble size based on simultaneous bounds on frequencies of the numbers of
classifiers in error.

The next section shows that selecting a single classifier at random for each
example can outperform voting over all ensemble classifiers. In Section 3, we
show how the distribution of number of ensemble classifiers in error impacts
the optimal number of voters, by considering the error curves over numbers of
voters for each number of classifier errors as a basis for all possible
distribution error curves over numbers of voters. In Section 4, we prove that
any number of voters may be optimal. Section 5 discusses methods to select the
number of voters, showing that an out-of-sample error estimate based on
inference has less variance than direct estimates. Then Section 6 outlines
methods to compute out-of-sample error bounds based on inference estimates,
including a discussion of challenges for the future.

##  2 Does voting always help?

To begin, compare worst-case error rate for majority voting over all
classifiers to selecting a single classifier at random for each example. Let
$m$ be the number of classifiers in the ensemble, and let $p$ be their average
error rate. Then the single-classifier strategy has error rate $p$, by
linearity of expectations. For the all-voting strategy, the out-of-sample
error rate depends on patterns of agreement among the classifiers as well as
their out-of-sample error rates. For example, suppose three classifiers each
have a 10% error rate. Then, for each pair of classifiers, it is possible that
they err together (and the classifier outside the pair is correct) with
probability 5%, producing a 15% voting error rate. In general,

######  Theorem 1.

For $m$ classifiers in an ensemble, with $m$ odd, if the average out-of-sample
classifier error rate is $p$, with $p<\frac{1}{2}$, then the maximum possible
all-voting error rate is

$2p\left(1-\frac{1}{m+1}\right).$ (1)

###### Proof.

All-voting error is maximized by having the smallest possible majority of
voters in error be as probable as the average error bound allows, and
otherwise having zero errors. Maximize the probability (call it $\hat{p}$) of
the slimmest majority, $\frac{m+1}{2}$, being incorrect, given the constraint
that the sum of error rates over classifiers is $mp$:

$\hat{p}\left(\frac{m+1}{2}\right)=mp,$ (2)

and solve for $\hat{p}$:

$\hat{p}=2p\left(1-\frac{1}{m+1}\right).$ (3)

If $\frac{m+1}{2}$ are incorrect with probability $\hat{p}$ and zero are
incorrect with probability $1-\hat{p}$, then $\hat{p}$ is the all-voting error
rate. ∎

As $m$ increases, all-voting error rate can approach twice the error rate of
selecting a classifier at random, because a voting classifier can have nearly
half its classifiers correct and still be incorrect. Discretization can favor
the individual.

##  3 A basis to analyze voting

Now consider ensemble classifiers with (odd) $m$ classifiers, average
classifier error rate $p$, and an (odd) number of voters $v$ from one to $m$.
Setting $v=1$ gives the single-voter strategy, and $v=m$ gives the all-voting
strategy. In this section, we analyze error rate curves over numbers of
voters, given numbers of ensemble classifiers incorrect. Those curves form a
basis for error rate curves over numbers of voters, in the sense that the
weighted sums of those basis curves (with nonnegative weights that sum to one)
are all the possible error rate curves over numbers of voters:

######  Theorem 2.

For an ensemble with $m$ classifiers, for each
$i\in\left\\{{0,\ldots,m}\right\\}$, let $w_{i}$ be the probability that
exactly $i$ of the $m$ classifiers are in error for an example drawn at random
from an out-of-sample distribution. Then, for subset voting with $v$
classifiers, the average error rate over the out-of-sample distribution is

$\sum_{i=0}^{m}w_{i}r(m,i,v),$ (4)

where

$r(m,i,v)=\sum_{j=\frac{v+1}{2}}^{v}\frac{{{i}\choose{j}}{{m-i}\choose{v-j}}}{{{m}\choose{v}}}$
(5)

is the expected voting error rate given that $i$ of $m$ classifiers are in
error.

###### Proof.

Voting has average error rate

$\sum_{i=0}^{m}w_{i}\hbox{Pr}\left\\{{\hbox{voting error}|i}\right\\},$ (6)

where $i$ is the number of the $m$ classifiers that are in error. Voting error
requires a majority of voters to be in error, so

$\hbox{Pr}\left\\{{\hbox{voting
error}|i}\right\\}=\sum_{j=\frac{v+1}{2}}^{v}\hbox{Pr}\left\\{{\hbox{$j$
voters are in error}|i}\right\\},$ (7)

and

$\hbox{Pr}\left\\{{\hbox{$j$ voters are in
error}|i}\right\\}=\frac{{{i}\choose{j}}{{m-i}\choose{v-j}}}{{{m}\choose{v}}},$
(8)

since this is the number of ways to select $j$ voters from the $i$ incorrect
ones and $v-j$ voters from the $m-i$ correct ones, divided by the number of
ways to select $v$ voters from the $m$ classifiers. ∎

Figure 1: Average error rates $r(m,i,v)$, for $v$ voters, if
$i\in\left\\{{0,\ldots,101}\right\\}$ of $m=101$ classifiers are incorrect.
The line for $i=0$ is at the bottom of the figure – a flat line of average
error rate zero, since if all classifiers are correct, then any number of
voters gives correct classification. Similarly, the line for $i=101$ is at the
top, and successive curves are for successive $i$-values. (Only the middle
four are labeled, to avoid cluttering the figure.).

Figure 1 shows how the probability of error for a voting classifier,
$r(m,i,v)$ varies with the number of voters $v$, given that $i$ of $m$
classifiers are in error. The plot is for $m=101$, with a curve for each
number of errors $i\in\left\\{{0,\ldots,101}\right\\}$, connecting $r(m,i,v)$
values for odd $v$ from one to 101. Think of the curves as a basis. The set of
weighted averages of the curves is the set of all possible error curves with
respect to number of voters $v$ for ensembles of $m=101$ classifiers.

From Figure 1, notice that if more than half the classifiers are in error
($i\geq 51$), then using more voters increases the out-of-sample error rate
(except for $i=101$ since it always gives a 100% error rate). To see why
consider $i=51$. If 51 of 101 classifiers are in error, then selecting a
single one and using it gives expected error rate $\frac{51}{101}$, but using
all $101$ always results in an error, because 51 is a (slight) majority of the
101 voters. Between 1 and 101, using more voters increases the error rate, by
making it more likely that the majority of voters will be incorrect. Also,
notice that as $i$ increases above 51, the increase in error rate with number
of voters goes from concave up to nearly linear to concave down, showing that
the loss in accuracy due to using a few voters rather than a single classifier
increases with $i$.

The following theorem shows that some things we can observe in Figure 1 are
true in general: adding voters strengthens classification for examples with
fewer than half the ensemble classifiers in error, and it weakens
classification for examples with more than half the ensemble classifiers in
error. These effects only cease when there are so many voters that the
minority among the ensemble (correct or incorrect) is too small to be a
majority of the voters.

######  Theorem 3.

Let $r(m,i,v)$ be the voting ensemble error rate if $i$ of $m$ ensemble
classifiers are in error, $v$ voters are selected at random without
replacement from the ensemble, and their majority vote is returned. (Assume
$v$ is odd.) Define the error rate difference due to increasing the number of
voters by two:

$\Delta_{v}(m,i,v)\equiv r(m,i,v+2)-r(m,i,v).$ (9)

Then:

  * 1.

If $i<\frac{v+1}{2}$ then $r(m,i,v)=0$ and $\Delta_{v}(m,i,v)=0$.

  * 2.

If $i<\frac{m}{2}$ and $i\geq\frac{v+1}{2}$, then $\Delta_{v}(m,i,v)<0$.

  * 3.

If $i>\frac{m}{2}$ and $m-i\geq\frac{v+1}{2}$, then $\Delta_{v}(m,i,v)>0$.

  * 4.

If $m-i<\frac{v+1}{2}$ then $r(m,i,v)=1$ and $\Delta_{v}(m,i,v)=0$.

###### Proof.

The first and last bullet points in the theorem are straightforward. For the
others, suppose $v$ voters have been selected from $m$ classifiers. How can
adding two voters make an incorrect decision correct? There is only one way:
the $v$ voters must contain the maximum number of incorrect voters to still be
correct: $\frac{v-1}{2}$, and both added voters must be incorrect. That makes
the number of incorrect voters

$\frac{v-1}{2}+2=\frac{v+3}{2}=\frac{(v+2)+1}{2},$ (10)

out of $v+2$ voters. Since this is the minimum possible majority, starting
with fewer than $\frac{v-1}{2}$ incorrect voters or adding fewer than two
incorrect voters will not work. Similarly, to go from incorrect with $v$
voters to correct with $v+2$ voters, it is necessary to start with
$\frac{v+1}{2}$ incorrect voters and add two correct voters.

Note that $\Delta_{v}(m,i,v)$ is the difference between the probability of
going from correct to incorrect and the probability of going from incorrect to
correct. The probability of going from incorrect to correct is the probability
of selecting $\frac{v-1}{2}$ of the $i$ incorrect voters when selecting $v$ of
the $m$ classifiers without replacement, times the probability of getting two
incorrect classifiers when selecting two of the remaining $m-v$ classifiers as
voters:

$\frac{{{i}\choose{\frac{v-1}{2}}}{{m-i}\choose{\frac{v+1}{2}}}}{{{m}\choose{v}}}\left(\frac{i-\frac{v-1}{2}}{m-v}\right)\left(\frac{i-\frac{v-1}{2}-1}{m-v-1}\right).$
(11)

Similarly, the probability of going from incorrect to correct is:

$\frac{{{i}\choose{\frac{v+1}{2}}}{{m-i}\choose{\frac{v-1}{2}}}}{{{m}\choose{v}}}\left(\frac{m-i-\frac{v-1}{2}}{m-v}\right)\left(\frac{m-i-\frac{v-1}{2}-1}{m-v-1}\right).$
(12)

To find the difference, $\Delta_{v}(m,i,v)$, note that

${{i}\choose{\frac{v-1}{2}}}=\frac{i(i-1)!}{\left(\frac{v-1}{2}\right)!\left(i-\frac{v-1}{2}\right)\left(i-1-\frac{v-1}{2}\right)!}$
(13) $=i{{i-1}\choose{\frac{v-1}{2}}}\left(\frac{1}{i-\frac{v-1}{2}}\right),$
(14)

and

${{i}\choose{\frac{v+1}{2}}}=\frac{i(i-1)!}{\left(\frac{v+1}{2}\right)\left(\frac{v-1}{2}\right)!\left(i-\frac{v+1}{2}\right)!}$
(15)
$=\frac{i(i-1)!}{\left(\frac{v+1}{2}\right)\left(\frac{v-1}{2}\right)!\left(i-1-\frac{v-1}{2}\right)!}$
(16) $=i{{i-1}\choose{\frac{v-1}{2}}}\left(\frac{1}{\frac{v+1}{2}}\right).$
(17)

Similarly,

${{m-i}\choose{\frac{v+1}{2}}}=\left(m-i\right){{m-i-1}\choose{\frac{v-1}{2}}}\left(\frac{1}{\frac{v+1}{2}}\right),$
(18)

and

${{m-i}\choose{\frac{v-1}{2}}}=\left(m-i\right){{m-i-1}\choose{\frac{v-1}{2}}}\left(\frac{1}{m-i-\frac{v-1}{2}}\right).$
(19)

Use these equalities to factor out some common terms:

$\Delta_{v}(m,i,v)={{m}\choose{v}}^{-1}i{{i-1}\choose{\frac{v-1}{2}}}\left(m-i\right){{m-i-1}\choose{\frac{v-1}{2}}}$
(20)
$\left[\frac{\left(\frac{i-\frac{v-1}{2}}{m-v}\right)\left(\frac{i-\frac{v-1}{2}-1}{m-v-1}\right)}{\left(i-\frac{v-1}{2}\right)\left(\frac{v+1}{2}\right)}\right.$
(21)
$\left.-\frac{\left(\frac{m-i-\frac{v-1}{2}}{m-v}\right)\left(\frac{m-i-\frac{v-1}{2}-1}{m-v-1}\right)}{\left(\frac{v+1}{2}\right)\left(m-i-\frac{v-1}{2}\right)}\right].$
(22)

For both terms in brackets, cancel one denominator factor with a numerator
factor, and factor out the other denominator factors:

$\Delta_{v}(m,i,v)={{m}\choose{v}}^{-1}i{{i-1}\choose{\frac{v-1}{2}}}\left(m-i\right){{m-i-1}\choose{\frac{v-1}{2}}}$
(23)
$\frac{\left[\left(i-\frac{v-1}{2}-1\right)-\left(m-i-\frac{v-1}{2}-1\right)\right]}{\left(\frac{v+1}{2}\right)\left(m-v\right)\left(m-v-1\right)}.$
(24)

Then cancel in brackets:

$\Delta_{v}(m,i,v)={{m}\choose{v}}^{-1}i{{i-1}\choose{\frac{v-1}{2}}}\left(m-i\right){{m-i-1}\choose{\frac{v-1}{2}}}$
(25)
$\frac{\left[2i-m\right]}{\left(\frac{v+1}{2}\right)\left(m-v\right)\left(m-v-1\right)}.$
(26)

Only the term $2i-m$ may be negative. It is negative if $i<\frac{m}{2}$ and
positive if $i>\frac{m}{2}$. Based on the second through fifth factors,
$\Delta_{v}(m,i,v)=0$ if at least one of the following conditions holds:
$i=0$, $i=m$, $i-1<\frac{v-1}{2}$ (equivalently: $i<\frac{v+1}{2}$), or
$m-i<\frac{v+1}{2}$. ∎

##  4 Optimal numbers of voters

Figure 2: Any (odd) number of voters may be optimal. For $m=101$, error curves
for which each $v_{*}\in\left\\{{1,3,\ldots,99}\right\\}$ is an error-
minimizing number of voters. (Each curve is based on a different distribution
over number of ensemble classifiers incorrect. Average ensemble classifier
error rate is 0.3.) Figure 3: Distributions $w_{i}$ for
$i\in\left\\{{0,\ldots,101}\right\\}$ that produce curves for which $v=v_{*}$
is an error-minimizing number of voters.

Any (odd) number of voters may be optimal. For each
$v_{*}\in\left\\{{1,3,\ldots,99}\right\\}$, with $m=101$, Figure 2 shows a
voting error rate curve for a distribution $(w_{0},\ldots,w_{m})$ for which
$v_{*}$ is an error-minimizing number of voters. For each curve, the
distribution $(w_{0},\ldots,w_{m})$ is produced by a linear program that
maximizes difference in error rates between using 101 and using $v_{*}$
voters, subject to constraints:

  * 1.

voting error rate with $v_{*}$ classifiers is no more than that for a single
voter, for $v_{*}-2$ voters, or for $v_{*}+2$ voters,

  * 2.

voting error rate with all classifiers voting is at most $0.5$ (otherwise, it
is possible to just use the opposite of its output to get a lower error rate),
and

  * 3.

average error rate over classifiers is 0.3.

The figure shows that any odd number of voters up to 99 can minimize error
rate for $m=101$. The figure does not show this for $v_{*}=101$, since the
linear program optimizes the difference between using $v_{*}$ and using 101
voters. However, Figure 1 shows that 101 is the optimal number of voters for
the distribution $w_{50}=1$ and all other $w_{i}=0$.

Figure 3 shows the distributions of weights for each $v_{*}$ curve in Figure
2. For most $v_{*}$ values, the error count distributions
$(w_{0},\ldots,w_{m})$ that give the largest gap between using $v_{*}$ voters
and the full set of $m=101$ voters have some weight on $w_{0}$, some on
$w_{51}$, and some on one or two intermediate numbers of errors. The curve for
each $v_{*}$ is the weighted sum of the ”basis” curves for $i=0$, $i=51$, and
the intermediate value or values from Figure 1. The weight on $w_{0}$ lowers
error rates, helping enforce the constraint on average error rate over
classifiers and the constraint on error rate for 101 voters. The weight on
$w_{51}$ ensures that the curve for $v_{*}$ goes up on the right, increasing
the difference in error rates between $v_{*}$ voters and 101 voters as well as
helping to ensure that $v_{*}$ voters is locally optimal compared to $v_{*}+2$
voters. Any weights on intermediate values can contribute to the curvature,
ensuring that $v_{*}$ voters is locally optimal compared to $v_{*}-2$ voters.
These weights can give us insight into how to prove that any (odd) number of
voters can be optimal for any number $m$ of classifiers:

######  Theorem 4.

For $m>0$ and any $v_{*}\in\left\\{{1,3,\ldots,m}\right\\}$, there is a
distribution $(w_{0},\ldots,w_{m})$, where $w_{i}$ is the probability that $i$
of $m$ classifiers are in error, such that $v_{*}$ voters achieves the minimum
voting error rate.

###### Proof.

First consider the boundary cases: $v_{*}=1$ and $v_{*}=m$ (or $v_{*}=m-1$ if
$m$ is even). If $v_{*}=1$, then set $w_{m-1}=1$. That gives a $\frac{m-1}{m}$
error rate for $v=1$, since there is one correct classifier, and error rate
one for $v\geq 3$, since the single correct classifier cannot form a majority.
Similarly, if $v_{*}=m$ or $v_{*}=m-1$, then set $w_{i}=1$ for
$i=\frac{v_{*}-1}{2}$. That produces error rate zero for $v_{*}$ voters,
because the incorrect voters cannot form a majority, but the error rate for
smaller $v$ values is positive since the incorrect voters can form a majority
for those values.

Now consider intermediate values: $1<v_{*}<m-1$. Let $a=\frac{v_{*}-1}{2}$ and
$b=m-\frac{v_{*}+1}{2}$. For $a$ errors among $m$ classifiers, the voting
error rate is zero for $v\geq v_{*}$. For $b$ errors, it is one for $v>v_{*}$,
but less than one for $v=v_{*}$, because the $\frac{v_{*}+1}{2}$ can form a
majority among $v_{*}$ voters. As a result, any weighted average (with
positive weights) of error curves for $a$ and $b$ has voting error rate
greater than $v_{*}$ for all $v>v_{*}$. So set $w_{a}=\theta$,
$w_{b}=1-\theta$, and $w_{i}=0$ for all other $i$ values.

Then select $\theta\in(0,1)$ to ensure that the linear combination of curves
has voting error rates less than the rate for $v_{*}$ for all $v<v_{*}$. It is
possible to do this by taking $\theta$ sufficiently close to one, because
doing so makes the combined curve resemble the curve for $a$ errors more and
the curve for $b$ errors less. (This requires that the error rates on the
curve for $b$ be bounded, so that multiplying by $1-\theta$ can reduce their
influence as $1-\theta$ approaches zero, but they are bounded by one since
they are error rates.) By Theorem 3, the curve for $a$ errors is strictly
decreasing in $v$ for $v<v_{*}$, since $i=a=\frac{v_{*}-1}{2}<\frac{m}{2}$ and
$i=a=\frac{v_{*}-1}{2}\geq\frac{v+1}{2}$. ∎

##  5 Selecting the number of voters

Assume we have $n$ validation examples, drawn i.i.d. from the out-of-sample
distribution, and not used to train or select classifiers for the ensemble,
and we want to use them to select the number of voters for the ensemble. A
straightforward method is to apply the voting classifier for each odd number
of voters $v$ in one to $m$ to all the validation examples, selecting voters
at random for each number of voters and validation example. Then calculate the
error rate over the validation examples for each number of voters, and select
the number of voters with the lowest validation error rate.

To get error bounds, for each number of voters $v$, let $k_{v}$ be the number
of errors over the validation examples. Let $u(n,k,\delta)$ be a PAC (probably
approximately correct) upper bound and $t(n,k,\delta)$ be a PAC lower bound
for the probability that produces $k$ events in $n$ samples with bound failure
probability $\delta$. Since we simultaneously validate error rates for
$\frac{m+1}{2}$ different numbers of voters and use two-sided bounds, for
$\delta>0$, with probability at least $1-\delta$, each number of voters has
out-of-sample distribution error rate in the range
$t(n,k_{v},\frac{\delta}{m+1})$ to $u(n,k_{v},\frac{\delta}{m+1})$. For
example, using Hoeffding bounds (Hoeffding, 1963), the range is:

$\frac{k_{v}}{n}\pm\sqrt{\frac{\ln(m+1)-\ln\delta}{2n}}.$ (27)

In practice, use a binomial inversion bound (Hoel, 1954; Langford, 2005), to
get a tighter bound range.

Selecting voters at random for each example introduces some variance. To
produce lower-variance estimates of voting error rates, instead compute for
each validation example $j$ the number of ensemble classifiers in error
$i_{j}$. Recall from Equation 5 that $r(m,i,v)$ is the expected voting error
rate for $v$ voters, given $i$ ensemble classifiers in error. Then, for each
number of voters $v$, an estimate of out-of-sample error rate is:

$\frac{1}{n}\sum_{j=1}^{n}r(m,i_{j},v).$ (28)

Let $\hat{w}_{i}$ be the fraction of validation examples for which there are
$i$ classifiers in error ($i_{j}=i$). Then the estimate is

$=\sum_{i=0}^{m}\hat{w}_{i}r(m,i,v).$ (29)

Refer to these estimates as the inference estimates, since they use estimates
of the rates of numbers of errors in the ensemble to infer a estimates of out-
of-sample error rates for different numbers of voters.

######  Theorem 5.

For each number of voters $v$, the out-of-sample error rate estimate from
using validation data to compute estimates $\hat{w}_{i}$ and using them to
infer average voting error rate has variance less than or equal to the
estimate from applying randomly-selected voters to validation examples.

###### Proof.

For inference, the estimate is the mean of $r(m,i,v)$ over validation
examples, where $i$ is the number of ensemble classifiers in error. For
brevity, call $r(m,i,v)$ simply $r_{i}$. The direct estimate is the mean over
validation examples of one if voting errs and zero otherwise. For both, the
variance sums over examples, since the validation examples are independent
samples. So we can focus on the variances for a single validation example.

For direct estimation, the single-example error estimate is one with
probability $p$, where $p$ is the out-of-sample distribution error rate for
using $v$ voters, and zero with probability $1-p$. Since it is a Bernoulli
random variable, it has variance $p(1-p)=p-p^{2}$.

For inference, the single-example error estimate is $r(m,i,v)$, with
probability $w_{i}$ for each value of $i$. The variance is the difference
between the expectation of the square and the square of the expectation:

$\sum_{i}w_{i}r_{i}^{2}-\left[\sum_{i}w_{i}r_{i}\right]^{2}.$ (30)

But

$p=\sum_{i}w_{i}r_{i},$ (31)

so the variance is

$\sum_{i}w_{i}r_{i}^{2}-p^{2}.$ (32)

Recall that the variance for direct estimation is $p-p^{2}$. So the difference
between variances is

$p-\sum_{i}w_{i}r_{i}^{2}=\sum_{i}w_{i}r_{i}-\sum_{i}w_{i}r_{i}^{2}=\sum_{i}w_{i}\left[r_{i}-r_{i}^{2}\right].$
(33)

Since each $r_{i}$ is a probability (of voting error given $i$ ensemble
errors), $r_{i}\in[0,1]$. So $r_{i}^{2}\leq r_{i}$. ∎

##  6 Error Bounds and Inference

###  6.1 Error Bounds

Now consider how to compute error bounds based on the inference estimates. One
way is to apply simultaneous Hoeffding bounds:

######  Theorem 6.

With probability at least $1-\delta$, the out-of-sample error rates for all
numbers of voters $v$ are within

$\sqrt{\frac{\ln(m+1)-\ln\delta}{2n}}$ (34)

of the inference estimates from Expressions 28 and 29.

###### Proof.

From Expression 28, the inference estimate for each $v$ is

$\frac{1}{n}\sum_{j=1}^{n}r(m,i_{j},v).$ (35)

This is the average of $n$ i.i.d. random variables $r(m,i_{j},v)\in[0,1]$, one
for each validation example $j$. The estimate’s mean (over draws of validation
examples) is the out-of-sample error rate for $v$, since $r(m,i,v)$ is the
average error rate for $v$ voters, averaged over all sets of $v$ voters. So
Hoeffding bounds apply (Hoeffding, 1963). There are $\frac{m+1}{2}$ numbers of
voters, and two-sided bounds, making $m+1$ simultaneous validations. So set
$\delta$ to $\frac{\delta}{m+1}$ in the Hoeffding bound. ∎

###  6.2 Validation by Inference

Alternatively, we could first bound out-of-sample rates of $i$ errors among
the ensemble classifiers, then use those bounds to infer bounds on ensemble
error rates. (This strategy is called validation by inference (Bax, 2000).) As
before, let $w_{i}$ be the out-of-sample rate of $i$ errors among the $m$
ensemble classifiers, and let $\hat{w}_{i}$ be the in-sample rate over $n$
validation examples. Also as before, let $u(n,k,\delta)$ and $t(n,k,\delta)$
be PAC upper and lower bounds on the out-of-sample probability that produces
$k$ events in $n$ samples, with bound failure probability $\delta$.

Then, using simultaneous validation for $2(m+1)$ bounds (2 for upper and lower
bounds, and $m+1$ for zero to $m$ errors among the ensemble classifiers), with
probability at least $1-\delta$,

$\forall_{i\in\\{1,\ldots,m\\}}w_{i}\in\left[t(n,\hat{w}_{i}n,\frac{\delta}{2(m+1)}),u(n,\hat{w}_{i}n,\frac{\delta}{2(m+1)})\right].$
(36)

(Dividing $\delta$ to get simultaneous bounds is known as the Bonferroni
correction (Bonferroni, 1936; Dunn, 1961).)

To derive out-of-sample error bounds for each number of voters $v$, use linear
programming to optimize

$\sum_{i=0}^{m}w_{i}r(m,i,v)$ (37)

over the set of feasible out-of-sample rates of numbers of errors given by
Expression 36, with the additional constraints

$\sum_{i=0}^{m}w_{i}=1\hbox{ and }\forall i:w_{i}\geq 0,$ (38)

minimizing for lower bounds and maximizing for upper bounds.

Compare these bounds to the bounds from Theorem 6. These bounds allow binomial
inversion for each $t_{i}$ and $u_{i}$, since each $\hat{w}_{i}$ has a
binomial distribution, and these tend to be tighter than Hoeffding bounds and
other derived bounds. (Binomial inversion gives sharp bounds.) However, these
bounds divide $\delta$ by $2(m+1)$ rather than $m+1$, doubling the bound
failure probability allocated to each probability bound, because we use $m+1$
estimated rates of numbers of errors among classifiers to infer error bounds
for only $\frac{m+1}{2}$ numbers of voters $v$.

###  6.3 Using the Multinomial Distribution – Future Work

Together, the $\hat{w}_{i}$ values are a sample from a multinomial
distribution with probabilities $w_{i}$. We should be able to use this
information to get tighter bounds on the $w_{i}$ values from multinomial
bounds, instead of using simultaneous binomial bounds over all $\hat{w}_{i}$.
Let $L(\mathbf{\hat{w}},\delta)$ be the set of probability vectors
$\mathbf{w}=(w_{0},\ldots,w_{m})$ that have probability at least $1-\delta$ of
generating a sample vector that is more likely than
$\mathbf{\hat{w}}=(\hat{w}_{0},\ldots,\hat{w}_{m})$. Call
$L(\mathbf{\hat{w}},\delta)$ the likely set. (Informally, $\mathbf{w}$ is in
the likely set unless $\mathbf{\hat{w}}$ is in the $\delta$-tail of the
multinomial distribution generated by probabilities $\mathbf{w}$.)

To compute an upper bound on out-of-sample error rate for each number of
voters $v$, solve:

$\max_{\mathbf{w}\in L(\mathbf{\hat{w}},\delta)}\sum_{i=0}^{m}w_{i}r(m,i,v).$
(39)

(For lower bounds, minimize instead of maximizing.) This produces valid upper
and lower bounds for all numbers of voters, with probability at least
$1-\delta$.

Constraining $\mathbf{w}$ to the likely set based on the multinomial
distribution allows validation by inference without using a Bonferroni
correction to divide $\delta$ by $2(m+1)$ as was required for the constraints
in Expression 36. This produces tighter constraints, so the resulting bounds
are at least as strong.

The challenge lies in computing the error bounds. We want to optimize a linear
function over the likely set. But the likely set may have a challenging shape
for optimization, because the tails of multinomial distributions are not
continuous in $\mathbf{w}$. To see why, suppose that for some $\mathbf{w}$
some other sample vector is equally as likely as $\mathbf{\hat{w}}$. Then
perturbing $\mathbf{w}$ can change the ordering of those likelihoods, so that
the likelihood of the other sample vector becomes greater than that of
$\mathbf{\hat{w}}$, shifting the other sample vector’s full probability out of
the tail in a discontinuous jump.

So one goal for future research is to identify a superset of the likely set
that is amenable to optimization and does not contain distributions
$\mathbf{w}$ outside the likely set that would significantly weaken the
resulting error bounds. There are approximations to the likely set that make
optimization easier. For example, consider Pearson’s $X^{2}$ statistic
(Pearson, 1900; Read and Cressie, 1988; Cressie and Read, 1984):

$X^{2}(\mathbf{w},\mathbf{\hat{w}})=(m+1)\sum_{i=0}^{m}\frac{(\hat{w}_{i}-w_{i})^{2}}{w_{i}},$
(40)

with term $i$ zero if $w_{i}=\hat{w}_{i}=0$. Asymptotically, $X^{2}$ has a
chi-squared distribution with $m$ degrees of freedom. So if we let
$C_{\delta}$ be the value for which the cdf of that distribution is $\delta$,
then we can define an approximate likely set:

$\tilde{L}(\mathbf{\hat{w}},\delta)\equiv\left\\{\mathbf{w}\left|X^{2}(\mathbf{w},\mathbf{\hat{w}})\leq
C_{\delta}\right.\right\\}.$ (41)

This set has smooth boundaries. However, it is not a superset of the likely
set.

To identify a suitable superset of the likely set, perhaps we can apply bounds
on the difference between $X^{2}$ (or similar statistics) and the chi-squared
distribution (Matsunawa, 1977; Siotani and Fujikoshi, 1984; Bickel and Ghosh,
1990; Taneichi et al., 2002; Gaunt et al., 2016; Ouimet, 2021) to expand an
approximate likely set, for example by increasing the constraint $C_{\delta}$
on $X^{2}$ to ensure that all $\mathbf{w}$ in the likely set are enclosed in
the region of the approximate set while keeping the set small enough to yield
effective error bounds. It may also be possible to extend bounds on $L_{1}$
distance between $\mathbf{\hat{w}}$ and $\mathbf{w}$ (Valiant and Valiant,
2017; Balakrishnan and Wasserman, 2018) to derive a superset of the likely set
that gives linear constraints instead of a feasible region with curved
boundaries.

Within optimization procedures, computing tail probabilities (the cdf of
$\mathbf{\hat{w}}$ given $\mathbf{w}$) directly is infeasible for even
moderate-sized ensembles, because the number of ways for $n$ samples to fall
into $m+1$ categories is ${n+m}\choose{m}$. Monte Carlo methods (Hope, 1968;
Jann, 2008) can estimate the tail probability to arbitrary accuracy with
arbitrarily high probability. Also, there are evolving methods to cleverly
collect terms for exact tail computation (Baglivo et al., 1992; Keich and
Nagarajan, 2006; Resin, 2020).

The problem of identifying a worst likely generator for multinomial samples is
an interesting statistical problem, with applications beyond ensemble
validation. It is not clear whether approaches based on the multinomial tail
can be more effective in practice than approaches that split $\delta$ and
perform simultaneous validation over individual categories. (In our case, each
number of errors $i$ among the ensemble classifiers is a category.) The
simpler approach of simultaneous validation can use sharp binomial inversion
bounds within each category, and it can also benefit from the freedom to split
$\delta$ non-uniformly. Finally, both approaches could benefit from tuning the
constraints to the weights (the $r(m,i,v)$ values in our case) used to
evaluate the generating distributions. For example, it is possible to merge
categories that have similar weights to reduce the problem’s dimensionality.

## References

  * Baglivo et al. (1992) Baglivo, J., Olivier, D., Pagano, M., 1992.  Methods for exact goodness-of-fit tests.  Journal of the American Statistical Association 87, 464–469.  doi:10.1080/01621459.1992.10475227.
  * Balakrishnan and Wasserman (2018) Balakrishnan, S., Wasserman, L., 2018\.  Hypothesis testing for high-dimensional multinomials: A selective review.  The Annals of Applied Statistics 12, 727 – 749.  URL: https://doi.org/10.1214/18-AOAS1155SF, doi:10.1214/18-AOAS1155SF.
  * Bax (1998) Bax, E., 1998.  Validation of voting committees.  Neural Computation 10, 975–986.  URL: https://doi.org/10.1162/089976698300017584, doi:10.1162/089976698300017584.
  * Bax (2000) Bax, E., 2000.  Using validation by inference to select a hypothesis function, in: Pattern Recognition, International Conference on, IEEE Computer Society, Los Alamitos, CA, USA. p. 2700.  URL: https://doi.ieeecomputersociety.org/10.1109/ICPR.2000.906171, doi:10.1109/ICPR.2000.906171.
  * Begin et al. (2016) Begin, L., Germain, P., Laviolette, F., Roy, J.F., 2016\.  Pac-bayesian bounds based on the renyi divergence.  Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) .
  * Bennett and Lanning (2007) Bennett, J., Lanning, S., 2007\.  The netflix prize.  Proceedings of the KDD Cup Workshop , 3–6.
  * Bickel and Ghosh (1990) Bickel, P.J., Ghosh, J.K., 1990\.  A Decomposition for the Likelihood Ratio Statistic and the Bartlett Correction–A Bayesian Argument.  The Annals of Statistics 18, 1070 – 1090.  URL: https://doi.org/10.1214/aos/1176347740, doi:10.1214/aos/1176347740.
  * Bonab and Can (2019) Bonab, H., Can, F., 2019\.  Less is more: A comprehensive framework for the number of components of ensemble classifiers.  IEEE Transactions on Neural Networks and Learning Systems 30, 2735–2745.
  * Bonferroni (1936) Bonferroni, C.E., 1936.  Teoria statistica delle classi e calcolo delle probabilità .
  * Breiman (1996) Breiman, L., 1996.  Bagging predictors.  Machine Learning 24, 123–140.
  * Breiman (2001) Breiman, L., 2001.  Random forests.  Machine Learning 45, 5–32.
  * Chen and Guestrin (2016) Chen, T., Guestrin, C., 2016\.  Xgboost: A scalable tree boosting system.  KDD ’16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , 785–794URL: https://arxiv.org/pdf/1603.02754v1.pdf.
  * Cressie and Read (1984) Cressie, N., Read, T.R.C., 1984\.  Multinomial goodness-of-fit tests.  J. R. Statist. Soc. B 46, 440–464.
  * Dietterich (2000) Dietterich, T.G., 2000.  Ensemble methods in machine learning, in: Multiple Classifier Systems, Springer Berlin Heidelberg, Berlin, Heidelberg. pp. 1–15.
  * Dunn (1961) Dunn, O.J., 1961.  Multiple comparisons among means.  Journal of the American Statistical Association 56, 52–64.  URL: https://www.tandfonline.com/doi/abs/10.1080/01621459.1961.10482090, doi:10.1080/01621459.1961.10482090.
  * Esposito and Saitta (2004) Esposito, R., Saitta, L., 2004\.  A monte carlo analysis of ensemble classification.  doi:10.1145/1015330.1015386.
  * Freund and Schapire (1997) Freund, Y., Schapire, R., 1997\.  A decision-theoretic generalization of on-line learning and an application to boosting.  System Sciences 55, 119–139.
  * Gaunt et al. (2016) Gaunt, R.E., Pickett, A., Reinert, G., 2016.  Chi-square approximation by Stein’s method with application to Pearson’s statistic.  arxiv URL: https://arxiv.org/pdf/1507.01707.pdf.
  * Gomes et al. (2017) Gomes, H.M., Barddal, J.P., Enembreck, F., Bifet, A., 2017\.  A survey on ensemble learning for data stream classification.  ACM Comput. Surv. 50.  URL: https://doi.org/10.1145/3054925, doi:10.1145/3054925.
  * Hernández-Lobato et al. (2013) Hernández-Lobato, D., Martínez-Muñoz, G., Suárez, A., 2013.  How large should ensembles of classifiers be?  Pattern Recognition 46, 1323 – 1336.  URL: http://www.sciencedirect.com/science/article/pii/S0031320312004554, doi:https://doi.org/10.1016/j.patcog.2012.10.021.
  * Ho (1995) Ho, T.K., 1995.  Random decision forests.  Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal, QC , 278–282.
  * Ho (1998) Ho, T.K., 1998.  The random subspace method for constructing decision forests.  EEE Transactions on Pattern Analysis and Machine Intelligence 20, 832–844.
  * Hoeffding (1963) Hoeffding, W., 1963.  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association 58, 13–30.
  * Hoel (1954) Hoel, P.G., 1954.  Introduction to Mathematical Statistics.  Wiley.
  * Hope (1968) Hope, A.C.A., 1968.  A simplified Monte Carlo significance test procedure.  Journal of the Royal Statistical Society. Series B 30, 582–598.
  * Hu (2001) Hu, X., 2001.  Using rough sets theory and database operations to construct a good ensemble of classifiers for data mining applications.  Proc. IEEE Int. Conf. Data Mining (ICDM) , 233–240.
  * Jackowski (2018) Jackowski, K., 2018.  New diversity measures for data stream classification ensembles 74, 23–34.
  * Jann (2008) Jann, B., 2008.  Multinomial goodness-of-fit: Large-sample tests with survey design correction and exact tests for small samples.  The Stata Journal 8, 147–169.  URL: https://doi.org/10.1177/1536867X0800800201, doi:10.1177/1536867X0800800201, arXiv:https://doi.org/10.1177/1536867X0800800201.
  * Keich and Nagarajan (2006) Keich, U., Nagarajan, N., 2006\.  A fast and numerically robust method for exact multinomial goodness-of-fit test.  Journal of Computational and Graphical Statistics 15, 779--802.  URL: https://doi.org/10.1198/106186006X159377, doi:10.1198/106186006X159377.
  * Kuncheva (2004) Kuncheva, L.I., 2004.  Combining Pattern Classifiers: Methods and Algorithms.  Wiley.
  * Kuncheva et al. (2003) Kuncheva, L.I., Whitaker, C.J., Shipp, C.A., Duin, R.P.W., 2003\.  Limits on the majority vote accuracy in classifier fusion.  Pattern Analysis & Applications 6, 22--31.  URL: https://doi.org/10.1007/s10044-002-0173-7, doi:10.1007/s10044-002-0173-7.
  * Lam and Suen (1997) Lam, L., Suen, S.Y., 1997\.  Application of majority voting to pattern recognition: an analysis of its behavior and performance.  IEEE Transactions on Systems, Man, and Cybernetics \- Part A: Systems and Humans 27, 553--568.
  * Langford (2005) Langford, J., 2005.  Tutorial on practical prediction theory for classification.  Journal of Machine Learning Research 6, 273--306.
  * Langford et al. (2001) Langford, J., Seeger, M., Megiddo, N., 2001.  An improved predictive accuracy bound for averaging classifiers, in: In Proceeding of the Eighteenth International Conference on Machine Learning, pp. 290--297.
  * Li (2010) Li, P., 2010.  Robust logitboost and adaptive base class (abc) logitboost.  Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI’10) , 302–311.
  * Liu et al. (2004) Liu, H., Mandvikar, A., Mody, J., 2004.  An empirical study of building compact ensembles.  Web-Age Information Management (WAIM) , 622--627.
  * Matsunawa (1977) Matsunawa, T., 1977.  Approximations to the probabilities of binomial and multinomial random variables and chi-square type statistics.  Annals of the Institute of Statistical Mathematics 29, 333.  URL: https://doi.org/10.1007/BF02532796, doi:10.1007/BF02532796.
  * McAllester (1999) McAllester, D.A., 1999.  Pac-bayesian model averaging, in: In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, ACM Press. pp. 164--170.
  * Oshiro et al. (2012) Oshiro, T.M., Perez, P.S., Baranauskas, J.A., 2012.  How many trees in a random forest?, in: Perner, P. (Ed.), Machine Learning and Data Mining in Pattern Recognition, Springer Berlin Heidelberg, Berlin, Heidelberg. pp. 154--168.
  * Ouimet (2021) Ouimet, F., 2021.  A precise local limit theorem for the multinomial distribution and some applications.  Journal of Statistical Planning and Inference 215, 218--233.  URL: https://www.sciencedirect.com/science/article/pii/S0378375821000392, doi:https://doi.org/10.1016/j.jspi.2021.03.006.
  * Pearson (1900) Pearson, K., 1900.  On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling.  Philosophical Magazine. Series 5 302, 157--175.
  * Read and Cressie (1988) Read, T.R.C., Cressie, N.A.C., 1988\.  Goodness-of-fit statistics for discrete multivariate data.  New York: Springer-Verlag.
  * Resin (2020) Resin, J., 2020.  A simple algorithm for exact multinomial tests.  arxiv URL: https://arxiv.org/abs/2008.12682.
  * Rokach (2009) Rokach, L., 2009.  Collective-agreement-based pruning of ensembles.  Computational Statistics & Data Analysis 53, 1015 -- 1026.  URL: http://www.sciencedirect.com/science/article/pii/S0167947308005707, doi:https://doi.org/10.1016/j.csda.2008.12.001.
  * Rokach (2010) Rokach, L., 2010.  Ensemble-based classifiers.  Artificial Intelligence Review 33, 1--39.  URL: https://doi.org/10.1007/s10462-009-9124-7, doi:10.1007/s10462-009-9124-7.
  * Schapire (1990) Schapire, R.E., 1990.  The strength of weak learnability.  Machine Learning 5, 197--227.
  * Shahzad and Lavesson (2013) Shahzad, R.K., Lavesson, N., 2013\.  Comparative analysis of voting schemes for ensemble-based malware detection.  Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA) 4, 98--117.
  * Siotani and Fujikoshi (1984) Siotani, M., Fujikoshi, Y., 1984\.  Asymptotic approximations for the distributions of multinomial goodness-of-fit statistics.  Hiroshima Math J. 14, 115--124.
  * Taneichi et al. (2002) Taneichi, N., Sekiya, Y., Suzukawa, A., 2002.  Asymptotic approximations for the distributions of the multinomial goodness-of-fit statistics under local alternatives.  Journal of Multivariate Analysis 81, 335--359.  URL: https://www.sciencedirect.com/science/article/pii/S0047259X01920020, doi:https://doi.org/10.1006/jmva.2001.2002.
  * Tsoumakas et al. (2008) Tsoumakas, G., Partalas, I., Vlahavas, I., 2008.  A taxonomy and short review of ensemble selection.  Proc. Workshop Supervised Unsupervised Ensemble Methods Appl. , 41--46.
  * Valiant and Valiant (2017) Valiant, G., Valiant, P., 2017\.  An automatic inequality prover and instance optimal identity testing.  SIAM Journal on Computing 46, 429--455.
  * Wolpert (1992) Wolpert, D., 1992.  Stacked generalization.  Neural networks 5, 241--259.
  * Yang (2011) Yang, L., 2011.  Classifiers selection for ensemble learning based on accuracy and diversity.  Procedia Engineering 15, 4266 -- 4270.  URL: http://www.sciencedirect.com/science/article/pii/S1877705811023010, doi:https://doi.org/10.1016/j.proeng.2011.08.800. cEIS 2011.
  * Zheng et al. (2019) Zheng, H., Park, K.H., Lee, J.Y., Ryu, K.H., 2019\.  A majority voting ensemble classifier to predict hypertension based on knhanes dataset.  International Journal of Design, Analysis and Tools for Integrated Circuits and Systems 8, 13--18.