text:
\section{Appendix: The Initial Dynamic Basis}
\label{init-dyn-bas-app}
We\index{76.1} shall indicate components of the initial basis by the subscript 0.
The initial dynamic basis is
\[ \B_0\ =\ \F_0,\G_0,\E_0\]
where
\begin{itemize}
\item $\F_0\ =\ \emptymap$
\item $\G_0\ =\ \emptymap$
\item $\E_0\ =\ \E_0'+\E_0''$
\end{itemize}
$\E_0'$ contains bindings of identifiers to the basic values BasVal and
basic exception names \BasExc; in fact
~$\E_0'\ =\ \SE_0',\VE_0',\EE_0'$~, where:
\begin{itemize}
\item $\SE_0'\ =\ \emptymap$
\item $\VE_0'\ =\ \{\id\mapsto\id\ ;\ \id\in$ BasVal$\}
                             \cup\{$\verb+:=+ $\mapsto$ \verb+:=+$\}$
\item $\EE_0'\ =\ \{\id\mapsto\id\ ;\ \id\in$ \BasExc$\}$
\end{itemize}
Note that $\VE_0'$ is the identity function on BasVal; this is because
we have chosen to denote these values by the names of variables
to which they are initially bound.
The semantics of these basic values (most of which are functions)
lies principally in their behaviour under APPLY, which we describe below.
On the other hand the semantics of \verb+:=+ is provided by a special
semantic rule, rule~\ref{assapp-dyn-rule}.
Similarly, $\EE_0'$ is the identity function on \BasExc, the set of
basic exception names, because we have also chosen
these names to be just those exception constructors to which they
are initially bound.
These exceptions are raised by APPLY as described below.

 $\E_0''$ contains initial variable bindings which, unlike BasVal, are
 definable in ML; it is the result of evaluating
 the following declaration in the basis $\F_0,\G_0,\E_0'$.  For convenience,
 we have also included all basic infix directives in this declaration.
 \begin{verbatim}
                infix  3  o
                infix  4  = <> < > <= >=
                infix  5  @
                infixr 5  ::
                infix  6  + - ^
                infix  7  div mod / *

                fun (F o G)x = F(G x)

                fun nil @ M = M
                  | (x::L) @ M = x::(L @ M)

                fun s ^ s' = implode((explode s) @ (explode s'))

                fun map F nil = nil
                  | map F (x::L) = (F x)::(map F L)

                fun rev nil = nil
                  | rev (x::L) = (rev L) @ [x]

                fun not true = false
                  | not false = true

                fun ! (ref x) = x
 \end{verbatim}

We now\index{77.1} describe the effect of APPLY upon each value
$b\in\BasVal$.  For special values, we shall normally use $i$, $r$,
$n$, $s$ to range over integers, reals, numbers (integer or real),
strings respectively.  We also take the liberty of abbreviating
``APPLY(\mbox{{\tt abs}}, $r$)'' to ``\mbox{{\tt abs}}($r$)'',
``APPLY({\tt mod}, $\{\verb+1+\mapsto i,\verb+2+\mapsto d\}$)'' to
``$i\ {\tt mod}\ d$'', etc. .
\begin{itemize}
\item \verb+~+($n$)~ returns the negation of $n$, or the
      packet ~[{\tt Neg}]~ if the result is out of range.
\item \mbox{{\tt abs}}($n$)~ returns the absolute value of $n$, or
      the packet ~[{\tt Abs}]~ if the result is out of range.
\item {\tt floor}($r$)~ returns the largest integer $i$ not greater than $r$;
      it returns the packet ~[{\tt Floor}]~ if $i$ is out of range.
\item {\tt real}($i$)~ returns the real value equal to $i$.
\item {\tt sqrt}($r$)~ returns the square root of $r$, or the packet
      ~[{\tt Sqrt}]~ if r is negative.
\item {\tt sin}($r$)~,  {\tt cos}($r$)~ return the result of the appropriate
      trigonometric functions.
\item {\tt arctan}($r$)~ returns the result of the appropriate
      trigonometric function in the range $\underline{+}\pi/2$.
\item {\tt exp}($r$)~, {\tt ln}($r$)~ return respectively the exponential
      and the natural logarithm of $r$, or an exception packet
      ~[{\tt Exp}]~ or ~[{\tt Ln}]~ if the result is out of range.
\item {\tt size}($s$)~ returns the number of characters in $s$.
\item {\tt chr}($i$)~ returns the character numbered $i$ (see Section~\ref{cr:speccon}) if $i$ is in the interval $[0,255]$, and the packet
      ~[{\tt Chr}]~ otherwise.
\item {\tt ord}($s$)~ returns\index{78.0} the number of the first character
      in $s$ (an integer in the interval $[0,255]$, see Section~\ref{cr:speccon}),
      or the packet ~[{\tt Ord}]~ if $s$ is empty.
\item {\tt explode}($s$)~ returns the list of characters (as single-character
      strings) of which $s$ consists.
\item {\tt implode}($L$)~ returns the string formed by concatenating all members
      of the list $L$ of strings.
\item The arithmetic\index{78.1} functions ~\verb+/+,\verb+*+,\verb-+-,\verb+-+~ all
      return the results of the usual
      arithmetic operations, or exception packets respectively
      [{\tt Quot}], [{\tt Prod}], [{\tt Sum}], [{\tt Diff}]
      if the result is undefined or out of range.
\item $i\ {\tt mod}\ d$~,~$i\ {\tt div}\ d$~ return integers $r,q$
      (remainder, quotient) determined by the equation $d\times q +r=i$,
      where either $0\leq r<d$ or $d<r\leq 0$.  Thus the remainder has the
      same sign as the divisor $d$. The packet [{\tt Mod}] or
      [{\tt Div}] is returned if $d=0$.
\item The order relations ~\verb+<+,\verb+>+,\verb+<=+,\verb+>=+~ return
      boolean values in accord with their usual meanings.
\item $v_1$\verb+ = +$v_2$~ returns {\TRUE} or {\FALSE} according as
      the values $v_1$ and $v_2$ are, or are not, identical.
      The type discipline (in particular, the fact that function types
      do not admit equality) ensures that equality is only ever applied
      to special values, nullary constructors, addresses, and values
      built out of such by record formation and constructor application.
%version 2:\item $v_1$\verb+ = +$v_2$~ returns the boolean value of $v_1=v_2$,
%      where the equality of values (=) is defined recursively as follows:
%      \begin{itemize}
%      \item If $v_1,v_2$ are constants (including nullary constructors) or
%      addresses, then $v_1=v_2$ iff $v_1$ and $v_2$ are identical.
%      \item $(\con_1,v_1)=(\con_2,v_2)$ iff $\con_1,\con_2$ are identical and
%            $v_1=v_2$.
%      \item $r_1=r_2$ (for records $r_1,r_2$) iff $\Dom r_1=\Dom r_2$ and, for
%            each $\lab\in\Dom r_1$, $r_1(\lab)=r_2(\lab)$.
%      \end{itemize}
%      The type discipline (in particular, the fact that function types
%      do not admit equality) makes it unnecessary to specify equality in
%      any other cases.
\item $v_1$\verb+ <> +$v_2$ returns the opposite boolean value to
      $v_1$\verb+ = +$v_2$.
\end{itemize}
It remains to define the effect of APPLY upon basic values concerned with
input/output; we therefore proceed to describe the ML input/output system.

Input/Output in ML uses the concept of a {\sl stream}. A stream is a finite or
infinite sequence of characters; if finite, it may or may not be terminated.
(It may be convenient to think of a special end-of-stream character
signifying termination, provided one realises that this ``character'' is
never treated as data).
Input streams -- or {\sl instreams} --
are of type ~\INSTREAM~ and will be denoted by ~$is$~;
output streams -- or {\sl outstreams} -- are of type ~\OUTSTREAM~ and will
be denoted by ~$os$~. Both these types of stream are {\sl abstract}, in the
sense that streams may only be manipulated by the functions provided in
BasVal.

Associated with an instream is a {\sl producer}, normally an I/O device or
file; similarly an outstream is associated with a {\sl consumer}.  After this
association has been established -- either initially or by the ~{\tt open\_in}~
or ~{\tt open\_out}~ function -- the stream acts as a vehicle for character
transmission from producer to program, or from program to consumer.
The association can be broken by the ~{\tt close\_in}~ or ~{\tt close\_out}~
function.\index{79.1}
A closed stream permits no further character transmission; a closed
instream is equivalent to one which is empty and terminated.

There\index{79.1.1} are two streams in BasVal:
\begin{itemize}
\item  {\tt std\_in}: an instream whose producer is the terminal.
\item  {\tt std\_out}: an outstream whose consumer is the terminal.
\end{itemize}
The other basic values concerned with Input/Output are all functional, and
the effect of APPLY upon each of them given below. We take the
liberty of abbreviating ``APPLY({\tt open\_in}, $s$)'' to
``{\tt open\_in}($s$)''
etc., and
we shall use ~$s$~ and ~$n$~ to range over strings and integers
respectively.
\begin{itemize}
\item  {\tt open\_in}($s$)~ returns a new instream ~$is$~, whose producer is
       the external file named ~$s$~. It returns exception packet
       \begin{quote}
       [$(${\tt Io},\verb+"Cannot open +$s$\verb+"+$)$]
       \end{quote}
       if file ~$s$~ does not exist or does not provide read access.
\item  {\tt open\_out}($s$)~ returns a new outstream ~$os$~, whose consumer is
       the
       external file named ~$s$~. If file $s$ is non-existent, it is taken to
       be initially empty.
\item  {\tt input}($is,n$)~ returns a string ~$s$~ containing the first $n$
       characters of ~$is$~, also removing them from ~$is$~.  If only $k<n$
       characters are available on ~$is$~, then
       \begin{itemize}
       \item If ~$is$~ is terminated after these $k$ characters, the
             returned string
            ~$s$~ contains them alone, and they are removed from ~$is$~.
       \item Otherwise no result is returned until the producer of ~$is$~
             either supplies $n$ characters or terminates the stream.
       \end{itemize}
\item  {\tt lookahead}($is$)~ returns a single-character string ~$s$~ containing
       the next character of ~$is$~, without removing it. If no character is
       available on ~$is$~ then
       \begin{itemize}
       \item If ~$is$~ is closed, the empty string is returned.
       \item Otherwise no result is returned until the producer of ~$is$~
             either supplies a character or closes the stream.
       \end{itemize}
\item  {\tt close\_in}($is$)~ empties and terminates the instream ~$is$~ .
\item  {\tt end\_of\_stream}($is$)~ returns {\TRUE} if
       ~{\tt lookahead}($is$)~ returns the empty string, {\FALSE} otherwise;
        it detects the end of the instream ~$is$~.
\item {\tt output}($os,s$)~ writes the characters of ~$s$~  to the outstream
       ~$os$~, unless ~$os$~ is closed, in which case it returns the exception
       packet
       \begin{quote}
       [$(${\tt Io},\verb+"Output stream is closed"+$)$]
       \end{quote}
\item  {\tt close\_out}($os$)~ terminates the outstream ~$os$~.\index{79.2}
\end{itemize}
%\end{document}

%              Constructors
%\newcommand{\FALSE}{\mbox{\tt false}}
%\newcommand{\TRUE}{\mbox{\tt true}}
%\newcommand{\NIL}{\mbox{\tt nil}}
%\newcommand{\REF}{\mbox{\tt ref}}
%\newcommand{\UNIT}{\mbox{\tt unit}}

%              Basic Values BasVal
%\newcommand{\STDIN}{\mbox{\tt std\_in}}
%\newcommand{\STDOUT}{\mbox{\tt std\_out}}


