text:
\section{Introduction}\label{section:introduction}

	Factorization machines (FM)~\cite{rendle2010factorization,rendle2012factorization} are one of the
	most popular models to leverage the interactions between features. It models nested feature interactions
	via a factorized parametrization, and achieves success in many sparse predictive areas, such as recommender systems and click-through rate predictions \cite{juan2016field}. Recently there are many follow-up researches, such as high-order FMs \cite{blondel2016higher}, convex FMs \cite{blondel2015convex}, neural-network-based FMs \cite{he2017neural,guo2017deepfm}, locally linear FMs \cite{liu2017locally}, etc.

	Most of the existing approaches allocate a fixed rank of embedding vectors to each feature~\cite{liu2017locally,guo2017deepfm,Zheng2016,zheng2016neural,du2018collaborative,lauly2017document,jiang2017}. However, the frequencies of different features occurring in real-world datasets vary a lot. Fig. \ref{fig:feature-freq} shows the numbers of occurrences of different features in two public datasets, i.e. MovieLens\footnote{\url{https://grouplens.org/datasets/movielens}} Tag and Avazu\footnote{\url{https://www.kaggle.com/c/avazu-ctr-prediction/data}} respectively. It is shown that a large number of features scarsely occur in the dataset, while only a few features frequently occur. Fixing the rank of FMs may lead to overfitting problems for features with few occurrences, and underfitting problems for features with many occurrences.

	\begin{figure}
		\centering
		\includegraphics[width=0.8\linewidth]{feature-freq.eps}
				\vspace{-6mm}
		\caption{Occurrences of different features in (a) ML Tag; (b) Avazu. Example: in ML Tag, more than 40,000 features only occur once or twice, while less than 5,000 features occur more than 128 times.}
		\label{fig:feature-freq}
				\vspace{-5mm}
	\end{figure}

	There are also researches allocating with different ranks to each feature\cite{li2016difacto,li2017mixture,juan2016field}. However, training and storing multiple embeddings lead to unaffordable computational burden, and the large number of parameters may even aggravate the overfitting problem \cite{li2017mixture}. To this end, this paper proposes a Rank-Aware FM (RaFM) model, i.e., to maintain embedding vectors with different ranks for each feature, which makes it possible to compute each pairwise interaction via proper ranks of embedding vectors. A key contribution of this paper is to prove that {\bf although RaFM maintains multiple embeddings with different ranks for each feature, it can be stored, evaluated, and trained as efficiently as, or even more efficiently than a single FM with a fixed rank}.

	Specifically, we analyze the time and space complexity of RaFM, and show that there are many inactive factors which need not be stored and evaluated. Therefore, both the computational time and the storage can be significantly reduced, and the entire computational burden can be even smaller than that of a single FM under some reasonable conditions. Furthermore,  we provide an algorithm to train all embedding vectors of RaFM in one concise model where the inactive factors will not be stored and trained, and then prove the convergence rate and the performance bound of the training algorithm. Thus, the computational burden of the training process can also be effectively reduced. Experiments show the effectiveness of RaFM in both public datasets and datasets of industrial applications. The proposed RaFM model improves the performance of FMs while incurring a comparable or even less computational burden, therefore also has attractive potential in industrial applications.

		\vspace{-1mm}
	\section{Problem Formulation} \label{section:efm}
		\vspace{-1mm}
	\subsection{General Interaction Form of FMs}
	Here we provide a general interaction form of the FM model:
	\begin{equation} \label{eq:g-fm}
	\hat{y} = \sum_{i,j\in\mathcal{F},i<j}\left<\mathcal{V}_i,\mathcal{V}_j\right>x_ix_j + \sum_iw_ix_i + bias
	\end{equation}
	where $\mathcal{F}$ is the index set of features, $x_i$ is the value of the $i$-th feature, $w_i$ is the weight of the $i$-th feature in the linear part, and $bias$ is the bias of the model. $\mathcal{V}_i$ is the embedding of the $i$-th feature, describing the characteristics of this feature when interacting with other features. $\left<\mathcal{V}_i,\mathcal{V}_j\right>$ represents the bi-interaction between the $i$-th feature and the $j$-th feature.

	Clearly, the computation of the bi-interaction $\left<\mathcal{V}_i,\mathcal{V}_j\right>$ highly depends on the formulations of the embedding term $\mathcal{V}_i$. In the original FM model, $\mathcal{V}_i$ is a vector of a fixed rank, and $\left<\mathcal{V}_i,\mathcal{V}_j\right>$ is the dot product. Specifically, assume we have $m$ FMs, the rank of the $k$-th of which is $D_k$, then we have
	\begin{equation} \label{eq:fm}
	\left<\mathcal{V}_i,\mathcal{V}_j\right>_{FM_k} = \bm{v}_i^{(k)}\cdot\bm{v}_j^{(k)}=\sum_{f=1}^{D_k}v_{i,f}^{(k)}v_{j,f}^{(k)}
	\end{equation}
	where $\bm{v}_i^{(k)}$ is the embedding with dimension $D_k$, and $v_{i,f}^{(k)}$ is the $f$-th coordinate of $\bm{v}_i^{(k)}$. We assume the $m$ FMs are ordered such that $D_1\leq D_2 \leq \cdots \leq D_m$. Let $D = D_m$. We use $\bm{v}^{(k)}$ to represent the parameter set $\{\bm{v}_i^{(k)}:i\in\mathcal{F}\}$.

	According to Fig. \ref{fig:feature-freq}, the frequencies of different features occurring in real-world datasets vary a lot, hence fixed rank FMs may have unsatisfying performance on these datasets. Specifically, a certain embedding $\mathcal{V}_i$ will be trained only when $x_i$ are both nonzero. Therefore in the $k$-th FM, the embedding $\mathcal{V}_i = \bm{v}_i^{(k)}$ will suffer from underfitting if the $i$-th feature frequently occurs, and from overfitting if the feature scarsely occurs, as shown in Fig. \ref{fig:efm-scheme}(a)(b).

	\subsection{RaFM: Rank-Aware Factorization Machines}
	From the abovementioned discussions, it is beneficial to allocate different ranks of embedding vectors to different features.
	In this paper, we allocate multiple embedding vectors to each feature in RaFM, i.e.,
	\begin{equation} \label{eq:efm}
	\mathcal{V}_i = \left\{\bm{v}_i^{(1)},\bm{v}_i^{(2)},\cdots, \bm{v}_i^{(k_i)}\right\}
	\end{equation}
	where the rank of the $k$-th vector is $D_k$. The value $k_i$ means that the maximum rank of the embedding vectors is $D_{k_i}$. $k_i$ can be interpreted as: if $k>k_i$, the rank of $\bm{v}_i^{(k)}$ will be too large compared to the occurrences of the $i$-th feature, which will lead to the overfitting problem. $k_i$ can be chosen according to the number of occurrences of the $i$-th feature, and in this paper, we regard $k_i$ as hyperparameters. Although some boosting
	methods~\cite{li2018boosting} might be used to select appropriate $k_i$, we leave it for future work.

	Here we emphasize that the multiple embeddings in $\mathcal{V}_i$ are not independent in the RaFM model. Intuitively speaking, $\bm{v}_i^{(1)}$ can be regarded as a ``projection'' of $\bm{v}_i^{(2)}$ from the $D_2$-dimensional space to the $D_1$-dimensional space. We will return to this point in Section \ref{section:train}, which provides an efficient training problem maintaining this property.

    The pairwise interaction can be computed as
	\begin{equation} \label{eq:assumption}
	\left<\mathcal{V}_i,\mathcal{V}_j\right>_{RaFM} = \bm{v}_i^{(k_{ij})}\cdot\bm{v}_j^{(k_{ij})}
	\end{equation}
	where
	\begin{equation}
	    k_{ij}=\min(k_i,k_j)
	\end{equation}
	which means the dimensionality to compute the pairwise interaction between the $i$-th and $j$-th features depends on the maximum common dimensionality of the embedding vectors of the $i$-th and the $j$-th feature. Therefore, the computation of $\left<\mathcal{V}_i,\mathcal{V}_j\right>$ achieves a good trade-off between overfitting problems and underfitting problems, which is the intuition why RaFM outperforms FM. Fig.~\ref{fig:efm-scheme} also illustrates the idea of RaFM.

	\begin{figure}[t]
	    \centering
	    \includegraphics[width=\columnwidth]{efm-scheme.eps}
	    \vspace{-5mm}
	    \caption{The intuition of RaFM. (a) FM with a high dimension; (b) FM with a low dimension; (c) RaFM}
	    \label{fig:efm-scheme}
	    \vspace{-5mm}
	\end{figure}

	A key challenge of RaFM is the computational burden when storing, evaluating, and training RaFM:
	\begin{enumerate}
		\item It is well-known that FM can be evaluated efficiently in $O(D\left|\mathcal{F}\right|)$. However, the straight computation of RaFM, i.e. \eqref{eq:g-fm}\eqref{eq:assumption}, is $O(D\left|\mathcal{F}\right|^2)$, which is not satifying.
		\item To train the RaFM, we need to train multiple embedding vectors for a feature, which incurs a large computational burden and storage consumption.
	\end{enumerate}

	We separate the discussions into two sections: Section \ref{section:complexity} shows that RaFM can be stored and evaluated as efficient, or even more efficient than a single FM, whereas Section \ref{section:train} provides an efficient training algorithm.

	\color{black}
	\vspace{-2mm}
	\section{Model Complexity of RaFM}
	\label{section:complexity}
	This section analyzes the space and time complexity of RaFM. Trivial bounds of the space and time complexity are $O(\sum_{k=1}^mD_k\left|\mathcal{F}\right|)$ and $O(D\left|\mathcal{F}\right|^2)$ respectively. In this section, they will be significantly improved to be comparable or even less than a single FM under reasonable conditions.

	\vspace{-2mm}
	\subsection{Space Complexity} \label{section:space-complexity}
	Before discussing the complexity of RaFM, we introduce a class of feature sets, i.e.

	\begin{equation}
	\mathcal{F}_k = \{i\in\mathcal{F}:k_i\geq k\}, k=1,2,\cdots,m

	\end{equation}
	then we have $\mathcal{F}_1 \supset \mathcal{F}_2 \cdots \supset \mathcal{F}_m$. We have $\mathcal{F}=\mathcal{F}_1$ due to $k_i\geq 1$ by definition.

	Although the RaFM in Eq. \eqref{eq:efm} contains $m$ group of embeddings with different ranks, not all the parameters each group of embeddings will be used. Specifically, if we use $\mathcal{F}-\mathcal{F}_k$ to denote the set difference of $\mathcal{F}$ and $\mathcal{F}_k$, then for $i\in\mathcal{F}-\mathcal{F}_{k}$ and $l>k$, the factor $\bm{v}_i^{(l)}$ will never be used according to Eq. \eqref{eq:assumption}. These factors are called \textit{inactive factors}. In other words, only $\bm{v}^{(k)}_i,i\in\mathcal{F}_k$ need to be maintained, which are called \textit{active factors}. Therefore we have
	\begin{proposition} \label{prop:space-complexity}
		The space complexity of parameters in RaFM \eqref{eq:efm} is $O \left( \sum_{k=1}^mD_k\left|\mathcal{F}_k\right| \right) $.
	\end{proposition}

	\vspace{-2mm}
	\subsection{Time Complexity} \label{section:time-complexity}
	To derive the time complexity of RaFM, we introduce two notations, i.e. $\mathcal{A}_{l,k}$ and $\mathcal{B}_{l,k}$. Specifically,
	\begin{equation} \label{eq:a-l-k}
	\begin{split}
	\mathcal{A}_{l,k} &= \sum_{i,j\in\mathcal{F}_k,i< j}\bm{v}_i^{(l)}\cdot\bm{v}_j^{(l)}x_ix_j \\ &= \frac{1}{2}\left(\left\|\sum_{i\in\mathcal{F}_k}\bm{v}_i^{(l)}x_i\right\|_2^2-\sum_{i\in\mathcal{F}_k}\left\|\bm{v}_i^{(l)}x_i\right\|_2^2\right)
	\end{split}
	\end{equation}
	And when $l\leq k$, $\mathcal{B}_{l,k}$ is defined as
	\begin{equation}
	\mathcal{B}_{l,k} = \sum_{i< j}\bm{v}_i^{(k_{ij}|_{[l,k]})}\cdot\bm{v}_j^{(k_{ij}|_{[l,k]})}x_ix_j
	\end{equation}
	where $k_{ij}|_{[l,k]}=\max[l,\min(k,k_{ij})]$.

	$\mathcal{A}_{l,k}$ and $\mathcal{B}_{l,k}$ are introduced in order to transform the original RaFM in Eq.~\eqref{eq:g-fm}\eqref{eq:assumption} to a computationally efficient form. Actually, the following properties are obvious:
	\begin{proposition} \label{prop:a-b-simple}
	We have the following properties regarding $\mathcal{A}_{l,k}$ and $\mathcal{B}_{l,k}$:
	\begin{enumerate}
		\item $\mathcal{A}_{k,1}$ and $\mathcal{B}_{k,k}$ both denote the $k$-th FM model in Eq.\eqref{eq:fm}.
		\item The RaFM model in Eq. \eqref{eq:g-fm}\eqref{eq:assumption} is $\mathcal{B}_{1,m}$;
		\item The computational complexity of $\mathcal{A}_{l,k}$ is $O(D_l\left|\mathcal{F}_k\right|)$ due to the second equality in Eq. \eqref{eq:a-l-k}.
	\end{enumerate}
	\end{proposition}
	The proof is omitted since these statements are obvious. According to Proposition \ref{prop:a-b-simple}, the time complexity of $\mathcal{A}_{l,k}$ is known, and all we need to do is to compute $\mathcal{B}_{l,k}$ according to $\mathcal{A}$. To achieve this, we provide the following theorem:
	\begin{theorem} \label{thm:a-b}
	$\mathcal{A}_{l,k}$ and $\mathcal{B}_{l,k}$ satisfy the following equality: $\mathcal{B}_{l,k+1} = \mathcal{B}_{l,k}-\mathcal{A}_{k,k+1}+\mathcal{A}_{k+1,k+1}$
	\end{theorem}
	\begin{proof}
	It is easy to show that

		\begin{equation}
		\begin{split}
		\mathcal{B}_{l,k+1}=\mathcal{B}_{l,k}&- \sum_{i< j,k_{ij}> k}\bm{v}_i^{(k)}\cdot\bm{v}_j^{(k)}x_ix_j\\
		&+\sum_{i< j,k_{ij}> k}\bm{v}_i^{(k+1)}\cdot\bm{v}_j^{(k+1)}x_ix_j
		\end{split}
		\end{equation}
		Moreover, according to \eqref{eq:assumption}, the feature set $\{i<j:k_{ij}>k\}$ can be rewritten as
		\begin{equation}
		\{i<j:k_{ij}>k\}=\{i<j:i,j\in\mathcal{F}_{k+1}\}
		\end{equation}
		Then we have the 4th property according to the definition of $\mathcal{A}_{k,k+1}$ and $\mathcal{A}_{k+1,k+1}$.
	\end{proof}

	\begin{corollary} \label{corollary:time}
	    Regarding the computational complexity of RaFM, we have
		\begin{enumerate}
		\item The time complexity of $\mathcal{B}_{l,k}$ is $O \left(D_l\left|\mathcal{F} \right|+ \sum_{p=l+1}^kD_p\left|\mathcal{F}_p\right| \right) $;
		\item The time complexity of the RaFM model \eqref{eq:efm}, i.e. $\mathcal{B}_{1,m}$, is $O \left( \sum_{k=1}^mD_k\left|\mathcal{F}_k\right| \right) $.
		\end{enumerate}
	\end{corollary}
	\begin{proof}
		We only prove the 1st statement, and the 2nd statement is the direct corollary of the 1st when $l=1,k=m$.

		We prove by induction. When $k=l$, the time complexity of $\mathcal{B}_{l,l}$ is $O\left(D_l\left|\mathcal{F}\right|\right)$. If the time complexity of $\mathcal{B}_{l,k}$ is $O \left(D_l\left|\mathcal{F} \right|+ \sum_{p=l+1}^kD_p\left|\mathcal{F}_p\right| \right) $, then the time complexity of $\mathcal{B}_{l,k+1}$ should be

		\begin{equation}
		\begin{split}
		&O \left(D_l\left|\mathcal{F} \right|+ \sum_{p=l+1}^kD_p\left|\mathcal{F}_p\right| \right)  + O\left(D_k\left|\mathcal{F}_{k+1}\right|\right) \\&+ O\left(D_{k+1}\left|\mathcal{F}_{k+1}\right|\right) = O \left(D_l\left|\mathcal{F} \right|+ \sum_{p=l+1}^{k+1}D_p\left|\mathcal{F}_p\right| \right)
		\end{split}
		\end{equation}
		where the fact $D_k\leq D_{k+1}$ is used.
	\end{proof}

	\begin{remark}
		Similar to FM, when the data is sparse, $\left|\mathcal{F}_k\right|$ should be replaced by $n(\mathcal{F}_k)$, which is the expected number of occurrences of $\mathcal{F}_k$ in a data sample. In such cases, the time complexity is in the sense of expectation.
	\end{remark}

	\subsection{Comparison with FM} \label{section:complexity-discussion}

	This section compares the complexity of RaFM with that of FM. When using a single FM as the predictor, we usually use a large rank to ensure the performance, and use regularization to avoid overfitting. Here we use the FM with rank $D_m$ for comparison, of which the space and time complexities are $O(D\left|\mathcal{F}\right|)$ and $O(Dn(\mathcal{F}))$ respectively.

	The space and time complexity of RaFM are similar to each other except that $\left|\mathcal{F}_k\right|$ should be replaced by $n(\mathcal{F}_k)$ in the time complexity, so we discuss them together. Generally, when $k$ increases, $D_k$ will increase and $\left|\mathcal{F}_k\right|$ will decrease. Table \ref{tab:complexity} provides the complexity under different speeds of $D_k$ increasing and $\left|\mathcal{F}_k\right|$ decreasing. It is shown that if $D_k$ increases and $\left|\mathcal{F}_k\right|$ decreases moderately (e.g. linearly), the complexity of RaFM will be large. However, if one or two of them vary rapidly (e.g. exponentially), the complexity of RaFM will be comparable or smaller than the FM model.

	\begin{table}

		\centering
		\begin{small}
			\caption{Complexity of RaFM under different conditions}
			\resizebox{\linewidth}{\height}{
				\begin{tabular}{ccc}
					\hline
					&$D_k=\Theta(\frac{k}{m}D)$&$D_k=\Theta(2^{k-m}D)$ \\
					\hline
					$\left|\mathcal{F}_k\right|=\Theta((1-\frac{k-1}{m})\left|\mathcal{F}\right|)$&$O(mD\left|\mathcal{F}\right|)$&$O(D\left|\mathcal{F}\right|)$\\
					\hline
					$\left|\mathcal{F}_k\right|=\Theta(2^{1-k}\left|\mathcal{F}\right|)$&$O(D\left|\mathcal{F}\right|)$&$O(\frac{m}{2^{m-1}}D\left|\mathcal{F}\right|)$\\
					\hline
				\end{tabular}
			}

			\label{tab:complexity}
		\end{small}
	\end{table}

	In practice, it is widely-accepted that $D_k$ varies rapidly when $k$ increases \cite{he2017neural,li2017mixture}. As indicated by Fig. \ref{fig:feature-freq}, $\left|\mathcal{F}_k\right|$ decreases rapidly when $k$ increases. In contrast, the speed of $n(\mathcal{F}_k)$ decreasing may not be as rapidly as that of $\left|\mathcal{F}_k\right|$, but is still likely to be superlinear. Therefore, in such conditions, \textit{RaFM will significantly reduce the space complexity of FM while incur a comparable or smaller time complexity.} This statement will also be validated by experiments in Section \ref{section:experiment-complexity}.

		\vspace{-2mm}
	\section{Efficient Learning of RaFM} \label{section:train}

	\begin{algorithm}
		\caption{Training the RaFM} \label{algo:learning}
		\begin{algorithmic}[1]
			\STATE Initialize all the parameters

			\WHILE{not convergent}

			\STATE Sample a data point $(\bm{x},y)$ randomly

			\FOR{$1\leq p<m$}
			\STATE \hspace{-4mm}$\left.\bm{v}^{(p)}\right|_{\mathcal{F}_{p+1}} \gets \left.\bm{v}^{(p)}\right|_{\mathcal{F}_{p+1}} - \rho_d\frac{\partial L(\mathcal{B}_{1,p},\mathcal{B}_{1,p+1})}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_{p+1}}}$

			\STATE \hspace{-4mm}$\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}} \gets \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}} - \rho_f\frac{\partial L(\mathcal{B}_{1,m}, y)}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}$
			\ENDFOR
			\STATE $\left.\bm{v}^{(m)}\right|_{\mathcal{F}_m} \gets \left.\bm{v}^{(m)}\right|_{\mathcal{F}_m} - \rho_f\frac{\partial L(\mathcal{B}_{1,m}, y)}{\partial \left.\bm{v}^{(m)}\right|_{\mathcal{F}_m}}$

			\ENDWHILE
		\end{algorithmic}
				\vspace{-1mm}
	\end{algorithm}

	This section provides a computationally efficient learning algorithm of RaFM, i.e. Algorithm \ref{algo:learning}, where the inactive factors need not be stored and trained. We first provide the objective function and the learning algorithm, then prove that the proposed algorithm is to train the upper bounds of all the $m$ FMs simultaneously.

	We emphasize that although the analysis in this section is somehow technical, the final algorithm, i.e., Algorithm \ref{algo:learning}, can be regarded as an extension to SGD methods, hence is easy to implement.

	\subsection{Constrained Optimization of RaFM}\label{section:train-obj}

	The goal of the training algorithm is to obtain the parameters in $\mathcal{B}_{1,m}$. According to Eq.~\eqref{eq:a-l-k} and Theorem ~\ref{thm:a-b}, the parameters are $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p},\forall 1\leq p\leq m$. In other words, $\left.\bm{v}^{(p)}\right|_{\mathcal{F}-\mathcal{F}_p},\forall 1\leq p\leq m$ are the inactive factors that need not be trained. In order to avoid the training of inactive factors, we provide the following bi-level optimization model:

	\begin{subequations} \label{eq:efm-train-opt}
		\begin{align}
		&\min \frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,m}, y) \label{eq:efm-train-opt-obj}\\
		\text{s.t.~} &\left.\bm{v}^{(p)}\right|_{ \mathcal{F}_{p+1}} = \arg\min \frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,p},\mathcal{B}_{1,p+1}),\forall 1\leq p < m \label{eq:efm-train-opt-constraint}
		\end{align}
	\end{subequations}
	where $L$ is the loss function, and $\left.\bm{v}^{(p)}\right|_{ \mathcal{F}_{p+1}}$ denotes the $\bm{v}_i^{(p)}$ where $i\in\mathcal{F}_{p+1}$.

	The variables in Eq. \eqref{eq:efm-train-opt} can be classified into two groups, i.e. free variables and dependent variables.  $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p - \mathcal{F}_{p+1}},\forall 1\leq p< m$ and $\left.\bm{v}^{(m)}\right|_{ \mathcal{F}_m}$ are free variables, while $\left.\bm{v}^{(p)}\right|_{ \mathcal{F}_{p+1}}, \forall 1\leq p<m$ are dependent variables since they are determined by $\left.\bm{v}^{(p+1)}\right|_{ \mathcal{F}_{p+1}}$ via the constraint \eqref{eq:efm-train-opt-constraint}. The basic idea of Eq. \eqref{eq:efm-train-opt} is to regard $\bm{v}_i$ in its highest dimensionality as free variables to be optimized, and to regard other lower-dimensionality counterparts as its ``projections'' in lower dimensions, which can be approximated by the constraint \eqref{eq:efm-train-opt-constraint}.
	Note that inactive factors $\left.\bm{v}^{(p)}\right|_{\mathcal{F}-\mathcal{F}_p},1\leq p \leq m$ does not exist in Eq. \eqref{eq:efm-train-opt}. Therefore, Eq. \eqref{eq:efm-train-opt} makes it possible to maintain the model size given by Proposition \ref{prop:space-complexity} in the training process.

		\vspace{-2mm}
	\subsection{Learning} \label{section:train-sgd}

	This subsection will show that Eq. \eqref{eq:efm-train-opt} can be efficiently trained. Due to \eqref{eq:efm-train-opt-constraint}, the dependent variables $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_{p+1}}$ can be obtained by taking the stochastic gradient descent (SGD) algorithm on the first term in $L(\mathcal{B}_{1,p},\mathcal{B}_{1,p+1})$. The major challenge is the estimation of the gradient direction of the free variables due to that the optimization problem \eqref{eq:efm-train-opt} is a multi-stage optimization problem. Taking $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$ for a certain $p$ as an example, the gradient with respect to $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$ should be

	\begin{equation} \label{eq:grad}
	\begin{split}
	grad= \frac{1}{N}\sum_{\bm{x}}&\left(\frac{\partial L(\mathcal{B}_{1,m},y)}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} \right. \\
	&\left.+ \frac{\partial L(\mathcal{B}_{1,m},y)}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}} \frac{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}\right)
	\end{split}
	\end{equation}
	where $\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p} / \partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$ is a $\left|\mathcal{F}_p\right|D_{p-1}\times (\left|\mathcal{F}_{p}\right|-\left|\mathcal{F}_{p+1}\right|)D_p$ matrix representing the relationship between the dependent variable $\left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}$ and the free variable $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$ given by the constraint \eqref{eq:efm-train-opt-constraint}. According to the theorem of implicit functions,

	\begin{equation} \label{eq:implicit}
	\begin{split}
	\frac{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}=& \left[\frac{1}{N}\sum_{\bm{x}}\frac{\partial^2 L(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})}{\partial \left(\left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}\right)^2}\right]^{-1} \\
	&
	\left[\frac{1}{N}\sum_{\bm{x}}\frac{\partial^2 L(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p} \partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}\right]
	\end{split}
	\end{equation}
	Apply Eq. \eqref{eq:implicit} to Eq. \eqref{eq:grad},

	\begin{equation} \label{eq:grad-derive}
	\begin{split}
	&grad = \frac{1}{N}\sum_{\bm{x}}\frac{\partial L(\mathcal{B}_{1,m},y)}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}\\ &+\frac{1}{N^2}\sum_{\bm{x,x'}} \frac{\partial L(\mathcal{B}_{1,m},y)}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}
	\bm{G}^{-1}
	\frac{\partial^2 L(\mathcal{B}'_{1,p-1},\mathcal{B}'_{1,p})}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p} \partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}
	\end{split}
	\end{equation}
	where $\bm{G} = \frac{1}{N}\sum_{\bm{x}}\left[\partial^2 L/\partial \left(\left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}\right)^2\right]$ is the first term in the right of \eqref{eq:implicit}, which is a $\left|\mathcal{F}_p\right|D_{p-1}\times \left|\mathcal{F}_p\right|D_{p-1}$ matrix. $\mathcal{B}'_{l,k}$ denotes the $\mathcal{B}_{l,k}$ of input vector $\bm{x}'$. By exchanging $\bm{x}$ and $\bm{x}'$ in the second term of the right of \eqref{eq:grad-derive}, and using one sample $\bm{x}$ to estimate the gradient, we have
		\vspace{-1mm}
	\begin{equation} \label{eq:grad-sgd}
	\begin{split}
	&\widehat{grad} = \frac{\partial L(\mathcal{B}_{1,m},y)}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} \\ &+\frac{1}{N}\sum_{\bm{x'}} \frac{\partial L(\mathcal{B}'_{1,m},y)}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}
	\bm{G}^{-1}
	\frac{\partial^2 L(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p} \partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}
	\end{split}
	\end{equation}

	\vspace{-1mm}
	In the right of Eq. \eqref{eq:grad-sgd}, the first term can be obtain by the chain rule, while the second term contains second order derivatives which are challenging to compute. However, we have the following theorem:
	\begin{theorem} \label{thm:sgd}
		The direction of $\widehat{grad}$ is parallel to its first term $\partial L(\mathcal{B}_{1,m},y)/\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$.
	\end{theorem}
		\vspace{-3mm}
	\begin{proof}
		See Section 1 in the supplementary material.
	\end{proof}
		\vspace{-3mm}

	In SGD, the direction of the gradient vector is more important than the length. Theorem \ref{thm:sgd} shows that we can use the first term in Eq. \eqref{eq:grad-sgd} to estimate the descent direction over free variables. The same discussion can be applied to $\left.\bm{v}^{(m)}\right|_{\mathcal{F}_m}$, therefore we can use Algorithm \ref{algo:learning} to learn Eq. \eqref{eq:efm-train-opt}, where $\rho_d$ and $\rho_f$ are the learning rates of dependent variables and free variables, respectively.

	Now we discuss the complexity of Algorithm \ref{algo:learning}. Note that in each step, only active factors are used and updated, which means the space complexity follows Proposition \ref{prop:space-complexity}. Moreover, we do not need to compute $\mathcal{B}_{1,p}$ seperately since the it is a part of $\mathcal{B}_{1,m}$. Therefore, the time complexity also follows Corollary \ref{corollary:time}. Therefore, as discussed in Section \ref{section:complexity-discussion}, training RaFM via Algorithm \ref{algo:learning} is as efficient as, or more efficient than training a single FM.

	Moreover, it can be proven that the proposed learning algorithm minimizes an upper bound of each FM with a single rank $D_k,1\leq k\leq m$. We put the proof in Section 2 of the supplementary material due to space constraints.

	\section{Related Work} \label{section:related}

	The most related researches on the combination of FMs with different ranks are DiFacto\cite{li2016difacto}, MRMA\cite{li2017mixture}, and FFM\cite{juan2016field}. We compare them with RaFM thoroughly in this section. There are many other researches to improve the performance of FMs by deep models, such as NFM\cite{he2017neural}, AFM\cite{xiao2017attentional}, DeepFM\cite{guo2017deepfm}, etc. The idea of RaFM is orthogonal to these researches. It is also an attractive direction to combine RaFM with these models, and we leave it for future work.
	\subsection{DiFacto}
		DiFacto also uses multiple ranks in one FM. However, for each feature, DiFacto only allocates an embedding vector with a single rank, while RaFM allocates multiple embeddings with different ranks. In DiFacto, the pairwise interaction between features with different ranks is obtained by simply truncating the embedding with a higher rank to a lower rank.
		In cases such as SVD of a complete matrix, such truncations are reasonable, since the best $k$-rank approximation is equivalent to the $k$-prefix of any $k+n$-rank approximation. However, in recommender systems where the training samples are highly sparse,
		such truncations usually lead to worse performances, as will be shown in Section \ref{section:experiment}. Therefore, DiFacto reduces the computational burden of FM by sacrificing the performance, while RaFM improves the performance of FM with a lower computational burden.

	\subsection{MRMA}
	MRMA is a matrix approximation model, of which the key idea is also to combine models with different ranks. The major difference is that it stores the entire models with different ranks, thus leading to a large computational burden and storage burden. Moreover, the large number of parameters may also cause severe overfitting problems, and this is why \cite{li2017mixture} provides the Iterated Conditional Modes (ICM) to train MRMA. In contrast, RaFM will significantly reduce the number of parameters by eliminating inactive factors, and will not be likely to suffer from overfitting problems.

	\subsection{FFM}
	RaFM is totally different from FFM, although they both use multiple embeddings for each feature. On the one hand, FFM uses different embeddings for interactions between different field-pairs, while the concept ``field'' never exists in RaFM. For problems without the concept of fields or problems with only 2 fields, FFM fails or degenerates to the original FM, while RaFM still works. On the other hand, different embeddings in FFM are independent, while embeddings in a lower rank can be regarded as the projection of embeddings in higher rank, which is guaranteed by the learning algorithm. This property largely reduces the computational burden and avoids the overfitting problem, while FFM suffers from the large computational burden.

	\begin{figure}
		\centering

		\includegraphics[width=0.9\columnwidth]{fm-vs-efm.eps}
				\vspace{-3mm}
		\caption{FM vs. RaFM in ML Tag}
		\vspace{-3mm}
		\label{fig:fm-vs-efm}
	\end{figure}

	\begin{table}

		\centering

		\caption{Performance and Complexity under Different Settings}

		\begin{tabular}{cccc}
			\hline
			&logloss&\#param & train time \\
			\hline
			FM($D$=512)&0.2538&46.40M&$1\times$ \\
			\hline
			RaFM($S_1$)&0.2405&17.89M&$0.43\times$ \\
			\hline
			RaFM($S_2$)&0.2416&9.63M&$0.17\times$ \\
			\hline
			RaFM($S_3$)&0.2387&9.23M&$0.24\times$ \\
			\hline
			RaFM($S_4$)&0.2391&17.75M&$1.35\times$\\
			\hline
		\end{tabular}
		\label{tab:complexity-comparison}

	\end{table}

	\vspace{-2mm}
	\section{Experiments} \label{section:experiment}
	This section provides the experiments of the proposed approach and other benchmarks in several datasets. In Experiment A, we test our approach on 7 public datasets while in Experiment B, we perform the RaFM approach on the news CTR data provided by Tencent to show the effectiveness of the proposed approach in industrial applications. The code of RaFM is available at \url{https://github.com/cxsmarkchan/RaFM}.
	\begin{table*}[t]

		\centering

		\caption{Results on Regression Tasks}

		\begin{tabular}{cccccccccc}
			\hline
			\hline
			&\multicolumn{3}{c}{ML 10M}&\multicolumn{3}{c}{ML 20M}&\multicolumn{3}{c}{AMovie} \\
			\cline{2-10}
			&square&\multirow{2}{*}{\#param}&train/test&square&\multirow{2}{*}{\#param}&train/test&square&\multirow{2}{*}{\#param}&train/test\\
			&loss&&time&loss&&time&loss&&time\\
			\hline
			\multirow{2}{*}{FM}&0.8016&\multirow{2}{*}{2.66M}&\multirow{2}{*}{$1\times$}&0.8002&\multirow{2}{*}{5.45M}&\multirow{2}{*}{$1\times$}&1.0203&\multirow{2}{*}{3.25M}&\multirow{2}{*}{$1\times$} \\
			&$\pm$0.0010&&&$\pm$0.0008&&&$\pm$0.0046&&\\
			\multirow{2}{*}{DiFacto}&0.7950&\multirow{2}{*}{1.79M}&$0.82\times$/&0.7948&\multirow{2}{*}{3.22M}&$0.70\times$/&1.0268&\multirow{2}{*}{1.76M}&$0.75\times$/\\
			&$\pm$0.0011&&$0.95\times$&$\pm$0.0005&&$0.80\times$&$\pm$0.0051&&$0.75\times$\\
			\multirow{2}{*}{MRMA}&0.7952&\multirow{2}{*}{4.11M}&$1.27\times$/&0.7855&\multirow{2}{*}{8.43M}&$1.19\times$/&1.0071&\multirow{2}{*}{5.02M}&$1.27\times$/\\
			&$\pm$0.0006&&$1.43\times$&$\pm$0.0011&&$1.38\times$&$\pm$0.0039&&$1.27\times$\\
			\multirow{2}{*}{RaFM}&\textbf{0.7870}&\multirow{2}{*}{1.57M}&$0.95\times$/&\textbf{0.7807}&\multirow{2}{*}{3.63M}&$0.74\times$/&\textbf{0.9986}&\multirow{2}{*}{1.76M}&$0.75\times$/\\
			&\textbf{$\pm$0.0008}&&$1.12\times$&\textbf{$\pm$0.0009}&&$0.85\times$&\textbf{$\pm$0.0035}&&$0.75\times$\\
			\hline
			\hline
		\end{tabular}

		\label{tab:result-regression}

	\end{table*}

	\begin{table*}[t]

		\centering

		\caption{Results on Classification Tasks}

		\begin{tabular}{ccccccccc}
			\hline
			\hline
			&\multicolumn{4}{c}{Frappe}&\multicolumn{4}{c}{ML Tag} \\
			\cline{2-9}
			&log loss&AUC&\#param&train/test time&log loss&AUC&\#param&train/test time\\
			\hline
			\multirow{2}{*}{FM}&0.1702&0.9771&\multirow{2}{*}{1.38M}&\multirow{2}{*}{$1\times$}&0.2538&0.9503&\multirow{2}{*}{46.40M}&\multirow{2}{*}{$1\times$} \\
			&$\pm$0.0023&$\pm$0.0008&&&$\pm$0.0009&$\pm$0.0006&& \\
			\multirow{2}{*}{DiFacto}&0.1711&0.9771&\multirow{2}{*}{0.61M}&$0.63\times$/&0.2529&0.9450&\multirow{2}{*}{16.97M}&$0.42\times$/\\
			&$\pm$0.0023&$\pm$0.0004&&$0.85\times$&$\pm$0.0007&$\pm$0.004&&$0.83\times$ \\
			\multirow{2}{*}{RaFM}&\textbf{0.1447}&\textbf{0.9811}&\multirow{2}{*}{0.71M}&$0.73\times$/&\textbf{0.2387}&\textbf{0.9526}&\multirow{2}{*}{9.23M}&$0.24\times$/\\
			&\textbf{$\pm$0.0015}&\textbf{$\pm$0.0002}&&$0.85\times$&\textbf{$\pm$0.0005}&\textbf{$\pm$0.0006}&&$0.71\times$ \\
			\hline
			\hline
			&\multicolumn{4}{c}{Avazu}&\multicolumn{4}{c}{Criteo} \\
			\cline{2-9}
			&log loss&AUC&\#param&train/test time&log loss&AUC&\#param&train/test time\\
			\hline
			\multirow{2}{*}{FM}&0.3817&0.7761&\multirow{2}{*}{18.81M}&\multirow{2}{*}{$1\times$}&0.4471&0.8030&\multirow{2}{*}{35.87M}&\multirow{2}{*}{$1\times$} \\
			&$\pm$0.0001&$\pm$0.0003&&&$\pm$0.0002&$\pm$0.0002&& \\
			\multirow{2}{*}{DiFacto}&0.3823&0.7778&\multirow{2}{*}{10.83M}&$0.82\times$/&0.4470&0.8030&\multirow{2}{*}{19.70M}&$0.63\times$/\\
			&$\pm$0.0003&$\pm$0.0003&&$1.79\times$&$\pm$0.0002&$\pm$0.0004&&$0.80\times$ \\
			\multirow{2}{*}{RaFM}&\textbf{0.3801}&\textbf{0.7826}&\multirow{2}{*}{10.17M}&$0.85\times$/&\textbf{0.4451}&\textbf{0.8060}&\multirow{2}{*}{20.88M}&$0.67\times$/\\
			&\textbf{$\pm$0.0002}&\textbf{$\pm$0.0003}&&$1.20\times$&\textbf{$\pm$0.0001}&\textbf{$\pm$0.0002}&&$0.84\times$ \\
			\hline
			\hline
		\end{tabular}

		\label{tab:result-classification}
				\vspace{-4mm}
	\end{table*}

	\subsection{Experiment A: Public Datasets}
	\subsubsection{Experiment Setup}

	We consider 3 datasets for regression tasks and 4 for classification tasks.	All these datasets are randomly split into train (80\%), validation (10\%), and test (10\%) sets. Datasets for regression tasks are the MovieLens 10M (ML 10M), 20M (ML 20M), and the Amazon movie review dataset\footnote{\url{http://jmcauley.ucsd.edu/data/amazon/}} (AMovie), respectively, of which the square loss is used as the performance criterion. Datasets for classification tasks are Frappe\footnote{\url{http://baltrunas.info/research-menu/frappe}}, Movielens Tag (ML Tag), Avazu, and Criteo\footnote{\url{http://labs.criteo.com/2014/02/kaggle-display-advertising-challenge-dataset/}}, respectively, of which the log loss and the area under curve (AUC) are used as the performance criteria.

	We use the standard FM \cite{rendle2010factorization} and Difacto \cite{li2016difacto} as baselines for all datasets, and MRMA as a baseline for datasets containing exactly two fields, i.e. ML 10M, ML 20M, and AMovie, respectively. We do not compare with deep models since
	the motivation of this work is to show that FMs with different ranks can be efficiently combined and trained while incurring less computational burden. However, we argue that RaFM is a flexible framework and
	deep FMs can be embedded. We adopt $L_2$ regularizations for each model, and search the $L_2$ coefficient from $\{1e^{-6},5e^{-6},1e^{-5},\dots,1e^{-1}\}$ on the validation set.
	We search the ranks from $\{32,64,128,256,512\}$ for each model, except for some discussions in Section \ref{section:experiment-complexity}, where we use more values.
	We compare the performance, the model size, the training time, and the test time. Since RaFM has more hyperparameters, to be fair, we tune $k_i$ by the following equation rather than grid search:

	\begin{equation}
	k_i = \arg\min_k \left|\log n_i -\log D_k\right|
	\end{equation}
	where $n_i$ is the number of occurrences of the $i$-th feature. This equation means choosing $k_i$ so that $D_k$ is the closest to $n_i$ in the sense of logarithm.
	Moreover, we use the same $L_2$ coefficient for all FM models in the RaFM, and search it from the same candidate set as baselines.

	\subsubsection{Advantages of RaFM over FM with Fixed Ranks}

	Fig. \ref{fig:fm-vs-efm} shows the comparison between FMs with different ranks and RaFM in the ML Tag dataset. The ranks of FMs range from 32 to 512, and the hyperparameters of RaFM are $m=2, D_1=32$ and $D_2=512$. The RaFM-low in Fig. \ref{fig:fm-vs-efm} represents the $\mathcal{B}_{1,1}$, i.e. the FM model with rank 32, but trained simultaneously with $\mathcal{B}_{1,2}$ by Eq. \eqref{eq:efm-train-opt-constraint}. It is shown that RaFM significantly outperforms all FMs. It is because that RaFM maintains 32 factors for most of the features with limited occurrences to avoid overfitting problems, and allocate 512 factors for features with enough occurrences to guarantee expressiveness. Moreover, RaFM-low achieves similar performance to FM with 32 factors, which means embeddings in RaFM has similar expressiveness of embeddings in FM with the same rank.

	\subsubsection{Performance and Complexity} \label{section:experiment-complexity}

	Table \ref{tab:complexity-comparison} shows the performance and complexity of RaFMs under different rank settings. We compare 4 sets of ranks, namely, $S_1 = \{32,512\}$, $S_2=\{32,128,512\}$, $S_3=\{32,64,128,256,512\}$, and $S_4=\{32,64,96,128,160,\cdots,480,512\}$. Therefore, ranks in $S_2,S_3$ varies exponentially, while ranks in $S_4$ varies arithmetically. RaFMs with these 4 sets achieves similar performances, all significantly better than FM with 512 factors, which is the best out of all FMs as shown in Fig. \ref{fig:fm-vs-efm}. RaFMs with $S_2,S_3$ have fewer parameters due to the expenentially increasing rank settings. RaFM with $S_4$ has a comparable number of parameters to $S_1$, but the train time is much longer. This comparison shows the impacts of the speed of rank increasing on the computational burden, which is consistent with what is discussed in Section \ref{section:complexity-discussion}.

	\subsubsection{Results and Discussion}

	As evidenced by Tables \ref{tab:result-regression} and \ref{tab:result-classification}, our algorithm significantly outperforms the baseline algorithms. For example, the relative improvements on square loss (log loss) criteria are $1\%\sim2\%$ in ML 10M, ML 20M
	and AMovie, $15\%$ on Frappe, $6\%$ on ML Tag, and 0.5\% on Avazu and Criteo. Empirically, all these improvements are regarded as significant in the researches
	on corresponding datasets. Taking Criteo as an example, RaFM reduces the logloss of FM by 0.002, while an improvement of $0.001$ in logloss is considered as practically significant \cite{wang2017deep}.

	Moreover, the complexity of RaFM is reduced compared to FMs. In fact, RaFM significantly reduces both the model size and the computational time. For example, the model size of RaFM is only 20\%$\sim$66\% of FM, and the training time is 24\%$\sim$95\% of FM.

	Although Difacto can also reduce the computational burden, it cannot guarantee the performance. The major reason is that Difacto assumes the low-dimensional counterpart of a high-dimensional feature can be obtained by parameter sharing. However, this assumption is not usually reasonable. In contrast, MRMA performs better than FM and DiFacto due to it combines models with different ranks. However, its model size and training time are significantly larger than RaFM, while its performance is a bit worse than that of RaFM due the overfitting problem caused by a large number of parameters.

	In summary, RaFM not only achieves a better performance, but also reduces the model size and computational time. Therefore, the proposed RaFM model also has an attractive potential in industrial applications.

	\subsection{Experiment B: Industrial Level Click-Through-Rate Dataset}
	\subsubsection{Experiment Setup}
	Here we perform an experiment on the news CTR data provided by Tencent in order to show the potential of RaFM in industrial applications. We use the records of 8 consecutive days, of which the first 7 days are used as the training dataset, the last day is used on the test dataset. The dataset contains 1.7 billion records and 120 millions features.

	We compare the proposed RaFM approach with LR, FM and DiFacto, and the performance standard is the AUC, which is consistent with the requirement of online predictions. For FM/DiFacto/RaFM, the dimensionality of factors are chosen from $\{1,2,4,8\}$. We use the FTRL algorithm to guarantee the sparsity of learned weights, and use distributed learning to accelerate the learning process.

	\subsubsection{Results}
	We show the comparisons of AUC and the model size in Fig.~\ref{fig:kuaibao}. We use the number of parameters of LR, which is 13.19M in our experiments, as the unit of the model size. The comparison of training time of these approaches is not provided here, because they are very similar (about 6 hours for training, and 30 minutes for testing in our experiments) due to the fact that the training timeis dominated by the communication time of distributed learning rather than the computational time.
	\begin{figure}
		\centering
		\includegraphics[width=\columnwidth]{kuaibao.eps}
		\caption{Comparisons of AUC and the model size on industrial level CTR dataset.}
		\label{fig:kuaibao}
	\end{figure}

	Since the number of records in the training dataset is sufficiently large, it is natural to hope that the AUC will continuously increase when the model size increases, and the AUCs in Fig.~\ref{fig:kuaibao} can be further improved if we allow a larger rank of factors. However, the model size to achieve such an improvement is the main issue, since a larger model size will undoubtedly bring a heavier burden to the parameter server. According to Fig.~\ref{fig:kuaibao}, RaFM increases the AUC by about 1\% compared to LR, while its model size is only 1.55 times that of LR. In comparison, FM needs 7 times the model size of LR to achieve a similar performance. In other words, the model size of RaFM is only 22\% that of FM to achieve a similar AUC, which means the proposed RaFM approach achieves a good trade-off between model size and performance, and has an attractive potential in industrial applications.

	\section{Conclusion and Future Work} \label{section:conclusion}

	This paper proposes an RaFM model which adopts pairwise interactions from embeddings with different ranks. RaFM can be stored and evaluated as efficiently as, or even more efficiently than FMs with fixed ranks. Moreover, we provide a learning algorithm for efficiently training all embeddings in one concise model, and prove that the training error of each FM is bounded from above.
	Experiments demonstrate that RaFM not only has better performance in regression and classification datasets whose different features have significantly varying frequencies of occurrence, but also reduces the computational burden of FMs.

	RaFM is a flexible framework, therefore an interesting direction in future study is to combine it with deep models in order to achieve better performances. Moreover, a more effective hyperparameter tuning approach is also an attractive research direction.

	\bibliographystyle{icml2019}

\section{Proof of Theorem 6}
		\begin{proof}
		Recall the estimated gradient:
		\begin{equation*
		\begin{split}
		\widehat{grad} = \frac{\partial L(\mathcal{B}_{1,m},y)}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} +\frac{1}{N}\sum_{\bm{x'}} \frac{\partial L(\mathcal{B}'_{1,m},y)}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}
		\bm{G}^{-1}
		\frac{\partial^2 L(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p} \partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}
		\end{split}
		\end{equation*}
		According to the chain rule and the fact that $\mathcal{B}_{1,p-1}$ does not contain $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$, we have
		\begin{equation} \label{eq:2nd-derivative}
		\begin{split}
		&\frac{\partial^2 L(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p} \partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} \\
		=& L_{12}(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p}) \left(\frac{\partial \mathcal{B}_{1,p-1}}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}\right)^{\top}\frac{\partial \mathcal{B}_{1,p}}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} \\
		&+L_{22}(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p}) \left(\frac{\partial \mathcal{B}_{1,p}}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}\right)^{\top}\frac{\partial \mathcal{B}_{1,p}}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} \\
		&+L_{2}(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p}) \frac{\partial^2 \mathcal{B}_{1,p}}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}\partial\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}
		\end{split}
		\end{equation}
		where $L_2$ means the partial derivative of $L$ with regard to its first value, while $L_{12}$ and $L_{22}$ are the second-order partial derivatives of $L$. Note that the last line of \eqref{eq:2nd-derivative} equals 0 because that each pairwise interaction in the RaFM will not contain vectors from different FMs. Therefore,
		\begin{equation*}
		\begin{split}
		\frac{\partial^2 L(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p} \partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}
		= \bm{H}\frac{\partial \mathcal{B}_{1,p}}{\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}
		\end{split}
		\end{equation*}
		where $\bm{H}$ is a $(\left|\mathcal{F}_p\right|D_{p-1})\times 1$ matrix:
		\begin{equation*}
		\bm{H}=L_{12}(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})\left(\frac{\partial \mathcal{B}_{1,p-1}}{\left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}\right)^{\top} + L_{22}(\mathcal{B}_{1,p-1},\mathcal{B}_{1,p})\left(\frac{\partial \mathcal{B}_{1,p}}{\left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}\right)^{\top}
		\end{equation*}
		Then we have
		\begin{equation*}
		\begin{split}
		\widehat{grad} =& L_1(\mathcal{B}_{1,m},y)\frac{\partial \mathcal{B}_{1,m}}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} \\
		&+\frac{1}{N}\sum_{\bm{x'}} L_1(\mathcal{B}'_{1,m},y)\frac{\partial \mathcal{B}'_{1,m}}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}
		\bm{G}^{-1}\bm{H}\frac{\partial \mathcal{B}_{1,p}}{\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}\\
		=& L_1(\mathcal{B}_{1,m},y)\frac{\partial \mathcal{B}_{1,m}}{\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}} + \lambda\frac{\partial \mathcal{B}_{1,p}}{\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}}
		\end{split}
		\end{equation*}
		where
		\begin{equation*}
		\lambda = \frac{1}{N}\sum_{\bm{x'}} L_1(\mathcal{B}'_{1,m},y)\frac{\partial \mathcal{B}'_{1,m}}{\partial \left.\bm{v}^{(p-1)}\right|_{\mathcal{F}_p}}
		\bm{G}^{-1}\bm{H}
		\end{equation*}
		Note that $\lambda$ is the multiplication of a $1\times \left|\mathcal{F}_p\right|D_{p-1}$ matrix, a $\left|\mathcal{F}_p\right|D_{p-1}\times \left|\mathcal{F}_p\right|D_{p-1}$ matrix, and a $\left|\mathcal{F}_p\right|D_{p-1}\times 1$ matrix, and thus is a scalar. Moreover, the derivative of $\mathcal{B}_{1,m}$ and $\mathcal{B}_{1,p}$ with respect to $\left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$ is the same. Therefore, the direction of $\widehat{grad}$ is parallel to that of $L_1(\mathcal{B}_{1,m},y)\left(\partial \mathcal{B}_{1,m}/\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}\right)$, i.e. $\partial L(\mathcal{B}_{1,m},y)/\partial \left.\bm{v}^{(p)}\right|_{\mathcal{F}_p-\mathcal{F}_{p+1}}$.
	\end{proof}

	\section{Performance Bound of the Learning Algorithm}
	\begin{theorem} \label{thm:bound}
		Assume there exist two nonnegative functions $d(\cdot)$ and $\Delta(\cdot,\cdot)$ such that $d$ is monotonically increasing, and for all $f_1(\cdot),f_2(\cdot)$ we have
		\begin{equation} \label{eq:triangle}
		\begin{split}
		d\left(\frac{1}{N}\sum_{\bm{x}}L(f_1(\bm{x}),y)\right) &\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(f_2(\bm{x}),y)\right) \\
		&+ d\left(\frac{1}{N}\sum_{\bm{x}}\Delta(f_1(\bm{x}),f_2(\bm{x}))\right)
		\end{split}
		\end{equation}
		then regarding the training error of the $k$-th FM model, i.e. $\mathcal{B}_{k,k}$, we have
		\begin{equation}
		\begin{split}

		d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{k,k}^*,y)\right)&\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,m}^*,y)\right)\\
		&+ \sum_{p=k}^{m-1}d\left(\frac{1}{N}\sum_{\bm{x}}\Delta(\mathcal{B}_{1,p}^*,\mathcal{B}_{1,p+1}^*)\right) \label{eq:upper-bound}
		\end{split}
		\end{equation}
		where $\mathcal{B}_{1,m}^*$ is the optimal $\mathcal{B}_{1,m}$, and $\mathcal{B}_{1,p}^*$ is defined in the same way.
	\end{theorem}

	\textbf{Remark}:
	In practice, $\Delta$ represents the error of expressing $f_2$ by $f_1$. Eq. \eqref{eq:triangle} is an extension to the triangle inequality, and can be applied to both regression tasks and classification tasks. In regression tasks, $L$ is the square loss, then we can set $d$ as the square root function and $\Delta=L$. In classification tasks, $L$ is the logarithm loss, then we can let $d$ be an identity function, and define $\Delta$ as
	\begin{equation}
	\Delta(f_1(\bm{x}),f_2(\bm{x})) = C_{\theta,\delta}\mathcal{D}_{KL}\left[f_1(\bm{x})\|f_2(\bm{x})\right] + \log \delta
	\end{equation}
	where $\delta>1$, $C_{\theta,\delta} = \frac{\log \delta}{\theta\log\delta + (1-\theta)\log\frac{1-\theta}{1-\theta/\delta}}$, and $\theta=\min_{\bm{x}}\left[yf_2(\bm{x})+ (1-y)(1-f_2(\bm{x}))\right]$. $\mathcal{D}_{KL}$ is the KL divergence of two bimonial variables. The readers can refer to Section 3 in the supplementary material for the proof of Eq.  \eqref{eq:triangle} for logarithm loss.

	In order to prove Theorem \ref{thm:bound}, we first provide the following lemma:
	\begin{lemma}
		The following inequalities hold
		\begin{equation} \label{eq:model-capacity}

	  d\left(\frac{1}{N}\sum_{\bm{x}}l(\mathcal{B}_{l,k}^*,y)\right) \leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{l-1,k}^*,y)\right)
		\end{equation}
	\end{lemma}
	\begin{proof}
	Note that we have $\mathcal{B}_{l,k}=\mathcal{B}_{l-1,k}$ provided that
	\begin{equation*}
	\bm{v}_i^{(l)} =
	\begin{bmatrix}
	\bm{0}_{D_{l}-D_{l-1}} \\
	\bm{v}_i^{(l-1)}
	\end{bmatrix}
	, \forall i \in \mathcal{F}_{l}
	\end{equation*}
	And such solution also satisfies the constraint (12) in the main body of the paper. Therefore $\mathcal{B}_{l-1,k}$ is a submodel of $\mathcal{B}_{l,k}$, and thus the optimal training error of $\mathcal{B}_{l,k}$ is smaller than $\mathcal{B}_{l-1,k}$, and \eqref{eq:model-capacity} follows.
	\end{proof}

	\begin{proof}[Proof of Theorem \ref{thm:bound}]
		According to \eqref{eq:model-capacity} we have
		\begin{equation*}
		\begin{split}
		d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{k,k}^*,y)\right)&\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{k-1,k}^*,y)\right)\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{k-2,k}^*,y)\right)\\
		&\dots\\
		&\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,k}^*,y)\right)
		\end{split}
		\end{equation*}
		Moreover, according to \eqref{eq:triangle} we have
		\begin{equation*}
		\begin{split}
		d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,k}^*,y)\right)&\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,k+1}^*,y)\right) + d\left(\frac{1}{N}\sum_{\bm{x}}\Delta(\mathcal{B}_{1,k}^*,\mathcal{B}_{1,k+1}^*)\right)\\
		&\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,k+2}^*,y)\right) + \sum_{p=k}^{k+1}d\left(\frac{1}{N}\sum_{\bm{x}}\Delta(\mathcal{B}_{1,p}^*,\mathcal{B}_{1,p+1}^*)\right)\\
		&\dots\\
		&\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,m}^*,y)\right) + \sum_{p=k}^{m-1}d\left(\frac{1}{N}\sum_{\bm{x}}\Delta(\mathcal{B}_{1,p}^*,\mathcal{B}_{1,p+1}^*)\right)
		\end{split}
		\end{equation*}

		Therefore we have
		\begin{equation*}
		d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{k,k}^*,y)\right)\leq d\left(\frac{1}{N}\sum_{\bm{x}}L(\mathcal{B}_{1,m}^*,y)\right) + \sum_{p=k}^{m-1}d\left(\frac{1}{N}\sum_{\bm{x}}\Delta(\mathcal{B}_{1,p}^*,\mathcal{B}_{1,p+1}^*)\right)
		\end{equation*}

	\end{proof}

	\section{Quasi-Triangle Inequality for Logarithmic Loss}
	The following proposition is an extension of the triangle inequality for log loss.
	\begin{proposition} \label{prop:triangle-logloss}
		Suppose $y\in\{0,1\}, 0< \hat{y}_1,\hat{y}_2< 1$, and define the log loss function $L(\hat{y}_i,y)$ and the KL divergence $\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2)$ as
		\begin{equation*}
		\begin{split}
		L(\hat{y}_i,y)&=-y\log\hat{y}_i-(1-y)\log(1-\hat{y}_i) \\
		\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2)&=\hat{y}_1\log\frac{\hat{y}_1}{\hat{y}_2}+(1-\hat{y}_1)\log\frac{1-\hat{y}_1}{1-\hat{y}_2}
		\end{split}
		\end{equation*}
		then $\forall \delta > 1,0<\theta\leq y\hat{y}_1 + (1-y)(1-\hat{y}_1)$, we have
		\begin{equation}
		L(\hat{y}_2,y)\leq L(\hat{y}_1,y)+C_{\theta,\delta}\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2)+\log\delta
		\end{equation}
		where
		\begin{equation}
		C_{\theta,\delta} = \frac{\log \delta}{\theta\log\delta + (1-\theta)\log\frac{1-\theta}{1-\theta/\delta}}
		\end{equation}
	\end{proposition}

	Before proving Proposition \ref{prop:triangle-logloss}, we first provide some lemmas.
	\begin{lemma} \label{lemma:monotonicity}
		$\forall \theta>0,\delta>1$, we have $C_{\theta,\delta}>0$, and $C_{\theta,\delta}$ monotonically decreases when $\theta$ increases.
	\end{lemma}
	\begin{proof}
		Consider $g(\theta)=1/C_{\theta,\delta}=\theta + \left[(1-\theta)\log\frac{1-\theta}{1-\theta/\delta}/\log\delta\right]$, then we have
		\begin{equation*}
		\begin{split}
		g'(\theta)\log\delta&=\log\delta - \log\frac{1-\theta}{1-\theta/\delta} - 1 + \frac{1}{\delta}\frac{1-\theta}{1-\theta/\delta} \\
		&=- \log\left(\frac{1}{\delta}\frac{1-\theta}{1-\theta/\delta}\right) +\left( \frac{1}{\delta}\frac{1-\theta}{1-\theta/\delta}-1\right) > 0
		\end{split}
		\end{equation*}
		here we use the fact that $\log x< (x-1)$ unless $x=1$. Due to that $\log\delta>0$, we have $g'(\theta)\geq 0$, thus $g(\theta)$ is an increasing function. Moreover we have
		\begin{equation*}
		g(\theta)> g(0) = 0
		\end{equation*}
		Therefore, $C_{\theta,\delta}=1/g(\theta)$ is a decreasing function  with respect to $\theta$, and $C_{\theta,\delta}>0$.
	\end{proof}
	\begin{lemma} \label{lemma:simplified}
		For $0<\hat{y}_1,\hat{y}_2<1$, we have
		\begin{equation} \label{eq:triangle-simplified}
		\log \frac{\hat{y}_1}{\hat{y}_2} \leq C_{\hat{y}_1,\delta}\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2) + \log \delta
		\end{equation}
	\end{lemma}
	\begin{proof}
		When $\hat{y}_1<\delta\hat{y}_2$, we have $\log (\hat{y}_1/\hat{y}_2) \leq \log \delta$, thus \eqref{eq:triangle-simplified} holds due to the nonnegativity of the KL divergence. Now we discuss the case when $\hat{y}_1\geq \delta\hat{y}_2$. Consider the ratio between $\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2)$ and $\log (\hat{y}_1/\hat{y}_2)$:
		\begin{equation*}
		\frac{\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2)}{\log (\hat{y}_1/\hat{y}_2)}=\hat{y}_1 + (1-\hat{y}_1)\frac{\log(1-\hat{y}_1) -\log(1-\hat{y}_2)}{\log \hat{y}_1-\log \hat{y}_2}=\hat{y}_1 + (1-\hat{y}_2)h(\hat{y}_1,\hat{y}_2)
		\end{equation*}
		where $h(\hat{y}_1,\hat{y}_2) = \log\frac{1-\hat{y}_1}{1-\hat{y}_2}/\log\frac{\hat{y}_1}{\hat{y}_2}$. It is easy to show that
		\begin{equation*}
		\frac{\partial h}{\partial \hat{y}_2} = -\frac{\mathcal{D}_{KL}(\hat{y}_2\|\hat{y}_1)}{(\log\hat{y}_1-\log\hat{y}_2)^2\hat{y}_2(1-\hat{y}_2)} \leq 0
		\end{equation*}
		Therefore according to $\hat{y}_1\geq \delta \hat{y}_2$, we have $h(\hat{y}_1,\hat{y}_2)\geq h(\hat{y}_1,\hat{y}_1/\delta)$, and
		\begin{equation*}
		\frac{\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2)}{\log (\hat{y}_1/\hat{y}_2)} \geq\hat{y}_1 + (1-\hat{y}_1)\frac{\log(1-\hat{y}_1) -\log(1-\hat{y}_1/\delta)}{\log \hat{y}_1-\log (\hat{y}_1/\delta)} = \frac{1}{C_{\hat{y}_1,\delta}}
		\end{equation*}
		Therefore \eqref{eq:triangle-simplified} also holds when $\hat{y}_1\geq\delta\hat{y}_2$.
	\end{proof}
	\begin{proof}[Proof of Proposition \ref{prop:triangle-logloss}]
		We first prove the case when $y=1$. In this case, we have $\theta \leq \hat{y}_1$, and
		\begin{equation*}
		\begin{split}
		L(\hat{y}_2,y)-L(\hat{y}_1,y) &= \log\frac{\hat{y}_1}{\hat{y}_2} \\
		&\leq C_{\hat{y}_1,\delta}\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2) + \log \delta \\
		&\leq C_{\theta,\delta}\mathcal{D}_{KL}(\hat{y}_1\|\hat{y}_2) + \log \delta
		\end{split}
		\end{equation*}
		where the first and second inequalities are according to Lemmas \ref{lemma:simplified} and \ref{lemma:monotonicity}. For $y=0$, we can let $y'=1-y,\hat{y}'_1=1-\hat{y}_1,$ and $\hat{y}'_2=1-\hat{y}_2$, and use the same discussion for $y',\hat{y}'_1$ and $\hat{y}'_2$.
	\end{proof}

