$\displaystyle\log\left(\frac{1}{\varepsilon}\right)$
$\displaystyle=\order{\log\left(\frac{\kappa^{3}\log^{2}\left(\frac{\kappa}{\delta_{b}}\right)}{\delta_{b}}\right)}$
$\displaystyle=\order{\log\left(\frac{\kappa}{\delta}\right)}$

Now we can substitute the cost of the individual components in Equation 35 to
obtain the final cost as

$\displaystyle\order{\kappa\log\kappa\left(\frac{\sqrt{w_{\text{max}}}\norm{A}_{F}+\sqrt{\lambda}\norm{L}_{F}}{\sqrt{w_{\text{max}}}\norm{A}+\sqrt{\lambda}\norm{L}}\log\left(\frac{\kappa}{\delta}\right)\mathrm{polylog}\left(\frac{Nd}{\varepsilon}\right)+\sqrt{\frac{{w_{\text{max}}}}{{w_{\text{min}}}}}\mathrm{polylog}\left(\frac{N\kappa}{\delta}\right)\right)}$
$\displaystyle=\order{\kappa\left(\frac{\sqrt{w_{\text{max}}}\norm{A}_{F}+\sqrt{\lambda}\norm{L}_{F}}{\sqrt{w_{\text{max}}}\norm{A}+\sqrt{\lambda}\norm{L}}+\sqrt{\frac{{w_{\text{max}}}}{{w_{\text{min}}}}}\right)\mathrm{polylog}\left(\frac{Nd\kappa}{\delta}\right)}$

∎

Now, for the sparse access model, we can obtain a block encoding similar to
Lemma 37 and a quantum state similar to Lemma 38, with the same query
complexities. Thus we have an algorithm similar to Theorem 39 in the sparse
access model as well. We directly state the complexity of this algorithm.

######  Theorem 40 (Quantum Weighted Least Squares with General
$\ell_{2}$-Regularization in the Sparse Access Model).

Let $A\in\mathbb{R}^{N\times d}$ be $(s^{A}_{r},s^{A}_{c})$ row-column sparse,
and similarly, let $L\in\mathbb{R}^{N\times d}$ be $(s^{L}_{r},s^{L}_{c})$
row-column sparse, with effective condition numbers $\kappa_{A}$ and
$\kappa_{L}$ respectively. Let $\lambda\in\mathbb{R}^{+}$. Let
$W\in\mathbb{R}^{N\times N}$ be a diagonal matrix with the largest and the
smallest diagonal entries being ${w_{\text{max}}},{w_{\text{min}}}$,
respectively. Suppose that the diagonal entries of $W$ are stored in a QROM
such that, for any $\delta>0$, we can compute
$\ket{j}{0}\mapsto\ket{j}\ket{w_{j}}$ in cost
$O\left(\mathrm{polylog}\left(Nd/\delta\right)\right)$ as well as
${w_{\text{max}}}$. Furthermore, suppose there exists a unitary that prepares
$\ket{b}$ at a cost $T_{b}$ and define,

$\kappa:=\kappa_{L}\left(1+\frac{\sqrt{{w_{\text{max}}}}\norm{A}}{\sqrt{\lambda}\norm{L}}\right)$

Then for any $\delta>0$ we can prepare a quantum state that is $\delta$-close
to

$\frac{(A^{T}WA+\lambda L^{T}L)^{-1}A^{T}W\ket{b}}{\norm{(A^{T}WA+\lambda
L^{T}L)^{-1}A^{T}W\ket{b}}}$

with probability $\Theta(1)$, at a cost of

$\order{\kappa\left(\frac{\sqrt{w_{\text{max}}}\sqrt{s_{r}^{A}s_{c}^{A}}+\sqrt{\lambda}\sqrt{s_{r}^{L}s_{c}^{L}}}{\sqrt{w_{\text{max}}}\norm{A}+\sqrt{\lambda}\norm{L}}+\sqrt{\frac{{w_{\text{max}}}}{{w_{\text{min}}}}}\leavevmode\nobreak\
T_{b}\right)\mathrm{polylog}\left(Nd,\kappa,\frac{1}{\delta}\right)}$ (51)

####  4.2.2 Quantum Generalized Least Squares

In this section, we assume that we have block-encoded access to the
correlation matrix $\Omega\in\mathbb{R}^{N\times N}$, with condition number
$\kappa_{\Omega}$. We begin by preparing a block encoding of $\Omega^{-1/2}$,
given an approximate block-encoding of $\Omega$.

######  Lemma 41 (Preparing $\Omega^{-1/2}$).

Let $\Omega\in\mathbb{R}^{N\times N}$ be a matrix with condition number
$\kappa_{\Omega}$ Let $U_{\Omega}$ be an
$(\alpha_{\Omega},a_{\Omega},\varepsilon_{\Omega})$-block-encoding of
$\Omega$, implemented in time $T_{\Omega}$. For any $\delta$ such that

$\varepsilon_{\Omega}=o\left(\frac{\sqrt{\norm{\Omega}}\delta}{\kappa^{1.5}\log\left(\frac{\kappa}{\sqrt{\norm{\Omega}}\delta}\right)}\right),$

we can prepare a
$(2\sqrt{\kappa_{\Omega}/\norm{\Omega}},a_{\Omega}+1,\delta)$-block-encoding
of $\Omega^{-1/2}$ at a cost of

$\order{\frac{\alpha_{\Omega}\kappa_{\Omega}}{\norm{\Omega}}\log\left(\frac{\kappa_{\Omega}}{\delta\sqrt{\norm{\Omega}}}\right)T_{\Omega}}$

Moreover, the condition number of $\Omega^{-1/2}$ is bounded by
$\sqrt{\kappa_{\Omega}}$.

###### Proof.

$U_{\Omega}$ can be re-interpreted as a
$(\frac{\alpha}{\norm{\Omega}},\leavevmode\nobreak\ a,\leavevmode\nobreak\
\frac{\varepsilon}{\norm{\Omega}})$-block-encoding of
$\frac{\Omega}{\norm{\Omega}}$. We can then prepare the required unitary by
invoking Theorem 30 on $U_{\Omega}$ with $c=1/2$ and some $\gamma$ such that
we get a $(2\sqrt{\kappa_{\Omega}},\leavevmode\nobreak\
a+1,\leavevmode\nobreak\ \gamma)$ block encoding of
$\sqrt{\norm{\Omega}}\Omega^{-1/2}$, which is a
$(2\sqrt{\frac{\kappa}{\norm{\Omega}}},\leavevmode\nobreak\
a+1,\leavevmode\nobreak\ \frac{\gamma}{\sqrt{\norm{\Omega}}})$ block encoding
of $\Omega^{-1/2}$. Fixing $\gamma=\sqrt{\norm{\Omega}}\delta$ gives us the
required result. ∎

We will now use this lemma in conjunction with Theorem 32 to develop quantum
algorithms for GLS with general $\ell_{2}$-regularization.

######  Theorem 42 (Quantum Generalized Least Squares with General
$\ell_{2}$-regularization).

Let $A,L\in\mathbb{R}^{N\times d}$ be the data and penalty matrices with
effective condition numbers $\kappa_{A},\kappa_{L}$ respectively. Let
$\Omega\in\mathbb{R}^{N\times N}$ be the covariance matrix with condition
number $\kappa_{\Omega}$. Let $\delta>0$ be the precision parameter. Define
$\kappa$ as

$\kappa:=\kappa_{L}\left(1+\frac{\sqrt{{\kappa_{\Omega}}}\norm{A}}{\sqrt{\lambda\norm{\Omega}}\norm{L}}\right).$

For some $\varepsilon_{A}$ such that

$\varepsilon_{A}=o\left(\frac{\delta\sqrt{{\norm{\Omega}}}}{\kappa^{3}\sqrt{{\kappa_{\Omega}}}\log^{2}\frac{\kappa}{\delta}}\right)$

we have access to $U_{A}$, an $(\alpha_{A},a_{A},\varepsilon_{A})$-block-
encoding of $A$ implemented in time $T_{A}$. For some $\varepsilon_{L}$ such
that

$\varepsilon_{L}=o\left(\frac{\delta}{\sqrt{\lambda}\kappa^{3}\log^{2}\frac{\kappa}{\delta}}\right)$

we have access to $U_{L}$, an $(\alpha_{L},a_{L},\varepsilon_{L})$-block-
encoding of $L$ implemented in time $T_{L}$. For some $\varepsilon_{\Omega}$
such that

$\varepsilon_{\Omega}=o\left(\frac{\delta}{\norm{A}\kappa^{3}{\kappa_{\Omega}}^{1.5}\log^{3}{\frac{\kappa}{\delta}}\log\left(\frac{{\kappa_{\Omega}}}{\norm{A}{\norm{\Omega}}}\right)}\right)$

we have access to $U_{\Omega}$, an
$(\alpha_{\Omega},a_{\Omega},\varepsilon_{\Omega})$-block-encoding of $\Omega$
implemented in time $T_{\Omega}$. Let $U_{b}$ be a unitary that prepares the
state $\ket{b}$ in time $T_{b}$.

Then we can prepare the quantum state that is $\delta$-close to

$\frac{\left(A^{T}\Omega^{-1}A+\lambda
L^{T}L\right)^{-1}A^{T}\Omega^{-1}\ket{b}}{\norm{\left(A^{T}\Omega^{-1}A+\lambda
L^{T}L\right)^{-1}A^{T}\Omega^{-1}\ket{b}}}$

with probability $\Theta(1)$, at a cost of

$\order{\kappa\sqrt{{\kappa_{\Omega}}}\log\kappa\left(\left(\frac{\alpha_{A}}{\norm{A}}T_{A}+\frac{\alpha_{L}}{\norm{L}}T_{L}+\frac{\alpha_{\Omega}{\kappa_{\Omega}}}{{\norm{\Omega}}}T_{\Omega}\right)\log^{3}\left(\frac{\kappa{\kappa_{\Omega}}\norm{A}\norm{L}}{\delta{\norm{\Omega}}}\right)+T_{b}\right)}$
(52)

using only $\order{\log\kappa}$ additional qubits.

###### Proof.

Observe that by choosing
$A^{\prime}:=\Omega^{-1/2}A,L^{\prime}:=L,\ket{b^{\prime}}:=\Omega^{-1/2}\ket{b}$
(upto normalization) in the quantum ordinary least squares, we get a state
proportional to $(A^{\prime T}A^{\prime}+\lambda L^{\prime
T}L^{\prime})^{-1}A^{\prime T}\ket{b^{\prime}}=(A^{T}\Omega^{-1}A+\lambda
L^{T}L)A^{T}\Omega^{-1}\ket{b}$, which is the desired state.

For convenience, let us define the matrix $B:=\Omega^{-1/2}$ (and therefore
$\kappa_{B}=\sqrt{{\kappa_{\Omega}}}$ and
$\norm{B}=\sqrt{{\kappa_{\Omega}}/{\norm{\Omega}}}$). We now need to prepare a
block-encoding of $BA$ and the quantum state
$\frac{B\ket{b}}{\norm{B\ket{b}}}$, which we then use to invoke Theorem 32.

We begin by using Lemma 41 with some precision $\varepsilon_{B}$ to construct
a $(\alpha_{B},a_{B},\varepsilon_{B})$-block-encoding of $B=\Omega^{-1/2}$,
where
$\alpha_{B}=2\sqrt{\frac{{\kappa_{\Omega}}}{{\norm{\Omega}}}}=2\norm{B}$, and
$a_{B}=a_{\Omega}+1$. This bounds $\varepsilon_{\Omega}$ as

$\varepsilon_{\Omega}=o\left(\frac{\sqrt{{\norm{\Omega}}}\varepsilon_{B}}{{\kappa_{\Omega}}^{1.5}\log\left(\frac{{\kappa_{\Omega}}}{\sqrt{{\norm{\Omega}}\varepsilon_{B}}}\right)}\right),$

and has a cost of

$T_{B}:=\order{\frac{\alpha_{\Omega}{\kappa_{\Omega}}}{{\norm{\Omega}}}\log\left(\frac{{\kappa_{\Omega}}}{\varepsilon_{B}\sqrt{{\norm{\Omega}}}}\right)T_{\Omega}}$

Then using Lemma 20 with precision $\gamma$ satisfying $\gamma\geq
4\sqrt{2}\max\left(\norm{B}\varepsilon_{A},\norm{A}\varepsilon_{B}\right)$, we
get a
$(2\norm{A}\norm{B},a_{A}+a_{B}+3,\gamma)$-block-encoding of
$A^{\prime}:=BA=\Omega^{-1/2}A$ at a cost

$T_{A^{\prime}}:=\order{\left(\frac{\alpha_{A}}{\norm{A}}T_{A}+\frac{\alpha_{B}}{\norm{B}}T_{B}\right)\log\left(\frac{\norm{A}\norm{B}}{\gamma}\right)}.$

To prepare $\frac{B\ket{b}}{\norm{B\ket{b}}}$, we use Lemma 13 with precision
$\varepsilon_{b}\geq 2\varepsilon_{B}\kappa_{B}/\norm{B}$. This prepares a
state that is $\varepsilon_{b}$-close to
$\ket{b^{\prime}}:=\frac{B\ket{b}}{\norm{B\ket{b}}}$ with constant success
probability at a cost of

$T_{b^{\prime}}:=\order{\frac{\alpha_{B}\kappa_{B}}{\norm{B}}(T_{B}+T_{b})}=\order{\kappa_{B}(T_{B}+T_{b})}$

We could invoke OLS directly using the above two, but that ends up with a
product of sub-normalization factors ($\alpha$ terms) in the complexity. We
want to avoid this, because in most common cases $\alpha$-s for block-
encodings are quite large. So we also pre-amplify $U_{L}$ using 12: for any
$\delta_{L}\geq 2\varepsilon_{L}$ we get a
$(\sqrt{2}\norm{L},a_{L}+1,\delta_{L})$-encoding of $L$ at a cost of

$T_{L^{\prime}}:=\order{\frac{\alpha_{L}}{\norm{L}}T_{L}\log\left(\frac{\norm{L}}{\delta_{L}}\right)}.$