text:
% !TEX options=--shell-escape
\documentclass [12pt]{article}
\usepackage {amsmath}
\usepackage {amsthm}
\usepackage {amssymb}
\usepackage {graphicx}
\usepackage {float}
\usepackage {multirow}
\usepackage {xcolor}
\usepackage {algorithmic}
\usepackage [ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e} \usepackage {array}
\usepackage {booktabs}
\usepackage {url}
\usepackage {parskip}
\usepackage [margin=1in]{geometry}
\usepackage [T1]{fontenc}
\usepackage {cmbright}
\usepackage [many]{tcolorbox}
\usepackage [colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage {enumitem}
\usepackage {xparse}
\usepackage {verbatim}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{csquotes}
\usepackage[cache=false]{minted}
\usepackage{mdframed}
\usepackage{tikz}
\usetikzlibrary{shapes.symbols}
\newtheorem{theorem}{Theorem}

\DeclareTColorBox {Solution}{}{breakable, title={Solution}}
\DeclareTColorBox {Solution*}{}{breakable, title={Solution (provided)}}
\DeclareTColorBox {Instruction}{}{boxrule=0pt, boxsep=0pt, left=0.5em, right=0.5em, top=0.5em, bottom=0.5em, arc=0pt, toprule=1pt, bottomrule=1pt}
\DeclareDocumentCommand {\Expecting }{+m}{\textbf {[We are expecting:} #1\textbf {]}}
\DeclareDocumentCommand {\Points }{m}{\textbf {(#1 pt.)}}
\newcommand {\hint }[1]{\noindent {[\textbf {HINT:} \em #1 \em ]}} \newcommand {\pts }[1]{\textbf {(#1 pt.)}}

\begin{document}

{\LARGE \textbf {COMP 285 (NC A\&T, Spr `22)}\hfill \textbf {Weekly Quiz 1} }

\begin{Instruction}

\paragraph{Reporting Issues} If you find any issues with the solutions, reach out to Chi Wang (author) or Luis Perez (reviewer).

\end{Instruction}

\section{} Recall the definitions of big-Oh, big-Omega, and big-Theta. Based on these definitions, select all statements below which are true.

\begin{Solution}
The below are all trust statements.
\begin{enumerate}
    \item Big-Oh is an upper bound. That is, intuitively, $T(n) = O(f(n))$ means $T(n) \leq c f(n)$ for some $c$.
    \item Big-Theta provides both upper and lower bounds.
    \item Big-Omega is a lower bound.
\end{enumerate}

The above are by definition.
\end{Solution}

\section{} What is the running time of the following function:
$T(n) = 13 + 12nlog(n) + 3n^2$

\begin{Solution}
$\Theta(n^2)$ because $n^2$ is both upper and bower bounds. The other terms grow much more slowly, which means for large $n$, they do not impact the result much.
\end{Solution}

\section{} Which of the following is the correct English description of $f(n) = O(g(n))$?

\begin{Solution}
There is some $c > 0$ and some $n_0$, such that for all $n \geq n0$ we have $f (n) \leq c \cdot g(n)$.
\end{Solution}

\section{} Suppose that $f (n) = O(g(n))$. Which of the following is implied by this fact?

\begin{Solution}
$g(n) = \Omega(f(n))$. Intuitively, $f(n) = O(g(n))$ means that $f(n) \leq c g(n)$ for some $c$ and large enough $n$. This means that $g(n) \geq \frac{1}{c} f(n)$ for large enough $n$ (divide both sides by $c$), which fits the definition of $g(n) = \Omega(f(n))$.
\end{Solution}

\section{} What is the smallest exponent x such that $n^2 + n^3 - n = O(n^x)$

\begin{Solution}
3. Because the asymptotic upper bound is $n^3$
\end{Solution}

\section{} Is Merge Sort’s worst case runtime asymptotically faster than Insertion Sort’s worst case runtime?

\begin{Solution}
Yes. Merge Sort’s worst case runtime is $O(n \log n)$, and Insertion Sort’s worst case runtime is $O(n^2)$.
\end{Solution}

\section{} Which of the following describes $\frac{n(n+1)(n+2)}{6}$

\begin{Solution}

\begin{itemize}
    \item {$O(n^4)$:}  $\frac{n(n+1)(n+2)}{6} = \frac{n^3 + 3n^2 + 2n}{6}$ so the asymptotic upper bound should be $O(n^3)$. Since $O(n^4)$ grows faster than $O(n^3)$, it can be the upper bound.
    \item {$O(n^3)$:} It's the asymptotic upper bound.
    \item {$\Theta(n^3)$:} It's both the upper bound and the lower bound.
    \item {$\Omega(n^2))$:} Since $O(n^2)$ grows slower than $O(n^3)$, it can be the lower bound.
\end{itemize}

\end{Solution}

\section{}  Is Merge Sort faster than Insertion Sort on some arrays?

\begin{Solution}
Yes, Merge Sort’s worst case runtime is $O(n \log n)$, and Insertion Sort’s worst case runtime is $O(n^2)$.

In particular, Insertion Sort will take $\Theta(n^2)$ steps on an array thats sorted in reverse order, while merge sort will that $\Theta(n \log n)$ steps.
\end{Solution}

\section{} Is Merge Sort faster than Insertion Sort on all input arrays?

\begin{Solution}
No. Merge Sort’s best case runtime is$ O(n \log n)$, and Insertion Sort’s best case runtime is $O(n)$.

In particular, Insertion Sort will take $\Theta(n)$ steps on an array that's already sorted, while merge sort will take $\Theta(n \log n)$ steps.
\end{Solution}

\section{} The Merge operation takes two arrays A and B of size $n$ which are already sorted and outputs the union of the two in sorted order. What is the smallest bound on the runtime of the Merge algorithm?

\begin{Solution}
$O(n)$. The Merge operation needs to walk through every element in A and B.
\end{Solution}

\end{document}

ext: tex

max_stars_repo_name: facebookEIR/algorithms-course

max_issues_repo_name: facebookEIR/algorithms-course

max_forks_repo_name: facebookEIR/algorithms-course


text:
\section{Poisson problem}
This section includes several algorithms/kernels, results and analysis of those performances.
The performance of the kernel setups will be compared and they have been evaluated for $N = 2048$ and \texttt{max\_iter} = $1000$. The chosen parameters gives the refrence algorithm a runtime of $\approx1.5$ secound.

\noindent The main purpose of this section is to find the speedup for difference GPU implementations in reference of the best OpenMP (\texttt{jac\_cpu}) version from previous assignment. The environment variable which determines the wait policy of the threads has not been set to \texttt{OMP\_WAIT\_POLICY=active} is in the previous assignment. The OpenMP is evaluated with \texttt{OMP\_NUM\_THREADS=12}.
The achieved speedups are presented in table \ref{tab:speedup_pos}.

\noindent It has been chosen to validate the implementation of the difference GPU kernels by visualizing their estimates of $u(x,y)$ after the last iteration. This give a visual verfication of the kernel and source implementations. See plots in figure \ref{fig:apped_vis_pos} in the appendix.

\noindent The iterative process is controlled by the host and it uses \texttt{cudaDeviceSynchronize()} to make sure the work of the threads on the devices is done before incrementing the iteration. The iterative process \texttt{while(k < max\_iter)} which includes pointer switchs and new kernel calls is identical for all three GPU versions. Although the kernels are called by different
kernel launch parameters: \texttt{<<<grid,block>>>}.

\noindent The initialization of the boundary conditions in $u$ and $u\_old$, and of the heating source given by $f$ are done on the on the host. The and copied to the device by using the approiate cuda calls.
The I/O duration for transferring the initial matrices to the device and the duration of the transferring the estimate of $u$ back to host is included in the total compute time in order to make a fair comparison to the \texttt{jac\_cpu} function.

\subsection{Sequential GPU Jacobi}
The kernel used in the Sequential Poisson is provided in algorithm \ref{alg:jac_v1}.

\noindent \texttt{jac\_gpu1} is called by the following launch parameters \texttt{<<<1,1>>>jac\_gpu1}. This ensures it only enables one block with one thread. See algo. \ref{alg:app_jac_v1} for the complete source code.

\lstinputlisting[label={alg:jac_v1},caption={Algo. \texttt{jac\_gpu1}.},style=CStyle, linerange={23-33}]{code_3/jac_gpu1.cu}.

\subsection{Naive GPU Jacobi}
The Naive Poisson kernel have been implemented by using one thread per grid point which enables the high parallelism of the device. The implementation uses global memory and line 2-3 shows how the upadted element is determined. The kernel is presented in algo. \ref{alg:jac_v2}.

\lstinputlisting[label={alg:jac_v2},caption={Algo. \texttt{jac\_gpu2}.},style=CStyle, linerange={24-31}]{code_3/jac_gpu2.cu}.

\noindent The kernel is called by following launch paramters: \texttt{<<<dim\_grid,dim\_block>>>jac\_gpu2} which creates a 2D thread blocks. The 2D grid and block size are given by:
\begin{align}
dim3 \quad &dim\_grid \left(  \frac { N+bs-1 }{ bs },\frac { N+bs-1 }{ bs } \right)  \\
dim3\quad  &dim\_block\left(bs, bs \right)
\end{align}
where $bs=16$ is the number of threads in each block.

\subsubsection{\texttt{nvvp}}
The \texttt{nvvp} analyzing tool tells that the \texttt{jac\_gpu2()} has a "Low Compute Utilization" $\approx 16\%$, presented in figure \ref{fig:computebound}. This is as expected, as all memory is fetched globally in the implementation, and as only few floating point operations are performed every time memory is retrieved. Due to this difficulty, the Jacobi method is memory bound. This could be optimized by splitting up the copying, such that the algorithm could copy and compute simultaneously and hereby reduce the computation time. By using more specialized analysis tools within \texttt{nvvp}, a bandwidth limitation is proposed. This limits also supports the claim that the problem is memory bound.  The solution to the Poisson problem using this algorithm is presented in \ref{fig:jac_gpu2} in the appendix.\\

\begin{figure}[H]
\centering
\includegraphics[width=1\textwidth]{data_3/pos_sceenshots/computebound.png}
\caption{The \texttt{nvvp} analysis of \texttt{jac\_gpu2()}. This reports that the algorithm is memory bound as the percentage of utilized memory is much bigger than the utilization of the computation.}
\label{fig:computebound}
\end{figure}

%Vi bruger lang tid på at copiere data, dette kunne blive forbredet hvis man kun kopierede lidt over af gangen . low compute utilization (16\%) pga lang tid om at kopiere. N = 2048, 1000 iterationer. low kernel concurrency.

\subsection{Multiple GPU Jacobi}
The third version the Jacobi version use multiply (two) GPUs. The problem is hereby split equally between the devices. It has been chosen to create a horizontal split.

\noindent The kernels, \texttt{jac\_gpu3}, used to solve the Poisson problem is presented in algorithm \ref{alg:jac_v3_alg}.

\noindent The \texttt{cudaDeviceEnablePeerAccess()} method is used to solve the boarder issues between the top and bottom problem as the Jacobi iteration uses the adjacent grid points when updating an element. See the complete source implementation, algo. \ref{alg:app_jac_v3} in the appendix.

\lstinputlisting[label={alg:jac_v3_alg},caption={Algo. \texttt{jac\_gpu3}.},style=CStyle, linerange={26-46}]{code_3/jac_gpu3.cu}

\noindent The kernel is, as in \texttt{jac\_gpu2}, called by the following launch paramters: \texttt{<<<dim\_grid,dim\_block>>> jac\_gpu3}. Noticeable the grid is $N/2$ in the second axis in order to support the dimensions of the each subproblem. The 2D grid and block size are given by:
\begin{align}
dim3 \quad &dim\_grid \left(  \frac { N+bs-1 }{ bs },\frac { N/2+bs-1 }{ bs } \right)  \\
dim3\quad  &dim\_block\left(bs, bs \right)
\end{align}

\subsection{Speedup}
The expected compute speedup is 8x\footnote{PerformanceTuningIntro.pdf, slide 20.} when deploying the algorithm on the GPU compared to the CPU.
Table \ref{tab:speedup_pos} reports the achieved speedups for the three implementations.

\begin{table}[!th]
\centering
\begin{tabular}{l|r}
Algo. & Speedup \\\hline
\input{data_3/performance_pos_speedup.tex}
\end{tabular}
\caption{This table present the speed-ups of \texttt{jac\_gpu1}, \texttt{jac\_gpu2} and, \texttt{jac\_gpu3} in reference to the fastest CPU version from assignment 2, \texttt{cpu()} }
\label{tab:speedup_pos}
\end{table}

\noindent As expected the \texttt{jac\_gpu1} does not gain any improvements. The reason why is the lack of parallelism. Hence there is only launched one block with one kernel.

\noindent The speedup gained by \texttt{jac\_gpu2} is $\approx 10x$ which slightly higher than the expected compute speedup. This can be caused by a version of the OpenMP implementation, which is not fully optimized. If the implementation is sub-optimal the comparison is not fair to the fully parallel implementation on the GPU.

\noindent When splitting the problem into two subproblems the expected speedup is \underline{not} $2x$ between \texttt{jac\_gpu2} and \texttt{jac\_gpu3}. The reason is due to the nature of the Jacobi algorithm. There needs to be shared global memory access between the two devices in order to update the "middle" horizontal boarders elements. The shared global memory, accessed by peer access, is transferred on the PCIe express bus which introduce a latency and therefore not able to scale $2x$.

% \begin{figure}[H]
% \centering
% \begin{tikzpicture}[scale = 1]
% \begin{axis}[
%     width=10cm, height=8cm,     % size of the image
%     ybar,
%     %symbolic x coords={},
%     xticklabels={\texttt{jac\_cpu},\texttt{jac\_gpu1},\texttt{jac\_gpu2},\texttt{jac\_gpu3}},
%     xtick=data,
%     ytick={0,1,2,9,10,11,15,16,17},
%     ylabel=x,
%     %xlabel=Algo,
%     ]

% \addplot table [x=x, y=speed, col sep=comma]{data_3/performance_pos.txt};

% %\addplot table[x=interval,y=carT]{\mydata};
% \end{axis}
% \end{tikzpicture}
% \caption{Caption}
% \label{fig:speedup_pos}
% \end{figure}

max_stars_repo_name: anderslaunerbaek/HPC

max_issues_repo_name: anderslaunerbaek/HPC

max_forks_repo_name: anderslaunerbaek/HPC


text:
\documentclass{article}

% if you need to pass options to natbib, use, e.g.:
%     \PassOptionsToPackage{numbers, compress}{natbib}
% before loading neurips_2018

% ready for submission
% \usepackage{neurips_2018}

% to compile a preprint version, e.g., for submission to arXiv, add add the
% [preprint] option:
    \usepackage[preprint]{neurips_2018}

% to compile a camera-ready version, add the [final] option, e.g.:
%     \usepackage[final]{neurips_2018}

% to avoid loading the natbib package, add option nonatbib:
%     \usepackage[nonatbib]{neurips_2018}

\usepackage[utf8]{inputenc} % allow utf-8 input
\usepackage[T1]{fontenc}    % use 8-bit T1 fonts
\usepackage{hyperref}       % hyperlinks
\usepackage{url}            % simple URL typesetting
\usepackage{booktabs}       % professional-quality tables
\usepackage{amsfonts}       % blackboard math symbols
\usepackage{nicefrac}       % compact symbols for 1/2, etc.
\usepackage{microtype}      % microtypography

\title{Using prediction at multiple timescales for object representation learning}

% The \author macro works with any number of authors. There are two commands
% used to separate the names and addresses of multiple authors: \And and \AND.
%
% Using \And between authors leaves it to LaTeX to determine where to break the
% lines. Using \AND forces a line break at that point. So, if LaTeX puts 3 of 4
% authors names on the first line, and the last on the second line, try using
% \AND instead of \And before the third author name.

\author{%
  Andrew D~Zaharia\thanks{Use footnote for providing further information
    about author (webpage, alternative address)---\emph{not} for acknowledging
    funding agencies.} \\
  Zuckerman Mind Brain Behavior Institute\\
  Columbia University\\
  New York, NY 10027 \\
  \texttt{andrew.z@columbia.edu} \\
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
% \nipsfinalcopy is no longer used

\maketitle

\begin{abstract}
  Coming soon.
\end{abstract}

\section{Introduction}

How to best learn representations of the environment that are useful for solving tasks is a fundamental question in neural network research. State-of-the-art techniques for many machine learning tasks, such as object classification, involve supervised learning. Machine performance on these tasks lags behind human performance---they generally don't learn representations of object categories in the same, fully supervised manner. Yet they do not learn in a fully unsupervised manner either: in addition to rewards in the environment, there is a wealth of information that is contained in the stimuli themselves.

\section*{Outline of the rest of the introduction}
\subsection*{the rest of the introduction in the introduction}
\begin{itemize}
  \item Identities of objects and scenes in the real world tend to be relatively stable, while their appearance in pixel space can change drastically (e.g., lighting, rotation, scaling, within-category variation). cf. Slow feature analysis \cite{Wiskott2002}
  \item Want disentangled representations \cite{DiCarlo2007,Bengio2009,Chen2016,Higgins2017,Alemi2017}
  \item Making predictions, and comparing those predictions to incoming stimuli can serve as a self-supervision signal \cite{Whitney2016,Doersch2015}
\end{itemize}
\subsection*{Recent work}
\begin{itemize}
  \item Contrastive Predictive Coding (CPC) \cite{Oord2018} uses prediction as a self-supervision signal to attempt to learn more "useful" object representations.
  \item Furthermore, CPC uses an objective function that implicitly maximizes the mutual information between latent "context" variables and \emph{future} inputs, by explicitly minimizing normalized density ratios of inferred \emph{future latent} variables and samples from the posterior.
  \item CPC makes predictions at one level of abstraction, and on immediately subsequent instances in input stream
\end{itemize}
\subsection*{Our Contribution}
\begin{itemize}
  \item Making extremely precise predictions of the future (e.g., pixel-level image predictions) only makes sense for very short time intervals, and becomes impossible for longer time scales
  \item we aim to make predictions on multiple time scales, with increasing levels of abstraction and complexity for increasing time horizons
  \item As yet not determined method: we will implement a hierarchical, autoregressive model (e.g. ResNet VAE \cite{Kingma2016}, Ladder VAE \cite{Sonderby2016}, Variational Ladder Autoencoder \cite{Zhao2017}, etc) with a CPC-like objective that makes predictions on latent variables at multiple levels of abstraction
\end{itemize}
\subsection*{Possible tasks}
\begin{itemize}
  \item A sequence of frames in which a subset MNIST digits appear at random locations from frame to frame, but the same subset of digits have a very high probability of occurring in the subsequent frame.
  \begin{itemize}
    \item e.g., 1 and 2 each have a 99\% probability of being in a given frame, and 3 and 4 have a 1\% probability of occurring in a given frame
    \item the point of this task is to dissociate location cues with object identity
    \item we want the model to only represent and synthesize the objects that predictably appear, and ignore the ``distractor'' objects
  \end{itemize}
  \item self-supervised training using the CORe50 dataset \cite{Lomonaco2017}, which has 15sec 20fps videos of 50 objects, held in hand, belonging to 10 categories, each recorded in 11 distinct sessions (8 indoor, 3 outdoor). test object classification of new instances in the dataset
  \item A similar task on Basel faces \cite{Paysan2009}, as in \cite{Kulkarni2015,Whitney2016}
\end{itemize}

\bibliography{refs}
\bibliographystyle{unsrt}

\end{document}

max_stars_repo_name: zahariaa/disentangled-dynamics

max_issues_repo_name: zahariaa/disentangled-dynamics

max_forks_repo_name: zahariaa/disentangled-dynamics


text:
% see the original template for more detail about bibliography, tables, etc: https://www.overleaf.com/latex/templates/handout-design-inspired-by-edward-tufte/dtsbhhkvghzz

\documentclass{tufte-handout}

%\geometry{showframe}% for debugging purposes -- displays the margins

\usepackage{amsmath}

\usepackage{hyperref}

\usepackage{fancyhdr}

\usepackage{hanging}

\hypersetup{colorlinks=true,allcolors=[RGB]{97,15,11}}

\fancyfoot[L]{\emph{History of Media Studies}, vol. 1, 2021}

% Set up the images/graphics package
\usepackage{graphicx}
\setkeys{Gin}{width=\linewidth,totalheight=\textheight,keepaspectratio}
\graphicspath{{graphics/}}

\title[Wonderful Invention!]{Wonderful Invention! } % longtitle shouldn't be necessary

% The following package makes prettier tables.  We're all about the bling!
\usepackage{booktabs}

% The units package provides nice, non-stacked fractions and better spacing
% for units.
\usepackage{units}

% The fancyvrb package lets us customize the formatting of verbatim
% environments.  We use a slightly smaller font.
\usepackage{fancyvrb}
\fvset{fontsize=\normalsize}

% Small sections of multiple columns
\usepackage{multicol}

% Provides paragraphs of dummy text
\usepackage{lipsum}

% These commands are used to pretty-print LaTeX commands
\newcommand{\doccmd}[1]{\texttt{\textbackslash#1}}% command name -- adds backslash automatically
\newcommand{\docopt}[1]{\ensuremath{\langle}\textrm{\textit{#1}}\ensuremath{\rangle}}% optional command argument
\newcommand{\docarg}[1]{\textrm{\textit{#1}}}% (required) command argument
\newenvironment{docspec}{\begin{quote}\noindent}{\end{quote}}% command specification environment
\newcommand{\docenv}[1]{\textsf{#1}}% environment name
\newcommand{\docpkg}[1]{\texttt{#1}}% package name
\newcommand{\doccls}[1]{\texttt{#1}}% document class name
\newcommand{\docclsopt}[1]{\texttt{#1}}% document class option name

\begin{document}

\begin{titlepage}

\begin{fullwidth}
\noindent\LARGE\emph{Launch essay
} \hspace{85mm}\includegraphics[height=1cm]{logo3.png}\\
\noindent\hrulefill\\
\vspace*{1em}
\noindent{\Huge{Wonderful Invention!\par}}

\vspace*{1.5em}

\noindent\LARGE{Ira Wagman}\par}\marginnote{\emph{Ira Wagman, ``Wonderful Invention!'' \emph{History of Media Studies} 1 (2021), \href{https://doi.org/10.32376/d895a0ea.ef8f548f}{https://doi.org/10.32376/d895a0ea.ef8f548f}.} \vspace*{0.75em}}
\vspace*{0.5em}
\noindent{{\large\emph{Carleton University}, \href{mailto:ira.wagman@carleton.ca}{ira.wagman@carleton.ca}\par}} \marginnote{\href{https://creativecommons.org/licenses/by-nc/4.0/}{\includegraphics[height=0.5cm]{by-nc.png}}}

% \vspace*{0.75em} % second author

% \noindent{\LARGE{<<author 2 name>>}\par}
% \vspace*{0.5em}
% \noindent{{\large\emph{<<author 2 affiliation>>}, \href{mailto:<<author 2 email>>}{<<author 2 email>>}\par}}

% \vspace*{0.75em} % third author

% \noindent{\LARGE{<<author 3 name>>}\par}
% \vspace*{0.5em}
% \noindent{{\large\emph{<<author 3 affiliation>>}, \href{mailto:<<author 3 email>>}{<<author 3 email>>}\par}}

\end{fullwidth}

\vspace*{1em}

\newthought{On September 8,} 1957, the Roman Catholic Church published the papal
encyclical on motion pictures, radio, and television. The title,
\emph{Miranda Prorsus}, is a Latin term meaning both ``absolutely
remarkable'' and ``remarkable advance'' in English. These different
connotations coalesced around powerful media technologies in the
encyclical's opening phrase ``Miranda prorsus technicae artis
inventa.''\footnote{Pius VII, \emph{Miranda Prorsus}, Encyclical Letter,
  September 8, 1957,
  \url{https://www.vatican.va/content/pius-xii/en/encyclicals/documents/hf_p-xii_enc_08091957_miranda-prorsus.html}
  (last accessed September 19, 2021). The opening phrase translates to
  ``remarkable technological inventions.''} The encyclical outlined Pope
Pius VII's position on cinema, radio, television, and the press, and it
provided advice for clergy, administrators, and laity on how best to
approach these powerful media technologies. Since encyclicals provide
papal guidance on matters of public concern, this one also represented
an attempt by the Catholic Church to consider media as sites through
which to comprehend broader social and spiritual problems. With that
twin purpose in mind, \emph{Miranda Prorsus} asks\emph{:} Are media
technologies threats to moral virtue, or can they be deployed as tools
for eternal salvation?

In what follows I suggest that \emph{Miranda Prorsus} can draw our
attention to a few different lines of argument we might explore in
accounting for the history of media studies. First, it offers us the
occasion to consider how knowledge about media travels within
communities that exist outside the academy. At the risk of sounding
flippant, I also want to say that it draws our attention to the fact
that ``media studies'' is something different organizations do all the
time. The more we recognize this fact, the better equipped we could be
to appreciate the pathways of exchange, circulation, imitation, and
incorporation that exist between academic and non-expert social
institutions. Second, in conceptualizing media both as a contemporary
concern and one grounded within the ambit of theological doctrine,
\emph{Miranda Prorsus} also asks us to consider the histories of
different styles of reasoning about media. To put it a different way,
then, I believe that

\enlargethispage{2\baselineskip}

\vspace*{2em}

\noindent{\emph{History of Media Studies}, vol. 1, 2021}

 \end{titlepage}

\noindent \emph{Miranda Prorsus} can be read as an
\emph{argument about media} as much as it constitutes a set of
instructions for other people about \emph{what to do} with the means of
mass communication. As such it calls on us to account for the history of
thinking about media in ways that make them objects for study and
intervention, whether by academics or, in this case, by the Vatican.
Both of these themes let us appreciate the benefits of a capacious sense
of what we understand as ``media studies'' force us to think more
carefully about what we have historically understood as media.

As primary documents encyclicals provide rich sources for thinking about
the communication of religious doctrine. Although intended for clergy
and laity, journalists, Catholic and non-Catholic alike, routinely cover
their dissemination. This gives encyclicals the quality, as Clare
Donagle explains, of ``an extended press release within which a given
pope can declare his agenda to the world.''\footnote{Clare Donagle,
  ``The Politics of Extra/Ordinary Time: Encyclical Thinking,''
  \emph{Cogent Arts and Humanities} 4, no. 1 (2017): n.p.} In their
rhetorical style, encyclicals also express a way of thinking about
matters of institutional concern that mixes biblical quotations with
previous church doctrine. This has the effect of situating the Catholic
Church's intervention within a particular temporal frame, one that
``lies outside of history, the possibility of eternal life through
Christian faith.''\footnote{Donagle, ``The Politics of Extra/Ordinary
  Time.''} For Donagle, the tension between an encyclical's policy
objectives and its reminder about the ephemerality of human existence
shows how encyclicals reflect a tension ``between Christianity's
evangelical and existential aspects.''\footnote{Donagle, ``The Politics
  of Extra/Ordinary Time.''}

With \emph{Miranda Prorsus} we can see the forward-looking view of the
Catholic Church refracted through its more traditional ontological and
theological visions.\footnote{See Daniel Biltereyst and Daniela Traveri Gennari, eds., \emph{Moralizing Cinema: Film, Catholicism and Power} (New York: Routledge, 2015) for further discussion of \emph{Vigilanti Cura} and for several historical case studies exploring the Catholic Church’s on-the-ground activities in different national and local contexts.} In contrast to the harder-edged encyclical on
cinema to U.S. clergy issued by Pius's predecessor, \emph{Vigilanti
Cura} (\emph{Vigilant Care}), which called for closer controls and even
the censorship of films, \emph{Miranda Prorsus} adopted a tone I would
characterize as anxiously optimistic. Blending prior church statements
on media with quotations from scripture and references to Thomas
Aquinas, the encyclical characterized media in ways familiar to
introductory media studies courses: showing considerable respect for its
technical possibilities; highlighting its capacity to appeal to sensory
perceptions and to provide knowledge of the world; noting its ability to
blur boundaries of public and domestic space; and recognizing
how~``these new forms of art exercise very great influence on the manner
of thinking and acting of individuals and every group of
men.''\footnote{Pius VII, \emph{Miranda Prorsus.}} The document shows
the church wrestling with the twin forces of media power: On the one
hand, it recognized that these technologies~``may be spread among men
like good seed which bring forth fruits of truth and goodness''; on the
other hand, it later acknowledged that ``not all obey the
gospel.''\footnote{Pius VII, \emph{Miranda Prorsus.}}

In \emph{Miranda Prorsus} we see Pius attempting to tip the balance in
his preferred direction. The encyclical argues that Catholics ranging
from film critics to bishops must be agents in promoting the responsible
arts of mediated communication, to play an active role in publicizing
Christian doctrine and encourage media producers to create works that
might fulfill the higher potential of art. The document details how some
church officials have made use of the capacity of long-distance
communication to ensure that ``Our voice, passing in sure and safe
flight over the expanse of the sea and land and even over the troubled
emotions of souls may reach men's minds in a healing influence, in
accordance with the demands of the task of the supreme apostolate,
confided to Us and today extended without limit.''\footnote{Pius VII,
  \emph{Miranda Prorsus.}} Assessing the various media forms in turn,
the encyclical provides instructions for national authorities to lobby
for more programs with Catholic themes, to monitor and measure media
content, and to train both the producers of media and its audiences to
take seriously their respective roles in making and consuming the
products of these powerful means of mass communication.

Furthermore, \emph{Miranda Prorsus} urged the clergy, its
administrators, and the Catholic Action groups and affiliated
organizations operating locally and nationally to play active roles in
teaching the laity and in informing the wider public about how to best
make forms of mass communication achieve their spiritual objectives. To
do this meant priest should have ``a sound knowledge of all questions
which confront the souls of Christians with regards to Motion Pictures,
Radio, and Television'' and ``must know what modern, science, art and
technique assert whenever they touch on the end of man and his moral and
religious life.''\footnote{Pius VII, \emph{Miranda Prorsus.}} This
involved encouraging clergy to provide guidance for film, television,
and radio producers, actors, broadcasters, and distributors, and to make
use of media to produce religious content reflecting Christian doctrine.
With some of the groundwork established, \emph{Miranda Prorsus} can be
viewed as one of a series of major statements the church made about
media during this time. Such efforts continued during the Second Vatican
Council decree, \emph{Inter Mirifica} (\emph{Among the Wonders}),
outlining the church's statement on social communication, which was
published just six years later. The document, along with the papal
instruction \emph{Communio et Progressio} (\emph{Community and
Progress}, 1971), played an important role in the disciplinary
development of communication studies within universities in several
places around the world.\footnote{For example, see Raúl Fuentes-Navarro,
  ``Institutionalization and Internationalization of the Field of
  Communication Studies in Mexico and Latin America,'' and Maria
  Immacolata Vassallo de Lopes and Richard Romancini, ``History of
  Communication}

In this cursory treatment of \emph{Miranda Prorsus} we can envision some
pathways that could enrich the historiography of media studies. In one
sense, it reminds us of the powerful place of religious institutions in
the historical development of media studies. Menahem Blondheim and
Hanael\marginnote{in Brazil: The Institutionalization of an
  Interdisciplinary Field,'' both in \emph{The International History of
  Communication Study}, ed. Peter Simonson and David W. Park (New York:
  Routledge, 2016), for invaluable analyses on the institutionalization
  of communication studies programs in Mexico and Latin America and
  Brazil, respectively.} Rosenberg use the term \emph{media theology} to think about ``the
historical and theoretical project of religious thinking on the
relevance of communications to the relationship between God and humans
and to the ideological implications of those ideas.''\footnote{Menahem
  Blondheim and Hanael Rosenberg, ``Media Theology: New Communication
  Technologies as Religious Constructs, Metaphors, and Experiences,''
  \emph{New Media and Society} 19, no 2 (2016): 44.} If we were to
follow Jeremy Stolow's argument that religion and technology ``operate
along a series of analogous binaries, including faith and reason,
fantasy and reality, enchantment and disenchantment, magic and science,
and fabrication and fact,'' then it appears reasonable to ask about the
influence of theological thinking on the development of the scholarly
field of media studies.\footnote{Jeremy Stolow, ``Introduction:
  Religion, Technology, and the Things in Between,'' in \emph{Deus in
  Machina: Religion, Technology, and the Things in Between}, ed. Jeremy
  Stolow (New York: Fordham University Press, 2013), 2.} Moreover,
thinking in terms of media theology asks us to recognize how studies of
media have been used to represent religious ideas and to recognize how
religious institutions themselves \emph{study media} so as to
incorporate them into their own theological activities.

In this respect, we can also consider the encyclical as a form of public
deliberation, of thinking out loud about the characteristics of media
technologies---of working it out on paper, if you will. ``Reasoning is
done in public as well as in private,'' Ian Hacking writes, ``but also
by talking and arguing and showing.''\footnote{Ian Hacking,
  \emph{Historical Ontology} (Cambridge: Harvard University Press,
  2002), 180.~} From this we can say that what we may want to call
``media studies'' can be understood as a mentality or set of
dispositions that people occupy at different times and in different
contexts, one in which everyone from academic researchers to non-profit
organizations sees the expansion of communication technologies as
signaling an understanding that broader social and political problems
need to be comprehended in media terms. In Anna Shechtman's account of
debates over how to understand media at a 1959 gathering in
Pennsylvania's Pocono Mountains, we see a range of elite thinkers, from
Hannah Arendt to Paul Lazarsfeld to Daniel Bell to James Baldwin, who
consider the concept of media as ``as a rhetorical vehicle---an
overdetermined metaphor for the technical, ideological, and
environmental conditions of modern life.''\footnote{Anna Shechtman,
  ``Command of Media Metaphors,'' \emph{Critical Inquiry} 47, no. 2
  (2021): 649.} Indeed, situated within \emph{Miranda Prorsus} we find
the broader concern about media being used as a tool ``in those nations
where atheistic communism is rampant'' to ``root out all religious
ideals from the mind,'' a reminder of how \emph{media} is a term used to
think \emph{through} and not just \emph{about}.\footnote{Pius VII,
  \emph{Miranda Prorsus.} For further discussion, see Frank J. Coppa,
  ``Pope Pius XII and the Cold War: The Confrontation between
  Catholicism and Communism,'' in \emph{Religion and the Cold War}, ed.
  Dianne Kirby (London: Palgrave Macmillan, 2003).}

In that process of thinking things through, we can also consider the
decisions made to discard or ignore other forms of argument, evidence,
or rhetorical styles, as part of different exercises of power and
privilege. From this perspective, \emph{Miranda Prorsus} must be
integrated into the \emph{history of arguments about media} to better
appreciate what kinds of reasons have been put forward, accepted, and
ignored in the process of making an abstract concept such as media its
own object of study. If we consider Amin Alhassan's assertion that
processes of knowledge production often erase their connection with
colonial and postcolonial subjects and locations, then any discussion of
different styles of reasoning about media must be carried out with an
aim to re-establishing those connections.\footnote{Amin Alhassan, ``The
  Canonic Economy of Communication and Culture: The Centrality of the
  Postcolonial Margins,'' \emph{Canadian Journal of Communication} 32,
  no. 1 (2007).} This would encourage us to think more closely about the
lived effects of the application of academic knowledge in different
settings, and to further prompt greater questioning of the canonicity of
the concepts that form part of our field of inquiry.

In its appeal for the development of local and regional institutional
infrastructure for media education, \emph{Miranda Prorsus} also
encourages us to account for the networks of bishops, Catholic Action
groups, public information efforts, and mass education campaigns as
sites for the production, dissemination, and debate about lay media
knowledge.\footnote{An excellent example of this is François Yelle's
  discussion of the impact of media-related encyclicals---including
  \emph{Miranda Prorsus}---in Quebec. See François Yelle, ``Fifty Years
  Ago Today When the Pope Knew Everything There Was to Know About
  Media'' (paper presented at Two Days of Canada conference, Brock
  University, St. Catherine's, ON, November 6, 2008).} It asks us to
consider the extent to which the Catholic Church was engaged in research
about media; the role that intellectuals played within those efforts,
and the distribution of that research through its different
publications. Accounting for the institutional and infrastructural
systems of media-knowledge transmission will better equip us to
re-situate religious institutions within historiographical accounts of
disciplinary development. It will also show how those institutions have
acted as sites where media theories are transformed into theological
praxis and as clearinghouses for the dissemination of academic and lay
knowledge about media.

Finally, the encyclical also pushes us to think about the places where
media studies knowledge has been used, misused, and abused in different
institutional settings, as part of its pedagogical and educational
objectives. What role have media technologies---and the specific
knowledge about media that would have inspired their use---played in the
church's efforts in the fields of education and media literacy? In the context in which I am writing this article, it is impossible to not consider this question in relation to the legacy of the residential and day school systems for Canada’s First Nations, Métis, and Inuit communities that were operated by successive governments in partnership with the Catholic Church (and churches from other denominations) as part of a broader policy of forced assimilation, separation, disempowerment, and cultural genocide. According to the 2015 Summary of the Final Report of
Canada's Truth and Reconciliation Commission, it was during the 1950s
and 1960s that ``the prime mission of the residential schools was the
cultural transformation of Aboriginal children.''\footnote{Truth and
  Reconciliation Commission of Canada, \emph{Honouring the Truth,
  Reconciling the Future: Summary of the Final Report of the Truth and
  Reconciliation Commission of Canada}. (Ottawa: Truth and
  Reconciliation Commission of Canada, 2015),~5.~} That history forces
us to consider whether an encyclical like \emph{Miranda Prorsus}
foreshadowed the deployment of media to support these objectives and to
inquire about the kinds of scholarly knowledge that might have used to
support structures of forced assimilation and violence both in Canada
and elsewhere. Addressing that question would prove valuable for
thinking more seriously about the overlapping institutional and
disciplinary histories, epistemological frameworks, and ontological
categories that constitute the way we have researched, taught, and
studied media in different contexts and over time.

Let us, then, embark on this journey to trouble the history of ``media
studies'' in as many contexts as possible. May it begin by going
directly to some of the institutions that have been doing media studies
alongside so many of us for a long time. Let us ask about the extent to
which that knowledge has served to support systems of oppression,
control, racism, and colonialism; to appreciate the dynamic between
scientific and lay knowledge;\footnote{For example, see Ellen Seiter, \emph{Television and New
  Media Audiences} (Oxford: Oxford University Press, 1996), 58--60, and
  Patrick McCurdy ``Theorizing `Lay Theories of Media': A Case Study of
  the Dissent! Network at the 2005 Gleneagles G8 Summit,''
  \emph{International Journal of Communication} 5 (2011).~} to encourage counter-histories of our
field; to multiply the contexts in which we appreciate media as an
object of study; and to draw attention to ignored and marginalized
voices. And let us
more reflexively consider the ways that ``media studies'' can offer a
productive approach for undertaking more complex and subtle histories of
other areas of academic study.

\section{Bibliography}\label{bibliography}

\begin{hangparas}{.25in}{1}

Alhassan, Amin. ``The Canonic Economy of Communication and Culture: The
Centrality of the Postcolonial Margins.'' \emph{Canadian Journal of
Communication} 32, no. 1 (2007): 103--18.
\url{https://doi.org/10.22230/cjc.2007v32n1a1803}.

Biltereyst, Daniel, and Daniela Traveri Gennari, eds. \emph{Moralizing Cinema: Film, Catholicism and Power}. New York: Routledge, 2015.

Blondheim, Menahem, and Hanael Rosenberg. ``Media Theology: New
Communication Technologies as Religious Constructs, Metaphors, and
Experiences.'' \emph{New Media and Society} 19, no. 1 (2016): 43--51.
\url{https://doi.org/10.1177\%2F1461444816649915}.

Coppa, Frank J. ``Pope Pius XII and the Cold War: The Post-War
Confrontation between Catholicism and Communism.'' In \emph{Religion and
the Cold War}, edited by Dianne Kirby, 50--66. London: Palgrave
Macmillan, 2003.

Donagle, Clare. ``The Politics of Extra/Ordinary Time: Encyclical
Thinking.'' \emph{Cogent Arts and Humanities} 4, no. 1 (2017): n.p.
\url{https://doi.org/10.1080/23311983.2017.1390918}.

Fuentes-Navarro, Ra\'{u}l. ``Institutionalization and Internationalization
of the Field of Communication Studies in Mexico and Latin America.'' In
\emph{The International History of Communication Study}, edited by Peter
Simonson and David W. Park, 325--46. New York: Routledge, 2016.

Hacking, Ian. \emph{Historical Ontology.} Cambridge: Harvard University
Press, 2002.

Lopes, Maria Immacolata Vassallo de, and Richard Romancini. ``History of
Communication in Brazil: The Institutionalization of an
Interdisciplinary Field.'' In \emph{The International History of
Communication Study}, edited by Peter Simonson and David W. Park,
346--66. New York: Routledge, 2016.

McCurdy, Patrick. ``Theorizing `Lay Theories of Media': A Case Study of
the Dissent! Network at the 2005 Gleneagles G8 Summit.''
\emph{International Journal of Communication}, no. 5 (2011): 619--30.
\url{https://ijoc.org/index.php/ijoc/article/view/842}.

Pius VII, \emph{Miranda Prorsus.} Encyclical Letter. September 8, 1957.
\url{https://www.vatican.va/content/pius-xii/en/encyclicals/documents/hf_p-xii_enc_08091957_miranda-prorsus.html}.

Seiter, Ellen. \emph{Television and New Media Audiences.} Oxford: Oxford
University Press, 1999.

Shechtman, Anna. ``Command of Media Metaphors.'' \emph{Critical Inquiry}
47, no. 4 (2021): 644--74. \url{https://doi.org/10.1086/714512}.

Stolow, Jeremy. ``Introduction: Religion, Technology, and the Things in
Between.'' In \emph{Deus in Machina: Religion, Technology and the Things
In Between}, edited by Jeremy Stolow, 1--24. New York: Fordham
University Press, 2013.

Truth and Reconciliation Commission of Canada. \emph{Honouring the
Truth, Reconciling for the Future: Summary of the Final Report of the
Truth and Reconciliation Commission of Canada}. Ottawa: Truth and
Reconciliation Commission of Canada, 2015.

Yelle, François. ``Fifty Years Ago Today When the Pope Knew Everything
There Was to Know About Media.'' Paper presented at Two Days of Canada
conference, Brock University, St. Catherine's, ON, November 6, 2008.

\end{hangparas}

\end{document}

max_stars_repo_name: mediastudiespress/serials

max_issues_repo_name: mediastudiespress/serials

max_forks_repo_name: mediastudiespress/serials


text:
\documentclass{article} % For LaTeX2e
\usepackage[backend=bibtex, sorting=none]{biblatex}
\addbibresource{bibliography.bib}
\usepackage{nips15submit_e,times}
\usepackage{hyperref}
\usepackage{url}
\usepackage{amsmath}
\usepackage{tipa}
\usepackage{multicol}
\usepackage{multirow}
\usepackage{array}
\usepackage{graphicx}
\usepackage{bm}
\usepackage{mathtools,xparse}
\graphicspath{ {figures/} }
\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}
\usepackage[linesnumberedhidden,ruled,noend]{algorithm2e}
\usepackage{etoolbox}
\patchcmd{\abstract}{Abstract}{Project information}{}{}

\makeatletter
\def\BState{\State\hskip-\ALG@thistlm}
\makeatother
%\documentstyle[nips14submit_09,times,art10]{article} % For LaTeX 2.09

\title{COMPGI15: Information Retrieval and Data Mining Group Project - Report}

\author{
Sergiu Tripon\\
Department of Computer Science\\
University College London\\
Gower Street, London, WC1E\\
\texttt{sergiu.tripon.15@ucl.ac.uk}\\
\And
Santiago Gonzalez\\
Department of Computer Science\\
University College London\\
Gower Street, London, WC1E\\
\texttt{hernan.toral.15@ucl.ac.uk} \\
\And
Archie Norman \\
Department of Computer Science\\
University College London\\
Gower Street, London, WC1E\\
\texttt{archie.norman.15@ucl.ac.uk} \\
}

% The \author macro works with any number of authors. There are two commands
% used to separate the names and addresses of multiple authors: \And and \AND.
%
% Using \And between authors leaves it to \LaTeX{} to determine where to break
% the lines. Using \AND forces a linebreak at that point. So, if \LaTeX{}
% puts 3 of 4 authors names on the first line, and the last on the second
% line, try using \AND instead of \And before the third author name.

\newcommand{\fix}{\marginpar{FIX}}
\newcommand{\new}{\marginpar{NEW}}

\nipsfinalcopy % Uncomment for camera-ready version

\begin{document}

\maketitle

\section*{Project information}

The implementation code is available on GitHub at:

\url{https://github.com/santteegt/ucl-irdm-collaborative-filtering}

A manual is also available on GitHub at:

\url{https://github.com/santteegt/ucl-irdm-collaborative-filtering#user-content-collaborative-filtering-project-using-deep-learning}

\section{Introduction}

Nowadays, web enabled online services like e-stores and streaming platforms which offer an increasing amount of different products have been integrating Recommender Systems (RS) into their platforms aiming to make a more effective use of information. Recommender Systems play an important role by assisting customers to find products according to their taste over those platforms. Different approaches have been developed to provide accurate recommendations to users, however there has been a lack of data and research on the scope of music recommending systems.

Conventional methods use ratings given to items by users as the only source of recommendation. The prediction accuracy drops significantly when the ratings are very sparse. Moreover, they cannot be used for recommending new products which have yet to receive rating information from users. This is known as the "cold start" problem. Content information may be utilized, but loosely coupled methods process the auxiliary information once and then use it to provide features for the CF models (one-way interaction). Tightly coupled methods allow two-way interaction.

\section{Aim}

The aim of this group project is to develop and test a recommending system using two approaches: a pure probabilistic matrix factorization and a hierarchical Bayesian model using deep learning approach by employing the ratings (feedback) matrix and the related content information for learning stronger features. The recommender system will be evaluated in order to analyze how tightly coupled methods can automatically learn features from the auxiliary information and naturally balance the influence of the rating and the content information. The evaluation results of the implemented model will be compared with the baseline approach.

\section{Background \& Related work}

\subsection{Collaborative Topic Modeling for Recommending Scientific Articles}

Wang and Blei \cite{wang2011collaborative} developed an algorithm to recommend scientific articles to users of an online community. The algorithm combines the merits of traditional collaborative filtering and probabilistic topic modeling. It provides an interpretable latent structure for users and items, and can form recommendations about both existing and newly published articles, therefore tackling the cold start problem. The algorithm was evaluated against a large subset of data from CiteULike, a bibliography sharing service, which showed that the algorithm proposed provides a more effective recommender system than traditional collaborative filtering.

\subsection{A Hybrid GA-based Collaborative Filtering Model for Online Recommenders}

Ho et. al \cite{ho2007hybrid} created a Hybrid Genetic Algorithm-based Collborative Filtering MOdel applied on the MovieLens dataset. The model implements collaborative and content-based methods separately and then combines their predictions. It incorporates some content-based characteristics into a collaborative approach and some collaborative characteristics into a content-based approach. It also constructs a general unifying model that incorporates both content-based and collaborative characteristics. The model tackles the cold start problem occurring during the early period of usage, by adding an additional "preference" component which consists of features such as the user's preferred film type and language. This means that, during the early stage, the preference component will dominate the search function in the GA operation;

\subsection{Music recommendations using cover images}

A blog post by Eric Bernhardsson \cite{bernhardsson2014music} described an experiment which considered cover images as a means for music recommendations. The first attempt at recommendation involved resizing all image to 16x16, converting them to grayscale, subtracting the mean and normalizing by the variance, which resulted in fairly poor recommendations. A further attempt involved using pyleargist, a wrapper around a C library, which takes an image and outputs an image descriptor, which improved the recommendation results. According to Eric, the experiment's future work would involve learning a mapping from image space to collaborative filtering space and venturing into the realms of deep learning.

\subsection{Combining Spotify and Twitter Data for Generating a Recent and Public Dataset for Music Recommendation}

Pichl et al.'s research \cite{pichl2014combining} is based on the \#nowplaying dataset, the same dataset used in this project. Its aims were to implement and evaluate a pure collaborative filtering based recommender system. They found that for a high number of recommendations the recommender system was rather limited. During the evaluation phase, they discovered that further work was required. This included gathering of further context based information that is available such as time stamp or geolocation and implementing hybrid recommender system utilizing this additional context based information.

\subsection{Recommending music on Spotify with deep learning}

Sander Dieleman, a Spotify intern, wrote a blog post \cite{dieleman2014recommending} discussing his work on music recommendations using deep learning at Spotify. Dieleman's work focused on content-based music recommendation using convolutional neural networks. It involved training a model to predict the latent representations of songs that were obtained from a collaborative filtering model. This enabled the ability to predict the representation of a song in the collaborative filtering space, even if no usage data was available. If two songs are close together in this space, they are probably similar. If a song is close to a user, it is probably a good recommendation for that user, considering that they haven't listened to it yet. If predicting the position of a song in this space from audio is achieved, recommending the song to the right audience without having to rely on historical usage data can also be achieved.

\subsection{Collaborative Deep Learning for Recommender Systems}

Wang et al. \cite{wang2015collaborative} propose a a hierarchical Bayesian model called collaborative deep learning (CDL). CDL jointly performs deep representation learning for the content information and collaborative filtering for the ratings (feedback) matrix by using an stacked deep autoencoder model which is tightly coupled with a Collaborative Topic Model (CTR) in order to automatically learn features and balance them with the influence of ratings. Extensive experiments on three real-world datasets from different domains showed that CDL can significantly perform better than the state of the art.

\subsection{Types of Collaborative Filtering \cite{ho2007hybrid}}

\textbf{Content-based filtering}

As the name suggests, content-based filtering focuses on content. In a music-related context, a song will be recommended to a user if in the past the user has listened to another that shares the same genre as the song being recommended. Content-based filtering selects items based on the correlation between the content of the items and user preferences. For example, current search engines are based on automatic analysis of the content of documents and the content of user’s query. This type of filtering also bring disadvantages as the system can only recommend items scoring highly against the user profile. The user is restricted to see the items similar to those already rated and new items will never be recommended due to the working on an individual user.

\textbf{Item-based Collaborative Filtering}

Item-based Collaborative Filtering focuses on the similarity between the currently active user and other users. It aims to find new items the active user has never seen before but are predicted they would be interested in, based on other users' interest in the items. For example, users A, B and C all like Item 1. Two of the users, A and B also like Item 3. Item 3 would then be recommended to user C based on user A and B's interest in the item. The similarity can either be measured by the same item which is known as item-based CF or by the same type of user, which is known as user-based CF. This method is quite common for current recommendation systems, which have been wildly used by MovieLens and Yahoo. Item-based techniques first analyze a user-item matrix to identify relationships between different items, and then use these relationships to indirectly compute recommendations for users.

\textbf{User-based Collaborative Filtering}

User-based Collaborative Filtering is similar to item-based CF with the difference being that it looks at similarities between users rather than items. For example, User A likes Item 1, 2 and 4. User B likes Item 1 and 2. Items 1 and 2 are common between User A and B. Therefore, Item 4 will be recommended to User B as User A and B are deemed as like-minded users.

\section{Data}

For this project, we use as main data sources the \#nowplaying dataset \cite{zangerle2014nowplaying} and the public MusicBrainz\footnote{\url{https://musicbrainz.org/}} music encyclopedia for music metadata. The former is a social media-based dataset which combines Twitter and Spotify data in order to create a relationship indicating music listening behaviour of Twitter users. The authors attempted to find a match between the user's Twitter and Spotify user names. If the user names were identical, a match was found and that user's data was kept in the dataset. In the situation where a match was not found, the data was discarded in order to preserve data quality and accuracy. The dataset also provides Artist and Track IDs for the MusicBrainz database. Using these identifiers provided, we are able to extract further artist and track-related features which boosts recommendation accuracy.

\subsection{Dataset analysis}

Table \ref{table:1} presents number of tweets, users, tracks and artists in the \#nowplaying dataset dump downloaded on 06/04/2016.

\begin{table}[!htbp]
\caption{Number of tweets, users, tracks and artists in the dataset as of 06/04/2016.}
\label{table:1}
\begin{center}
\begin{tabular}{l l l l}
\multicolumn{1}{c}{\bf Tweets} & \multicolumn{1}{c}{\bf Users} & \multicolumn{1}{c}{\bf Artists} & \multicolumn{1}{c}{\bf Tracks}
\\ \hline \\
88,745,248 & 5,497,005 & 151,440 & 772,485\\
\end{tabular}
\end{center}
\end{table}

Table \ref{table:2} showcases the top 5 most popular sources used by the users in the \#nowplaying dataset as of 06/04/2016.

\begin{table}[ht]
\caption{Top 5 most popular sources as of 06/04/2016.}
\label{table:2}
\begin{center}
\begin{tabular}{l l l l}
\multicolumn{1}{c}{\bf Source} & \multicolumn{1}{c}{\bf Times used}
\\ \hline \\
Securenet Systems Radio Playlist Update & 13,326,642\\
Spotify                                 & 7,132,339\\
Web                                     & 4,139,372\\
SAM Broadcaster Song Info               & 3,439,207\\
BigUrl                                  & 3,170,726\\
%Twitter for iPhone                      & 3,080,571\\
%Twitter for Android                     & 2,348,784\\
%Share.Radionomy.com                     & 2,342,915\\
%iOS                                     & 2,257,604\\
%Wavepanel                               & 1,809,559\\
\end{tabular}
\end{center}
\end{table}

Table \ref{table:3} presents the top 5 most popular tracks listened to by the users in the \#nowplaying dataset as of 06/04/2016.

\begin{table}[!htbp]
\caption{Top 5 most popular tracks as of 06/04/2016.}
\label{table:3}
\begin{center}
\begin{tabular}{l l l l}
\multicolumn{1}{c}{\bf Artist} & \multicolumn{1}{c}{\bf Track} & \multicolumn{1}{c}{\bf Times played}
\\ \hline \\
ON              & Generations                & 934,021\\
NP              & B4                         & 597,004\\
Rihanna         & Should I?                  & 331,434\\
Coldplay        & Swallowed in the Sea       & 327,967\\
Taylor Swift    & Crazier                    & 264,918\\
%Katy Perry      & ET                         & 257,538\\
%Bruno Mars      & Talking to the Moon        & 251,635\\
%Michael Jackson & Can't Let Her Get Away      & 251,444\\
%One Direction   & Total Eclipse of the Heart & 249,959\\
%U2              & Salome                     & 245,442\\
\end{tabular}
\end{center}
\end{table}

\subsection{Sample Extraction}

During the data analysis phase of the project, we discovered that the data was too large for the computational power we had available. This lead to the decision of extracting a sample from the data set. For this, we used the following workflow for extracting a sample data set for training/validating our models:

\begin{enumerate}
    \item Aggregate the data and calculate each users tweet count (No. of songs published)
    \item Filter users with 3 or more tweets
    \item Extract a sample of 100.000 records using reservoir sampling
    \item Calculate basic statistics such as number of users and tracks, and mean and standard deviation of the number of publications (items) per user.
\end{enumerate}

Table \ref{table:4} presents stats of the extracted sample such as number of users and tracks, mean and standard deviation. Further explanation regarding to the sampling method used for this task is exposed in the following section.

\begin{table}[!htbp]
\caption{Stats of the extracted sample data set.}
\label{table:4}
\begin{center}
\begin{tabular}{c c c c}
\multicolumn{1}{c}{\bf Users} & \multicolumn{1}{c}{\bf Tracks} & \multicolumn{1}{c}{\bf Mean} & \multicolumn{1}{c}{\bf Std. Deviation}
\\ \hline \\
35,122 & 49,679 & 2.8 & 16.1\\
\end{tabular}
\end{center}
\end{table}

\subsection{Reservoir Sampling}

Reservoir Sampling \cite{reservoirsampling} is a collection of randomized algorithms used to choose a random sample of \textit{k} items from a list S containing \textit{n} items, in the context where \textit{n} is a very large or unknown number. Typically, \textit{n} is large enough for it to not fit into main memory. The pseudo-code for Reservoir Sampling:

\begin{itemize}
    \item Keep the first item in memory.
    \item When the \textit{i}-th item arrives (for \textit{i} \textgreater 1):
    \item with probability $ 1 / i $, keep the new item instead of the current item;
    \item with probability $ 1-1 / i $, keep the current item and discard the new item.
\end{itemize}

So:

\begin{itemize}
    \item when there is only one item, it is kept with probability 1;
    \item when there are 2 items, each of them is kept with probability $ 1/2 $;
    \item when there are 3 items, the third item is kept with probability $ 1/3 $, and each of the previous 2 items is also kept with probability $ (1/2)(1-1/3) = (1/2)(2/3) = 1/3 $;
    \item by induction, it is easy to prove that when there are \textit{n} items, each item is kept with probability $ 1/n $.
\end{itemize}

Figure \ref{fig:samplingP} shows the transformation schema used in Pentaho to getting a sample from the now playing data set that has users with 3+ published items.

\begin{figure}[ht]
\centering
\fbox{\includegraphics[scale=0.6]{figures/sampling}}
\caption{Reservoir Sampling in Pentaho: Data Integration Platform.}
\label{fig:samplingP}
\end{figure}

\subsection{Data Integration for content extraction}

In order to integrate the nowplaying sample set with the content information of each track from MusicBrainz, another transformation was built in Pentaho to obtain the list of user-tracks ids. Figure \ref{fig:forRatrings} outlines the flow diagram of the transformation, where only the track-based output was used in our project as it can be also used to obtained the artist content information. The obtained output file was used to obtain the content information from the MusicBrainz Postgres Database, as well as the required files to generate the rating matrix for the CTR matrix factorization model. The generated files can be found under the \textit{data} folder in project repository.

\begin{figure}[ht]
\centering
\fbox{\includegraphics[scale=0.6]{figures/forRatings}}
\caption{Mapping of nowPlaying/MusicBrainz Ids for content extraction and rating matrix construction}
\label{fig:forRatrings}
\end{figure}

\subsection{Ratings Matrix generation}

A ratings matrix was generated, consisting of the entire collection of items in the sample data set to give a J by S matrix X. We generated a binary matrix whereby if the user has listened to a track we assign a value of 1, while if they haven't listened to the track, we assign 0. Two files were generated, output\_by tracks and output\_by\_user. Each file aggregates each item and associates the user\_id or track\_id in the corresponding row. Tables \ref{table:5} and \ref{table:6} present an example of the format of each file generated.

\begin{table}[!htbp]
\caption{Aggregated tracks played per user.}
\label{table:5}
\begin{center}
\begin{tabular}{c c c c}
\textbf{user\_id} & \textbf{count} & \textbf{track\_id} & \textbf{track\_id}\\
693afc22f9b838a38... & 2 & 013d1e71\-f6a4\-3adc... & dcca7fcb\-aa17\-36d5...\\
ba6b4825ca63356b0... & 2 & 006cddf7\-52f3\-3eb8... & 001c124e\-c675\-3b0c...\\
\end{tabular}
\end{center}
\end{table}

\begin{table}[!htbp]
\caption{Aggregated users played per track.}
\label{table:6}
\begin{center}
\begin{tabular}{c c c c}
\textbf{track\_id} & \textbf{count} & \textbf{user\_id} & \textbf{user\_id}\\
114fd187\-dfed\-3fcd... & 2 &  662ed5aa9df25a7b43... &  663jd5aa9df25a3b...\\
063ed02c\-53d8\-3fd2... & 2 &  aae7d3b35d7fca7be0... &  762ed56aa9d65a7b...\\
\end{tabular}
\end{center}
\end{table}

\section{Technological Stack}

\subsection{Google: TensorFlow\texttrademark}

"TensorFlow\texttrademark is an open source software library for numerical computation using data flow graphs. Nodes in the graph represent mathematical operations, while the graph edges represent the multidimensional data arrays (tensors) communicated between them. The flexible architecture allows you to deploy computation to one or more CPUs or GPUs in a desktop, server, or mobile device with a single API." \cite{tensorflow}

\subsection{Dato: GraphLab Create}

"GraphLab Create is an extensible machine learning framework that enables developers and data scientists to easily build and deploy intelligent applications and services at scale. It includes distributed data structures and rich libraries for data transformation and manipulation, scalable task-oriented machine learning toolkits for creating, evaluating, and improving machine learning models, data and model visualization for all aspects of development, and a client to define and deploy both distributed batch jobs to Dato Distributed™ as well as real-time machine learning services to Dato Predictive Services™. It is designed for end-to-end developer productivity, scale, and the variety and complexity of real-world data." \cite{graphlabcreate}

\subsection{Pentaho: Data Integration}

"Pentaho Data Integration prepares and blends data to create a complete picture of your business that drives actionable insights. The platform delivers accurate, analytics-ready data to end users from any source. With visual tools to eliminate coding and complexity, Pentaho puts big data and all data sources at the fingertips of business and IT users." \cite{pentahodataintegration}

\section{Methodology}

\subsection{Item Similarity Model}

The item similarity model calculates the similarity between items using the historical data representing the interaction between the users and the tracks. Based on the similarity between track \textit{a} and \textit{b}, it recommends a track \textit{c} for user \textit{u} using a weighted average of the user's previous interactions.

Because the \#nowplaying dataset does not consist of rating information, the item similarity model uses Jaccard similarity to calculate the similarity between two tracks, which is an ideal choice when the information available only indicates whether the user listened to a song or not and not the rating a user awarded a song.

Jaccard similarity can be used to measure the similarity between two sets of tracks. In this model, calculating the Jaccard similarity between two tracks is achieved as follows:

\begin{equation}
    JS(a,b) = \frac{|U_a \cap U_b|}{|U_a \cup U_b|}
\end{equation}

where \textit{U\textsubscript{i}} is the set of users who listened to track \textit{i}.

\subsection{Popularity-based Recommender Model}

The Popularity-based Recommender Model determines a track's overall popularity and ranks the track based on it. The a track is recommended to a user, the track is scored based on the number of times it appears in the dataset. In this model, the track scores are identical for all users, which means the Popularity Recommender Model does not provide tailored recommendations. However, it can be used as a model for new users in an attempt to tackle the "cold start" problem.

\subsection{Factorization Recommender for Ranking Model}

The Factorization Recommender for Ranking model aims to learn latent factors for each user and track and uses the factors to rank recommendations in terms of the likelihood of observing (user, track) interactions.

\subsection{Collaborative Deep Learning (CDL) Model}

The Collaborative Deep Learning model is a novel tightly coupled method for Recommending Systems based on the Stacked Denoising Auto-Encoder (SDAE) deep learning model. Its basic version uses a bag-of-words representation for content features, where the CDL can simultaneously extract an effective deep feature representation from content and capture the similarity and relationship between items and users. Additionally, the deep autoencoder can be easily extended to incorporate other auxiliary information to further boost the performance.

Figure \ref{fig:cdlworkflow} describes each section of the proposed model. Our implementation is based on the Matlab code created by Wang et. al. \cite{wang2015collaborative} and the deep autoencoder implementation in Tensorflow presented by Green \cite{christofergreen2016}. First, an unsupervised pre-training is performed one layer at a time by minimizing the (cross-entrophy) error in reconstructing the input. Then, the middle layer $X_{L/2}$ serves as a bridge between the ratings and content information, being the key that enables CDL to simultaneously learn an effective feature representation and capture the similarity items. Finally, once all layers are pre-trained, the network goes through a second stage of training or supervised-fine-tuning, where the prediction error is to be minimized.

\begin{figure}[!htbp]
\begin{center}
\fbox{\includegraphics[width=13.7cm]{figures/cdl}}
\end{center}
\caption{Collaborative Deep Learning Model workflow.}
\label{fig:cdlworkflow}
\end{figure}

\section{Evaluation}

For evaluating our baseline recommender systems, we select 3/4 of the extracted sample data and set it as the training set while the remaining data is set as the test set. We use recall as the performance measure as the rating information is in the form of implicit feedback. Figure  \ref{fig:recalleval} presents the evaluation of recall over the top K items with K=10, and where results are averaged over all users. The rank factorization model is considered the most stable and better model as the recall increases with the number of top recommendations needed. Althought the popularity model performs better for K\textgreater6 but lower it is unstable for lower values of K as the recall value fluctuates. Additionally, the mean average precision was also evaluated for each model. Figure \ref{fig:mapeval} outlines once again the the factorization model is more stable with increasing K.

\begin{figure}[!hbtp]
\begin{center}
\fbox{\includegraphics[width=13.1cm]{figures/recall}}
\end{center}
\caption{Recall Evaluation over Top-K items.}
\label{fig:recalleval}
\end{figure}

\begin{figure}[!htbp]
\begin{center}
\fbox{\includegraphics[width=13.1cm]{figures/map}}
\end{center}
\caption{Mean Average Precision Evaluation over Top-K items.}
\label{fig:mapeval}
\end{figure}

\section{Results}

\subsection{Item Similarity Model}

When run, the Item Similarity Model recommends 10 tracks for each user. Additionally, using the model, similar tracks can also be retrieved. Table \ref{table:7} presents an example of 5 track recommendations generated by the Item Similarity Model, with Rock being a predominant genre. Table \ref{table:8} presents an example of 5 similar tracks generated by the Item Similarity Model, indicating poor similarity accuracy.

\begin{table}[!htbp]
\caption{Example of 5 track recommendations generated by the Item Similarity Model.}
\label{table:7}
\begin{center}
\begin{tabular}{l l l}
\multicolumn{1}{c}{\bf Artist} & \multicolumn{1}{c}{\bf Track} & \multicolumn{1}{c}{\bf Genre}
\\ \hline \\
James Morrison & You Make It Real     & Pop Rock\\
Prefab Sprout & King of Rock and Roll & Pop, Rock, Sophisti-Pop\\
Curtis Stigers & I Wonder Why         & Jazz, Soft Rock\\
Westlife & You Raise Me Up            & Pop\\
Toto & I'll Be Over You               & Soft Rock\\
\end{tabular}
\end{center}
\end{table}

\begin{table}[ht]
\caption{Example of 5 similar tracks generated by the Item Similarity Model.}
\label{table:8}
\begin{center}
\begin{tabular}{p{2cm} p{4.6cm} p{2cm} p{2.5cm}}
\multicolumn{1}{c}{\bf Track} & \multicolumn{1}{c}{\bf Similar Track} & \multicolumn{1}{c}{\bf Track Genre} & \multicolumn{1}{c}{\bf Similar Track Genre}
\\ \hline \\
Iris by Iris & Rockstar by Nickelback & Hard Rock & Southern Rock\\
Iris by Iris & Antenna by Fuse ODG & Hard Rock & Afrobeats, Dance\\
Iris by Iris & All I Wanna Do by Sheryl Crow & Hard Rock & Pop\\
Iris by Iris & Vertigo by Vertigo & Hard Rock & Alternative rock\\
Iris by Iris & Boomerang by Boomerang & Hard Rock & Electronic, Latin, Funk/Soul, Pop\\
\end{tabular}
\end{center}
\end{table}

\subsection{Popularity-based Recommender Model}

When run, the Popularity-based Recommender Model recommends 10 tracks for each user. Additionally, using the model, similar tracks can also be retrieved. Table \ref{table:9} presents an example of 5 track recommendations generated by the Popularity-based Recommender Model, with Electronic being a predominant genre. Table \ref{table:10} presents an example of 5 similar tracks generated by the Popularity-based Recommender Model, indicating significantly poor similarity accuracy.

\begin{table}[!htbp]
\caption{Example of 5 track recommendations generated by the Popularity-based Recommender Model.}
\label{table:9}
\begin{center}
\begin{tabular}{l l l}
\multicolumn{1}{c}{\bf Artist} & \multicolumn{1}{c}{\bf Track} & \multicolumn{1}{c}{\bf Genre}
\\ \hline \\
ON              & I               & Electronic, Rock\\
NP              & I               & Electronic\\
A               & A               & Alternative Rock\\
Ne              & Yo              & Electronic\\
Various Artists & Various Artists & N/A\\
\end{tabular}
\end{center}
\end{table}

\begin{table}[!htbp]
\caption{Example of 5 similar tracks generated by the Popularity-based Recommender Model.}
\label{table:10}
\begin{center}
\begin{tabular}{p{2.8cm} p{4cm} p{1.5cm} p{3cm}}
\multicolumn{1}{c}{\bf Track} & \multicolumn{1}{c}{\bf Similar Track} & \multicolumn{1}{c}{\bf Track Genre} & \multicolumn{1}{c}{\bf Similar Track Genre}
\\ \hline \\
2 Times by Ann Lee & Io non sono qui by Ushas & Eurodance & Hard Rock\\
2 Times by Ann Lee & Cinta Jangan Kau Pergi by Sheila Majid & Eurodance & Jazz, Funk/Soul, Pop\\
2 Times by Ann Lee & Seal Your Fate by Obituary & Eurodance & Rock\\
2 Times by Ann Lee & No Man Is an Island by Tenth Avenue North & Eurodance & Rock, Pop\\
2 Times by Ann Lee & My Life by Richie Spice & Eurodance & Reggae\\
\end{tabular}
\end{center}
\end{table}

\subsection{Factorization Recommender for Ranking Model}

When run, the Factorization Recommender for Ranking Model recommends 10 tracks for each user. Additionally, using the model, similar tracks can also be retrieved. Table \ref{table:11} presents an example of 5 track recommendations generated by the Factorization Recommender for Ranking Model, with Rock being somehow a predominant genre. Table \ref{table:12} presents an example of 5 similar tracks generated by the Factorization Recommender for Ranking Model, indicating poor similarity accuracy.

\begin{table}[!htbp]
\caption{Example of 5 track recommendations generated by the Factorization Recommender for Ranking Model.}
\label{table:11}
\begin{center}
\begin{tabular}{l l l}
\multicolumn{1}{c}{\bf Artist} & \multicolumn{1}{c}{\bf Track} & \multicolumn{1}{c}{\bf Genre}
\\ \hline \\
A            & A                 & Alternative Rock\\
Ne           & Yo                & Electronic\\
Ed Sheeran   & She               & Folk\\
Black Cherry & Acid Black Cherry & Rock\\
Ten Sharp    & Stay              & Pop Rock, Prog Rock\\
\end{tabular}
\end{center}
\end{table}

\begin{table}[!htbp]
\caption{Example of 5 similar tracks generated by the Factorization Recommender for Ranking Model.}
\label{table:12}
\begin{center}
\begin{tabular}{p{2.2cm} p{3.6cm} p{3.2cm} p{3.3cm}}
\multicolumn{1}{c}{\bf Track} & \multicolumn{1}{c}{\bf Similar Track} & \multicolumn{1}{c}{\bf Track Genre} & \multicolumn{1}{c}{\bf Similar Track Genre}
\\ \hline \\

Just Say Yes by Snow Patrol & It's Raining Men by The Weather Girls & Synthpop, Electronica & Hi-NRG, Post-disco\\
Just Say Yes by Snow Patrol & Catfish Blues by Robert Petway & Synthpop, Electronica & Blues\\
Just Say Yes by Snow Patrol & Amor Depredador by The Mills & Synthpop, Electronica & Latin Rock, Alternative rock\\
Just Say Yes by Snow Patrol & Damn It Feels Good to Be a Gangsta by Geto Boys & Synthpop, Electronica & Gangsta Rap, Southern Hip Hop, Horrorcore\\
Just Say Yes by Snow Patrol & Walking On The Sun by Smash Mouth & Synthpop, Electronica & Ska Pop, Psychedelic Rock\\

\end{tabular}
\end{center}
\end{table}

\subsection{Collaborative Deep Learning (CDL) Model}

Because of the limited time period we had available to finish this assignment, we were not able to finish the integration of the deep autoencoder implementation with the rating matrix factorization (the latter is an implementation of Wang et. al.\cite{wang2015collaborative}). However, in our GitHub repository, we include the developed code using TensorFlow in the \textit{cdl} folder, where we set up a Stacked Denoising Autoencoder configured with 2 hidden layers of 200 and 50 neurons, a dropout module to learn stronger features, and a Gradient Descent optimizer, even though a Momentum optimizer would be a better algorithm (easy to use in TensorFlow) that can be used to alleviate the local optimum problem.

\section{Future Work}

As CDL is actually a more general framework which can also admit other deep learning models, a further investigation could be done on integrating the current solution with existing models such as Boltzmann machines, Recurrent Neural Networks, and Convolutional Neural Networks. Additionally, refining the feature representation by adding audio signals from track previews to boost the prediction accuracy, as applied by Spotify \cite{van2013deep} is another potential future focus.

\clearpage
\printbibliography
\end{document}


text:
ConPaaS is an open-source runtime environment for hosting applications
in Cloud infrastructures~\cite{conpaasIC}.  Within the Cloud computing
paradigm, ConPaaS belongs to the platform-as-a-service family, in
which a variety of systems aim to simplify the deployment of
applications in the Cloud.

%Using ConPaaS,  developers can now focus their attention on application-specific concerns rather than making their applications suitable for the cloud.

\subsection*{Architecture}

In ConPaaS, an application is designed as a composition of one or more
elastic and distributed \emph{services}. Each service is dedicated to
host a particular type of functionality of an application. ConPaaS
currently supports seven different types of services: two web
application hosting services respectively specialized for hosting PHP
and JSP applications; a MySQL database service; a NoSQL database
service built around the Scalarix key-value store; a MapReduce
service; a TaskFarming service for high-performance batch
processing; and a shared file system service.
%Figure~\ref{arch} shows ConPaaS hosting an application composed of a PhP service and a MySQL service, that could represents the architecture of any today's web application.

Each ConPaaS service is made up of one manager virtual machine (VM)
and a number of agent VMs.

\begin{figure*}[Ht]
\begin{center}
\includegraphics[width=0.6\textwidth, height=6.2cm]{./images/conpaasSystemArch_2}
\end{center}
\vspace{-5mm}
\caption{ConPaaS system architecture.}
\label{arch}
\end{figure*}

\begin{description}
\item[Agent:] The agent VMs host the necessary components to provide the service-specific functionality. Based on the performance requirements or the application workload, agent VMs can be started or stopped on demand. Thus, as an example, the minimal configuration of the PHP web hosting service consists of a single agent VM. If necessary,
the service can grow to multiple agent VMs hosting its
components: load balancer for distributing the incoming traffic, web
servers for static pages and/or PHP servers for dynamic pages.
\item[Manager:] Each service is controlled by one manager VM. The manager is in charge of centralizing monitoring data, controlling the allocation of resources assigned to the service, and coordinating reconfigurations so no loss of service is experienced when adding or removing resources.
\end{description}

Figure~\ref{arch} shows the architecture of the ConPaaS deployment for
a typical PHP web application backed by a MySQL database. The
application is deployed using two ConPaaS services: the PHP service
and the MySQL service.

%On the other hand, in ConPaaS, there are two types of traffic: application and management. The application traffic is based on requests from end users willing to access the application, so that is addressed to the agents hosting such application.  On the other hand, the management traffic is directed from the service administrators to their service managers, and from those to the agents.  Service administrators can manage their services using a graphical front-end or a command-line tool.

\subsection*{Elasticity}

As illustrated in Figure~\ref{arch}, the manager VM of each ConPaaS
service includes a performance monitoring and a resource provisioning
system.

%ConPaaS incorporates a scalable distributed monitoring engine which is based on the Ganglia~\cite{ganglia} monitoring system. Ganglia consists of a server component (gmetad) that aggregates monitoring statistics from various VMs, and a reporting agent (gmond) which runs inside each VM. By default, Ganglia monitors only system-level metrics such as disk, CPU, memory and network usage. Unfortunately, these metrics often do not provide enough information about system performance due to the heterogeneity of the applications. As a consequence, in ConPaaS, we enhanced ganglia to also monitor service workloads by enhancing the reporting agent to track service-specific logs at runtime, and report statistics over a reporting period of 5 minutes. For instance, the PhP service includes new ganglia metrics that report statistics about the response time and request rate for static and dynamic user requests, respectively. Once the monitoring data is collected from the agents VMs, the resource provisioning  algorithm decides whether to trigger scaling operations based on this data.

The monitoring component is based on Ganglia~\cite{ganglia}, a
scalable distributed monitoring system. The monitoring data is
collected by the manager VM, which runs a so-called Ganglia
meta-daemon. We implemented modules that extend Ganglia's standard set
of monitoring metrics, by adding a number of service-specific
metrics. In particular for the PHP service, we added monitoring
metrics for measuring the request rate and response times of static
and dynamic documents.

%Unlike of implementing traditional trigger-based provisioning systems that scale services independently of whether they are part of an application. In ConPaaS, we designed a performance control model for multi-service applications. Using this model, the performance requirements are only imposed to the front-end service, while all the services collaborate in order to guarantee them. It improves the effectiveness and accuracy of the scaling decisions. Indeed, this allows to rapidly detect performance bottlenecks in applications, and thereby to minimize the resource consumption.

Each ConPaaS service can plug-in its own automatic resource
provisioning policies, taking into account specificities of the
service such as the structure of the service deployment, the
complexity of the requests and service-specific monitoring data. So
far our focus has been on the web hosting service, for which we
implemented a number of automatic resource provisioning policies.

% Instead of implementing simple performance-based triggers which provision each tier individually based on %its own performance, we designed a performance control model for the entire application.

%Ganglia stores monitored statistics in a custom roundrobin database (RRD); our monitoring engine can track %resource usage and application workload statistics by periodically querying this database and determining %whether any user-specified thresholds have been exceeded (e.g., thresholds on SLA violations, request %drops, or resource utilization).


text:
\section{Introduction}
After the PST meeting Jan 2020 there was a request for some simple instructions for the construction papers.
This technote addresses the request.

\section{\LaTeX}
To work locally on a paper it is assumed you have \LaTeX set up.
Get it from \url{https://www.tug.org/texlive/quickinstall.html}

After installation in a terminal you should be able to find \texttt{latexmk}.

\textbf{Note:} If you had a terminal open when you installed tex then it may not show up in that terminal - open a new one.

\section{The Papers}

All of the construction papers have been created in github repositories already.
See \url{https://confluence.lsstcorp.org/display/LSSTPO/LSST+Construction+Papers}.

This are all part of the DM technote infrastructure see \url{https://sqr-000.lsst.io/}.

\subsection{Viewing papers}
All the papers are rendered after each push to github. Use the handle (PSTN-NNN) with ".lsst.io" to get the master
version. e.g. \url{PSTN-017.lsst.io}.

\textbf{Note:} Usually work in progress is on a branch - you can view all branches bu clicking on "Change Version" or going to the "/v" url e.g. \url{https://pstn-017.lsst.io/v}.  In this case the working version is \url{https://pstn-017.lsst.io/v/DM-23153} which coincidentally relates to the jira ticket \jira{DM-23153}.

\subsection{Getting a paper to work on}
Use git to \texttt{clone} the paper you want e.g.
\begin{verbatim}
 git clone --recurse-submodules https://github.com/lsst-pst/pstn-020
\end{verbatim}

If you already have a cloned repo check if the lsst-texmf folder exists and is populated, if its empty
you do not have the sub module get it by executing:

\begin{verbatim}
  git submodule update --init --recursive
\end{verbatim}

in the repo directory.

Normally we work on branches so at this point it would be good to either checkout an existing branch or
create your own for your modifications create a branch by executing in the repo:
\begin{verbatim}
  git checkout -b /u/USERID/mydraft
\end{verbatim}
Where your USERID by convention is your LSST USERID and mydraft can be any identifier.

To see branches use \texttt{git branch -s}.

\subsection{Making changes}
You may edit the tex files with any editor you like. Some people like texworks, other sublime.
When you have some changes you need to put them in github. Hopefully you already made a branch (see above).
You must both commit and push your changes - you may commit as often as you wish (even in flight) but your repo is
not put on github until you push these are the commands:
\begin{verbatim}
  git commit -am "I did stuff "
  git push
\end{verbatim}

Make sure your push worked and you did not get any merge conflicts.

\section{Running local build and other tools}
To build you local file use the Makefile in the repo simply type \texttt{make}.

Because you have the DM texmf there are other tools included as follows.
The full DM docs are on \url{https://lsst-texmf.lsst.io/}.

\subsection{Authors}
The author list is generated form the author database \footnote{lsst-texmf/etc/authordb.yaml} - you list the relevant id in \texttt{authors.yaml}.
If you update authors.yaml run \texttt{make authors.tex}.

\subsection{Bibliography}
There are several bibliography files in \url{lsst-texmf/texmf/bibtex/bib/} for project documents and ADS papers.
So you may \texttt{\\cite} project handles like \cite{LSE-61}, \cite{PSTN-017} and ADS refs like \texttt{2019arXiv190713060O}\footnote{listed in refs\_ads.bib} \cite{2019arXiv190713060O}.

Additions to the general bibliography should be done as a Pull Request to \url{https://github.com/lsst/lsst-texmf/}.

See also \url{https://lsst-texmf.lsst.io/lsstdoc.html#bibliographies}.

You may also add refs to local.bib.
\subsection{Acronyms}

The generateAcronyms script can deal with acronyms or glossaries. It scans your tex and finds items that should be in the
acronym list and generates acronyms.tex for you.
You need to run it on its own to see the messages such as undefined terms run it using \texttt{make acronyms.tex}.

See also \url{https://lsst-texmf.lsst.io/lsstdoc.html#acronyms-or-glossaries}.