\end{document}

redpajama_set_name: RedPajamaArXiv


text:
New strategies for controlling crystallisation
Start date: 1 December 2015
Funder: Engineering and Physical Sciences Research Council (EPSRC)
Value: £1,408,821
Primary investigator: Professor Fiona Meldrum
Co-investigators: Professor Hugo Christenson (School of Physics and Astronomy)
Crystallisation is a phenomenon that touches every person, each day of their lives. It lies at the heart of a vast range of fields in science and technology, including pharmaceuticals, healthcare, nanomaterials and foodstuffs, as well as environmental issues like weathering and carbon-capture. Only by building a fundamental understanding of crystal nucleation and growth can we hope to control these processes.
Indeed, there has recently been a leap in our understanding of nucleation and growth thanks to advances in analytical techniques, which have enabled the study of the nanoscale processes which govern crystallisation. We are addressing this challenge by developing strategies to design and produce crystals with defined polymorph, orientation, morphology and size.
Crystallisation expertise
Over the last five years, we have built expertise and collaborations to study crystallisation using techniques such as synchrotron powder XRD, high-resolution cryo-TEM, AFM, EXAFS and the surface force apparatus. This has enabled us to show, for example, that crystallisation from vapour often proceeds via liquid condensates in surface pores, which has important implications for ice formation in clouds and climate modelling.
Bio-inspired crystallisation
We are especially interested in bio-inspired crystallisation, where the remarkable materials that are biominerals provide inspiration for the design and formation of synthetic crystals under ambient conditions. Here, we have shown that in contrast to current theories which emphasise control using biomolecules, nature uses physical confinement as a major route to controlling crystallisation.
We have also used bio-inspired strategies to produce "artificial biominerals" that have mechanical properties equivalent to their biogenic counterparts. The flexible resources available within this Platform Grant will be used to underpin our existing research portfolio and to explore new ideas and approaches to understanding and controlling crystallisation.
Attainment of this ambitious goal requires a strategy that includes longer-term, higher-risk research. Particular emphasis will be placed on the use of the physical environment - confinement and surface topography - to control crystallisation.
As examples, we will extend existing projects to investigate the combined effects of confinement and surface chemistry, and to study the crystallisation of amorphous minerals within carbon nanotubes. We will explore new directions including the control of protein crystallisation, and microfluidic devices for the study of crystallisation within droplets, with the expectation of building new research programmes based on the results.
Interdisciplinary research environment
The Platform Grant will also provide a superior research and training environment for PDRAs and students. Crystallisation is a truly interdisciplinary subject, and a particular strength of our group is its ability to take both chemical and physical perspectives on the subject.
This grant will hence be particularly valuable in providing a cohesive framework across the Schools of Physics and Chemistry at Leeds to help our researchers to work together as an integrated team. Staff funded by the grant will be assigned to projects rather than individual investigators, thereby enhancing the strategic nature of the platform support.
Furthermore, we will provide our PDRAs with enhanced career stability and continuity, and with superior professional development opportunities to help them to apply for competitive lectureships/fellowships or positions in industry.
Providing "added value", the Platform grant will be used to initiate/ strengthen collaborations with other internationally leading groups both within and outside the UK, and the PDRAs will gain enormously from research exchanges with other labs.
The flexibility of the grant ensures that we retain a critical mass of researchers in key areas (eg microfluidics, AFM) and that our large research group which is funded by many different grants remains integrated, responsive and dynamic.