Now that we have these, we can use Theorem 32 to get a quantum state
$\delta^{\prime}$-close to
$\ket{\psi}:=\frac{A_{L}^{+}\ket{b^{\prime}}}{\norm{A_{L}^{+}\ket{b^{\prime}}}}$,
where $A^{+}_{L}=(A^{T}\Omega^{-1}A+\lambda L^{T}L)^{-1}A^{T}\Omega^{-1/2}$.
This would require that $\gamma,\sqrt{\lambda}\delta_{L}\in
o\left(\frac{\delta^{\prime}}{\kappa^{3}\log^{2}\left(\frac{\kappa}{\delta^{\prime}}\right)}\right)$
and would cost

$\order{\kappa\log\kappa\left(\left(\frac{2\norm{A}\norm{B}+\sqrt{2\lambda}\norm{L}}{\norm{BA}+\sqrt{\lambda}\norm{L}}\right)\log\left(\frac{\kappa}{\delta^{\prime}}\right)(T_{A^{\prime}}+T_{L^{\prime}})+T_{b^{\prime}}\right)}.$

To simplify the ratio of norms term, we can first lower-bound
$\norm{BA}\geq\norm{A}/\norm{B^{-1}}=\norm{A}/\sqrt{\norm{\Omega}}$. And as
$\norm{B}=\sqrt{{\kappa_{\Omega}}/{\norm{\Omega}}}$, the whole term can be
simplified to $\order{\sqrt{{\kappa_{\Omega}}}}$. This simplifies the cost
expression to
$\order{\kappa\log\kappa\left(\sqrt{{\kappa_{\Omega}}}\log\left(\kappa/{\delta^{\prime}}\right)(T_{A^{\prime}}+T_{L^{\prime}})+T_{b^{\prime}}\right)}$.

We can compute the error between $\ket{\psi}$ and the expected state by using
Lemma 15. For the final error to be $\delta$, we have to choose
$\varepsilon_{b}=\delta/2\kappa$ and $\delta^{\prime}=\delta/2$. Therefore

$\displaystyle\varepsilon_{B}\leq\frac{\varepsilon_{b}\norm{B}}{4\kappa_{B}}=\Theta\left(\frac{\delta}{\kappa\sqrt{{\norm{\Omega}}}}\right)$
$\displaystyle\gamma,\sqrt{\lambda}\delta_{L}\in
o\left(\frac{\delta}{\kappa^{3}\log^{2}(\kappa/\delta)}\right)$
$\displaystyle\implies$
$\displaystyle\log\left(\frac{1}{\gamma}\right)=o\left(\log\left(\frac{\kappa}{\delta}\right)\right),\;\;\log\left(\frac{1}{\delta_{L}}\right)=o\left(\log\left(\frac{\sqrt{\lambda}\kappa}{\delta}\right)\right)$
$\varepsilon_{A}=o\left(\frac{\gamma}{\norm{B}}\right),\;\;\varepsilon_{B}=o\left(\frac{\gamma}{\norm{A}}\right)$

Combining both bounds of $\varepsilon_{B}$ by using sums or products, we can
effectively bound

$\varepsilon_{\Omega}=o\left(\frac{\delta}{\norm{A}\kappa^{3}{\kappa_{\Omega}}^{1.5}\log^{3}{\frac{\kappa}{\delta}}\log\left(\frac{{\kappa_{\Omega}}}{\norm{A}{\norm{\Omega}}}\right)}\right)$

Finally for the final costs, we calculate the respective coefficients of terms
$T_{A},T_{\Omega},T_{L}$ and $T_{b}$, (excluding the common factor of
$\kappa\sqrt{{\kappa_{\Omega}}}\log\kappa$ for brevity). Let us label these
“coefficient extraction” functions as $\mathcal{C}$ with matching subscripts,
and the total cost as $T$.

$\displaystyle\mathcal{C}_{A}(T)$
$\displaystyle=\order{\log\left(\frac{\kappa}{\delta}\right)\mathcal{C}_{A}(T_{A^{\prime}})}$
$\displaystyle=\order{\log\left(\frac{\kappa}{\delta}\right)\frac{\alpha_{A}}{\norm{A}}\log\left(\frac{\norm{A}\norm{B}}{\gamma}\right)}$
$\displaystyle=\order{\frac{\alpha_{A}}{\norm{A}}\log^{2}\left(\frac{\kappa{\kappa_{\Omega}}\norm{A}}{\delta{\norm{\Omega}}}\right)}$
$\displaystyle\mathcal{C}_{L}(T)$
$\displaystyle=\order{\log\left(\frac{\kappa}{\delta}\right)\mathcal{C}_{L}(T_{L^{\prime}})}$
$\displaystyle=\order{\log\left(\frac{\kappa}{\delta}\right)\frac{\alpha_{L}}{\norm{L}}\log\left(\frac{\norm{L}}{\delta_{L}}\right)}$
$\displaystyle=\order{\frac{\alpha_{L}}{\norm{L}}\log^{2}\left(\frac{\kappa\norm{L}}{\delta}\right)}$
$\displaystyle\mathcal{C}_{\Omega}(T)$
$\displaystyle=\order{\log\left(\frac{\kappa}{\delta}\right)\mathcal{C}_{\Omega}(T_{A^{\prime}})+\frac{\mathcal{C}_{\Omega}(T_{b^{\prime}})}{\sqrt{{\kappa_{\Omega}}}}}$
$\displaystyle=\order{\left(\log\left(\frac{\kappa}{\delta}\right)\log\left(\frac{\norm{A}\norm{B}}{\gamma}\right)+1\right)\mathcal{C}_{\Omega}(T_{B})}$
$\displaystyle=\order{\log^{2}\left(\frac{\kappa{\kappa_{\Omega}}\norm{A}}{\delta{\norm{\Omega}}}\right)\frac{\alpha_{\Omega}{\kappa_{\Omega}}}{{\norm{\Omega}}}\log\left(\frac{{\kappa_{\Omega}}}{\varepsilon_{B}\sqrt{{\norm{\Omega}}}}\right)}$
$\displaystyle=\order{\frac{\alpha_{\Omega}{\kappa_{\Omega}}}{{\norm{\Omega}}}\log^{3}\left(\frac{\kappa{\kappa_{\Omega}}\norm{A}}{\delta{\norm{\Omega}}}\right)}$
$\displaystyle\mathcal{C}_{b}(T)$
$\displaystyle=\order{\frac{\mathcal{C}_{\Omega}(T_{b^{\prime}})}{\sqrt{{\kappa_{\Omega}}}}}=\order{1}$

And hence the final complexity is given by the expression

$\displaystyle T$
$\displaystyle=\order{\kappa\sqrt{{\kappa_{\Omega}}}\log\kappa\left(\mathcal{C}_{A}(T)\cdot
T_{A}+\mathcal{C}_{L}(T)\cdot T_{L}+\mathcal{C}_{\Omega}(T)\cdot
T_{\Omega}+\mathcal{C}_{b}(T)\cdot T_{b}\right)}$
$\displaystyle=\order{\kappa\sqrt{{\kappa_{\Omega}}}\log\kappa\left(\frac{\alpha_{A}}{\norm{A}}\log^{2}\left(\frac{\kappa{\kappa_{\Omega}}\norm{A}}{\delta{\norm{\Omega}}}\right)T_{A}+\frac{\alpha_{L}}{\norm{L}}\log^{2}\left(\frac{\kappa\norm{L}}{\delta}\right)T_{L}+\frac{\alpha_{\Omega}{\kappa_{\Omega}}}{{\norm{\Omega}}}\log^{3}\left(\frac{\kappa{\kappa_{\Omega}}\norm{A}}{\delta{\norm{\Omega}}}\right)T_{\Omega}+T_{b}\right)}$
$\displaystyle=\order{\kappa\sqrt{{\kappa_{\Omega}}}\log\kappa\left(\left(\frac{\alpha_{A}}{\norm{A}}T_{A}+\frac{\alpha_{L}}{\norm{L}}T_{L}+\frac{\alpha_{\Omega}{\kappa_{\Omega}}}{{\norm{\Omega}}}T_{\Omega}\right)\log^{3}\left(\frac{\kappa{\kappa_{\Omega}}\norm{A}\norm{L}}{\delta{\norm{\Omega}}}\right)+T_{b}\right)}$

∎

One immediate observation is that for the special case of the (unregularized)
quantum GLS problem (when $L=0$ and $\lambda=0$), our algorithm has a slightly
better complexity than [7] and requires fewer additional qubits. Now, we will
state the complexities of this algorithm in specific input models, namely the
quantum data structure model and the sparse-access input model.

######  Corollary 43 (Quantum Generalized Least Squares with General
$\ell_{2}$-Regularization in the Quantum Data Structure Model).

Let $A,L\in\mathbb{R}^{N\times d}$ be the data and penalty matrices with
effective condition numbers $\kappa_{A},\kappa_{L}$ respectively. and
$\Omega\in\mathbb{R}^{N\times N}$ be the covariance matrix with condition
number $\kappa_{\Omega}$. Let the matrices $A,L,\Omega$ and the vector $b$ be
stored in a quantum-accessible data structure. Define $\kappa$ as

$\kappa:=\kappa_{L}\left(1+\frac{\sqrt{{\kappa_{\Omega}}}\norm{A}}{\sqrt{\lambda\norm{\Omega}}\norm{L}}\right)$

Then for any $\delta>0$, we can prepare the quantum state that is
$\delta$-close to

$\frac{\left(A^{T}\Omega^{-1}A+\lambda
L^{T}L\right)^{-1}A^{T}\Omega^{-1}\ket{b}}{\norm{\left(A^{T}\Omega^{-1}A+\lambda
L^{T}L\right)^{-1}A^{T}\Omega^{-1}\ket{b}}}$

with probability $\Theta(1)$, at a cost of

$\order{\kappa\sqrt{{\kappa_{\Omega}}}\left(\frac{\mu_{A}}{\norm{A}}+\frac{\mu_{L}}{\norm{L}}+\frac{\kappa_{\Omega}\mu_{\Omega}}{\norm{\Omega}}\right)\mathrm{polylog}\left(Nd,\kappa,\frac{1}{\delta},\frac{{\kappa_{\Omega}}}{{\norm{\Omega}}},\norm{A},\norm{L},\lambda\right)}$
(53)

###### Proof.

The proof is very similar to 34 with the extra input of $\Omega$. We can use
the data structure to prepare the block-encodings for $A,L,\Omega$ and the
state $\ket{b}$, with precisions
$\varepsilon_{A},\varepsilon_{L},\varepsilon_{\Omega},\varepsilon_{b}$
respectively. We invoke Theorem 42 with a precision of $\delta_{b}$, and
choose the above $\varepsilon$ terms to be equal to their corresponding upper-
bounds. And finally we use Lemma 15 with $\varepsilon_{b}=\delta/2\kappa$ and
$\delta_{b}=\delta/2$ to get the final error as $\delta$. ∎

Now, $\mu_{A}=\norm{A}_{F}$ (similarly for $\mu_{L}$ and $\mu_{\Omega}$). As
$\norm{A}_{F}\leq\sqrt{r(A)}\norm{A}$, where $r(A)$ is the rank of $A$, we
have that the complexity of 43 can be re-expressed as

$\order{\kappa\sqrt{\kappa_{\Omega}}\left(\sqrt{r(A)}+\sqrt{r(L)}+\sqrt{r(\Omega)}\kappa_{\Omega}\right)\mathrm{polylog}\left(\frac{Nd\kappa}{\delta}\right)}.$
(54)

######  Corollary 44 (Quantum Generalized Least Squares with General
$\ell_{2}$-Regularization in the Sparse Access Model).

Let $A\in\mathbb{R}^{N\times d}$ be a $(s^{A}_{r},s^{A}_{c})$ row-column
sparse data matrix. Let $L\in\mathbb{R}^{N\times d}$ be a
$(s^{L}_{r},s^{L}_{c})$ row-column sparse penaly matrix. Let
$\Omega\in\mathbb{R}^{N\times N}$ be a $(s^{\Omega}_{r},s^{\Omega}_{c})$ row-
column sparse covariance matrix. Suppose we have a procedure to prepare
$\ket{b}$ in cost $T_{b}$. Define $\kappa$ as

$\kappa:=\kappa_{L}\left(1+\frac{\sqrt{{\kappa_{\Omega}}}\norm{A}}{\sqrt{\lambda\norm{\Omega}}\norm{L}}\right)$

Then for any $\delta>0$, we can prepare the quantum state that is
$\delta$-close to

$\frac{\left(A^{T}\Omega^{-1}A+\lambda
L^{T}L\right)^{-1}A^{T}\Omega^{-1}\ket{b}}{\norm{\left(A^{T}\Omega^{-1}A+\lambda
L^{T}L\right)^{-1}A^{T}\Omega^{-1}\ket{b}}}$

with probability $\Theta(1)$, at a cost of

$\order{\kappa\sqrt{{\kappa_{\Omega}}}\left(\frac{\sqrt{s^{A}_{r}s^{A}_{c}}}{\norm{A}}+\frac{\sqrt{s^{L}_{r}s^{L}_{c}}}{\norm{L}}+\frac{\kappa_{\Omega}\sqrt{s^{\Omega}_{r}s^{\Omega}_{c}}}{\norm{\Omega}}+T_{b}\right)\mathrm{polylog}\left(Nd,\kappa,\frac{1}{\delta},\frac{{\kappa_{\Omega}}}{{\norm{\Omega}}},\norm{A},\norm{L},\lambda\right)}$
(55)

###### Proof.

The algorithm is similar to 43, but with
$\alpha_{A}=\sqrt{s^{A}_{r}s^{A}_{c}}$,
$\alpha_{L}=\sqrt{s^{L}_{r}s^{L}_{c}}$,
$\alpha_{\Omega}=\sqrt{s^{\Omega}_{r}s^{\Omega}_{c}}$. ∎

##  5 Future Directions

