j)$ indicate the pixel indices. When the training set consists of precise image-mask pairs $(\mathbf{X},\mathbf{T})$, we refer to the task as \textbf{fully-supervised object localization (FSOL)}. In this paper, we consider the case when only an image-level label $Y\in\{0,1\}$ for global presence of the object of interest is provided per training image $\mathbf{X}$. This task is referred to as the \textbf{weakly-supervised object localization (WSOL)}.

One can treat an input image $\mathbf{X}$ as a bag of stride-1 sliding window patches of suitable side lengths, $h$ and $w$: $(X_{11},\cdots,X_{HW})$ with $X_{ij}\in\mathbb{R}^{h\times w}$. The object localization task is then the problem of predicting the object presence $T_{ij}$ at the image patch $X_{ij}$. The weak supervision imposes the requirement that each training image $\mathbf{X}$, represented as $(X_{11},\cdots,X_{HW})$, is only collectively labeled with a single label $Y\in\{0,1\}$ indicating whether at least one of the patches represents the object. This formulation is an example of the multiple-instance learning (MIL)~\cite{MIL}, as observed by many traditional WSOL works~\cite{papandreou2015weakly,WSOLasMIL2,WSOLasMIL3,WSOLasMIL4}. 


Following the patch classification point of view, we formulate WSOL task as a mapping from patches $X$ to the binary labels $T$ (indices dropped). We assume that the patches $X$, image-level labels $Y$, and  the pixel-wise labeling $T$ in our data arise in an i.i.d. fashion from the joint distribution $p(X,Y,T)$. See Figure~\ref{fig:overview} for an overview. The aim of WSOL is to produce a scoring function $s(X)$ such that thresholding it at $\tau$ closely approximates the binary label $T$.

\addition{
\subsection{Case study: CAM as MIL}

In light of the above discussion, we re-interpret CAM~\cite{CAM} and its variants, a representative class of methods for WSOL, as a patch classifier trained under the MIL objective.

CAM~\cite{CAM} use the scoring rules based on the posterior $s(X)=p(Y|X)$.
Originally, CAM is a technique applied on a convolutional neural network classifier $h:\mathbb{R}^{3\times H \times W}\rightarrow\mathbb{R}^{C}$, where $C$ is the number of classes, of the following form:
\begin{equation}
h_{c}(X)=\sum_{d}W_{cd}\left(\frac{1}{HW}\sum_{ij}g_{dij}(\mathbf{X})\right)
\end{equation}
where $c,d$ are the channel-dimension indices and $i,j$ are spatial-dimension indices. In other words, $h$ is a fully convolutional neural network, followed by a global average pooling (GAP) and a linear (fully-connected) layer into a $C$-dimensional vector. We may swap the GAP and linear layers without changing the representation:
\begin{align}
h_{c}(X)
&=\frac{1}{HW}\sum_{ij}\left(\sum_{d}W_{cd}g_{dij}(\mathbf{X})\right) \\
&=:\frac{1}{HW}\sum_{ij}f_{cij}(\mathbf{X}) 
\end{align}
where $f$ is now a fully-convolutional network. Each pixel $(i,j)$ in the feature map, $\left(f_{1ij}(\mathbf{X}),\cdots,f_{Cij}(\mathbf{X})\right)$, corresponds to the classification result of the corresponding field of view in the input $\mathbf{X}$, written as $X_{ij}$. Thus, we equivalently write \begin{align}
h_{c}(X)=\frac{1}{HW}\sum_{ij}f_{c}(X_{ij}) 
\end{align}
where $f$ is now re-defined as a image patch classifier with 1-dimensional feature output (not fully convolutional).

The bag of patch-wise classification scores $f_{c}(X_{ij})$ is then supervised by the error between the mean outputs $h_{c}(X)$ and the ground truth label $Y$, measured by the softmax cross-entropy loss:
\begin{equation}
    \log p(Y|\mathbf{X}):=
    \log \text{softmax}^Y\left(\frac{1}{HW}\sum_{ij}f(X_{ij})\right).
\end{equation}
In other words, CAM trains the network for patch-wise scores $f_{c}(X_{ij})$ to estimate the image-wide posterior $p(Y|\mathbf{X})$. 

At inference time, CAM estimates the pixel-wise posterior $p(Y|X_{ij})$ approximately by performing a score normalization for $f_Y(X_{ij})$ (Table~\ref{tab:prior_wsol_operating_thresholds}).
}

\subsection{When is WSOL ill-posed?}
\label{subsec:when_is_wsol_unsolvable}

We show that if background cues are more strongly associated with the target labels $T$ than some foreground cues, the localization task cannot be solved, even when we know the exact posterior $p(Y|X)$ for the image-level label $Y$. We will make some strong assumptions in favor of the learner, and then show that WSOL still cannot be perfectly solved. 

We assume that there exists a finite set of \textbf{cue} labels $\mathcal{M}$ containing all patch-level concepts in natural images. For example, patches from a duck image are one of \{duck's head, duck's feet, sky, water, $\cdots$\} (see Figure~\ref{fig:duck_feet_lake}). We further assume that every patch $X$ is equivalently represented by its cue label $M(X)\in\mathcal{M}$. Therefore, from now on, we write $M$ instead of $X$ in equations and examine the association arising in the joint distribution $p(M,Y,T)$. 
We write $M^{\text{fg}},M^{\text{bg}}\in\mathcal{M}$ for foreground and background cues.

\newcommand{\text{duck}}{\text{duck}}
\newcommand{\text{duck}^c}{\text{duck}^c}
\newcommand{\text{feet}}{\text{feet}}
\newcommand{\text{water}}{\text{water}}

\begin{figure}[t]
    \centering
    \includegraphics[width=1\linewidth]{figures/wsol_illposed_v5.pdf}\vspace{0.3em}
    \caption{\small\textbf{Ill-posed WSOL: An example.} Even the true posterior $s(M)=p(Y|M)$ may not lead to the correct prediction of $T$ if background cues are more associated with the class than the foreground cues (\eg $p(\text{duck}|\text{water})> p(\text{duck}|\text{feet})$).}
    \label{fig:duck_feet_lake}
    \vspace{-1.5em}
\end{figure}

\addition{We first define an evaluation metric for our score map for an easier argumentation. 
\begin{definition}
For a scoring rule $s$ and a threshold $\tau$, we define the \textbf{pixel-wise localization accuracy} $\text{\pxacc}(s,\tau)$ as the probability of correctly predicting the pixel-wise labels:
\begin{align}
    \text{\pxacc}(s,\tau)=
    {P}_{X,T}(s(X)\geq\tau\mid T=1)\cdot{P}_{X,T}(T=1)
    \nonumber\\
    +{P}_{X,T}(s(X)<\tau\mid T=0)\cdot{P}_{X,T}(T=0)
    \nonumber
\end{align}
\end{definition}
}

We argue that, even with access to the joint distribution $p(Y,M)$, it may not be possible to make perfect predictions for the patch-wise labels $T(M)$.
\begin{lemma}
    Assume that the true posterior $p(Y|M)$ with a continuous pdf is used as the scoring rule $s(M)=p(Y|M)$. Then, there exists a scalar $\tau\in\mathbb{R}$ such that $s(M)\geq\tau$ is identical to $T$ if and only if the foreground-background posterior ratio $\frac{p(Y=1|M^{\text{fg}})}{p(Y=1| M^{\text{bg}})}\geq 1$ almost surely, conditionally on the event $\{T(M^{\text{fg}})=1\text{ and }T(M^{\text{bg}})=0\}$.
\end{lemma}
\addition{\begin{proof}
    We write $E