redpajama_set_name: RedPajamaCommonCrawl


text:
Colorado Vote To Abolish Slavery
by toucana on October 16th, 2018, 11:51 am
Ummm - Didn't they do that already, about 150 years ago ? You might well ask.
https://edition.cnn.com/videos/us/2018/10/15/colorado-slavery-amendment-koaa-pkg-vpx.koaa
The answer is both yes and no. Colorado first became an independent territory in 1861 just as the Civil War was taking hold. The city of Colorado Springs was founded by General William Jackson Palmer who was a strong abolitionist. But Colorado didn't become a state until 1876 when President Ulysses Grant signed proclamation 230 admitting Colorado to the Union as the 38th state. It became known as the 'Centennial State' because it became a state exactly 100 years after the signing of the US Declaration of Independence in 1776.
The problem was that when Colorado drafted its new state constitution, like many other new states, it borrowed the text of the existing 13th Amendment from the Federal constitution (the amendment rapper Kanye West wants to abolish) which passed into law in 1865 and included a provision that was copied into the constitution of Colorado as follows:
Section 26 - Slavery prohibited. There shall never be in this state either slavery or involuntary servitude, except as a punishment for crime, whereof the party shall have been duly convicted.
The question of removing this qualification about "except as a punishment for crime" was first raised in a state ballot in the Colorado legislature in 2016, but attempts to remove the offending part of Section 26 were thwarted amidst concern over the possible impact of the change on the perceived legality of prisoner work programs in the Colorado state penitentiary system.
Two years later in 2018 Caitlin Trussel, a spokesperson of the 'Together Colorado' movement hopes a new ballot on the issue will succeed this time.
Last edited by toucana on October 16th, 2018, 12:13 pm, edited 1 time in total.
Re: Colorado Vote To Abolish Slavery
by TheVat on October 16th, 2018, 12:05 pm
The continued practice of slavery in the U.S. by means of the penal system has been well-documented. In the South especially, it was routine to convict African-Americans on trifling offenses, given them jail time, and put them on chain gangs. I think the chains have largely been phased out, but using prisoners for cheap labor is still going on. Some historians theorize that formerly harsh marijuana laws were first enacted when MJ use was predominantly in the black population - this created a new class of felony convictions for small infractions that allowed large scale incarceration of blacks, forced servitude, and disenfranchisement. Whatever the actual intent of those profiting from this system, it did succeed at giving some states good-sized labor pools for nasty jobs.