Our algorithms for quantum linear regression with general
$\ell_{2}$-regularization made use of QSVT to implement various several matrix
operations. However, it is possible to use QSVT directly to obtain the
solution to quantum ridge regression. This requires computing a polynomial
approximation for the transformation
$\sigma\mapsto\sigma/(\sigma^{2}+\lambda)$, to be applied on the singular
values of $A$, which lie between $[1/\kappa_{A},1]$. However, it is unclear
how to extend this while considering general $\ell_{2}$-regularization. For
instance, even when the data matrix and the penalty matrix share the same
right singular vectors, this approach involves obtaining polynomial
approximations to directly implement transformations of the form
$\sigma\mapsto\sigma/(\sigma^{2}+\lambda\widetilde{\sigma}^{2})$, where
$\widetilde{\sigma}$ is a singular value of the penalty matrix $L$. A monomial
is no longer sufficient to approximate this quantum singular value
transformation. It would be interesting to explore whether newly developed
ideas of M-QSVT [37] can be used to implement such transformations directly
with improved complexity.

While developing quantum machine learning algorithms, it is essential to point
out the caveats, even at the risk of being repetitive [1]. Our quantum
algorithms output a quantum state $\ket{x}$ whose amplitudes encode the
solution of the classical (regularized) linear regression problem. While given
access to the data matrix and the penalty matrix, we achieve an exponential
advantage over classical algorithms, this advantage is not generic. If similar
assumptions ($\ell_{2}$-sample and query access) are provided to a classical
device, Gilyén et al. developed a quantum algorithm [15] for ridge regression
(building upon [8]) which has a running time in
$\order{\mathrm{poly}(\kappa,\mathrm{rank}(A),1/\delta)}$. This implies that
any quantum algorithm for this problem can be at most polynomially faster in
$\kappa$ under these assumptions. One might posit that similar quantum-
inspired classical algorithms for general $\ell_{2}$-regression can also be
developed. The exponential quantum speedup, however, is retained when the
underlying matrices are sparse.

Another future direction of research would be to recast our algorithms in the
framework of adiabatic quantum computing (AQC) following the works of [30, 2].
Quantum algorithms for linear systems in this framework have the advantage
that a linear dependence on $\kappa$ can be obtained without using complicated
subroutines like variable-time amplitude amplification. The strategy is to
implement these problems in the AQC model and then use time-dependent
Hamiltonian simulation [31] to obtain their complexities in the circuit model.
One caveat is that, so far, time-dependent Hamiltonian simulation algorithms
have only been developed in the sparse-access model and therefore the
advantage of the generality of the block-encoding framework is lost.

In the future, it would also be interesting to explore other quantum
algorithms for machine learning such as principal component regression and
linear support vector machines [38] using QSVT. Finally, following the results
of [5], it would be interesting to investigate techniques for quantum machine
learning that do not require the quantum linear systems algorithm as a
subroutine.

## Acknowledgements

SC thanks András Gilyén, Stacey Jeffery and Jérémie Roland for useful
discussions. SC acknowledges funding from the Science and Engineering Board,
Department of Science and Technology (SERB-DST), Government of India via grant
number SRG/2022/000354. SC is also supported by IIIT Hyderabad via the Faculty
Seed Grant. AP thanks Michael Walter for useful discussions. AP acknowledges
support by the BMBF through project Quantum Methods and Benchmarks for
Resource Allocation (QuBRA).

## References

  * Aar [15] Scott Aaronson.  Read the fine print.  Nature Physics, 11(4):291–293, Apr 2015.  doi:10.1038/nphys3272.
  * AL [22] Dong An and Lin Lin.  Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm.  ACM Transactions on Quantum Computing, 3(2), mar 2022.  doi:10.1145/3498331.
  * Amb [12] Andris Ambainis.  Variable time amplitude amplification and quantum algorithms for linear algebra problems.  In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pages 636–647, Dagstuhl, Germany, 2012. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.STACS.2012.636.
  * Bis [95] Chris M. Bishop.  Training with noise is equivalent to tikhonov regularization.  Neural Computation, 7(1):108–116, 1995.  doi:10.1162/neco.1995.7.1.108.
  * CdW [21] Yanlin Chen and Ronald de Wolf.  Quantum algorithms and lower bounds for linear regression with norm constraints.  arXiv preprint, 2021.  doi:10.48550/ARXIV.2110.13086.
  * CGJ [18] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery.  The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation.  arXiv preprint, 2018.  doi:10.48550/arXiv.1804.01973.
  * CGJ [19] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery.  The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.ICALP.2019.33.
  * CGL+ [20] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang.  Sampling-Based Sublinear Low-Rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning, page 387–400.  Association for Computing Machinery, New York, NY, USA, 2020.  doi:10.1145/3357713.3384314.
  * CKS [17] Andrew M. Childs, Robin Kothari, and Rolando D. Somma.  Quantum algorithm for systems of linear equations with exponentially improved dependence on precision.  SIAM Journal on Computing, 46(6):1920–1950, Jan 2017.  doi:10.1137/16M1087072.
  * CYGL [22] Menghan Chen, Chaohua Yu, Gongde Guo, and Song Lin.  Faster quantum ridge regression algorithm for prediction.  International Journal of Machine Learning and Cybernetics, Apr 2022.  doi:10.1007/s13042-022-01526-6.
  * EHN [96] H.W. Engl, M. Hanke, and A. Neubauer.  Regularization of Inverse Problems.  Mathematics and Its Applications. Springer Netherlands, 1996.  URL: https://link.springer.com/book/9780792341574.
  * GHO [99] Gene H. Golub, Per Christian Hansen, and Dianne P. O’Leary.  Tikhonov regularization and total least squares.  SIAM Journal on Matrix Analysis and Applications, 21(1):185–194, 1999.  doi:10.1137/S0895479897326432.
  * GSLW [18] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics.  arXiv preprint, jun 2018.  doi:10.48550/arXiv.1806.01838.
  * GSLW [19] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3313276.3316366.
  * GST [22] András Gilyén, Zhao Song, and Ewin Tang.  An improved quantum-inspired algorithm for linear regression.  Quantum, 6:754, June 2022.  doi:10.22331/q-2022-06-30-754.
  * GTC [19] Yimin Ge, Jordi Tura, and J. Ignacio Cirac.  Faster ground state preparation and high-precision ground energy estimation with fewer qubits.  Journal of Mathematical Physics, 60(2):022202, 2019.  doi:10.1063/1.5027484.
  * Hem [75] William J. Hemmerle.  An explicit solution for generalized ridge regression.  Technometrics, 17(3):309–314, 1975.  URL: http://www.jstor.org/stable/1268066, doi:10.2307/1268066.
  * HH [93] Martin Hanke and Per Christian Hansen.  Regularization methods for large-scale problems.  Surv. Math. Ind, 3(4):253–315, 1993.
  * HHL [09] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Physical Review Letters, 103(15), Oct 2009.  doi:10.1103/physrevlett.103.150502.
  * HK [00] Arthur E. Hoerl and Robert W. Kennard.  Ridge regression: Biased estimation for nonorthogonal problems.  Technometrics, 42(1):80–86, 2000.  URL: http://www.jstor.org/stable/1271436, doi:10.2307/1271436.
  * KKR [06] Julia Kempe, Alexei Kitaev, and Oded Regev.  The complexity of the local hamiltonian problem.  SIAM Journal on Computing, 35(5):1070–1097, 2006.  doi:10.1137/S0097539704445226.
  * KP [17] Iordanis Kerenidis and Anupam Prakash.  Quantum Recommendation Systems.  In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.ITCS.2017.49.
  * KP [20] Iordanis Kerenidis and Anupam Prakash.  Quantum gradient descent for linear systems and least squares.  Phys. Rev. A, 101:022316, Feb 2020.  doi:10.1103/PhysRevA.101.022316.
  * [24] Guang Hao Low and Isaac L Chuang.  Hamiltonian simulation by uniform spectral amplification.  arXiv:1707.05391, 2017.  doi:10.48550/ARXIV.1707.05391.
  * [25] Guang Hao Low and Isaac L. Chuang.  Optimal hamiltonian simulation by quantum signal processing.  Phys. Rev. Lett., 118:010501, Jan 2017.  doi:10.1103/PhysRevLett.118.010501.
  * LC [19] Guang Hao Low and Isaac L. Chuang.  Hamiltonian simulation by qubitization.  Quantum, 3:163, Jul 2019.  doi:10.22331/q-2019-07-12-163.
  * LMR [14] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum principal component analysis.  Nature Physics, 10(9):631–633, Sep 2014.  doi:10.1038/nphys3029.
  * Low [17] Guang Hao Low.  Quantum signal processing by single-qubit dynamics.  PhD thesis, Massachusetts Institute of Technology, 2017.  URL: http://hdl.handle.net/1721.1/115025.
  * [29] Lin Lin and Yu Tong.  Near-optimal ground state preparation.  Quantum, 4:372, December 2020.  doi:10.22331/q-2020-12-14-372.
  * [30] Lin Lin and Yu Tong.  Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems.  Quantum, 4:361, November 2020.  doi:10.22331/q-2020-11-11-361.
  * LW [18] Guang Hao Low and Nathan Wiebe.  Hamiltonian simulation in the interaction picture.  arXiv preprint, 2018.  doi:10.48550/arXiv.1805.00675.
  * LYC [16] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang.  Methodology of resonant equiangular composite quantum gates.  Phys. Rev. X, 6:041067, Dec 2016.  doi:10.1103/PhysRevX.6.041067.
  * Mar [70] Donald W. Marquardt.  Generalized inverses, ridge regression, biased linear estimation, and nonlinear estimation.  Technometrics, 12(3):591–612, 1970.  URL: http://www.jstor.org/stable/1267205, doi:10.2307/1267205.
  * MRTC [21] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang.  Grand unification of quantum algorithms.  PRX Quantum, 2:040203, Dec 2021.  doi:10.1103/PRXQuantum.2.040203.
  * Mur [12] Kevin P Murphy.  Machine learning: a probabilistic perspective.  MIT press, 2012.  URL: https://mitpress.mit.edu/books/machine-learning-1.
  * Pra [14] Anupam Prakash.  Quantum Algorithms for Linear Algebra and Machine Learning. PhD thesis, EECS Department, University of California, Berkeley, Dec 2014.  URL: http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.html.
  * RC [22] Zane M. Rossi and Isaac L. Chuang.  Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle.  Quantum, 6:811, September 2022.  doi:10.22331/q-2022-09-20-811.
  * RML [14] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd.  Quantum support vector machine for big data classification.  Phys. Rev. Lett., 113:130503, Sep 2014.  doi:10.1103/PhysRevLett.113.130503.
  * SSP [16] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione.  Prediction by linear regression on a quantum computer.  Phys. Rev. A, 94:022342, Aug 2016.  doi:10.1103/PhysRevA.94.022342.
  * SX [20] Changpeng Shao and Hua Xiang.  Quantum regularized least squares solver with parameter estimate.  Quantum Information Processing, 19(4):113, Feb 2020.  doi:10.1007/s11128-020-2615-9.
  * Tan [19] Ewin Tang.  A quantum-inspired classical algorithm for recommendation systems.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 217–228, New York, NY, USA, 2019. Association for Computing Machinery.  doi:10.1145/3313276.3316310.
  * Vin [78] Hrishikesh D. Vinod.  A survey of ridge regression and related techniques for improvements over ordinary least squares.  The Review of Economics and Statistics, 60(1):121–131, 1978.  URL: http://www.jstor.org/stable/1924340, doi:10.2307/1924340.
  * vW [15] Wessel N. van Wieringen.  Lecture notes on ridge regression, 2015.  doi:10.48550/ARXIV.1509.09169.
  * Wan [17] Guoming Wang.  Quantum algorithm for linear regression.  Phys. Rev. A, 96:012335, Jul 2017.  doi:10.1103/PhysRevA.96.012335.
  * WBL [12] Nathan Wiebe, Daniel Braun, and Seth Lloyd.  Quantum algorithm for data fitting.  Phys. Rev. Lett., 109:050505, Aug 2012.  doi:10.1103/PhysRevLett.109.050505.
  * YGW [21] Chao-Hua Yu, Fei Gao, and Qiao-Yan Wen.  An improved quantum algorithm for ridge regression.  IEEE Transactions on Knowledge and Data Engineering, 33(3):858–866, 2021.  doi:10.1109/TKDE.2019.2937491.

##  Appendix A Algorithmic Primitives

This appendix contains detailed proofs for certain lemmas and corollaries in
Section 3, for completeness. These proofs are not necessary to understand the
techniques and results of the paper, but may help the reader develop a better
intuition for the methods used.

See 12

###### Proof.

We can re-interpret $U$ as a $(\alpha/\norm{A},a,\varepsilon/\norm{A})$-block-
encoding of $A/\norm{A}$. Invoking Lemma 11 with
$\gamma=\frac{\delta}{2\norm{A}}$, we get $U^{\prime}$, a
$(\sqrt{2},a+1,\varepsilon/\norm{A}+\frac{\delta}{2\norm{A}})$-block-encoding
of $A/\norm{A}$, implemented at a cost of
$\order{\frac{\alpha}{\norm{A}}T_{U}\log\left(\norm{A}/\delta\right)}$ which
is a $(\sqrt{2}\norm{A},a+1,\delta)$-block-encoding of $A$. ∎

See 13

###### Proof.

The proof is similar to Lemma 24 of [7]. We have
$\norm{A\ket{b}}\geq\frac{\norm{A}}{\kappa}$. By applying $U_{A}$ to
$\ket{0}\ket{b}$ (implementable at a cost of $T_{A}+T_{B}$), followed by
$\frac{\alpha\kappa}{\norm{A}}$-rounds of amplitude amplification (conditioned
on having $\ket{0}$ in the first register) , we obtain a quantum state that
within $\delta$ of $\ket{0}\otimes\frac{A\ket{b}}{\norm{A\ket{b}}}$. ∎

See 14

###### Proof.

We first pre-amplify the unitary using 12 with some $\gamma\geq 2\varepsilon$.
We get a $(\sqrt{2}\norm{A},a+1,\gamma)$-block-encoding of $A$ implemented at
a cost of