text:
Operations & Sustainability
ESG – Field Service Safety Critical to Operational Efficiency
Aaron McDaniel, Superintendent, Operations & Field Services
Echo Production is committed to creating a workplace that is safe, healthy and injury-free. Our employees and contractors are our most valuable assets, and their safety and health are our first priority. Safety is essential to all business functions and to ensure each of our employees and partners go home safe and sound at the end of every day. Some tenets of Echo's safety program include:
Stop Work Authority
At Echo Production every employee and contractor have the right, authority, responsibility and obligation to suspend any and all unsafe work actions or conditions through Stop Work Authority.
We follow an incident reporting protocol. All employees and contractors are expected to report all injuries, near misses, property damage, observations of unsafe work, security issues, environmental issues, and stop work incidents. We pro-actively track hazard identifications that could cause impacts on personnel, equipment or the environment and implement corrective actions.
Contractor Management Program
Echo's safety culture is connecting and communicating with our employees and contractors to continually enhance safety processes. Each company is screened for their safety programs and compliance and undergoes a risk assessment. The partnership continues through face-to-face communication and contractor safety meetings.
Our commitment to workplace safety is evident through all levels of the organization. We continue to refine our processes and metrics as we work towards our goal of zero injuries.
More to explorer...
Echo Production and Pureline Join Forces On Beneficial Reuse Plans
The partnership signals the first step in a three-phase process that Echo CFO Tompie Hall will result in a large beneficial reuse operation that includes multiple partners, including landowners and potentially other oil & gas operators and water midstream companies, as well as potential angel investors.
Matthew B. Myers Appointed to Echo Board of Directors
Echo Production, Inc., an integrated energy company, announced the appointment of Matthew B. Myers to the Board of Directors. He will be a member of the Audit Committee and Chairman of the ESG Committee.
"CleanOnGreen" Echo's Environmental, Safety, and Governance Journey
Echo Production Superintendent, Aaron McDaniel, knows the importance of the environment in contributing to good health for families, co-workers and communities.
"CleanOnGreen" Echo Production & PureLine Sign JV To Clean Oil Production Wastewater For Non-Edible Agriculture Production
It is Anne's objective to treat Echo's produced wastewater so that farmers could have an abundance of water for non-edible crops such as cotton. Anne went further, "This is a win/win not only for our industry and environment but has economic benefit for all parties including oil producers, farmers, communities and families".
A New Player Is Arriving In Dallas-Fort Worth And It's On The Hunt For Distressed Energy Deals
An independent Texas oil and gas company on the hunt for distressed energy assets will relocate its headquarters to Dallas-Fort Worth this year as it shops for deals in the $50 million to $100 million range.
Echo Production, Inc. Appoints Three Energy Experts as Outside Directors
Echo Production, Inc., an independent oil and gas company located in Graham, Texas, has appointed the following energy experts as outside Directors to the Company's Board of Directors.
© Copyright 2021 Echo Production Inc.


Retravision has sent a letter to all 180 stores explaining the next stages of the "orderly wind down" of the business and the transfer to new retail groups.
The letter, distributed yesterday by Retravision Western chief executive officer, Paul Holt, was titled "Orderly Wind Down of Retravision Support Services and Transfer of Business to New Service Providers".
"Following on from our letter dated 7 November 2012 and the subsequent update that you will either have received yesterday or today regarding the winding down of our business and the transfer of the ownership of the "Retravision" brand to the Narta narGroup from the 1 April 2013, the purpose of this short note is to provide you with further guidance as to how we believe the transition process will work in coming weeks and months.
"You will shortly receive a letter of introduction and an outline offer from a member within the Narta Group of Companies or from the Leading Edge Group. This letter will commence a process that will consider on how and when best to transition your business support needs across to your new service provider (subject to your agreement of course).
"We are focused on ensuring that your transition is managed as seamlessly as possible and, to this end, we will continue to provide pricing, advertising and IT support (the "Support Services") until at least the 31 March 2013 to all stores in the Retravision group as and where required.
"Importantly, and in order to ensure that we are able to meet our financial obligations throughout this transition period and remain solvent, all stores in the group will be required to pay the monthly Retravision Service fees and charges through to March 2013 on account of the Support Services, irrespective of the date that your store may transition to another group.
"In consideration of Retravision WA Ltd continuing to provide the Support Services, the Narta Group of companies and the Leading Edge Group have all agreed not to implement service fees to stores until 1 April 2013 in order to minimise the cost impost on stores whilst the transition takes place.
"The best thing you can do right now is to focus on preparing your store for a busy Christmas trading period and to await correspondence from a new service provider in the next week or two.
"Once that contact has been made, you can assess the offer that you are made and begin to determine a course of action with your new service provider that will suit the requirements of your business. Please feel free to obtain proper legal and/or financial advice before you accept any offer.
"Remaining patient on this issue for a little while longer will enable the new service providers to focus on their planning and communication tasks with a view to making all the operational changes required going into next year.
"There will be very little change across the group before Christmas as all of the new service providers are planning dealer road shows across the country to be able to meet with store owners and outline their plans in person before implementing changes.