$T_{A^{\prime}}:=\order{\frac{\alpha
T_{A}}{\norm{A}}\log\left(\frac{\norm{A}}{\gamma}\right)}$

Now we invoke Lemma 13 with $\delta=\frac{2\kappa\gamma}{\norm{A}}$ and the
above unitary to prepare the state, which has a time complexity of

$\order{\kappa\left(T_{A^{\prime}}+T_{b}\right)}=\order{\frac{\alpha\kappa}{\norm{A}}\log\left(\frac{\kappa}{\delta}\right)T_{A}+\kappa
T_{b}}$

∎

See 15

###### Proof.

We know that

$\norm{\ket{b}-\ket{b^{\prime}}}\leq\frac{\varepsilon}{2\kappa}$

and

$\norm{\ket{\psi}-\frac{A\ket{b^{\prime}}}{\norm{A\ket{b^{\prime}}}}}\leq\frac{\varepsilon}{2}$

For small enough $\varepsilon\ll\kappa$, we can assume that
$\norm{A\ket{b}}\approx\norm{A\ket{b^{\prime}}}$. We can derive the final
error as

$\displaystyle\norm{\ket{\psi}-\frac{A\ket{b}}{\norm{A\ket{b}}}}$
$\displaystyle=\norm{\ket{\psi}-\frac{A\ket{b}-A\ket{b^{\prime}}+A\ket{b^{\prime}}}{\norm{A\ket{b}}}}$
$\displaystyle=\norm{\ket{\psi}-\frac{A\ket{b^{\prime}}}{\norm{A\ket{b}}}+\frac{A\ket{b^{\prime}}-A\ket{b^{\prime}}}{\norm{A\ket{b}}}}$
$\displaystyle\leq\norm{\ket{\psi}-\frac{A\ket{b^{\prime}}}{\norm{A\ket{b^{\prime}}}}}+\norm{\frac{A\ket{b^{\prime}}-A\ket{b^{\prime}}}{\norm{A\ket{b}}}}$
$\displaystyle\leq\frac{\varepsilon}{2}+\frac{\norm{A}\norm{\ket{b}-\ket{b^{\prime}}}}{\norm{A\ket{b}}}$
$\displaystyle\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}$
$\displaystyle=\varepsilon$

∎

###  A.1 Arithmetic with Block-Encoded Matrices

See 17

###### Proof.

Let $a=max_{j}(a_{j})+s$ and $\alpha=\sum_{j}y_{j}\alpha_{j}$. For each
$j\in\\{0,\ldots,m-1\\}$, construct the extended unitary $U^{\prime}_{j}$ by
padding ancillas to $U_{j}$, i.e. $U_{j}^{\prime}=I_{a-s-a_{j}}\otimes U_{j}$.
Note that $U^{\prime}_{j}$ is a $(\alpha_{j},a-s,\varepsilon_{j})$-block-
encoding of $A_{j}$. Let $B_{j}=(\bra{0}^{a_{j}}\otimes
I_{s})U_{j}(\ket{0}^{a_{j}}\otimes I_{s})$ denote the top left block of
$U_{j}$ and $U_{j}^{\prime}$, and observe that
$\|A_{j}-\alpha_{j}B_{j}\|\leq\varepsilon_{j}$. We also construct $P$ — an
$\eta$ state-preparation unitary s.t.
$P\ket{0}=\sum_{j}\sqrt{y_{j}\alpha_{j}}\ket{j}$ — by invoking Definition 16.

Consider the unitary $W=(P^{\dagger}\otimes I_{a-1}\otimes
I_{s})(\sum_{j}\outerproduct{j}{j}\otimes U_{j}^{\prime})(P\otimes
I_{a-1}\otimes I_{s})$. This is a $(\alpha,a,\varepsilon)$-block-encoding of
$A=\sum_{j}y_{j}A_{j}$, where $\varepsilon$ is computed as:

$\displaystyle\norm{A-\alpha(\bra{0}^{a}\otimes I_{s})W(\ket{0}^{a}\otimes
I_{s})}$
$\displaystyle=\norm{\sum_{j=0}^{m-1}y_{j}A_{j}-\alpha(\bra{0}^{a}\otimes
I_{s})W(\ket{0}^{a}\otimes I_{s})}$
$\displaystyle=\norm{\sum_{j}y_{j}A_{j}-\alpha(\bra{0}^{a}\otimes
I_{s})(\sum_{j}P^{\dagger}\outerproduct{j}{j}P\otimes
U_{j}^{\prime})(\ket{0}^{a}\otimes I_{s})}$
$\displaystyle=\norm{\sum_{j}y_{j}A_{j}-\alpha\sum_{j}\bra{0}P^{\dagger}\outerproduct{j}{j}P\ket{0}\otimes
B_{j}}$
$\displaystyle=\norm{\sum_{j}\bigg{(}y_{j}A_{j}-\alpha\bra{0}P^{\dagger}\outerproduct{j}{j}P\ket{0}B_{j}\bigg{)}}$
$\displaystyle=\norm{\sum_{j}\bigg{(}y_{j}A_{j}-\alpha\Big{(}\frac{y_{j}\alpha_{j}}{\alpha}\Big{)}B_{j}\bigg{)}}$
$\displaystyle\leq\sum_{j}y_{j}\norm{A_{j}-\alpha_{j}B_{j}}$
$\displaystyle\leq\sum_{j}y_{j}\varepsilon_{j}=\varepsilon$

∎

See 21

###### Proof.

From the property of Kronecker products $(A\otimes B)(C\otimes
D)=(AC)\otimes(BD)$. For $j\in\\{1,2\\}$ let
$\tilde{A_{j}}=\left(\bra{0}^{\otimes a_{j}}\otimes
I_{s}\right)U_{j}\left(\ket{0}^{\otimes a_{j}}\otimes I_{s}\right)$. Then it
follows that

$\left(\bra{0}^{\otimes a}\otimes I_{s}\otimes\bra{0}^{\otimes b}\otimes
I_{t}\right)(U_{1}\otimes U_{2})\left(\ket{0}^{\otimes a}\otimes
I_{s}\otimes\ket{0}^{\otimes b}\otimes
I_{t}\right)=\tilde{A}_{1}\otimes\tilde{A}_{2}$ (56)

Therefore $\tilde{A}_{1}\otimes\tilde{A}_{2}$ is block-encoded in
$U_{1}\otimes U_{2}$ as a non-principal block-encoding, and we can use SWAP
gates to move it to the principal block as follows.

$\displaystyle S\left(\ket{0}^{\otimes a}\otimes I_{s}\ket{0}^{\otimes
b}\otimes I_{t}\right)$
$\displaystyle=\Pi_{i=1}^{s}\texttt{SWAP}_{a+b+i}^{a+i}\left(\ket{0}^{\otimes
a}\otimes I_{s}\ket{0}^{\otimes b}\otimes I_{t}\right)$
$\displaystyle=\Pi_{i=1}^{s-1}\texttt{SWAP}_{a+b+i}^{a+i}\texttt{SWAP}_{a+b+s}^{a+s}\left(\ket{0}^{\otimes
a}\otimes I_{s}\ket{0}^{\otimes b}\otimes I_{t}\right)$
$\displaystyle=\Pi_{i=1}^{s-1}\texttt{SWAP}_{a+b+i}^{a+i}\left(\ket{0}^{\otimes
a}\otimes I_{s-1}\ket{0}^{\otimes b}\otimes I_{t+1}\right)$
$\displaystyle=\ldots$ $\displaystyle=\ket{0}^{\otimes a+b}\otimes I_{s+t}$

Similarly,

$\left(\bra{0}^{\otimes a}\otimes I_{s}\otimes\bra{0}^{\otimes b}\otimes
I_{t}\right)S^{\dagger}=\bra{0}^{\otimes a+b}\otimes I_{s+t}.$

From Equation 56 we have

$\displaystyle\tilde{A}_{1}\otimes\tilde{A}_{2}$
$\displaystyle=\left(\bra{0}^{\otimes a}\otimes I_{s}\otimes\bra{0}^{\otimes
b}\otimes I_{t}\right)S^{\dagger}S(U_{1}\otimes
U_{2})S^{\dagger}S\left(\ket{0}^{\otimes a}\otimes I_{s}\ket{0}^{\otimes
b}\otimes I_{t}\right)$ $\displaystyle=\left(\bra{0}^{\otimes a+b}\otimes
I_{s+t}\right)S(U_{1}\otimes U_{2})S^{\dagger}\left(\ket{0}^{\otimes
a+b}\otimes I_{s+t}\right)$

Next, we look at the subnormalization and error terms.

$\displaystyle\norm{A_{1}\otimes
A_{2}-\alpha\beta\tilde{A}_{1}\otimes\tilde{A}_{2}}_{2}$
$\displaystyle\leq\norm{(\alpha\tilde{A}_{1}+\varepsilon_{1}I_{s})\otimes(\beta\tilde{A}_{2}+\varepsilon_{2}I_{t})-\alpha\tilde{A}_{1}\otimes\beta\tilde{A}_{2}}_{2}$
$\displaystyle=\norm{\alpha\tilde{A}_{1}\otimes\varepsilon_{2}I_{2}+\varepsilon_{1}I_{s}\otimes\beta\tilde{A}_{2}+\varepsilon_{1}I_{s}\otimes\varepsilon_{2}I_{2}}_{2}$
$\displaystyle\leq\alpha\varepsilon_{2}\norm{\tilde{A}_{1}}_{2}+\beta\varepsilon_{2}\norm{\tilde{A}_{2}}_{2}+\varepsilon_{1}\varepsilon_{2}$
$\displaystyle=\alpha\varepsilon_{2}+\beta\varepsilon_{1}+\varepsilon_{1}\varepsilon_{2}$

where we have used
$\norm{A_{1}}_{2}\leq\alpha\norm{\tilde{A}_{1}}_{2}+\varepsilon_{1}$ and
$\norm{\tilde{A}_{1}}_{2}\leq 1$ and similarly for $A_{2}$.

∎


# Seeing is Knowing! Fact-based Visual Question Answering using Knowledge
Graph Embeddings