text:
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">

    <!--

        Licensed to the Apache Software Foundation (ASF) under one or more
        contributor license agreements.  See the NOTICE file distributed with
        this work for additional information regarding copyright ownership.
        The ASF licenses this file to You under the Apache License, Version 2.0
        (the "License"); you may not use this file except in compliance with
        the License.  You may obtain a copy of the License at

           http://www.apache.org/licenses/LICENSE-2.0

        Unless required by applicable law or agreed to in writing, software
        distributed under the License is distributed on an "AS IS" BASIS,
        WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
        See the License for the specific language governing permissions and
        limitations under the License.
    -->

    <modelVersion>4.0.0</modelVersion>

    <parent>
        <groupId>org.apache.felix.karaf.shell</groupId>
        <artifactId>shell</artifactId>
        <version>1.4.1-SNAPSHOT</version>
    </parent>

    <groupId>org.apache.felix.karaf.shell</groupId>
    <artifactId>org.apache.felix.karaf.shell.log</artifactId>
    <packaging>bundle</packaging>
    <version>1.4.1-SNAPSHOT</version>
    <name>Apache Felix Karaf :: Shell Log Commands</name>

    <description>
        Provides the OSGi Log commands
    </description>

    <properties>
        <appendedResourcesDirectory>${basedir}/../../etc/appended-resources</appendedResourcesDirectory>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.apache.felix.karaf.shell</groupId>
            <artifactId>org.apache.felix.karaf.shell.console</artifactId>
        </dependency>

        <dependency>
            <groupId>org.apache.felix</groupId>
            <artifactId>org.osgi.core</artifactId>
            <scope>provided</scope>
        </dependency>

        <dependency>
            <groupId>org.apache.felix</groupId>
            <artifactId>org.osgi.compendium</artifactId>
            <scope>provided</scope>
        </dependency>

        <dependency>
            <groupId>org.ops4j.pax.logging</groupId>
            <artifactId>pax-logging-service</artifactId>
        </dependency>

        <dependency>
            <groupId>org.ops4j.pax.logging</groupId>
            <artifactId>pax-logging-api</artifactId>
            <scope>test</scope>
        </dependency>

    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.felix</groupId>
                <artifactId>maven-bundle-plugin</artifactId>
                <configuration>
                    <instructions>
                        <Bundle-SymbolicName>${artifactId}</Bundle-SymbolicName>
                        <Export-Package>${pom.artifactId}*;version=${project.version}</Export-Package>
                        <Import-Package>
                            !${pom.artifactId}*,
                            org.osgi.service.command,
                            org.apache.felix.gogo.commands,
                            org.apache.felix.karaf.shell.console,
                            *
                        </Import-Package>
                        <Private-Package>!*</Private-Package>
                        <_versionpolicy>${bnd.version.policy}</_versionpolicy>
                    </instructions>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>