Kiran Ramnath  {kiranr2<EMAIL_ADDRESS>Mark Hasegawa-Johnson
{kiranr2<EMAIL_ADDRESS>
###### Abstract

Fact-based Visual Question Answering (FVQA), a challenging variant of VQA,
requires a QA-system to include facts from a diverse knowledge graph (KG) in
its reasoning process to produce an answer. Large KGs, especially common-sense
KGs, are known to be incomplete, i.e., not all non-existent facts are always
incorrect. Therefore, being able to reason over incomplete KGs for QA is a
critical requirement in real-world applications that has not been addressed
extensively in the literature. We develop a novel QA architecture that allows
us to reason over incomplete KGs, something current FVQA state-of-the-art
(SOTA) approaches lack due to their critical reliance on fact retrieval. We
use KG Embeddings, a technique widely used for KG completion, for the
downstream task of FVQA. We also employ a new image representation technique
we call ‘Image-as-Knowledge’ to enable this capability, alongside a simple
one-step CoAttention mechanism to attend to text and image during QA. Our FVQA
architecture is faster during inference time, being $O(m)$, as opposed to
existing FVQA SOTA methods which are $O(N\log N)$, where $m=$ number of
vertices, $N=$ number of edges $=O(m^{2})$. KG embeddings are shown to hold
complementary information to word embeddings: a combination of both metrics
permits performance comparable to SOTA methods in the standard answer
retrieval task, and significantly better (26% absolute) in the proposed
missing-edge reasoning task.

##  1 Introduction

Multi-modal reasoning has been a prime focus in the pursuit of artificial
general intelligence. One such task is Visual Question Answering Antol et al.
(2015); Goyal et al. (2017), which requires the system to answer a textual
question based on an image. VQA is challenging because it requires many
capabilities such as object detection, scene recognition, activity recognition
in addition to language understanding and commonsense reasoning.

Figure 1: Example of a fact-based visual question
Question \- Which object in this image is rich in potassium?
Supporting fact \- Bananas are rich in potassium
SPO triple \- (Bananas, HasProperty, rich in potassium)
Answer Source \- Image
Answer \- Bananas

Wang et al. (2016) noted that most of the questions in the VQA dataset didn’t
require commonsense knowledge residing outside of the image. Humans have a
remarkable ability to blend in knowledge from their own prior experiences when
answering a question about an image. Wang et al. (2016) therefore introduced
the FVQA benchmark, aiming to provide a more challenging set of questions
which ensure that the answer to a given question requires some form of
external knowledge, not present in the image or the question text. They
provide this external information in the form of knowledge graphs, which are
multi-relational graphs, storing relational representations between entities.
The task of FVQA boils down to retrieving the correct entity as the answer
most relevant to an image. For example, in Fig. 1 the fact triple – (Banana,
HasProperty, rich in Potassium) is the external information required to answer
the question; with the correct answer being ‘Banana’.

All published methods in the literature rely on retrieving the ground-truth
fact for a question, whereas a real world application will likely have
questions asked about facts not present in the KG. The primary contribution of
this paper is a method Seeing is Knowing (SiK) that permits FVQA to reason
about common-sense facts that are absent from the knowledge graph using KG
Embeddings. When used with a more general score function we define, the
resultant framework works well in both complete and incomplete KG settings. KG
embeddings permit us to offer two additional contributions to the SOTA in
FVQA: an ‘image-as-knowledge’ representation of visual information, and a
CoAttention method for combining visual and textual inputs. ‘Image-as-
knowledge’ represents the image as the span of the KG embedding vectors for
the entities found in it. Representing an image with textual semantics has
been attempted before Li et al. (2019), but not using KG embeddings; KG
embeddings provide robustness to incomplete KGs by encoding information about
the graph structure. CoAttention uses the words of the query to compute
weighted combinations of the entity vectors, thus the answer is a vector
within the span of the image entities. Two such identical models are trained
separately, which are gated in order to query the entities in the KG during
inference. Finally, SiK when used in a standalone fashion over incomplete KGs
is more time-efficient during inference. It is $O\left(m\right)$ as it only
needs to reason over existent nodes in the network. To the best of our
knowledge, our work is the first one to apply KG embeddings to a VQA task.

##  2 Related Work

###  2.1 Knowledge Graphs

Knowledge graphs Suchanek et al. (2007); Auer et al. (2007); Mitchell and
Fredkin (2014); Bollacker et al. (2008); Dong et al. (2014) have been studied
as an effective way of representing objects or concepts and their inter-
relationships. Such relational representations are formally defined in the RDF
(Resource Description Framework) as triples
$f=(\texttt{subject},\texttt{predicate},\texttt{object})$, where
$(\texttt{subject, object})$ are entities, predicate is the relation
connecting the two entities. Such linked representations have been found to
correlate highly with how humans process cognitive information Halford et al.
(2010).

###  2.2 KG embeddings

Common-sense KGs extracted from web-scale texts are usually incomplete. KG
embedding techniques Bordes et al. (2013); Sun et al. (2019); Socher et al.
(2013); Nickel et al. (2011); Dong et al. (2014); Dettmers et al. (2018) have
been studied as a means to remediate incompleteness of large-scale KGs. Score-
based latent feature models, which perform well on several benchmarks, learn a
score mapping $\phi(h,r,t):\mathcal{E\times R\times E}\rightarrow\Re$ where
$\mathcal{E}$ is the set of all entities, $\mathcal{R}$ is the set of all
relation-types. $h,t\in\mathcal{E}$ are the head (subject) and tail (object),
$r\in\mathcal{R}$ is the relation. $\mathcal{G}\subset\mathcal{E\times R\times
E}$ is the observed set of edges, while $\mathcal{G}_{o}\supset\mathcal{G}$ is
the unknown set of true edges. The embeddings $(h,r,t)$ are learned so that
the score $\phi(.)$ is high for edges in $\mathcal{G}_{o}$, and low for edges
in its complement.

We use Entity-Relation Multi-Layer Perceptron (ERMLP) Dong et al. (2014) which
uses an MLP to produce the score $\phi(h,r,t)$ for each fact triple. Distance-
based models learn embeddings $h$, $r$ and $t$ in order to minimize the
distance between $t$ and $f(h,r)$, for some projection function $f(\cdot)$. We
explore the use of two such distance-based models (results in Appendix):
TransE Bordes et al. (2013) and RotatE Sun et al. (2019). TransE models
$f(h,r)=h+r$. RotatE models $f(h,r)$ as a Hadamard product, $h\circ r$, where
the embedding vectors $h$, $r$ and $t$ are in the complex plane and $r$ is
enforced to be unit norm, so that $h\circ r$ is a rotation in the complex
plane.

Knowledge-graph question answering (KGQA) is the task of answering questions
using the facts in a KG. EmbedKGQA Saxena et al. (2020) tries to reason over
missing edges for text-only multi-hop questions using KG embeddings. Our task
involves the visual modality in addition, as well as reasoning over a common-
sense KG.

Figure 2: Seeing is Knowing architecture. (1) Scenes, objects, & actions are
detected in the image. (2) For detected entities, we retrieve their KG
embedding representations. The span of these embedding vectors represents the
‘image-as-knowledge’. (3) Lexical semantic vectors for each word in the query
are accumulated via an LSTM. (4) The joint image-question encoding is derived
using a CoAttention mechanism described in Fig. 3, then (5) passed through a
multi-layer perceptron, whose (6) last layer is used as a pair of queries that
are (7) gated, and (8) used to retrieve the entity to answer the question.

###  2.3 FVQA

The fact-based visual question answering (FVQA Wang et al. (2016)) benchmark
was designed using questions that obey the following condition: for each
(question,image,answer) triplet in the dataset
($(q_{i},I_{i},y_{i})\in{\mathcal{D}}$), there exists exactly one supporting
fact in the knowledge graph ($f_{j}=(h,r,t)\in{\mathcal{G}}$) such that the
correct answer $y_{i}$ is either the head or the tail of $f_{j}$, and such
that at least one of the two entities is visible in the image.

The accompanying KG is also diverse, comprising facts from three individual
KGs: Webchild Tandon et al. (2014), ConceptNet Liu and Singh (2004), and
DBPedia Auer et al. (2007). In total, the dataset contains 13 relations:
${\mathcal{R}}\in$ {Category, HasProperty, RelatedTo, AtLocation, IsA, HasA,
CapableOf, UsedFor, Desires, PartOf, ReceivesAction, CreatedBy, Comparative}.
The dataset consists of 2190 images sampled from the ILSVRC Russakovsky et al.
(2015) and the MSCOCO Lin et al. (2014) datasets. The accompanying KG consists
of roughly 194500 facts, concerning 88606 entities. Roughly 82% of the
questions have a Key Visual Concept (KVC) as the answer, whereas 18% have
information from the Knowledge Base (KB) as the answer.

Answering questions in FVQA is to solve for

$\hat{y}=\operatorname*{argmax}\limits_{e\in\mathcal{E}}\>p(y=e\>|\>q,I,\mathcal{G}),$
(1)

i.e., finding the most probable entity as the answer given a question $q$ and
image $I$, and given the graph $\mathcal{G}$. Our formulation of the missing
edge reasoning task considers $\mathcal{G}_{o}$.

Wang et al. (2016) attempted FVQA as a parsing and querying problem,
constructing 32 different templates of queries, and classifying each image-
question pair as requiring one of these templates. Simple keyword matching
techniques further prune the retrieved facts. Straight to the Facts (STTF)
Narasimhan and Schwing (2018) approached FVQA by directly learning to retrieve
supporting facts, where each fact-entity was represented using lexical
semantic representations. Narasimhan et al. (2018) extended this approach in
Out-of-the box (OOB), the current SOTA, by using local neighbourhood-based
reasoning via a Graph Convolution Network (GCN) Kipf and Welling (2017) to
answer each question. All of these current approaches rely on the ground-truth
edge to be present in the KG.

##  3 Our approach - Seeing is Knowing

The proposed architecture for FVQA is shown in Fig. 2. As shown, a given image
$I$ and query $q$ are combined via CoAttention to form two entity query
vectors, $f_{KVC}(q,I)$ and $f_{KB}(q,I)$. The KG is then queried for the
answer to the question, according to

$\hat{y}(q|I)=\begin{cases}\operatorname*{argmax}\limits_{e\in\mathcal{E}}f_{KVC}(q,I)^{T}e&g_{KVC}(q)=1\\\
\operatorname*{argmax}\limits_{e\in\mathcal{E}}f_{KB}(q,I)^{T}e&g_{KVC}(q)=0\end{cases}$
(2)

where the gating function $g_{KVC}(q)\in\left\\{0,1\right\\}$ is equal to 1 if
the text of the question indicates that the answer is visible in the image,
equal to 0 otherwise.

The rest of this section addresses representations of the entities, image, and
query, the information fusion functions, the gating function, and the loss
function.

###  3.1 KG representation

KG Embeddings are learned by training a surrogate binary classifier to
discriminate true edges from false. Since the KG only contains positive
examples, we perform hard negative mining to generate negative examples using
self-adversarial negative sampling Sun et al. (2019). A total of $n$
adversarial examples are generated for each positive example, and used to
train discriminative embeddings using noise contrastive estimation Gutmann and
Hyvärinen (2010). Thus the knowledge graph embedding loss
${\mathcal{L}}_{KGE}$ includes the negative log probability that each observed
edge is true ($\ln\sigma(\phi(f_{i}))$), and the expected log probability that
the adversarial edges are false
($\ln\sigma(-\phi(f_{j}^{\prime}))=\ln\left(1-\sigma(\phi(f_{j}^{\prime}))\right)$):

${\mathcal{L}}_{KGE}=-\sum\limits_{i=1}^{|\mathcal{G}|}\left(\ln\sigma\big{(}\phi(f_{i})\big{)}+E_{i}\left[\ln\sigma\big{(}-\phi(f_{j}^{\prime})\big{)}\right]\right),$
(3)

where expectation is with respect to the probability $p_{i}(f_{j}^{\prime})$,
tuned using a temperature hyperparameter $\alpha$ as

$p_{i}(f_{j}^{\prime})=\frac{\exp(\alpha\>\phi(f_{j}^{\prime}))}{\sum\limits_{k=1}^{n}\exp(\alpha\>\phi(f_{k}^{\prime}))}.$
(4)

Eq. (3) is used to train embeddings of the head ($h$) and tail ($t$), which
are applied to the FVQA task as described in the next several subsections. Eq.
(3) also trains relation embeddings ($r$) and MLP weights for the ERMLP
scoring function ($w_{MLP}$); these quantities are not used for the downstream
FVQA task.

###  3.2 Image representation

Narasimhan et al. (2018) found that providing raw feature maps from a standard
convolutional network like ResNet He et al. (2016) or VGG Simonyan and
Zisserman (2015) actually hurt performance on FVQA. We therefore represent
each image using visual concepts found in the image.

Objects: We use Torchvision’s Coco object-detector, a Faster RCNN detector Ren
et al. (2015) with ResNet50 backbone He et al. (2016), and feature pyramid
network Lin et al. (2017), which detects 80 object classes. We also use a
detector ZFTurbo (2018) trained on an OpenImages 600-class detection task. We
include classes present in ImageNet 200 plus those in Wu et al. (2016) to
maximize overlap with the dataset used with FVQA.

Scenes: We use a wideresnet Zagoruyko and Komodakis (2016) detector trained on
MIT365 places dataset Zhou et al. (2017) and consider the 205 classes that
were used in constructing the FVQA KG.

Overall, we detect 540 visual concepts.

Having detected visual concepts in each image, we represent the
$i^{\textrm{th}}$ image as a collection of entities,
$I_{i}=[e_{i}^{1},\ldots,e_{i}^{m}]\in\Re^{N_{e}\times m}$, where $N_{e}$ is
the embedding dimension, and $m$ is the number of visual concepts detected in
the image. We detect a maximum of $m=14$ visual concepts in each image. Our
findings imply that for FVQA reasoning, an image is best represented as a
collection of KG entity embedding vectors $e_{i}^{j}$, apparently because
these KG embeddings encode the graph structure and background information
necessary to be able to answer questions. We think this is an important
finding, and we show its effect on the answer prediction accuracy.

Figure 3: Image and query are fused using the CoAttention mechanism depicted
here. First, self-attention computes a weighted summary of the query (bottom
orange circle). Second, the query is used to compute an attention-weighted
summary of the concepts in the image (top orange circle). The resulting image
query is a vector drawn from the span of the entities present in the image.

####  3.2.1 Language representation

For representing the question words, we use the last layer of contextual
ALBERT Lan et al. (2020) embeddings without finetuning for FVQA training.
After passing through an LSTM, we use the hidden state representation for each
word $w_{t}$ for further processing as $q_{i}^{t}=h(w_{t})$ as the question
representation.

Parameters |  Used for |  Loss Function
---|---|---
$h,r,t,w_{MLP}$ |  KG embeddings |  ${\mathcal{L}}_{KGE}$
$w_{\alpha_{q}}$, $w_{\alpha_{I}}$, $w_{KVC}$, $w_{KB}$, $\theta_{LSTM}$ |  Answer-retrieval based on image and question |  ${\mathcal{L}}_{FVQA}$
$w_{g},\theta_{LSTM}$ |  Choose answer source $\in\left\\{f_{KVC},f_{KB}\right\\}$ |  Cross entropy
Table 1: Summary of all trainable parameters. Head ($h$) and tail ($t$) use identical embedding vectors. Method |  Sampling |  MR |  MRR |  Hits@1 |  Hits@3 |  Hits@10
---|---|---|---|---|---|---
ERMLP |  adversarial |  11194 |  0.156 |  0.132 |  0.152 |  0.197
ERMLP |  uniform |  $14907$ |  $0.122$ |  $0.09$ |  $0.128$ |  $0.173$
Incomplete KG results
ERMLP (QA facts missing) |  adversarial |  $11071\pm 479$ |  $0.162\pm 0.007$ |  $0.136\pm 0.003$ |  $0.162\pm 0.005$ |  $0.204\pm 0.007$
ERMLP (50% KG) |  adversarial |  $12880$ |  $0.144$ |  $0.1$ |  $0.13$ |  $0.161$
Table 2: KG Embedding accuracy for ERMLP (see Appendix for TransE and RotatE).

###  3.3 Fusion Functions $f_{KVC}$ and $f_{KB}$

Image and query are fused using a CoAttention mechanism, as depicted in Fig.
3. First, we calculate attention weights for each word in the question, and
subsequently a self-attention-weighted encoding for the question as:

$A(q_{i})=\sum\limits_{t=1}^{|q_{i}|}\alpha_{q}^{t}\>q_{i}^{t},~{}~{}~{}\\\
\alpha_{q}^{t}=\frac{\exp(w_{\alpha_{q}}^{T}q_{i}^{t})}{\sum\limits_{t=1}^{|q_{i}|}\exp(w_{\alpha_{q}}^{T}q_{i}^{t})}$
(5)

where $\alpha_{q}^{t},w_{\alpha_{q}}$ are respectively the attention paid to
word $w_{t}$, and the weight vector from which it is computed.

Then, using $A(q_{i})$ as a query, we compute an attention-weighted summary of
the image:

$A(I_{i})=\sum\limits_{j=1}^{m}\alpha_{I}^{j}\>e_{i}^{j},~{}~{}~{}\alpha_{I}^{j}=\frac{\exp\left(w_{\alpha_{I}}^{T}\left[\begin{array}[]{c}A(q_{i})\\\
e_{i}^{j}\end{array}\right]\right)}{\sum_{k=1}^{m}\exp\left(w_{\alpha_{I}}^{T}\left[\begin{array}[]{c}A(q_{i})\\\
e_{i}^{k}\end{array}\right]\right)}$ (6)

where $\alpha_{I}^{j},w_{\alpha_{I}},e_{i}^{j}$ are respectively the attention
paid to concept $j$ in the image, the weight vector from which it is computed,
and the $j^{\textrm{th}}$ concept present in the image. $A(I_{i})$ is the
attention-weighted representation of the image. Both $A(I_{i})$ and $A(q_{i})$
learn a mapping: $R^{N_{e}\times\>m}\rightarrow R^{N_{e}}$.

These attention-weighted image and question encodings compute joint image-
question encodings via late fusion, as:

$\displaystyle f_{KVC}(q_{i},I_{i})$
$\displaystyle=h\left(A(I_{i}),A(q_{i});w_{KVC}\right)$ (7) $\displaystyle
f_{KB}(q_{i},I_{i})$ $\displaystyle=h\left(A(I_{i}),A(q_{i});w_{KB}\right)$
(8)

where $h(\cdot)$ is a two-layer fully-connected network with ReLU activation
functions. Using $f_{KVC}(q_{i},I_{i})=A(I_{i})$, i.e., the attention weighted
image encodings to directly retrieve the answer significantly reduces
accuracy, suggesting the need for successive fully connected layers to add
capacity.

###  3.4 Gating function $g_{KVC}$

The fusion functions $f_{KVC}$ and $f_{KB}$ are trained to retrieve two
different entities from the KG, either of which might be the answer to the
question. The gating function, $g_{KVC}$, selects one of these two. The gating
function is a sigmoid fully-connected layer applied to the final output state
of an LSTM, whose input is the query, and which is trained using binary cross
entropy so that $g_{KVC}=1$ if the correct answer is a key visual concept in
the image.

###  3.5 Loss function

A summary of all parameters is provided in Table 1. Entity embeddings are
learned in order to minimize the loss function in Eq. (3), then all parameters
are jointly trained in order to minimize the cosine distance between the
ground truth entity, $y_{i}$, and the network output:

${\mathcal{L}}_{FVQA}=\frac{1}{n}\sum_{i=1}^{n}\left(1-y_{i}^{T}\hat{y}(q_{i}|I_{i})\right)$
(9)

where $\hat{y}(q_{i}|I_{i})$ is as given in Eq. (2).

##  4 Text-augmented composite score

###  4.1 Text-augmented score metric

for  _$q_{i},I_{i}\in\mathcal{D}$_ do

Obtain token set $\mathcal{T}=\texttt{TOKENIZE}(q_{i},I_{i})$;

for  _$f_{k}\in\mathcal{G}$_ do

for  _$w_{t}\in\texttt{TOKENIZE}(f_{k})$_ do

$S(w_{t})=\underset{c\in\mathcal{T}}{\max}\frac{g(w_{t})^{T}g(c)}{|g(w_{t})||g(c)|}$;

end for

$\mathcal{M}=\\{w_{j}:\underset{j\in|f_{k}|}{\texttt{argsort}}\ S(w_{j})\\}$;

$\eta(f_{k})=\sum_{j=1}^{0.8*|\mathcal{M}|}S(w_{j})$;

end for

$\mathcal{F}_{100}=\\{f_{k}:\underset{k\in|\mathcal{G}|}{\texttt{argsort}}\
\eta(f_{k})\\}_{k=1}^{100}$;

end for

Algorithm 1 Pruning entity search space to set of most relevant facts
$\mathcal{F}_{100}$

To enhance SiK’s answer retrieval, we define additionally a text-augmented
metric to leverage lexical similarity between the facts and the question in
the algorithm as described in 1. Firstly, a pruning strategy as described in
Narasimhan et al. (2018) is implemented. Using GLoVE 100-D embeddings, a
similarity score is computed for each KG fact, by first computing cosine
similarity for each word in the fact with every word in the question and
detected visual entities. The top 80% scoring words from each fact are
retained, and these similarity scores are averaged to assign a score to each
fact for a given question. The top 100 scoring facts are retrieved for each
question, denoted as ${\mathcal{F}}_{100}$. Answer retrieval then takes place
from entities within this reduced set of facts ${\mathcal{F}}_{100}$. We
define the score function, a convex combination of three complementary
metrics, as follows:

$\displaystyle\hat{y}(q|I)$
$\displaystyle=\operatorname*{argmax}\limits_{e\in{\mathcal{F}}_{100}}\left\\{\lambda_{1}K(q,I)^{T}e+\lambda_{2}{J(q,e)}\right.$
$\displaystyle\left.+\lambda_{3}G(q,e)\right\\}~{}~{}~{}~{}\mbox{s.t.}~{}\sum_{k=1}^{3}\lambda_{k}=1$

Here, $K(q,I)^{T}e$ is the KG similarity score of an entity with the query
produced by the SiK network. $J(q,e)=\max_{f\in{\mathcal{F}}_{100},e\in
f}j(q,f)$, where $j(q,f)$ is the Jaccard (word-token) similarity between the
question and one of the retrieved facts $f$. An entity may be a part of more
than one fact in ${\mathcal{F}}_{100}$; $e\in f$ means that $e$ is either the
head or tail of $f$. $G(q,e)=\max_{f\in{\mathcal{F}}_{100},e\in f}g(q,f)$
where $g(q,f)$ is the similarity between its fact and a question based on
averaged GloVe embeddings.

Technique |  Hits@1 |  Hits@3
---|---|---
HieCoAtt |  $33.7\pm 1.18$ |  $50.00\pm 0.78$
FVQA top-1 qq-mapping |  $52.56\pm 1.03$ |  $59.72\pm 0.82$
STTF |  $62.2\pm NR$ |  $75.6\pm NR$
OOB top-1 rel |  $\mathbf{65.8\pm NR}$ |  $\mathbf{77.32\pm NR}$
OOB top-3 rel |  $69.35\pm NR$ |  $80.25\pm NR$
Seeing is Knowing
AvgEmbed, IaK |  $27.77\pm 0.72$ |  $32.43\pm 0.94$
ERMLP – Adv, Multihot |  $51.51\pm 1.14$ |  $64.89\pm 1.37$
ERMLP, IaK |  $53.16\pm 0.79$ |  $63.9\pm.63$
ERMLP -Adv, IaK |  $\mathbf{54.38\pm 0.94}$ |  $\mathbf{65.76\pm 0.5}$
Seeing is Knowing - text augmented
ERMLP - Adv, IaK ($\lambda_{1}=0.4$, $\lambda_{2}=0.3$,$\lambda_{3}=0.3$) |  $\mathbf{60.82\pm 0.94}$ |  $\mathbf{77.14\pm 0.50}$
ERMLP - Adv, IaK ($\lambda_{1}=0$, $\lambda_{2}=0.5$,$\lambda_{3}=0.5$) |  $39.76\pm 1.08$ |  $60.84\pm 0.67$

Incomplete KG
---
Method | Only QA facts missing | 50% KG missing
AvgEmbed, IaK |  $27.77\pm 0.72$ |  $32.43\pm 0.94$ |  $27.77\pm 0.72$ |  $32.43\pm 0.94$
OOB top-3 rel |  $28.58\pm 0.01$ |  $43.56\pm 0.01$ |  $27.53\pm 0.01$ |  $41.56\pm 0.01$
ERMLP -Adv, IaK |  $53.45\pm 0.77$ |  $65.1\pm 1.41$ |  $52.29\pm 0.86$ |  $62.74\pm 0.69$
ERMLP - Adv, IaK ($\lambda_{1}=0.34$, $\lambda_{2}=0.33$,$\lambda_{3}=0.33$) |  $\mathbf{55.13\pm 0.97}$ |  $\mathbf{73.04\pm 0.54}$ |  $\mathbf{55.14\pm 1.1}$ |  $\mathbf{72.95\pm 0.38}$
ERMLP - Adv, IaK ($\lambda_{1}=0$, $\lambda_{2}=0.5$,$\lambda_{3}=0.5$) |  $26.8\pm 0.90$ |  $49.24\pm 0.62$ |  $26.78\pm 0.856$ |  $49.20\pm 0.63$

Table 3: FVQA accuracy (IaK - Image as Knowledge, Adv - self-adversarial
negative sampling, NR - Not reported)

##  5 Experimental Setup

###  5.1 KG Embeddings training

For training of each KG embedding algorithm, we split all the facts in the KG
as 80% train, 20% test. Entity and relation embeddings have a dimension of
$N_{e}=300$. Batch size is 1000. Each network is trained for 25000 steps using
the Adam optimizer with learning rate initallized as 0.01 shrunk every 10000
steps by 0.1. Learning rates for all experiments were decided by choosing from
the set {0.1, 0.01. 0.001, 0.0001}. We set $\alpha=1$ for all experiments. We
use $n=16$ negative samples for each positive sample. ERMLP uses a three layer
neural network with $3N_{e}$ (taking in head, rel, and tail embeddings),
$2N_{e}=600$ and $N_{e}=300$ units respectively, and the output contains one
sigmoid unit (the score $\phi(h,r,t)$). Hidden activations are ReLU. No
dropout was used.

KGE accuracy is measured using standard metrics: Hits @1, Hits @3, Hits @10
determine how often each correct tail/head gets ranked in the top 1, 3, or 10
ranked facts for each ground-truth $(h,r)$/$(r,t)$ pair. Mean Rank measures
the mean rank of each true fact in the dataset, Mean Reciprocal Rank =
$\frac{1}{|{\mathcal{D}}|}\Sigma_{i}\frac{1}{R_{i}}$. While we report these
metrics, we do note that these metrics are not best suited for common-sense
KGs for reasons mentioned before. However we leave a more refined analysis of
these methods for future work.

###  5.2 FVQA training

We report Hits @1 and Hits @3 for each algorithm. All numbers are based on
averaging results across five train - test splits provided with the dataset.
The number of questions varies slightly, but roughly fall half into both
training and testing sets for each split. Stochastic gradient descent with a
batch size of 64 trains $f_{KVC}$ and $f_{KB}$ for 250 steps with a learning
rate of 0.01, reduced by 0.1 every 100 epochs, and a weight decay of 1e-3.
Fully-connected layers use a dropout probability of 0.3. The gating function
$g_{KVC}$ is trained for 20 steps with step-size of 0.1.

GPUs provided by Google Colab are used to train all models. Our heaviest KG
embedding technique (ERMLP) takes roughly 3 hours to train, while one train
split for $f_{KVC}$ takes roughly 30 minutes. Subgraph construction for each
queston takes about 1s, and 250 epochs to train our implementation of OOB took
roughly 3 hours.

###  5.3 Baselines

Results in the standard QA task for the models FVQA, STTF, and OOB are taken
from the respective papers since the codes for these systems have not been
made available. HieCoAtt denotes using a Hierarchical CoAttention network Lu
et al. (2016) as implemented in Wang et al. (2016). AvgEmbed denotes a method
which compares STTF’s and OOB’s fact representation methodology with our
architecture to correctly perform missing-edge reasoning. We use averaged
300-dimensional GLoVE embeddings Pennington et al. (2014) to represent each
entity. We also report results from our OOB implementation in the incomplete
KG setting.

##  6 Results and Discussion

The gating function achieves an accuracy of 96%, same as reported in
Narasimhan and Schwing (2018). We discuss below the performance of other
modules of our architecture.

###  6.1 ${\mathcal{F}}_{100}$ fact recall and impact on FVQA

We only observe 63% fact recall within ${\mathcal{F}}_{100}$ across the entire
dataset as opposed to 84.8% as reported by Narasimhan et al. (2018). This
further goes down to 53% if filtering for top-3 relationships. This difference
is significant, and FVQA accuracy reported by OOB at such levels of fact
recall are lower. One factor for lower recall is noisy visual detections,
whose keywords impact fact retrieval. Therefore, with access to similar visual
detections as the other methods, SiK could potentially achieve even higher
accuracy. Furthermore, owing to the lower fact retrieval recall, our OOB
implementation could not replicate the reported performance in the standard QA
task. This also highlights the crucial reliance of OOB on correct fact
retrieval and further substantiates our observation of its low performance
when the KG is incomplete.

|  |
---|---|---
Question 1: What is the difference between the instrument & the violin?
SPO triple: : {Cello, HasProperty, like a violin but larger}
Answer Source: KG
Answer: like a violin but larger
Answer predicted: like a violin but larger |  Question 2: Which object in this image belongs to the category Herbivorous animals?
SPO triple: {Giraffe, Category, Herbivorous animals}
Answer Source: Image
Answer: Giraffe
Answer predicted: Giraffe |  Question 3: What popular pet is in this image?
SPO triple: {Goldfish, IsA, popular pet}
Answer Source: Image
Answer: Goldfish
Answer predicted: Fish
|  |
Question 4: What object in this image is commonly eaten for lunch?
SPO triple: {Sandwich, IsA, meal commonly eaten for lunch}
Answer Source: Image
Answer:Sandwich
Answer predicted: Bread |  Question 5:Where can you find the large object in the back of this image?
SPO triple:{Bus, AtLocation, Bus stop}
Answer Source: KG
Answer: Bus stop
Answer predicted: Wait place |  Question 6: What can we find in the place shown in this image?
SPO triple: {Furniture, AtLocation, Bedroom}
Answer Source: KG
Answer:Furniture
Answer predicted: Your House
Figure 4: Success and Failure cases of Seeing is Knowing

###  6.2 Incomplete KGs

The robustness of SiK is demonstrated in the incomplete KG setting. Here we
discuss two of them - one where only the QA-related facts are missing and
another where 50% of the KG is missing (more settings in Appendix). In both
cases, we see standalone SiK and text-augmented SiK only lose some of their
accuracy. Our implementation of OOB, and AvgEmbed both underperform SiK by
over 25%. Setting $\lambda_{1}=0$ in the score also leads to similar
performance, highlighting the importance of KG features for FVQA. For a more
detailed discussion of the missing edges experiments, the interested reader is
directed to the Appendix.

###  6.3 Composite metric performance

When the required edge is present in the graph, standalone SiK underperforms
OOB by 11%. This is enhanced using the composite score, which sees a 6% point
improvement. Quite remarkably, text-augmented SiK works best when roughly
equal coefficients are used for all three similarities. However, the strongest
similarity metric is still that obtained from SiK (see Table 3 and Appendix).

###  6.4 Image as Knowledge

To understand how useful the Image-as-Knoweldge representation is compared to
other variants, we compare it to the multihot variant proposed by Narasimhan
et al. (2018) along with our best performing KG embedding technique. ‘Image-
as-knowledge’ provides a 3-point performance improvement (Table 3), apparently
because the retrieval of an entity happens in the entity space spanned by the
vectors of the IaK representation.

###  6.5 Success and Failure cases

To investigate the only learning module in the score, we look at the failure
modes for the standalone SiK architecture. Since the gating function performs
with almost perfect accuracy, our main source of error is incorrect entity
prediction. Since a prediction is considered correct only if there’s an exact
match in the entities, a lot of inaccuracies stem from cases where the network
predicts a semantically valid but different entity. Entities sharing parent-
child relationships (Question 3, Fig. 1) or similar attributes through multi-
hop relationships (Questions 4-6) are commonly mistaken by the SiK network. We
discuss more failure cases in the appendix.

##  7 Conclusion

An architecture is proposed that solves the FVQA task even when the required
edge is missing from the knowledge graph. In the process, we present the first
approach to use KG embeddings for FVQA. A composite answer retrieval method
augments its accuracy by incorporating complementary lexical features and KG
semantic features. Serendipitous benefits of the standalone approach include:
(1) improved computational complexity, and (2) an improved representation of
each image, as the span of KG embeddings of the visible entities.

##  8 Ethical impact

Figure 5:  Question: Where is this place?
SPO triple: : {Life, AtLocation, Zoo}
Answer Source: Knowledge Base
Answer: Zoo
Answer predicted: in Zimbabwe

We now examine the ethical implications of our work. A prominent issue could
be that of different biases known to exist in our data sources. Shankar et al.
(2017) show population / representation bias existing in OpenImages and
ImageNet. Fisher et al. (2019) showed web-scale common-sense KGs can be tough
to curate and can allow biases to creep in. Janowicz et al. (2018) note how
the density of world locations generating DBPedia data (extracted from
Wikipedia) is at odds with world population density. Fig. 5 shows how this
manifests in our system. The answer for a place relevant to giraffes in
wildlife, comes up as Zimbabwe, even though the only edges present in the KG
concerning Zimbabwe were {Person, AtLocation, in Zimbabwe}, {Dog, AtLocation,
in Zimbabwe}, {Tree, AtLocation, in Zimbabwe}, {Elephant, AtLocation, in
Zimbabwe}. Such an error is quite informative and humbling – this means that
different modalities (image, language, graph) working in tandem could still
amplify their individual biases. For deploying such a system, we recommend
debiasing of parameters learned in our architecture. While ConceptNet has been
active in debiasing their representations, debiasing KG embeddings has not
received as much attention, and it could pose subtle problems given that most
entities would have low node-degree. A multimodal approach to debias
representations could be an interesting research direction.

## References

  * Antol et al. (2015) S. Antol, A. Agrawal, J. Lu, M. Mitchell, D. Batra, C. L. Zitnick, and D. Parikh. 2015.  Vqa: Visual question answering.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 2425–2433.
  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Zachary Ives, and et al. 2007.  Dbpedia: A nucleus for a web of open data.  In _PROC. 6TH INT’L SEMANTIC WEB CONF_. Springer.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008\.  Freebase: a collaboratively created graph database for structuring human knowledge.  In _SIGMOD Conference_ , pages 1247–1250.
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In _In Advances in Neural Information Processing Systems 26. Curran Associates, Inc_ , pages 2787–2795.
  * Dettmers et al. (2018) T. Dettmers, P. Minervini, P. Stenetorp, and S. Riedel. 2018.  Convolutional 2D knowledge graph embeddings.  In _Proc. AAAI_ , pages 1811–1818.
  * Dong et al. (2014) Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Patrick Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. 2014.  Knowledge vault: a web-scale approach to probabilistic knowledge fusion.  In _Knowledge Distillation and Data Mining_ , pages 601–610.
  * Fisher et al. (2019) Joseph Fisher, Dave Palfrey, Christos Christodoulopoulos, and Arpit Mittal. 2019\.  Measuring social bias in knowledge graph embeddings.
  * Goyal et al. (2017) Yash Goyal, Tejas Khot, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh. 2017\.  Making the v in vqa matter: Elevating the role of image understanding in visual question answering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Gutmann and Hyvärinen (2010) Michael Gutmann and Aapo Hyvärinen. 2010.  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.  Proceedings of Machine Learning Research, pages 297–304, Chia Laguna Resort, Sardinia, Italy.
  * Halford et al. (2010) Graeme S. Halford, William H. Wilson, and Steven Phillips. 2010.  Review relational knowledge: the foundation of higher cognition.
  * He et al. (2016) Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. 2016.  Deep residual learning for image recognition.  _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778.
  * Janowicz et al. (2018) Krzysztof Janowicz, Bo Yan, Blake Regalia, Rui Zhu, and Gengchen Mai. 2018.  Debiasing knowledge graphs: Why female presidents are not like female popes.  In _Proceedings of the ISWC 2018 Posters & Demonstrations_.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations (ICLR)_.
  * Lan et al. (2020) Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. 2020.  Albert: A lite bert for self-supervised learning of language representations.  In _International Conference on Learning Representations_.
  * Li et al. (2019) Hui Li, Peng Wang, Chunhua Shen, and A. V. D. Hengel. 2019.  Visual question answering as reading comprehension.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 6312–6321.
  * Lin et al. (2014) T-Y Lin, M Maire, S Belongie, J Hays, P Perona, D Ramanan, P Dollár, and CL Zitnick. 2014.  Microsoft COCO: Common objects in context.  _Lecture Notes in Computer Science_ , 8693:740–755.
  * Lin et al. (2017) Tsung-Yi Lin, Piotr Dollar, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie. 2017.  Feature pyramid networks for object detection.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Liu and Singh (2004) Hugo Liu and Push Singh. 2004.  Conceptnet: A practical commonsense reasoning toolkit.  _BT TECHNOLOGY JOURNAL_ , 22:211–226.
  * Lu et al. (2016) Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh. 2016.  Hierarchical question-image co-attention for visual question answering.  In _Advances in Neural Information Processing Systems 29_ , pages 289–297.
  * Mitchell and Fredkin (2014) T. Mitchell and E. Fredkin. 2014.  Never-ending language learning.  In _2014 IEEE International Conference on Big Data (Big Data)_ , pages 1–1.
  * Narasimhan et al. (2018) Medhini Narasimhan, Svetlana Lazebnik, and Alexander Schwing. 2018.  Out of the box: Reasoning with graph convolution nets for factual visual question answering.  In _Advances in Neural Information Processing Systems 31_ , pages 2654–2665.
  * Narasimhan and Schwing (2018) Medhini Narasimhan and Alexander G. Schwing. 2018.  Straight to the facts: Learning knowledge base retrieval for factual visual question answering.  _CoRR_.
  * Nickel et al. (2011) M. Nickel, V. Tresp, and H.P. Kriegel. 2011.  A three-way model for collective learningon multi-relational data.  In _Proc. International Conference on Machine Learning_.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014.  GloVe: Global vectors for word representation.  In _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1532–1543.
  * Ren et al. (2015) Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. 2015.  Faster r-cnn: Towards real-time object detection with region proposal networks.  In _Advances in Neural Information Processing Systems 28_ , pages 91–99.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. 2015.  ImageNet Large Scale Visual Recognition Challenge.  _International Journal of Computer Vision (IJCV)_.
  * Saxena et al. (2020) Apoorv Saxena, Aditay Tripathi, and Partha Talukdar. 2020.  Improving multi-hop question answering over knowledge graphs using knowledge base embeddings.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4498–4507, Online. Association for Computational Linguistics.
  * Shankar et al. (2017) Shreya Shankar, Yoni Halpern, Eric Breck, James Atwood, Jimbo Wilson, and D. Sculley. 2017.  No classification without representation: Assessing geodiversity issues in open data sets for the developing world.  In _NIPS 2017 workshop: Machine Learning for the Developing World_.
  * Simonyan and Zisserman (2015) K Simonyan and A Zisserman. 2015.  Very deep convolutional networks for large-scale image classification.  In _Proc. International Conference on Learning Representations_.
  * Socher et al. (2013) R. Socher, D. Chen, C.D. Manning, and A.Y. Ng. 2013.  Reasoning with neural tensor networks for knowledgebase completion.  In _Advances in Neural Information Processing Systems_ , page 926–934. Curran Associates, Inc.
  * Suchanek et al. (2007) Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007.  Yago: A core of semantic knowledge.  In _IN PROC. OF WWW ’07_ , pages 697–706. ACM.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In _Proc. International Conference on Learning Representations_ , pages 1–18.
  * Tandon et al. (2014) Niket Tandon, Gerard de Melo, Fabian M. Suchanek, and Gerhard Weikum. 2014.  Webchild: harvesting and organizing commonsense knowledge from the web.  In _Seventh ACM International Conference on Web Search and Data Mining, WSDM 2014, New York, NY, USA, February 24-28, 2014_ , pages 523–532.
  * Wang et al. (2016) Peng Wang, Qi Wu, Chunhua Shen, Anton van den Hengel, and Anthony R. Dick. 2016\.  FVQA: fact-based visual question answering.  _CoRR_ , abs/1606.05433.
  * Wu et al. (2016) Q. Wu, C. Shen, L. Liu, A. Dick, and A. Van Den Hengel. 2016.  What value do explicit high level concepts have in vision to language problems?  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 203–212.
  * Zagoruyko and Komodakis (2016) Sergey Zagoruyko and Nikos Komodakis. 2016.  Wide residual networks.  In _BMVC_.
  * ZFTurbo (2018) ZFTurbo. 2018.  Keras-retinanet for open images challenge 2018.  https://github.com/ZFTurbo/Keras-RetinaNet-for-Open-Images-Challenge-2018.git.
  * Zhou et al. (2017) Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. 2017\.  Places: A 10 million image database for scene recognition.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_.

##  9 Appendix

First Author
Affiliation / Address line 1
Affiliation / Address line 2
Affiliation / Address line 3
email@domain
&Second Author
Affiliation / Address line 1
Affiliation / Address line 2
Affiliation / Address line 3
email@domain

Seeing is Knowing - Supplementary material

Method |  KG Occlusion |  MR |  MRR |  Hits@1 |  Hits@3 |  Hits@10
---|---|---|---|---|---|---
ERMLP |  Only QA facts |  $11071$ |  $0.162$ |  $0.136$ |  $0.162$ |  $0.204$
ERMLP |  10% of KG |  $9690$ |  $0.175$ |  $0.148$ |  $0.1779$ |  $0.22$
ERMLP |  20% of KG |  $10733$ |  $0.1613$ |  $0.133$ |  $0.162$ |  $0.213$
ERMLP |  30% of KG |  $10437$ |  $0.154$ |  $0.127$ |  $0.156$ |  $0.199$
ERMLP |  40% of KG |  $11467$ |  $0.139$ |  $0.116$ |  $0.138$ |  $0.179$
ERMLP |  50% of KG |  $12880$ |  $0.144$ |  $0.1$ |  $0.13$ |  $0.161$
Table 4: KG Embedding performance of ERMLP when varying levels of the KG is occluded. ERMLP |  KG Occlusion |  Hits @1 |  Hits @3
---|---|---|---
ERMLP |  QA facts |  $53.45\pm 0.77$ |  $65.1\pm 1.41$
ERMLP |  10% of KG |  $53.19\pm 0.47$ |  $65.67\pm 0.31$
ERMLP |  20% of KG |  $53.62\pm 1.01$ |  $64.72\pm 0.98$
ERMLP |  30% of KG |  $53.15\pm 1.62$ |  $64.55\pm 1.23$
ERMLP |  40% of KG |  $53.14\pm 0.47$ |  $64.77\pm 0.55$
ERMLP |  50% of KG |  $52.29\pm 0.86$ |  $62.74\pm 0.69$
Table 5: FVQA accuracy of Seeing is Knowing using ERMLP when varying levels of
the KG is occluded.

## A. Experiments with incomplete KG

Table 4 shows the performance of KG Embeddings using standard metrics at
different levels of KG incompleteness. As expected, there is a small but
monotonous decline in the performance with more and more occlusion. A known
shortcoming of these metrics is that when the KG has $(subject,predicate)$
pairs that can lead to more than one $object$ entity, they will consider a
different but factually correct entity as incorrect.

Quite remarkably however, there is only a very slight decrease in SiK’s
performance when using any of these KG embeddings for the downstream FVQA task
(see Table 5). Only at 50% KG occlusion, we see a statistically significant
yet still small drop in performance. This highlights the robustness of using
KG embeddings for down-stream semantic tasks.

|  |
---|---|---
Question 1: What is the animal famous for?
SPO triple: {Giraffe, HasProperty, Long necked}
Answer Source: KG
Answer:long necked
Answer predicted: work for day without water |  Question 2: Which object in this image is used in spaghetti sauce?
SPO triple: {Sphagetti sauce, RelatedTo, Tomato}
Answer Source: Image
Answer: Tomato
Answer predicted: Bell Pepper |  Question 3: What is the family of the animal in this image?
SPO triple:{Fox, Category, Canidae}
Answer Source: KG
Answer:Canidae
Answer predicted: Burundian Culture
|  |
Question 4: What is the wooden thing used for?
SPO triple: {Flute, UsedFor, making music}
Answer Source: KG
Answer:making music
Answer predicted: Practice |  Question 5: What is the material of the chair?
SPO triple: {Chair, RelatedTo, Wooden}
Answer Source: KG
Answer:
Answer predicted: come in many style |  Question 6: What is the object in the left of the image used for?
SPO triple:{Bed, UsedFor, Laying on}
Answer Source: KG
Answer: Laying on
Answer predicted: Loose (sic) thing in
|  |
Question 7: What can we do in this place shown in this image?
SPO triple:{Lake, UsedFor, row a boat}
Answer Source: KG
Answer: row a boat
Answer predicted: build a treehouse |  Question 8: This game is most popular in which country?
SPO triple:{Table Tennis, HasProperty, Popular in China}
Answer Source: KG
Answer:Table Tennis
Answer predicted: Game Person Play |  Question 9: What the baseball bat looks like?
SPO triple: {Baseball, IsA, Long round tapered object}
Answer Source: KG
Answer: long round tapered object
Answer predicted: aggressive animal
Figure 6: Performance of standalone Seeing is Knowing network without the
composite score-based retrieval

## B. Characterizing inaccuracies of Seeing is Knowing Network: Qualitative
discussion

In order to analyze the types of errors SiK is prone to make, we now discuss
some more failure cases. We observe that there are three broad categories of
errors -

  1. 1.

Semantically correct answer, but answer is a different entity

  2. 2.

Incorrect answer, explainable relevance to question and image

  3. 3.

Entirely incorrect answers

An empirical study of these errors shows a significant fraction of them fall
in the first two categories. Errors in the first category can arise when the
model has implicitly pinned down the correct key visual entity and
relationship being asked about, but then chose a different entity (see
Question 4-6 Fig.6). A bed is an object one can lose things in, chairs come in
many styles, and a flute can be used for practice. These errors can also arise
if the model has chosen to place visual emphasis on an entity that is
different from ground truth, but is equally valid given a question (see
Question 7 Fig.6). Here, the model has retrieved the answer ‘build a
treehouse’ that appears in a fact with ‘tree’, but the ground truth of the
question asks about the entity ‘lake’.

Errors of the second category can arise in mainly two cases - incorrect
language and / or visual grounding. In cases where the visual grounding is
off, it could be due to false positives in detections (see Questions 1-3
Fig.6). Giraffes, tomatoes, and foxes are mistaken to be camels, bell peppers,
and lion respectively; entities relevant to the mistaken entities are then
chosen as answers.

In cases where the language grounding is off, one case could be that the model
has predicted the correct symbolism for a question (i.e. correct entity and
relationship), but the retrieved entity comes from a fact that is not grounded
in the language of the question. In Question 8 Fig. 6, ‘game person play’, a
property about the game table tennis is chosen, but it is not grounded in the
question-text which asks about the country where it is popular. A fix for this
would be to ensure that entities’ representations contain both lexical and
graph-based features. One approach could be to use contextual word embeddings
to encode entities before doing graph learning. Another approach involving
RotatE, could be to fix real part of the entities as lexical representations
during training, so that the imaginary parts could be enforced to encode
graph-based features for fixed lexical semantic features.

Lastly, entirely incorrect answers, such as Question 9 Fig.6 can occur in case
of sparse node connections (only one edge is present for ‘aggressive animal’).
SiK is indeed prone to making such unexplainable errors, highlighting the
scope for improvement to be gained from incorporating better lexical semantic
features as used in our composite score function.

## C. Attention maps

To investigate the performance of the Image-as-Knowledge module, Fig.7 depicts
both the visual and textual attention maps learnt by the network. We can see
that the CoAttention module is learning to pay attention to contextually
relevant cues based on the input word embeddings in the question and the KG
embeddings of the visual concepts. For Question 1 the textual attention
correctly attends to the word ’amber and green’ and the image attention
correctly attends to the entity ’traffic light’. In Question 2 similarly, the
textual attention attends to the word ’jazz club’ while the image attention
attends to the entity ’trumpet’. Likewise in Question 3, words ’centre of the
image’ and entity ’runway’ are correctly attended to.

In cases where the answer is incorrectly predicted, the learnt attention map
throws light on the reasoning of the network.

|  |
---|---|---
Question 1: Which object in this image is colored red, amber and green?
SPO triple: {Traffic Light, HasProperty, colour red amber and green}
Answer Source: Image
Answer: Traffic light
Answer predicted: Traffic light |  |
|  |
Question 2: Which object can be found in a jazz club?
SPO triple: {Trumpet, AtLocation, jazz club}
Answer Source: Image
Answer: Trumpet
Answer predicted: Trumpet |  |
|  |
Question 3: Where can object in the center of the image be found?
SPO triple: {Airplane, AtLocation, airport}
Answer Source: KG
Answer: Airport
Answer predicted: Runway |  |
Figure 7: Visualizing CoAttention weights learnt by Seeing is Knowing

## D. Choosing hyperparameters for composite score-based retrieval

To investigate the importance of each metric in the composite score, we vary
the respective coefficient $\lambda_{k}$ to each metric across a range of
values.

The first three rows of Table 6 demonstrate that the KG similarity metric
individually is strongest by some margin. Considering only Jaccard similarity
or GLoVe similarity is not enough to produce the accurate answer. This further
highlights the crucial involvement that a KG reasoning module has in
performance of any FVQA system. A standalone KG similarity metric, however,
falls short of the highest achieved accuracy, owing to its relative inability
to leverage lexical similarity between entity words and words in the question.
(Note that the system obtained by assigning all the weight to only SiK metric
is not the same as directly using SIK to retrieve the answer, since the former
still uses the subgraph construction method to prune the fact search space.
This is also demonstrated in the slightly different accuracy value of the two
methods.)

Coefficient values | Top 100 facts | Top 500 facts
---|---|---
$\lambda_{1}$ |  $\lambda_{2}$ |  $\lambda_{3}$ |  Hits @1 |  Hits @3 |  Hits @1 |  Hits @3
Single similarity metric being used
$1$ |  $0$ |  $0$ |  $56.05\pm 0.57$ |  $71.84\pm 0.44$ |  $55.43\pm 0.57$ |  $69.55\pm 0.58$
$0$ |  $1$ |  $0$ |  $17.44\pm 0.55$ |  $42.98\pm 0.86$ |  $13.83\pm 0.57$ |  $34.64\pm 1.00$
$0$ |  $0$ |  $1$ |  $13.38\pm 0.75$ |  $30.67\pm 0.80$ |  $11.75\pm 0.62$ |  $28.82\pm 0.75$
Equal importance to all similarity metrics
$0.34$ |  $0.33$ |  $0.33$ |  $60.73\pm 0.82$ |  $77.03\pm 0.46$ |  $60.63\pm 0.73$ |  $76.9\pm 0.51$
$0.4$ |  $0.3$ |  $0.3$ |  $60.53\pm 0.94$ |  $\mathbf{77.14\pm 0.50}$ |  $60.33\pm 0.92$ |  $77.01\pm 0.55$
$0.5$ |  $0.5$ |  $0$ |  $\mathbf{60.82\pm 0.98}$ |  $75.83\pm 0.42$ |  $59.96\pm 0.89$ |  $74.48\pm 0.47$
$0.5$ |  $0.25$ |  $0.25$ |  $59.96\pm 0.72$ |  $76.73\pm 0.37$ |  $59.57\pm 0.68$ |  $76.31\pm 0.57$
$0.5$ |  $0$ |  $0.5$ |  $54.59\pm 71.76$ |  $71.76\pm 0.46$ |  $52.52\pm 0.74$ |  $71.03\pm 0.68$
$0$ |  $0.5$ |  $0.5$ |  $40.18\pm 1.13$ |  $61.62\pm 0.47$ |  $39.76\pm 1.08$ |  $60.84\pm 0.67$
Highest importance to KG similarity
$0.6$ |  $0.2$ |  $0.2$ |  $58.89\pm 0.54$ |  $75.89\pm 0.44$ |  $58.5\pm 0.51$ |  $75.1\pm 0.658$
$0.7$ |  $0.15$ |  $0.15$ |  $58.05\pm 0.64$ |  $74.87\pm 0.49$ |  $57.6\pm 0.5$ |  $73.84\pm 0.49$
$0.8$ |  $0.1$ |  $0.1$ |  $57.23\pm 0.54$ |  $73.9\pm 0.56$ |  $56.73\pm 0.49$ |  $72.41\pm 0.40$
Table 6: FVQA performance for different convex combinations of $\lambda_{k}$ in the standard answer prediction task. KG Embedding algorithm used is ERMLP and image representation is Image-as-Knowledge. $\lambda_{1}$ is the coefficient of KG similarity, $\lambda_{2}$ is the coefficient of Jaccard similarity and $\lambda_{3}$ is the coefficient for GLoVE similarity Coefficient values | Only QA facts missing | 50% KG missing
---|---|---
$\lambda_{1}$ |  $\lambda_{2}$ |  $\lambda_{3}$ |  Hits @1 |  Hits @3 |  Hits @1 |  Hits @3
Single similarity metric being used
$1$ |  $0$ |  $0$ |  $55.23\pm 0.44$ |  $70.56\pm 0.41$ |  $55.20\pm 0.77$ |  $70.47\pm 0.36$
$0$ |  $1$ |  $0$ |  $9.91\pm 0.58$ |  $27.44\pm 1.09$ |  $9.92\pm 0.61$ |  $27.48\pm 1.06$
$0$ |  $0$ |  $1$ |  $12.42\pm 0.72$ |  $29.43\pm 0.72$ |  $12.44\pm 0.76$ |  $29.47\pm 0.72$
Equal importance to all similarity metrics
$0.34$ |  $0.33$ |  $0.33$ |  $55.13\pm 0.98$ |  $73.04\pm 0.54$ |  $55.13\pm 1.09$ |  $72.95\pm 0.38$
$0.4$ |  $0.3$ |  $0.3$ |  $56.35\pm 1.08$ |  $73.56\pm 0.58$ |  $56.38\pm 1.08$ |  $73.47\pm 0.44$
$0.5$ |  $0.5$ |  $0$ |  $54.78\pm 0.78$ |  $70.53\pm 0.56$ |  $54.79\pm 0.98$ |  $70.48\pm 0.33$
$0.5$ |  $0.25$ |  $0.25$ |  $\mathbf{56.80\pm 0.82}$ |  $\mathbf{73.62\pm 0.42}$ |  $\mathbf{56.81\pm 0.84}$ |  $\mathbf{73.54\pm 0.25}$
$0.5$ |  $0$ |  $0.5$ |  $53.68\pm 0.82$ |  $70.77\pm 0.67$ |  $53.63\pm 0.87$ |  $70.67\pm 0.35$
$0$ |  $0.5$ |  $0.5$ |  $26.8\pm 0.90$ |  $49.24\pm 0.62$ |  $26.79\pm 0.85$ |  $49.21\pm 0.63$
Highest importance to KG similarity
$0.6$ |  $0.2$ |  $0.2$ |  $56.46\pm 0.51$ |  $73.36\pm 0.51$ |  $56.45\pm 0.63$ |  $73.31\pm 0.22$
$0.7$ |  $0.15$ |  $0.15$ |  $56.23\pm 0.36$ |  $72.7\pm 0.39$ |  $56.17\pm 0.66$ |  $72.63\pm 0.34$
$0.8$ |  $0.1$ |  $0.1$ |  $55.88\pm 0.25$ |  $72.01\pm 0.46$ |  $55.85\pm 0.65$ |  $71.91\pm 0.31$
Table 7: FVQA performance for different convex combinations of $\lambda_{k}$ in the incomplete KG FVQA task for top-100 facts retrieved. KG Embedding algorithm used is ERMLP and image representation is Image-as-Knowledge.$\lambda_{1}$ is the coefficient of KG similarity, $\lambda_{2}$ is the coefficient of Jaccard similarity and $\lambda_{3}$ is the coefficient for GLoVE similarity Method |  Sampling |  MR |  MRR |  Hits@1 |  Hits@3 |  Hits@10
---|---|---|---|---|---|---
TransE |  adversarial |  $14692$ |  $0.1035$ |  $0.05$ |  $0.13$ |  $0.19$
TransE |  uniform |  $13736$ |  $0.0967$ |  $0.04$ |  $0.112$ |  $0.194$
RotatE |  adversarial |  $17660$ |  ${\bf 0.173}$ |  ${\bf 0.14}$ |  ${\bf 0.18}$ |  ${\bf 0.22}$
RotatE |  uniform |  $18468$ |  $0.144$ |  $0.122$ |  $0.152$ |  $0.179$
ERMLP |  adversarial |  11194 |  $0.156$ |  $0.132$ |  $0.152$ |  $0.197$
ERMLP |  uniform |  $14907$ |  $0.122$ |  $0.09$ |  $0.128$ |  $0.173$
Table 8: KG Embedding accuracy for standard retrieval task Technique |  Hits@1 |  Hits@3
---|---|---
TransE, IaK |  $38.64\pm 1.51$ |  $52.58\pm 1.93$
TransE – Adv, IaK |  $40.37\pm 0.87$ |  $53.1\pm 1.12$
RotatE, IaK |  $45.59\pm 0.52$ |  $56.55\pm 1.18$
RotatE – Adv, IaK |  $47.92\pm 1.15$ |  $61.3\pm 0.97$
ERMLP, IaK |  $53.16\pm 0.79$ |  $63.9\pm.63$
ERMLP -Adv, IaK |  $\mathbf{54.38\pm 0.94}$ |  $\mathbf{65.76\pm 0.5}$
Table 9: FVQA accuracy for standard retrieval task (IaK - Image as Knowledge,
Adv - self-adversarial negative sampling

The results in the next section in the table demonstrates that lexical and
distributional semantic features indeed hold complementary information to that
of KG embeddings. To remedy the trend of SiK ignoring lexical similarity,
roughly equal importance is assigned to the Jaccard and GLoVE similarity
metrics. Interestingly, the convex combination works best when each distance
metric is weighted roughly equally. Our experiments indicate that, the
majority of the correct answers are produced due to the similarity score
arising from SiK, but an equal weighting is required so as to nudge the
correct answer ahead of the incorrect ones.

Lastly, we observe that weighting the SiK metric more than 0.6 starts to yield
lesser and lesser benefits, and the performance monotonically decreases.

In both the incomplete KG settings (Table 7), we observe that pruning the fact
search space still improves accuracy over the standalone networks. But the
contribution of the textual similarity metrics becomes almost negligible
compared to its impact when required facts are present in the network.

## E. Performance of all KG Embedding algorithms

ERMLP has better mean-rank, while RotatE performs better in all other standard
metrics for KG embeddings. (Table 8). However, ERMLP-based embeddings are more
successful for FVQA (Table 9). Apparently ERMLP adds more capacity to the
embedding model, which also helps the downstream task of FVQA.

Using self-adversarial negative sampling is beneficial to all KG Embedding
algorithms. The FVQA accuracy improves by 1.67%, 2.47 %, and 1.25%
respectively for TransE, RotatE, and ERMLP. .