redpajama_set_name: RedPajamaGithub


text:
Towson University Faculty Produce Film on Jim Crow-Era Baltimore
Filed in African-American History on March 7, 2018
A new documentary film about life in Jim Crow-era Baltimore has been produced by faculty members at Towson University in Maryland. The film – Voices of Baltimore: Life Under Segregation – recently was premiered on the Towson University campus.
The film presents oral histories of seven Baltimore residents who recount growing up in the city before the civil rights era. The producers are developing a curriculum guidebook to accompany the film that could be the basis for a course offered by the university's College of Education.
Gary Homana, an assistant professor of education and one of the producers/directors of the film, said that "the purpose of the work is to serve as a way for students to critically analyze the continuing struggles around issues of equity, power, privilege, segregation and social justice faced in schools and neighborhoods across the country."
A video about the film can be seen below.
Related: Towson University
While documentaries are important and valuable, readers and viewers who consider themselves historically and contemporaneously informed would do well to acknowledge that Jim Crow Baltimore (my beloved hometown) is alive and well in 2018.
Leave a Reply to Frances


1. Question: Why do I have tooth decay even though I frequently brush my teeth well?
- Unclean toothbrush: There are many bacteria attached around the neck. Bacteria as much as foods high in carbohydrates, sugar. Bacteria fermented carbohydrates in the diet of acid-producing bacillus. Acid dissolves mineral salts of tooth enamel, causing deep holes on teeth.
+ Enamel tooth is easy to dissolve in the acid due to the composition of minerals in the surface of enamel.
+ The enamel surface has many deep grooves, easy to store food but difficult to brush clean. Feed is a nutrient source of bacteria, causing acid to cause cavities in the grooves.
Therefore, brushing alone is not enough to keep teeth from becoming deeper.
2. Question: What should I do to prevent cavities?
- Use products containing fluoride to help enamel less dissolved in acid.
- During the period when the teeth are growing, take the child to the dental office or the dental office of the school dental program and, if indicated, the gum surface of the newly molten teeth will be filled with a sealant.
- Control sugar in foods and how to eat sugar by giving children tea or candy immediately after two meals, then clean the jaw. Fresh meals should be served to children.
- Periodontal examination every 6 months for young people. Older or more problematic teeth, gingivitis or periodontitis should visit 3 or 4 times a year.
3. Question: How many times should I brush my teeth a day?
- Brushing brighten up to avoid odors caused by bacteria fermented during sleep.
- Brush after each meal to avoid food odors and cleanse food debris.
- In addition, brushing is also a chance for fluoride in toothpaste to reduce tooth decay. According to S. Moss in 1998, brushing teeth with fluoride cream at least twice a day, saliva and fluoride protect teeth safely for snack eaters.


I'm not sure Paula Cole can ever disappoint me.
On Saturday night the great searcher of cowboys performed at the intimate White Eagle Hall in Jersey City, NJ.
A show filled with social and political undertones, Cole opened the concert with "Watch The Woman's Hands." This is a track off of her first album Harbinger. Laced with female empowerment, Cole sang this song with passion and fury through her phrasing and vocal tones, proving Cole does not have to use her vocal acrobatics to make her point.
Next, Cole went into a song off her latest album Ballads, "I Wish (I Knew How It Feels to Be Free)." Her likeness of this song can only be compared with the originator, Nina Simone. Yes, it was that good. Cole brought this song with a calm intensity in a society that desperately needs its message.
As the concert continued, Paula Cole sang many fan favorites, including her smash hit "Where Have All The Cowboys Gone" along with lesser known songs like "Carmen" and "Strong Beautiful Woman." Gratitude filled the room from Cole as she ended each song to applause and standing ovations.
I have never felt more "thanked" for loving an artist than how Cole made me feel during her show.
It was easy to see Cole's gratitude to her listeners when she called up a long time fan to join her on "Hush, Hush, Hush." The bridge of this song is sung by Peter Gabriel on her This Fire album, but tonight it was sung by a fan simply known as Vincent to the audience.
Although one must be warned, you never know what you are going to get when you see Paula Cole, but one thing is certain, you will have a profound experience. Whether it's Paula belting her anguish or calmly portraying her grief and frustration, you will always walk away with a message of hope and resilience wrapped in the only medium that portrays both simultaneously, music.


Read all the instructions and study the drawings before beginning work. (Most families have found it helpful first to read the instructions aloud and then to discuss problems and work assignments.) When digging earth that is too firm to shovel without first breaking it up, start picking (or breaking with a shovel) in a line across the center of the trench. Next, shovel out a narrow trench 6 or 8 in. deep all the way across the width of the trench. Then with pick or shovel break off row after row of earth all the way across the width of the trench, as illustrated.


"Termites: the illegal occupation of paradise is a powerful work of decolonial and documentary poetry about the illegal and brutal overthrow of the Hawaiian Kingdom by the "United States of Aggression." Interwoven is the story of the poet, who was born in Utah, educated in Spain, and employed in Hawaiʻi as an Exterminator. Throughout, Payne explores what it means to live on occupied land, to kill so easily, to be haunted by the ghosts of history, and to desire peace and beauty."
Zachary Payne is poet and translator who works as a Spanish and Applied Linguistics Professor on the island of Oahu. He learned Spanish at the age of 19 and in this new language he regained his lost creativity and Spanish became the language of his poetic voice. He received his Ph.D. from the Complutense University in Madrid, in Spanish and Latin American Thought. Zachary is a member of the Editorial Collective for Caja de Resistencia (cajaderesistencia.cc) a contemporary online poetry journal that specializes in Critical or Dissident poetry.Poetically he has published poetry chapbooks in Spanish in Peru and Spain and has published two full collections of poems in Spanish, the most recent being Robos, Setas & Sombras (Huerga y Fierro, 2014) and was included in the anthology: Disidentes: antología de poetas críticos españoles 1990-2014 (La oveja roja, 2015). Zach continues to write in Spanish but on occasions will write in English. Termites: the illegal occupation of paradise with Hesterglock imprint Prote(s)xt is his first poetry collection written entirely in English.


District 5: Buona Vista, Dover, Pasir Panjang, West Coast.
Kent Ridge Hill Residences is designed to offer plenty of features to the residents. There will be a swimming pool where residentscan relax and unwind aftera tiring day at work or on weekends. For those who are into fitness, there will be a gymnasium. There will be clubhouse and function rooms as well, where different events can be hosted. Residents of the residence will enjoy the luxury of rejuvenating and refreshing in spas and jacuzzi that this development will feature.
The site of this project is located in a prime area from where numerous parts of the city can be accessed easily. The area is generally quiet and offers a serene and calm environment making it ideal for families. This is one focal point which has helped it to get immense popularity.


So, real quick, wanted to pop in and fire off a bit about the series I just finished before it all drizzled out of my mind, so here's the piping hot and super fresh review for you on Future Diary (Mirai Nikki for the Japanese purists), the anime. Try not to burn your mouth as it comes out the oven, eh?
So, ever wonder what might happen if Death Note and Shin Megami Tensei: Devil Survivor had a mutant anime baby? No? Then you're likely sane. But that's ok, we're gonna answer that question anyway: you'd get Mirai Nikki. The story follows poor wallflower Yukiteru "Yuki" Amano as he is drawn into a survival game using a diary that lets him see the future around him. Yeah, that part is basically taken straight from Demon Survivor, practically down to an early line along the lines of "Let's Survive". Granted, the trope is older than that, but still.
Episode one starts off confusing and brutal, and follows through with a scene change where the real plot gets to become unraveled. I love some of the dialog between Yuki and Deus, and I could write whole papers on the implications of the early conversations on later episodes and the ending itself, but that's something for another time. Let's just say that it opens itself up to a number of possibilities, and at least one of which is likely FAR more disturbing than the actual ending of the story.
Anyway, after a very fast paced opening, the show crawls itself on for a bit and all in all kinda reminds me of a sprinter trying to do a marathon. One moment, it surges forth with an alacrity that has you pinned to the seat, but the next minute we become so dialog heavy (with good exposition, don't get me wrong) that you think about grabbing a soda to pass the time. Don't get me wrong, you do yourself and the show an injustice to miss most any line as it builds on itself to much, but wow, exposition ho! Honestly though, the expositional parts are no worse than When The Cry (Higurashi no Naku Koro ni) or Death Note as it gives you bits of information and clues to start putting everything together. After all, despite the very intense fight scenes, at its core, Mirai Nikki is a horror/thriller instead of an action show, and it pulls it off pretty well.
One thing to admire for it is the number of times that things look one way and turn out another. I won't spoil with examples, but yeah, show is great for setting an anticipation and then ripping your heart out, or giving a key role a sudden face heel turn when things look grim. Totally fitting to the characters once you start to learn their why too, which is another thing to really admire the writer for: these characters may be nuts (in most cases) but they're still three dimensional, and trapped in one of the most horrible games imaginable. It adds a good flavor of humanity even to the most otherwise irredeemable characters, which makes the "everything is a shade of grey" theme all the more fitting.
In the end, though, I think it loses a lot of itself when it starts worrying more about causality and less about the interaction between Yuki and Yuno, but maybe that's just me. There's several points at the end where the expected (and practically spelled out) next event doesn't happen, and I don't mean because of the Future Diary changing itself. An epilogue (longer than the 5-second-a-group treatment anyway) would have been nice, though the show was already at 26 episodes, so that may have been a pacing issue, or simply having 27+ episodes worth of stuff and only 26 episodes greenlit, so I'll overlook that, at least there was an attempt at closure outside the obvious.
All in all, while it has its moments that make you question your sanity, and the sanity of most, if not all, of the characters (or at least their reasoning ability, their sanity can hardly be questioned in most cases), it is definitely worth watching. Right now, the whole thing is free on Hulu (subtitled, if you care), so even more of a reason to scope it out. If I get some interest, maybe I'll do a much more spoileriffic review and discussion, so if you're interested in that, let me know.
So, if anyone was wondering: Shadowrun pretending to be D&D=boring, Shadowrun pretending to be Firefly=awesome.
Just got home from my weekly Shadowrun game, had a lot of fun mucking around with space time in an adaptation of one of the old modules. Not going to spoil anything, but lots of fun. Favorite joke of the day was when the BBEG who is pretending to be the good guy to the town (not a spoiler to the player, it gets revealed a long time ago to us) and he says something about how in the wild west, death and dealing with death is a normal thing. So I insinuated that I'd shoot him dead. I don't have nearly enough dice to pull it off, so didn't ICly try, but a lot of fun was had at the joke (I rolled for the hell of it, after saying it wasn't an actual attempt, got a critical glitch, which really cemented that it was not meant to be). We couldn't finish the current section of the module, so that'll have to wait until next game. Oh well, still fun.
Game next week is canceled due to low player turnout, so those of us who are able to go will be playing Shadowrun Crossfire, once I have a game under my belt, I'm sure I'll post up a bit more about that quirky little game.
Enjoying the crap out of Future Diary, but that's being earmarked for a review once I finish the series. In the meantime though, I give you this crack: https://www.youtube.com/watch?v=EqIX1tslWDw. Please forgive me for any brain meltage.
:( And it looks like my headphones are dead. Now to find my other pair. LOL They served me well for many years, but like all things, eventually they fade away and serve a function no longer. The funeral for my headphones will be held tomorrow and noon, nah, I'm just screwing with you of course, into the trash they go. Now I have to deal with these weird headphones that I got awhile ago because they work for the PS3, 360 and PC, but they're not nearly as user friendly as one would hope. But meh, you get what you pay for, I suppose. Really, you'd think someone would have made a true wireless (as in no fob or anything) headset for the PS3 and 360 combined, and yes, I know that one is Bluetooth and the other isn't, but still, wouldn't that just mean that pairing is theoretically easier anyway?
Wonder how long it'll take me to stop playing the song linked above. LOL It's crazy catching to me for some reason.
Anyway, thanks for reading and be careful of those yandere!


To combine queries from different data sources, the data source from the Primary Query must be compatible with the data sources from any other queries. Look to the chart below. Note that the arrows point in the direction of compatible data sources. For example, if you use the PO data source for your Primary Query, you can add a PO Manifest Item fact as a compatible query.
If you were to use the Manifest data source as your Primary Query, you could use any of the following data sources as secondary queries.
Similarly, if you were to use the SKU data source as your Primary Query, you could use any of the following data sources as secondary queries. As you can see, you can add as many queries as you like as long as each is compatible with the Primary Query.


text:
Big Scary Face Show rocks The Heath
Joe Tyler
ROYSTON Heath hosted its own mini Glastonbury on Sunday in the shape of the Big Scary Face Show.
Eight bands performed in an open air arena in aid of children's charity Unicef, with organiser Andy Blackford delighted with how it turned out.
"The Big Scary Face Show proved to be an outstanding success, despite the less-than-ideal weather," said Mr Blackford, who performed on the day with his own band Big in Litlington.
"The music was of a consistently high quality and we're already talking about next year's event."
The gig was given its unusual name in homage to a painting by Mr Blackford's son Tom, a professional artist.
Revellers queued up to have their faces painted in a scary style.
"I saw Tom's drawing, which is on display at Waterloo Station, and found it a really striking image," said Mr Blackford.
"I decided to use it as the theme for the day and want as many face-painters and scary looking characters to come along."
Grunge band The Royal Cartel, who have recently supported My Chemical Romance, opened the show before Mr Blackford's band took to the stage.
They were followed by former Kinks member Jim Rodford's band, The Rodford Files, Van Morrison's backing musician Paul Moran and Cambridge Folk Festival stalwart Adrian Nation.
Funk-rockers Fat Friday, 70s cult-band Spreadeagle and Tim Bryant finished off the proceedings.
Mr Blackford was keen to thanks all the bands, Sue Marchant from BBC Radio Cambridgeshire who compeered the event and Paul Nickson who provided the sound.


How often have you complained about having to use reading glasses or bifocals or whined about having to squint to see things in the distance? If you're ever looking for inspiration or if you want to get over feeling self-pity, there is no more appropriate area to look than the athletic world.
This past month, a high school senior named Jay Spencer from St. John Paul II High School won the Alabama State wrestling championship, though his vision is limited to just a corner of his left eye. Jack Olson, completely blind since the age of 12, was a long snapper for his high school football team and walked on to the University of Southern California football team and successfully made the snap for an extra point against Western Michigan.
Still complaining about not being able to find your glasses?
Reid Fellner is a junior at Acalanes High School. His vision began to fail when he was in the second grade and was ultimately diagnosed with a condition called Stargardt's Disease. It is characterized by macular degeneration resulting in a progressive loss of vision. Whereas normal vision is 20/20, Fellner's vision is about 20/400.
Fellner responds matter of factly to his condition: "My vision can be a problem but I try not to let it affect me. I use magnifiers to read and I am able to utilize the current technology which is improving all the time. I try to get through the best way."
Fellner comes from an athletic family. His sister Kate played lacrosse at UC Davis and his other sister Lucy is on the swim team at UC Santa Barbara so it was natural for Reid to play sports as well. Reid, who is also on the swim team at Acalanes went out for the wrestling team as a freshman: "I wanted to try something new. I fell in love with the sport and have been wrestling since then. I love that it is both an individual and team sport. As it turned out, it was also the easiest sport for me with my visual limitations."
There is one concession made to wrestlers that are limited visually. Both wrestlers must stay in contact with each other and if they separate, the match is stopped and then restarted. Cory Salmon has been a high school wrestling official since 1996 and has only refereed two matches in which one of the wrestlers was visually impaired and has had far more matches in which a deaf wrestler was involved. "We start the match with both wrestlers having contact with each other, palm to palm," explains Salmon. "There was never any issue with the other wrestlers. It's just a subtle difference for them in not being able to break away from each other. Besides that, there is no difference in how I refereed those matches."
Acalanes head coach Micah Canestaro has been working with Fellner since his freshman year: "Reid has come a long way. When he began, he was more timid being new to wrestling and the physicality of it but he has always been a fighter and his heart has really stood out. He has become more offensive and physical. He never stops once the whistle blows to start the match until the end. The tenacity and the fight that he's learned is something that can translate to anything he does in life. It's beautiful to see that in a wrestler. He has unbelievable character and is very mentally tough and strong. He's just a good person to be around and everyone recognizes and appreciates that on campus. He's an inspiration to us as coaches and to the other kids as well."
Fellner wrestles at 145 pounds and appreciates how he has grown with the sport: "I have improved and am more comfortable and aggressive when I wrestle. I have become more confident and quicker and have improved my reaction time. Wrestling has helped me with my overall conditioning, leadership skills, working with a team and my overall physical skills."
Freshman Dashiell Fabela sees Fellner as someone to look up to: "Reid is a very positive person. He's very kind and thoughtful whenever he speaks. He is always trying to do better and I've never seen him be negative in any way."
Fellner's father, John, admired the way he handled the decline in his vision and the wrestling environment: "Reid has always been positive. It was actually harder on us than it ever was for him. It's a unique sport and Reid's coaches, teammates and the wrestling community as a whole has shown Reid great respect. It's been a hard, huge learning curve. Reid loves being involved in everything. He just keeps going and trying."
The character and drive Reid has demonstrated on the wrestling mat has also carried over to his classwork at Acalanes. "I enjoy history and math though my favorite class is in leadership," says Fellner. "My other senses have improved. It's hard to see details on people's faces but I am able to recognize other people's voices.
The attitude that Fellner has brought to wrestling, he brings to his overall perspective of life: "I really enjoy meeting new people. I don't think about the difficulties with anything that I do. I'm constantly looking to improve."