



\section{Introduction}
This format is to be used for submissions that are published in the
conference publications. We wish to give this volume a consistent,
high-quality appearance. We therefore ask that authors follow some
simple guidelines. In essence, you should format your paper exactly
like this document. The easiest way to do this is to replace the
content with your own material.


\section{ACM Copyrights \& Permission}
Accepted extended abstracts and papers will be distributed in the
Conference Publications. They will also be placed in the ACM Digital
Library, where they will remain accessible to thousands of researchers
and practitioners worldwide. To view the ACM's copyright and
permissions policy, see:
\url{http://www.acm.org/publications/policies/copyright_policy}.


\section{Page Size}
All SIGCHI submissions should be US letter (8.5 $\times$ 11
inches). US Letter is the standard option used by this \LaTeX\
template.

\section{Text Formatting}
Please use an 8.5-point Verdana font, or other sans serifs font as
close as possible in appearance to Verdana in which these guidelines
have been set. Arial 9-point font is a reasonable substitute for
Verdana as it has a similar x-height. Please use serif or
non-proportional fonts only for special purposes, such as
distinguishing \texttt{source code} text.

\subsubsection{Text styles}
The \LaTeX\ template facilitates text formatting for normal (for body
text); heading 1, heading 2, heading 3; bullet list; numbered list;
caption; annotation (for notes in the narrow left margin); and
references (for bibliographic entries). Additionally, here is an
example of footnoted\footnote{Use footnotes sparingly, if at all.}
text. As stated in the footnote, footnotes should rarely be used.

\begin{table}
  \caption{Table captions should be placed above the table. We
    recommend table lines be 1 point, 25\% black. Minimize use of
    table grid lines.}
  \label{tab:table1}
  \begin{tabular}{l r r r}
    & & \multicolumn{2}{c}{\small{\textbf{Test Conditions}}} \\
    \cmidrule(r){3-4}
    {\small\textit{Name}}
    & {\small \textit{First}}
      & {\small \textit{Second}}
    & {\small \textit{Final}} \\
    \midrule
    Marsden & 223.0 & 44 & 432,321 \\
    Nass & 22.2 & 16 & 234,333 \\
    Borriello & 22.9 & 11 & 93,123 \\
    Karat & 34.9 & 2200 & 103,322 \\
     \bottomrule
  \end{tabular}
\end{table}


\subsection{Language, style, and content}
The written and spoken language of SIGCHI is English. Spelling and
punctuation may use any dialect of English (e.g., British, Canadian,
US, etc.) provided this is done consistently. Hyphenation is
optional. To ensure suitability for an international audience, please
pay attention to the following:
\begin{itemize}
\item Write in a straightforward style. Use simple sentence
  structure. Try to avoid long sentences and complex sentence
  structures. Use semicolons carefully.
\item Use common and basic vocabulary (e.g., use the word ``unusual''
  rather than the word ``arcane'').
\item Briefly define or explain all technical terms. The terminology
  common to your practice/discipline may be different in other design
  practices/disciplines.
\item Spell out all acronyms the first time they are used in your
  text. For example, ``World Wide Web (WWW)''.
\item Explain local references (e.g., not everyone knows all city
  names in a particular country).
\item Explain ``insider'' comments. Ensure that your whole audience
  understands any reference whose meaning you do not describe (e.g.,
  do not assume that everyone has used a Macintosh or a particular
  application).
\item Explain colloquial language and puns. Understanding phrases like
  ``red herring'' requires a cultural knowledge of English. Humor and
  irony are difficult to translate.
\item Use unambiguous forms for culturally localized concepts, such as
  times, dates, currencies, and numbers (e.g., ``1-5- 97'' or
  ``5/1/97'' may mean 5 January or 1 May, and ``seven o'clock'' may
  mean 7:00 am or 19:00). For currencies, indicate equivalences:
  ``Participants were paid {\fontfamily{txr}\selectfont \textwon}
  25,000, or roughly US \$22.''
\item Be careful with the use of gender-specific pronouns (he, she)
  and other gender-specific words (chairman, manpower,
  man-months). Use inclusive language (e.g., she or he, they, chair,
  staff, staff-hours, person-years) that is gender-neutral. If
  necessary, you may be able to use ``he'' and ``she'' in alternating
  sentences, so that the two genders occur equally
  often~\cite{Schwartz:1995:GBF}.
\item If possible, use the full (extended) alphabetic character set
  for names of persons, institutions, and places (e.g.,
  Gr{\o}nb{\ae}k, Lafreni\'ere, S\'anchez, Nguy{\~{\^{e}}}n,
  Universit{\"a}t, Wei{\ss}enbach, Z{\"u}llighoven, \r{A}rhus, etc.).
  These characters are already included in most versions and variants
  of Times, Helvetica, and Arial fonts.
\end{itemize}


\begin{marginfigure}
    \includegraphics[width=\marginparwidth]{cats}\Description{An image
      of tesselated cats}
    \caption{In this image, the cats are tessellated within a square
      frame. Images should also have captions and be within the
      boundaries of the sidebar on page~\pageref{bar:sidebar}. Photo:
      \cczero~jofish on Flickr.}
    \label{fig:marginfig}
\end{marginfigure}

\section{Figures}
The examples on this and following pages should help you get a feel
for how screen-shots and other figures should be placed in the
template. Your document may use color figures (see
Figures~\ref{fig:sample}), which are included in the page limit; the
figures must be usable when printed in black and white. You can use
the \texttt{marginfigure} environment to insert figures in the (left) margin
of the document (see Figure~\ref{fig:marginfig}). Finally, be sure to
make images large enough so the important details are legible and
clear (see Figure~\ref{fig:map}).

\begin{figure*}
  \includegraphics[width=\fulltextwidth]{map}\Description{A world map}
  \caption{In this image, the map maximizes use of space.
    Note that \LaTeX\ tends to render large figures on a
    dedicated page. Image: \ccbynd~ayman on Flickr.}~\label{fig:map}
\end{figure*}


\section{Tables}


\begin{margintable}
    \caption{A simple narrow table in the left margin
      space.}
    \label{tab:table2}
    \begin{tabular}{r r l}
      & {\small \textbf{First}}
      & {\small \textbf{Location}} \\
      \toprule
      Child & 22.5 & Melbourne \\
      Adult & 22.0 & Bogot\'a \\
      \midrule
      Gene & 22.0 & Palo Alto \\
      John & 34.5 & Minneapolis \\
      \bottomrule
    \end{tabular}
\end{margintable}

You man use tables inline with the text (see Table~\ref{tab:table1})
or within the margin as shown in Table~\ref{tab:table2}. Try to
minimize the use of lines (especially vertical lines). \LaTeX\ will
set the table font and captions sizes correctly; the latter must
remain unchanged.

\section{Accessibility}
The Executive Council of SIGCHI has committed to making SIGCHI
conferences more inclusive for researchers, practitioners, and
educators with disabilities. As a part of this goal, the all authors
are asked to work on improving the accessibility of their
submissions. Specifically, we encourage authors to carry out the
following five steps:
\begin{itemize}
\item Add alternative text to all figures
\item Mark table headings
\item Generate a tagged PDF
\item Verify the default language
\item Set the tab order to ``Use Document Structure''
\end{itemize}

For links to instructions and resources, please see:
\url{http://chi2016.acm.org/accessibility}

Unfortunately good tools do not yet exist to create tagged PDF files
from Latex (see the ongoing effort at
\url{http://tug.org/twg/accessibility/}). \LaTeX\ users will need to
carry out all of the above steps in the PDF directly using Adobe
Acrobat, after the PDF has been generated.

For more information and links to instructions and resources, please
see:
\url{http://chi2016.acm.org/accessibility} and
\url{http://tug.org/twg/accessibility/}.


\section{Producing and Testing PDF Files}

We recommend that you produce a PDF version of your submission well
before the final deadline. Your PDF file must be ACM DL Compliant and
meet stated requirements,
\url{http://www.sheridanprinting.com/sigchi/ACM-SIG-distilling-settings.htm}.

\begin{sidebar}
  So long as you don't type outside the right
  margin or bleed into the gutter, it's okay to put annotations over
  here on the left. You may need to have
  to manually align the margin paragraphs to your \LaTeX\ floats using
  the \texttt{{\textbackslash}vspace{}} command.
\end{sidebar}


Test your PDF file by viewing or printing it with the same software we
will use when we receive it, Adobe Acrobat Reader Version 10. This is
widely available at no cost. Note that most reviewers will use a North
American/European version of Acrobat reader, so please check your PDF
accordingly.

\begin{acks}
  We thank all the volunteers, publications support, staff, and
  authors who wrote and provided helpful comments on previous versions
  of this document. As well authors 1, 2, and 3 gratefully acknowledge
  the grant from \grantsponsor{001}{NSF}{}
  (\#\grantnum{001}{1234-2222-ABC}). Author 4 for example may want to
  acknowledge a supervisor/manager from their original employer. This
  whole paragraph is just for example. Some of the references cited in
  this paper are included for illustrative purposes only.
\end{acks}

\section{References Format}

Your references should be published materials accessible to the
public. Internal technical reports may be cited only if they are
easily accessible and may be obtained by any reader for a nominal fee.
Proprietary information may not be cited. Private communications
should be acknowledged in the main text, not referenced (e.g.,
[Golovchinsky, personal communication]). References must be the same
font size as other body text. References should be in alphabetical
order by last name of first author. Use a numbered list of references
at the end of the article, ordered alphabetically by last name of
first author, and referenced by numbers in brackets. For papers from
conference proceedings, include the title of the paper and the name of
the conference. Do not include the location of the conference or the
exact date; do include the page numbers if available.

References should be in ACM citation format:
\url{http://www.acm.org/publications/submissions/latex_style}.  This
includes citations to Internet
resources~\cite{CHINOSAUR:venue,cavender:writing,psy:gangnam}
according to ACM format, although it is often appropriate to include
URLs directly in the text, as above. Example reference formatting for
individual journal articles~\cite{ethics}, articles in conference
proceedings~\cite{Klemmer:2002:WSC:503376.503378},
books~\cite{Schwartz:1995:GBF}, theses~\cite{sutherland:sketchpad},
book chapters~\cite{winner:politics}, an entire journal
issue~\cite{kaye:puc},
websites~\cite{acm_categories,cavender:writing},
tweets~\cite{CHINOSAUR:venue}, patents~\cite{heilig:sensorama},
games~\cite{supermetroid:snes}, and
online videos~\cite{psy:gangnam} is given here.  See the examples of
citations at the end of this document and in the accompanying
\texttt{BibTeX} document. This formatting is a edited version of the
format automatically generated by the ACM Digital Library
(\url{http://dl.acm.org}) as ``ACM Ref''. DOI and/or URL links are
optional but encouraged as are full first names. Note that the
Hyperlink style used throughout this document uses blue links;
however, URLs in the references section may optionally appear in
black.












\section{Introduction}

The \textit{proceedings} are the records of a conference.\footnote{This
  is a footnote}  ACM seeks
to give these conference by-products a uniform, high-quality
appearance.  To do this, ACM has some rigid requirements for the
format of the proceedings documents: there is a specified format
(balanced double columns), a specified set of fonts (Arial or
Helvetica and Times Roman) in certain specified sizes, a specified
live area, centered on the page, specified size of margins, specified
column width and gutter size.

\section{The Body of The Paper}
Typically, the body of a paper is organized into a hierarchical
structure, with numbered or unnumbered headings for sections,
subsections, sub-subsections, and even smaller sections.  The command
\texttt{{\char'134}section} that precedes this paragraph is part of
such a hierarchy.\footnote{This is a footnote.} \LaTeX\ handles the
numbering and placement of these headings for you, when you use the
appropriate heading commands around the titles of the headings.  If
you want a sub-subsection or smaller part to be unnumbered in your
output, simply append an asterisk to the command name.  Examples of
both numbered and unnumbered headings will appear throughout the
balance of this sample document.

Because the entire article is contained in the \textbf{document}
environment, you can indicate the start of a new paragraph with a
blank line in your input file; that is why this sentence forms a
separate paragraph.

\subsection{Type Changes and {\itshape Special} Characters}

We have already seen several typeface changes in this sample.  You can
indicate italicized words or phrases in your text with the command
\texttt{{\char'134}textit}; emboldening with the command
\texttt{{\char'134}textbf} and typewriter-style (for instance, for
computer code) with \texttt{{\char'134}texttt}.  But remember, you do
not have to indicate typestyle changes when such changes are part of
the \textit{structural} elements of your article; for instance, the
heading of this subsection will be in a sans serif\footnote{Another
  footnote here.  Let's make this a rather long one to see how it
  looks.} typeface, but that is handled by the document class file.
Take care with the use of\footnote{Another footnote.}  the
curly braces in typeface changes; they mark the beginning and end of
the text that is to be in the different typeface.

You can use whatever symbols, accented characters, or non-English
characters you need anywhere in your document; you can find a complete
list of what is available in the \textit{\LaTeX\ User's Guide}
\cite{Lamport:LaTeX}.

\subsection{Math Equations}
You may want to display math equations in three distinct styles:
inline, numbered or non-numbered display.  Each of
the three are discussed in the next sections.

\subsubsection{Inline (In-text) Equations}
A formula that appears in the running text is called an
inline or in-text formula.  It is produced by the
\textbf{math} environment, which can be
invoked with the usual \texttt{{\char'134}begin\,\ldots{\char'134}end}
construction or with the short form \texttt{\$\,\ldots\$}. You
can use any of the symbols and structures,
from $\alpha$ to $\omega$, available in
\LaTeX~\cite{Lamport:LaTeX}; this section will simply show a
few examples of in-text equations in context. Notice how
this equation:
\begin{math}
  \lim_{n\rightarrow \infty}x=0
\end{math},
set here in in-line math style, looks slightly different when
set in display style.  (See next section).

\subsubsection{Display Equations}
A numbered display equation---one set off by vertical space from the
text and centered horizontally---is produced by the \textbf{equation}
environment. An unnumbered display equation is produced by the
\textbf{displaymath} environment.

Again, in either environment, you can use any of the symbols
and structures available in \LaTeX\@; this section will just
give a couple of examples of display equations in context.
First, consider the equation, shown as an inline equation above:
\begin{equation}
  \lim_{n\rightarrow \infty}x=0
\end{equation}
Notice how it is formatted somewhat differently in
the \textbf{displaymath}
environment.  Now, we'll enter an unnumbered equation:
\begin{displaymath}
  \sum_{i=0}^{\infty} x + 1
\end{displaymath}
and follow it with another numbered equation:
\begin{equation}
  \sum_{i=0}^{\infty}x_i=\int_{0}^{\pi+2} f
\end{equation}
just to demonstrate \LaTeX's able handling of numbering.

\subsection{Citations}
Citations to articles~\cite{bowman:reasoning,
clark:pct, braams:babel, herlihy:methodology},
conference proceedings~\cite{clark:pct} or maybe
books \cite{Lamport:LaTeX, salas:calculus} listed
in the Bibliography section of your
article will occur throughout the text of your article.
You should use BibTeX to automatically produce this bibliography;
you simply need to insert one of several citation commands with
a key of the item cited in the proper location in
the \texttt{.tex} file~\cite{Lamport:LaTeX}.
The key is a short reference you invent to uniquely
identify each work; in this sample document, the key is
the first author's surname and a
word from the title.  This identifying key is included
with each item in the \texttt{.bib} file for your article.

The details of the construction of the \texttt{.bib} file
are beyond the scope of this sample document, but more
information can be found in the \textit{Author's Guide},
and exhaustive details in the \textit{\LaTeX\ User's
Guide} by Lamport~\shortcite{Lamport:LaTeX}.

This article shows only the plainest form
of the citation command, using \texttt{{\char'134}cite}.

Some examples.  A paginated journal article \cite{Abril07}, an enumerated
journal article \cite{Cohen07}, a reference to an entire issue \cite{JCohen96},
a monograph (whole book) \cite{Kosiur01}, a monograph/whole book in a series (see 2a in spec. document)
\cite{Harel79}, a divisible-book such as an anthology or compilation \cite{Editor00}
followed by the same example, however we only output the series if the volume number is given
\cite{Editor00a} (so Editor00a's series should NOT be present since it has no vol. no.),
a chapter in a divisible book \cite{Spector90}, a chapter in a divisible book
in a series \cite{Douglass98}, a multi-volume work as book \cite{Knuth97},
an article in a proceedings (of a conference, symposium, workshop for example)
(paginated proceedings article) \cite{Andler79}, a proceedings article
with all possible elements \cite{Smith10}, an example of an enumerated
proceedings article \cite{VanGundy07},
an informally published work \cite{Harel78}, a doctoral dissertation \cite{Clarkson85},
a master's thesis: \cite{anisi03}, an online document / world wide web
resource \cite{Thornburg01, Ablamowicz07, Poker06}, a video game (Case 1) \cite{Obama08} and (Case 2) \cite{Novak03}
and \cite{Lee05} and (Case 3) a patent \cite{JoeScientist001},
work accepted for publication \cite{rous08}, 'YYYYb'-test for prolific author
\cite{SaeediMEJ10} and \cite{SaeediJETC10}. Other cites might contain
'duplicate' DOI and URLs (some SIAM articles) \cite{Kirschmer:2010:AEI:1958016.1958018}.
Boris / Barbara Beeton: multi-volume works as books
\cite{MR781536} and \cite{MR781537}.

A couple of citations with DOIs: \cite{2004:ITE:1009386.1010128,
  Kirschmer:2010:AEI:1958016.1958018}.

Online citations: \cite{TUGInstmem, Thornburg01, CTANacmart}.


\subsection{Tables}
Because tables cannot be split across pages, the best
placement for them is typically the top of the page
nearest their initial cite.  To
ensure this proper ``floating'' placement of tables, use the
environment \textbf{table} to enclose the table's contents and
the table caption.  The contents of the table itself must go
in the \textbf{tabular} environment, to
be aligned properly in rows and columns, with the desired
horizontal and vertical rules.  Again, detailed instructions
on \textbf{tabular} material
are found in the \textit{\LaTeX\ User's Guide}.

Immediately following this sentence is the point at which
Table~\ref{tab:freq} is included in the input file; compare the
placement of the table here with the table in the printed
output of this document.

\begin{table}
  \caption{Frequency of Special Characters}
  \label{tab:freq}
  \begin{tabular}{ccl}
    \toprule
    Non-English or Math&Frequency&Comments\\
    \midrule
    \O & 1 in 1,000& For Swedish names\\
    $\pi$ & 1 in 5& Common in math\\
    \$ & 4 in 5 & Used in business\\
    $\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
  \bottomrule
\end{tabular}
\end{table}

To set a wider table, which takes up the whole width of the page's
live area, use the environment \textbf{table*} to enclose the table's
contents and the table caption.  As with a single-column table, this
wide table will ``float'' to a location deemed more desirable.
Immediately following this sentence is the point at which
Table~\ref{tab:commands} is included in the input file; again, it is
instructive to compare the placement of the table here with the table
in the printed output of this document.


\begin{table*}
  \caption{Some Typical Commands}
  \label{tab:commands}
  \begin{tabular}{ccl}
    \toprule
    Command &A Number & Comments\\
    \midrule
    \texttt{{\char'134}author} & 100& Author \\
    \texttt{{\char'134}table}& 300 & For tables\\
    \texttt{{\char'134}table*}& 400& For wider tables\\
    \bottomrule
  \end{tabular}
\end{table*}

It is strongly recommended to use the package booktabs~\cite{Fear05}
and follow its main principles of typography with respect to tables:
\begin{enumerate}
\item Never, ever use vertical rules.
\item Never use double rules.
\end{enumerate}
It is also a good idea not to overuse horizontal rules.


\subsection{Figures}

Like tables, figures cannot be split across pages; the best placement
for them is typically the top or the bottom of the page nearest their
initial cite.  To ensure this proper ``floating'' placement of
figures, use the environment \textbf{figure} to enclose the figure and
its caption.

This sample document contains examples of \texttt{.eps} files to be
displayable with \LaTeX.  If you work with pdf\LaTeX, use files in the
\texttt{.pdf} format.  Note that most modern \TeX\ systems will convert
\texttt{.eps} to \texttt{.pdf} for you on the fly.  More details on
each of these are found in the \textit{Author's Guide}.

\begin{figure}
\includegraphics{fly}\Description{A fly}
\caption{A sample black and white graphic.}
\end{figure}

\begin{figure}
\includegraphics[height=1in, width=1in]{fly}\Description{A fly image,
  to $1''\times1''$}
\caption{A sample black and white graphic
that has been resized with the \texttt{includegraphics} command.}
\end{figure}


As was the case with tables, you may want a figure that spans two
columns.  To do this, and still to ensure proper ``floating''
placement of tables, use the environment \textbf{figure*} to enclose
the figure and its caption.  And don't forget to end the environment
with \textbf{figure*}, not \textbf{figure}!

\begin{figure*}
\includegraphics{flies}\Description{Several flies, spanning two
  columns of text}
\caption{A sample black and white graphic
that needs to span two columns of text.}
\end{figure*}


\begin{figure}
\includegraphics[height=1in, width=1in]{rosette}\Description{A rosette}
\caption{A sample black and white graphic that has
been resized with the \texttt{includegraphics} command.}
\end{figure}

\subsection{Theorem-like Constructs}

Other common constructs that may occur in your article are the forms
for logical constructs like theorems, axioms, corollaries and proofs.
ACM uses two types of these constructs:  theorem-like and
definition-like.

Here is a theorem:
\begin{theorem}
  Let $f$ be continuous on $[a,b]$.  If $G$ is
  an antiderivative for $f$ on $[a,b]$, then
  \begin{displaymath}
    \int^b_af(t)\,dt = G(b) - G(a).
  \end{displaymath}
\end{theorem}

Here is a definition:
\begin{definition}
  If $z$ is irrational, then by $e^z$ we mean the
  unique number that has
  logarithm $z$:
  \begin{displaymath}
    \log e^z = z.
  \end{displaymath}
\end{definition}

The pre-defined theorem-like constructs are \textbf{theorem},
\textbf{conjecture}, \textbf{proposition}, \textbf{lemma} and
\textbf{corollary}.  The pre-defined de\-fi\-ni\-ti\-on-like constructs are
\textbf{example} and \textbf{definition}.  You can add your own
constructs using the \textsl{amsthm} interface~\cite{Amsthm15}.  The
styles used in the \verb|\theoremstyle| command are \textbf{acmplain}
and \textbf{acmdefinition}.

Another construct is \textbf{proof}, for example,

\begin{proof}
  Suppose on the contrary there exists a real number $L$ such that
  \begin{displaymath}
    \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = L.
  \end{displaymath}
  Then
  \begin{displaymath}
    l=\lim_{x\rightarrow c} f(x)
    = \lim_{x\rightarrow c}
    \left[ g{x} \cdot \frac{f(x)}{g(x)} \right ]
    = \lim_{x\rightarrow c} g(x) \cdot \lim_{x\rightarrow c}
    \frac{f(x)}{g(x)} = 0\cdot L = 0,
  \end{displaymath}
  which contradicts our assumption that $l\neq 0$.
\end{proof}

\section{Conclusions}
This paragraph will end the body of this sample document.
Remember that you might still have Acknowledgments or
Appendices; brief samples of these
follow.  There is still the Bibliography to deal with; and
we will make a disclaimer about that here: with the exception
of the reference to the \LaTeX\ book, the citations in
this paper are to articles which have nothing to
do with the present subject and are used as
examples only.




\section{Introduction}


As a new technology, Wireless Sensor Networks (WSNs) has a wide
range of applications \cite{Culler-01, Bahl-02, Akyildiz-01}, including
environment monitoring, smart buildings, medical care, industrial and
military applications. Among them, a recent trend is to develop
commercial sensor networks that require pervasive sensing of both
environment and human beings, for example, assisted living
\cite{Akyildiz-02, Harvard-01,CROSSBOW} and smart homes
\cite{Harvard-01, Adya-01,CROSSBOW}.
\begin{quote}
  ``For these applications, sensor devices are incorporated into human
  cloths \cite{Natarajan-01, Zhou-06, Bahl-02, Adya-01} for monitoring
  health related information like EKG readings, fall detection, and
  voice recognition''.
\end{quote}
While collecting all these multimedia information
\cite{Akyildiz-02} requires a high network throughput, off-the-shelf
sensor devices only provide very limited bandwidth in a single
channel: 19.2\,Kbps in MICA2 \cite{Bahl-02} and 250\,Kbps in MICAz.

In this article, we propose MMSN, abbreviation for Multifrequency
Media access control for wireless Sensor Networks. The main
contributions of this work can be summarized as follows.
\begin{itemize}
\item To the best of our knowledge, the MMSN protocol is the first
multifrequency MAC protocol especially designed for WSNs, in which
each device is equipped with a single radio transceiver and
the MAC layer packet size is very small.
\item Instead of using pairwise RTS/CTS frequency negotiation
\cite{Adya-01, Culler-01, Tzamaloukas-01, Zhou-06},
we propose lightweight frequency assignments, which are good choices
for many deployed comparatively static WSNs.
\item We develop new toggle transmission and snooping techniques to
enable a single radio transceiver in a sensor device to achieve
scalable performance, avoiding the nonscalable ``one
control channel + multiple data channels'' design \cite{Natarajan-01}.
\end{itemize}

\section{MMSN Protocol}

\subsection{Frequency Assignment}

We propose a suboptimal distribution to be used by each node, which is
easy to compute and does not depend on the number of competing
nodes. A natural candidate is an increasing geometric sequence, in
which
\begin{equation}
\label{eqn:01}
P(t)=\frac{b^{\frac{t+1}{T+1}}-b^{\frac{t}{T+1}}}{b-1},
\end{equation}
where $t=0,{\ldots}\,,T$, and $b$ is a number greater than $1$.

In our algorithm, we use the suboptimal approach for simplicity and
generality. We need to make the distribution of the selected back-off
time slice at each node conform to what is shown in
Equation~\eqref{eqn:01}. It is implemented as follows: First, a random
variable $\alpha$ with a uniform distribution within the interval $(0,
1)$ is generated on each node, then time slice $i$ is selected
according to the following equation:
\[
i=\lfloor(T+1)\log_b[\alpha(b-1)+1]\rfloor.
\]
It can be easily proven that the distribution of $i$ conforms to Equation
(\ref{eqn:01}).

So protocols \cite{Bahl-02, Culler-01,Zhou-06,Adya-01,
Tzamaloukas-01, Akyildiz-01} that use RTS/CTS
controls\footnote{RTS/CTS controls are required to be implemented by
802.11-compliant devices. They can be used as an optional mechanism
to avoid Hidden Terminal Problems in the 802.11 standard and
protocols based on those similar to \cite{Akyildiz-01} and
\cite{Adya-01}.} for frequency negotiation and reservation are not
suitable for WSN applications, even though they exhibit good
performance in general wireless ad-hoc
networks.

\subsubsection{Exclusive Frequency Assignment}


In exclusive frequency assignment, nodes first exchange their IDs
among two communication hops so that each node knows its two-hop
neighbors' IDs. In the second broadcast, each node beacons all
neighbors' IDs it has collected during the first broadcast period.

\paragraph{Eavesdropping}

Even though the even selection scheme leads to even sharing of
available frequencies among any two-hop neighborhood, it involves a
number of two-hop broadcasts. To reduce the communication cost, we
propose a lightweight eavesdropping scheme.

\subsection{Basic Notations}

As Algorithm~\ref{alg:one} states, for each frequency
number, each node calculates a random number (${\textit{Rnd}}_{\alpha}$) for
itself and a random number (${\textit{Rnd}}_{\beta}$) for each of its two-hop
neighbors with the same pseudorandom number generator.

\begin{algorithm}[t]
\SetAlgoNoLine
\KwIn{Node $\alpha$'s ID ($ID_{\alpha}$), and node $\alpha$'s
neighbors' IDs within two communication hops.}
\KwOut{The frequency number ($FreNum_{\alpha}$) node $\alpha$ gets assigned.}
$index$ = 0; $FreNum_{\alpha}$ = -1\;
\Repeat{$FreNum_{\alpha} > -1$}{
        $Rnd_{\alpha}$ = Random($ID_{\alpha}$, $index$)\;
        $Found$ = $TRUE$\;
        \For{each node $\beta$ in $\alpha$'s two communication hops
    }{
      $Rnd_{\beta}$ = Random($ID_{\beta}$, $index$)\;
      \If{($Rnd_{\alpha} < Rnd_{\beta}$) \text{or} ($Rnd_{\alpha}$ ==
          $Rnd_{\beta}$ \text{and} $ID_{\alpha} < ID_{\beta}$)\;
      }{
        $Found$ = $FALSE$; break\;
      }
        }
     \eIf{$Found$}{
           $FreNum_{\alpha}$ = $index$\;
         }{
           $index$ ++\;
     }
      }
\caption{Frequency Number Computation}
\label{alg:one}
\end{algorithm}


Bus masters are divided into two disjoint sets, $\mathcal{M}_{RT}$
and $\mathcal{M}_{NRT}$.
\begin{description}
\item[RT Masters]
$\mathcal{M}_{RT}=\{ \vec{m}_{1},\dots,\vec{m}_{n}\}$ denotes the
$n$ RT masters issuing real-time constrained requests. To model the
current request issued by an $\vec{m}_{i}$ in $\mathcal{M}_{RT}$,
three parameters---the recurrence time $(r_i)$, the service cycle
$(c_i)$, and the relative deadline $(d_i)$---are used, with their
relationships.
\item[NRT Masters]
$\mathcal{M}_{NRT}=\{ \vec{m}_{n+1},\dots,\vec{m}_{n+m}\}$ is a set
of $m$ masters issuing nonreal-time constrained requests. In our
model, each $\vec{m}_{j}$ in $\mathcal{M}_{NRT}$ needs only one
parameter, the service cycle, to model the current request it
issues.
\end{description}

Here, a question may arise, since each node has a global ID. Why
don't we just map nodes' IDs within two hops into a group of
frequency numbers and assign those numbers to all nodes within two
hops?

\section{Simulator}
\label{sec:sim}

If the model checker requests successors of a state which are not
created yet, the state space uses the simulator to create the
successors on-the-fly. To create successor states the simulator
conducts the following steps.
\begin{enumerate}
\item Load state into microcontroller model.
\item Determine assignments needed for resolving nondeterminism.
\item For each assignment.
      \begin{enumerate}
      \item either call interrupt handler or simulate effect of next instruction, or
      \item evaluate truth values of atomic propositions.
      \end{enumerate}
\item Return resulting states.
\end{enumerate}
Figure~\ref{fig:one} shows a typical microcontroller C program that
controls an automotive power window lift. The program is one of the
programs used in the case study described in Section~\ref{sec:sim}.
At first sight, the programs looks like an ANSI~C program. It
contains function calls, assignments, if clauses, and while loops.
\begin{figure}
  \includegraphics{mouse}
  \Description{A mouse}
  \caption{Code before preprocessing.}
  \label{fig:one}
\end{figure}

\subsection{Problem Formulation}

The objective of variable coalescence-based offset assignment is to find
both the coalescence scheme and the MWPC on the coalesced graph. We start
with a few definitions and lemmas for variable coalescence.

\begin{definition}[Coalesced Node (C-Node)]A C-node is a set of
live ranges (webs) in the AG or IG that are coalesced. Nodes within the same
C-node cannot interfere with each other on the IG. Before any coalescing is
done, each live range is a C-node by itself.
\end{definition}

\begin{definition}[C-AG (Coalesced Access Graph)]The C-AG is the access
graph after node coalescence, which is composed of all C-nodes and C-edges.
\end{definition}

\begin{lemma}
The C-MWPC problem is NP-complete.
\end{lemma}
\begin{proof} C-MWPC can be easily reduced to the MWPC problem assuming a
coalescence graph without any edge or a fully connected interference graph.
Therefore, each C-node is an uncoalesced live range after value separation
and C-PC is equivalent to PC. A fully connected interference graph is made
possible when all live ranges interfere with each other. Thus, the C-MWPC
problem is NP-complete.
\end{proof}

\begin{lemma}[Lemma Subhead]The solution to the C-MWPC problem is no
worse than the solution to the MWPC.
\end{lemma}
\begin{proof}
Simply, any solution to the MWPC is also a solution to the
C-MWPC. But some solutions to C-MWPC may not apply to the MWPC (if any
coalescing were made).
\end{proof}

\section{Performance Evaluation}

During all the experiments, the Geographic Forwarding (GF) by Akyildiz
et al.~\shortcite{Akyildiz-01} routing protocol is used. GF exploits
geographic information of nodes and conducts local data-forwarding to
achieve end-to-end routing. Our simulation is configured according to
the settings in Table~\ref{tab:one}. Each run lasts for 2 minutes and
repeated 100 times. For each data value we present in the results, we
also give its 90\% confidence interval.

\begin{table}%
\caption{Simulation Configuration}
\label{tab:one}
\begin{minipage}{\columnwidth}
\begin{center}
\begin{tabular}{ll}
  \toprule
  TERRAIN\footnote{This is a table footnote. This is a
    table footnote. This is a table footnote.}   & (200m$\times$200m) Square\\
  Node Number     & 289\\
  Node Placement  & Uniform\\
  Application     & Many-to-Many/Gossip CBR Streams\\
  Payload Size    & 32 bytes\\
  Routing Layer   & GF\\
  MAC Layer       & CSMA/MMSN\\
  Radio Layer     & RADIO-ACCNOISE\\
  Radio Bandwidth & 250Kbps\\
  Radio Range     & 20m--45m\\
  \bottomrule
\end{tabular}
\end{center}
\bigskip\centering
\footnotesize\emph{Source:} This is a table
 sourcenote. This is a table sourcenote. This is a table
 sourcenote.

 \emph{Note:} This is a table footnote.
\end{minipage}
\end{table}%


\section{Conclusions}

In this article, we develop the first multifrequency MAC protocol for
WSN applications in which each device adopts a
single radio transceiver. The different MAC design requirements for
WSNs and general wireless ad-hoc networks are
compared, and a complete WSN multifrequency MAC design (MMSN) is
put forth. During the MMSN design, we analyze and evaluate different
choices for frequency assignments and also discuss the nonuniform
back-off algorithms for the slotted media access design.


\section{Typical References in New ACM Reference Format}
A paginated journal article \cite{Abril07}, an enumerated
journal article \cite{Cohen07}, a reference to an entire issue \cite{JCohen96},
a monograph (whole book) \cite{Kosiur01}, a monograph/whole book in a series (see 2a in spec. document)
\cite{Harel79}, a divisible-book such as an anthology or compilation \cite{Editor00}
followed by the same example, however we only output the series if the volume number is given
\cite{Editor00a} (so Editor00a's series should NOT be present since it has no vol. no.),
a chapter in a divisible book \cite{Spector90}, a chapter in a divisible book
in a series \cite{Douglass98}, a multi-volume work as book \cite{Knuth97},
an article in a proceedings (of a conference, symposium, workshop for example)
(paginated proceedings article) \cite{Andler79}, a proceedings article
with all possible elements \cite{Smith10}, an example of an enumerated
proceedings article \cite{VanGundy07},
an informally published work \cite{Harel78}, a doctoral dissertation \cite{Clarkson85},
a master's thesis: \cite{anisi03}, an online document / world wide web
resource \cite{Thornburg01, Ablamowicz07, Poker06}, a video game (Case 1) \cite{Obama08} and (Case 2) \cite{Novak03}
and \cite{Lee05} and (Case 3) a patent \cite{JoeScientist001},
work accepted for publication \cite{rous08}, 'YYYYb'-test for prolific author
\cite{SaeediMEJ10} and \cite{SaeediJETC10}. Other cites might contain
'duplicate' DOI and URLs (some SIAM articles) \cite{Kirschmer:2010:AEI:1958016.1958018}.
Boris / Barbara Beeton: multi-volume works as books
\cite{MR781536} and \cite{MR781537}.

A couple of citations with DOIs: \cite{2004:ITE:1009386.1010128,
  Kirschmer:2010:AEI:1958016.1958018}.

Online citations: \cite{TUGInstmem, Thornburg01, CTANacmart}.


\section{Conclusion and Future Work}

Deep bidirectional self-attention architecture has achieved tremendous success in language understanding.
In this paper, we introduce a deep bidirectional sequential model called BERT4Rec for sequential recommendation.
For model training, we introduce the Cloze task which predicts the masked items using both left and right context.
Extensive experimental results on four real-world datasets show that our model outperforms state-of-the-art baselines.

Several directions remain to be explored.
A valuable direction is to incorporate rich item features (\textit{e.g.}, category and price for products, cast for movies) into BERT4Rec instead of just modeling item ids. %
Another interesting direction for the future work would be introducing user component into the model for explicit user modeling when the users have multiple sessions.




\bibliographystyle{ACM-Reference-Format}




\section{Experiments}





\subsection{Datasets}

\begin{table}
    \centering
    \caption{Statistics of datasets.}
    \label{tab:dataset}
    \begin{adjustbox}{max width=\linewidth}
    \begin{tabular}{l r r r r r}
    \toprule
    Datasets & \#users & \#items & \#actions & Avg. length &  Density\\
    \midrule
    Beauty & \num{40226} & \num{54542} & 0.35m & 8.8 & 0.02\% \\
    Steam & \num{281428} & \num{13044} & 3.5m & 12.4 & 0.10\% \\
    ML-1m & \num{6040} & \num{3416} & 1.0m & 163.5 & 4.79\% \\
    ML-20m & \num{138493} & \num{26744} & 20m & 144.4 & 0.54\%\\
    \bottomrule
    \end{tabular}
    \end{adjustbox}
\end{table}

We evaluate the proposed model on four real-world representative  datasets which vary significantly in domains and sparsity.

\begin{itemize}
    \item Amazon \textbf{Beauty}\footnote{\url{http://jmcauley.ucsd.edu/data/amazon/}}: This is a series of product review datasets crawled from Amazon.com by \citeauthor{McAuley:sigir2015}~\cite{McAuley:sigir2015}. 
    They split the data into separate datasets according to the top-level product categories on Amazon.
    In this work, we adopt the ``Beauty'' category.
    \item \textbf{Steam}\footnote{\url{https://cseweb.ucsd.edu/~jmcauley/datasets.html\#steam_data}}: 
    This is a dataset collected from Steam, a large online video game distribution platform, by \citeauthor{Kang:ICDM2018:SAS}~\cite{Kang:ICDM2018:SAS}.
    \item \textbf{MovieLens}~\cite{Harper:2015:MDH}: This is a popular benchmark dataset for evaluating recommendation algorithms.
    In this work, we adopt two well-established versions, MovieLens 1m (\textbf{ML-1m})\footnote{\url{https://grouplens.org/datasets/movielens/1m/}} and MovieLens 20m (\textbf{ML-20m})\footnote{\url{https://grouplens.org/datasets/movielens/20m/}}.
\end{itemize}

For dataset preprocessing, we follow the common practice in \cite{Rendle:WWW2010:FPM,Tang:WSDM2018:caser,Kang:ICDM2018:SAS}.
For all datasets, we convert all numeric ratings or the presence of a review to implicit feedback of 1 (\textit{i.e.}, the user interacted with the item).
After that, we group the interaction records by users and build the interaction sequence for each user by sorting these interaction records according to the timestamps.
To ensure the quality of the dataset, following the common practice~\cite{Rendle:WWW2010:FPM,He:www2017:NCF,Tang:WSDM2018:caser,Kang:ICDM2018:SAS}, we keep users with at least five feedbacks.
The statistics of the processed datasets are summarized in Table~\ref{tab:dataset}.

\subsection{Task Settings \& Evaluation Metrics}

To evaluate the sequential recommendation models, we adopted the \textit{leave-one-out} evaluation (\textit{i.e.}, next item recommendation) task, which has been widely used in~\cite{He:www2017:NCF,Tang:WSDM2018:caser,Kang:ICDM2018:SAS}.
For each user, we hold out the last item of the behavior sequence as the test data, treat the item just before the last as the validation set, and utilize the remaining items for training.
For easy and fair evaluation, we follow the common strategy in \cite{He:www2017:NCF,Tang:WSDM2018:caser,Kang:ICDM2018:SAS}, pairing each ground truth item in the test set with 100 randomly sampled \textit{negative} items that the user has not interacted with.
To make the sampling reliable and representative~\cite{Huang:sigir2018:ISR}, these 100 negative items are sampled according to their popularity.
Hence, the task becomes to rank these negative items with the ground truth item for each user.

\textbf{Evaluation Metrics}.
To evaluate the ranking list of all the models, we employ a variety of evaluation metrics, including \textit{Hit Ratio} (HR), \textit{Normalized Discounted Cumulative Gain} (NDCG), and \textit{Mean Reciprocal Rank} (MRR).
Considering we only have one ground truth item for each user, HR@$k$ is equivalent to Recall@$k$ and proportional to Precision@$k$; MRR is equivalent to Mean Average Precision (MAP).
In this work, we report HR and NDCG with $k={1,5,10}$.
For all these metrics, the higher the value, the better the performance.

\iffalse
$\bm{\mathrm{HR}@k}$ measures the proportion of cases that the desired item is among the top-$k$ items in all test cases.
It is computed as: 
\begin{equation*}
    \mathrm{HR}@k = \frac{1}{\vert \mathcal{U} \vert}\sum_{u \in \mathcal{U}} \mathbbm{1}(\mathrm{R}_{u, g_u} \leq k)
\end{equation*}
where, $g_u$ is the ground truth item for user $u$, $\mathrm{R}_{u, g_u}$ is the rank generated by the model for item $g_u$ and user $u$, and $\mathbbm{1}$ is an indicator function.
$\mathrm{HR}@k$ does not consider the actual rank of $g_u$ as long as it is among the top-$k$.

$\bm{\mathrm{NDCG}@k}$ is a position-aware metric which assigns larger weights on higher ranks. For next item recommendation, it is calculated as :
\begin{equation*}
    \mathrm{NDCG}@k = \frac{1}{\vert \mathcal{U} \vert}\sum_{u \in \mathcal{U}} \frac{2^{\mathbbm{1}(\mathrm{R}_{u, g_u} \leq k)} - 1}{\log_2 (\mathrm{R}_{u, g_u} + 1)}
\end{equation*}

\textbf{MRR} is the average of reciprocal ranks of the ground truth $\mathrm{R}_{u, g_u}$:
\begin{equation*}
    \mathrm{MRR} = \frac{1}{\vert \mathcal{U} \vert}\sum_{u \in \mathcal{U}}\frac{1}{\mathrm{R}_{u, g_u}}
\end{equation*}
\fi


\subsection{Baselines \& Implementation Details}

To verify the effectiveness of our method, we compare it with the following representative baselines:
\begin{itemize}[leftmargin=0.6cm]
    \item \textbf{POP}: It is the simplest baseline that ranks items according to their popularity judged by the number of interactions.
    \item \textbf{BPR-MF}~\cite{Rendle:UAI2009:BBP}: It optimizes the matrix factorization with implicit feedback using a pairwise ranking loss.
    \item \textbf{NCF}~\cite{He:www2017:NCF}: It models user–item interactions with a MLP instead of the inner product in matrix factorization.
    \item \textbf{FPMC}~\cite{Rendle:WWW2010:FPM}: It captures users' general taste as well as their sequential behaviors by combing MF with first-order MCs.
    \item \textbf{GRU4Rec}~\cite{Hidasi:ICLR2016:gru4rec}: It uses GRU with ranking based loss to model user sequences for session based recommendation.
    \item \textbf{GRU4Rec$^{+}$}~\cite{Hidasi:CIKM2018:RNN}: It is an improved version of GRU4Rec with a new class of loss functions and sampling strategy.
    \item \textbf{Caser}~\cite{Tang:WSDM2018:caser}: It employs CNN in both horizontal and vertical way to model high-order MCs for sequential recommendation.
    \item \textbf{SASRec}~\cite{Kang:ICDM2018:SAS}: It uses a left-to-right Transformer language model to capture users' sequential behaviors, and achieves state-of-the-art performance on sequential recommendation.
\end{itemize}


For NCF\footnote{\url{https://github.com/hexiangnan/neural_collaborative_filtering}}, GRU4Rec\footnote{\label{gru4rec}\url{https://github.com/hidasib/GRU4Rec}}, GRU4Rec$^+$\textsuperscript{\ref{gru4rec}}, Caser\footnote{\url{https://github.com/graytowne/caser_pytorch}}, and SASRec\footnote{\url{https://github.com/kang205/SASRec}}, we use code provided by the corresponding authors.
For BPR-MF and FPMC, we implement them using \texttt{TensorFlow}.
For common hyper-parameters in all models, we consider the hidden dimension size $d$ from $\{16, 32, 64, 128, 256\}$, the $\ell_2$ regularizer from \{1, 0.1, 0.01, 0.001, 0.0001\}, and dropout rate from \{$0, 0.1, 0.2,\cdots, 0.9$\}.
All other hyper-parameters (\textit{e.g.}, Markov order in Caser) and initialization strategies are either followed the suggestion from the methods' authors or tuned on the validation sets.
We report the results of each baseline under its optimal hyper-parameter settings.

We implement BERT4Rec\footnote{\url{https://github.com/FeiSun/BERT4Rec}} with \texttt{TensorFlow}.
All parameters are initialized using truncated normal distribution in the range $[-0.02, 0.02]$.
We train the model using Adam~\cite{Kingma:iclr2015:Adam} with learning rate of 1e-4, $\beta_1 = 0.9, \beta_2 = 0.999$, $\ell_2$ weight decay of 0.01, and linear decay of the learning rate.
The gradient is clipped when its $\ell_2$ norm exceeds a threshold of 5. %
For fair comparison, we set the layer number $L=2$ and head number $h=2$ and use the same maximum sequence length as in~\cite{Kang:ICDM2018:SAS}, $N=200$ for ML-1m and ML-20m, $N=50$ for Beauty and Steam datasets. %
For head setting, we empirically set the dimensionality of each head as 32 (single head if $d<32$).
We tune the mask proportion $\rho$ using the validation set, resulting in $\rho=0.6$ for Beauty, $\rho=0.4$ for Steam, and $\rho=0.2$ for ML-1m and ML-20m. %
All the models are trained from scratch without any pre-training on a single NVIDIA GeForce GTX 1080 Ti GPU with a batch size of 256.

\subsection{Overall Performance Comparison}
\begin{table*}[]
\setlength{\tabcolsep}{0.62em}
    \centering
    \caption{Performance comparison of different methods on next-item prediction. Bold scores are the best in each row, while underlined scores are the second best. Improvements over baselines are statistically significant with $p<0.01$.} %
    \begin{adjustbox}{max width=\textwidth}
        \begin{tabular}{l l c c c c c c c c c c}
        \toprule
        Datasets & Metric & POP & BPR-MF & NCF & FPMC & GRU4Rec & GRU4Rec$^+$ & Caser & SASRec & BERT4Rec & Improv.\\
        \midrule
        \multirow{6}{*}{Beauty} & HR@1 & 0.0077 & 0.0415 & 0.0407 & 0.0435 & 0.0402 & 0.0551 & 0.0475 & \underline{0.0906} & \textbf{0.0953} & ~~5.19\% \\
         & HR@5 & 0.0392 & 0.1209 & 0.1305 & 0.1387 & 0.1315 & 0.1781 & 0.1625 & \underline{0.1934} & \textbf{0.2207} & 14.12\%\\
         & HR@10 & 0.0762 & 0.1992 & 0.2142 & 0.2401 & 0.2343 & 0.2654 & 0.2590 & \underline{0.2653} & \textbf{0.3025} & 14.02\%\\
         & NDCG@5 & 0.0230 & 0.0814 & 0.0855 & 0.0902 & 0.0812 & 0.1172 & 0.1050 & \underline{0.1436} & \textbf{0.1599} & 11.35\%\\
         & NDCG@10 & 0.0349 & 0.1064 & 0.1124 & 0.1211 & 0.1074 & 0.1453 & 0.1360 & \underline{0.1633} & \textbf{0.1862} & 14.02\%\\
          & MRR & 0.0437 & 0.1006 & 0.1043 & 0.1056 & 0.1023 & 0.1299 & 0.1205 & \underline{0.1536} & \textbf{0.1701} & 10.74\%\\
         \midrule
        \multirow{6}{*}{Steam} & HR@1 & 0.0159 & 0.0314 & 0.0246 & 0.0358 & 0.0574 & 0.0812 & 0.0495 & \underline{0.0885} & \textbf{0.0957} & ~~8.14\%\\
         & HR@5 & 0.0805 & 0.1177 & 0.1203 & 0.1517 & 0.2171 & 0.2391 & 0.1766 & \underline{0.2559} & \textbf{0.2710} & ~~5.90\%\\
         & HR@10 & 0.1389 & 0.1993 & 0.2169 & 0.2551 & 0.3313 & 0.3594 & 0.2870 & \underline{0.3783} & \textbf{0.4013} & ~~6.08\% \\
         & NDCG@5 & 0.0477 & 0.0744 & 0.0717 & 0.0945 & 0.1370 & 0.1613 & 0.1131 & \underline{0.1727} & \textbf{0.1842} & ~~6.66\% \\
         & NDCG@10 & 0.0665 & 0.1005 & 0.1026 & 0.1283 & 0.1802 & 0.2053 & 0.1484 & \underline{0.2147} & \textbf{0.2261} & ~~5.31\%\\
         & MRR & 0.0669 & 0.0942 & 0.0932 & 0.1139 & 0.1420 & 0.1757 & 0.1305 & \underline{0.1874} & \textbf{0.1949} & ~~4.00\%\\
         \midrule
        \multirow{6}{*}{ML-1m} & HR@1 & 0.0141 & 0.0914 & 0.0397 & 0.1386 & 0.1583 & 0.2092 & 0.2194 & \underline{0.2351} & \textbf{0.2863} & 21.78\%\\
         & HR@5 & 0.0715 & 0.2866 & 0.1932 & 0.4297 & 0.4673 & 0.5103 & 0.5353 & \underline{0.5434} & \textbf{0.5876} & ~~8.13\%\\
         & HR@10 & 0.1358 & 0.4301 & 0.3477 & 0.5946 & 0.6207 & 0.6351 &  \underline{0.6692} & 0.6629 & \textbf{0.6970} & ~~4.15\%\\
         & NDCG@5 & 0.0416 & 0.1903 & 0.1146 & 0.2885 & 0.3196 & 0.3705 & 0.3832 & \underline{0.3980} & \textbf{0.4454} & 11.91\%\\
         & NDCG@10 & 0.0621 & 0.2365 & 0.1640 & 0.3439 & 0.3627 & 	0.4064 & 0.4268 & \underline{0.4368} & \textbf{0.4818} & 10.32\%\\
         & MRR & 0.0627 & 0.2009 & 0.1358 & 0.2891 & 0.3041 & 	0.3462 & 0.3648 & \underline{0.3790} & \textbf{0.4254} & 12.24\%\\
         \midrule
        \multirow{6}{*}{ML-20m} & HR@1 & 0.0221 & 0.0553 & 0.0231 & 0.1079 & 0.1459 & 0.2021 & 0.1232 & \underline{0.2544} & \textbf{0.3440} & 35.22\%\\
         & HR@5 & 0.0805 & 0.2128 & 0.1358 & 0.3601 & 0.4657 & 0.5118 & 0.3804 & \underline{0.5727} & \textbf{0.6323} & 10.41\%\\
         & HR@10 & 0.1378 & 0.3538 & 0.2922 & 0.5201 & 0.5844 & 0.6524 & 0.5427 & \underline{0.7136} & \textbf{0.7473} & ~~4.72\% \\
         & NDCG@5 & 0.0511 & 0.1332 & 0.0771 & 0.2239 & 0.3090 & 0.3630 & 0.2538 & \underline{0.4208} & \textbf{0.4967} & 18.04\%\\
         & NDCG@10 & 0.0695 & 0.1786 & 0.1271 & 0.2895 & 0.3637 & 	0.4087 & 0.3062 & \underline{0.4665} & \textbf{0.5340} & 14.47\% \\
         & MRR & 0.0709 & 0.1503 & 0.1072 & 0.2273 & 0.2967 & 0.3476 & 0.2529 & \underline{0.4026} & \textbf{0.4785} & 18.85\% \\
        \bottomrule
        \end{tabular}
    \end{adjustbox}
    \label{tab:result}
\end{table*}


Table~\ref{tab:result} summarized the best results of all models on four benchmark datasets.
The last column is the improvements of BERT4Rec relative to the best baseline.
We omit the NDCG@1 results since it is equal to HR@1 in our experiments.
It can be observed that:

The non-personalized POP method gives the worst performance\footnote{What needs to be pointed out is that such low scores for POP are because the negative samples are sampled according to the items' popularity.} on all datasets since it does not model user's personalized preference using the historical records.
Among all the baseline methods, sequential methods (\textit{e.g.}, FPMC and GRU4Rec$^+$) outperforms non-sequential methods (\textit{e.g.}, BPR-MF and NCF) on all datasets consistently.
Compared with BPR-MF, the main improvement of FPMC is that it models users' historical records in a sequential way.
This observation verifies that considering sequential information is beneficial for improving performances in recommendation systems.

Among sequential recommendation baselines, Caser outperforms FPMC on all datasets especially for the dense dataset ML-1m, suggesting that high-order MCs is beneficial for sequential recommendation.
However, high-order MCs usually use very small order $L$ since they do not scale well with the order $L$.
This causes Caser to perform worse than GRU4Rec$^+$ and SASRec, especially on sparse datasets.
Furthermore, SASRec performs distinctly better than GRU4Rec and GRU4Rec$^+$, suggesting that self-attention mechanism is a more powerful tool for sequential recommendation.


According to the results, it is obvious that BERT4Rec performs best  among all methods on four datasets in terms of all evaluation metrics.
It gains \textbf{7.24\%} HR@10, \textbf{11.03\%} NDCG@10, and \textbf{11.46\%} MRR improvements (on average) against the strongest baselines.

\noindent \textbf{Question 1}: \textit{Do the gains come from the bidirectional self-attention model or from the Cloze objective?}

To answer this question, we try to isolate the effects of these two factors by constraining the Cloze task to mask only one item at a time.
In this way, the main difference between our BERT4Rec (with 1 mask) and SASRec is that BERT4Rec predicts the target item jointly conditioning on both left and right context.
We report the results on Beauty and ML-1m with $d=256$ in Table~\ref{tab:analysis} due to the space limitation.
The results show that BERT4Rec with 1 mask significantly outperforms SASRec on all metrics.
It demonstrates the importance of bidirectional representations for sequential recommendation.
Besides, the last two rows indicate that the Cloze objective also improves the performances.
Detailed analysis of the mask proportion $\rho$ in Cloze task can be found in \S~\ref{sec:mask}

\begin{table}
    \centering
    \caption{Analysis on bidirection and Cloze with $d=256$.}
    \label{tab:analysis}
    \begin{adjustbox}{max width=\linewidth}
    \begin{tabular}
        {l c c c c c c}
        \toprule
       \multirow{2}{*}{Model} & \multicolumn{3}{c}{Beauty} & \multicolumn{3}{c}{ML-1m} \\ \cmidrule(lr){2-4} \cmidrule(lr){5-7}
        & HR@10 & NDCG@10 & MRR & HR@10 & NDCG@10 & MRR \\ \midrule
        SASRec & 0.2653 & 0.1633 & 0.1536 & 0.6629 & 0.4368 & 0.3790 \\
        BERT4Rec (1 mask) & 0.2940 & 0.1769 & 0.1618 & 0.6869 & 0.4696 & 0.4127 \\
        BERT4Rec & 0.3025 & 0.1862 & 0.1701 & 0.6970 & 0.4818 & 0.4254 \\ 
        \bottomrule
    \end{tabular}
    \end{adjustbox}
\end{table}



\noindent \textbf{Question 2}: \textit{Why and how does bidirectional model outperform unidirectional models?}
\begin{figure}
\vspace{2mm}
    \centering
    \begin{subfigure}[b]{0.45\linewidth}
        \includegraphics[width=\textwidth]{./figs/256_BERT_Attention_layer_0_head_1}
        \caption{Layer 1, head 1}
        \label{fig:l1h1}
    \end{subfigure}
    \quad
    \begin{subfigure}[b]{0.45\linewidth}
        \includegraphics[width=\textwidth]{./figs/256_BERT_Attention_layer_0_head_2}
        \caption{Layer 1, head 2}
        \label{fig:l1h2}
    \end{subfigure}
    \begin{subfigure}[b]{0.47\linewidth}
     ~~~\includegraphics[width=\textwidth]{./figs/256_BERT_Attention_layer_1_head_2}
        \caption{Layer 2, head 2}
        \label{fig:mouse}
    \end{subfigure}
    \quad
    \begin{subfigure}[b]{0.47\linewidth}
        \includegraphics[width=\textwidth]{./figs/256_BERT_Attention_layer_1_head_4}
        \caption{Layer 2, head 4}
        \label{fig:mouse}
    \end{subfigure}
    \caption{Heat-maps of average attention weights on Beauty, the last position ``9'' denotes ``\texttt{[mask]}'' (best viewed in color).}
    \label{fig:att_vis}
\end{figure}

To answer this question, we try to reveal meaningful patterns by visualizing the average attention weights of the last 10 items during the test on Beauty in Figure~\ref{fig:att_vis}. 
Due to the space limitation, we only report four representative attention heat-maps in different layers and heads.

\input{dim_exp_fig}
We make several observations from the results.
\begin {enumerate*}[label=\bfseries\itshape\alph*\upshape)]
\item Attention varies across different heads.
For example, in layer 1, head 1 tends to attend on items at the left side while head 2 prefers to attend on items on the right side.
\item Attention varies across different layers.
Apparently, attentions in layer 2 tend to focus on more recent items.
This is because layer 2 is directly connected to the output layer and the recent items play a more important role in predicting the future.
Another interesting pattern is that heads in Figure~\ref{fig:l1h1} and~\ref{fig:l1h2} also tend to attend on \texttt{[mask]}\footnote{This phenomenon also exists in text sequence modeling using BERT.}.
It may be a way for self-attention to propagate sequence-level state to the item level.
\item Finally and most importantly, unlike unidirectional model can only attend on items at the left side, items in BERT4Rec tend to attend on the items at both sides.
This indicates that bidirectional is essential and beneficial for user behavior sequence modeling.
\end {enumerate*}



In the following studies, we examine the impact of the hyper-parameters, including the hidden dimensionality $d$, the mask proportion $\rho$, and the maximum sequence length $N$.
We analyze one hyper-parameter at a time by fixing the remaining hyper-parameters at their optimal settings. 
Due to space limitation, we only report NDCG@10 and HR@10 for the follow-up experiments. %



\subsection{Impact of Hidden Dimensionality $d$}

We now study how the hidden dimensionality $d$ affects the recommendation performance.
Figure~\ref{fig:dim_exp} shows NDCG@10 and HR@10 for neural sequential methods with the hidden dimensionality $d$ varying from 16 to 256 while keeping other optimal hyper-parameters unchanged.
We make some observations from this figure.




The most obvious observation from these sub-figures is that the performance of each model tends to converge as the dimensionality increases.
A larger hidden dimensionality does not necessarily lead to better model performance, especially on sparse datasets like Beauty and Steam.
This is probably caused by overfitting.
In terms of details, Caser performs unstably on four datasets, which might limit its usefulness.
Self-attention based methods (\textit{i.e.}, SASRec and BERT4Rec) achieve superior performances on all datasets. %
Finally, our model consistently outperforms all other baselines on all datasets even with a relatively small hidden dimensionality.
Considering that our model achieves satisfactory performance with $d {\geq} 64$, we only report the results with $d{=}64$ in the following analysis.

\subsection{Impact of Mask Proportion $\rho$}
\label{sec:mask}

\input{mask_fig}

As described in \S~\ref{sec:ml}, mask proportion $\rho$ is a key factor in model training, which directly affects the loss function (Equation~\ref{eq:loss}).
Obviously, mask proportion $\rho$ should not be too small or it is not enough to learn a strong model.
Meanwhile, it should not be too large, otherwise, it would be hard to train since there are too many items to guess based on a few contexts in such case.
To examine this, we study how mask proportion $\rho$ affects the recommendation performances on different datasets.

Figure~\ref{fig:mask_fig} shows the results with varying mask proportion $\rho$ from 0.1 to 0.9.
Considering the results with $\rho > 0.6$ on all datasets, a general pattern emerges, the performances decreasing as $\rho$ increases.
From the results of the first two columns, it is easy to see that $\rho=0.2$ performs better than $\rho=0.1$ on all datasets.
These results verify what we claimed above.


In addition, we observe that the optimal $\rho$ is highly dependent on the sequence length of the dataset.
For the datasets with short sequence length (\textit{e.g.}, Beauty and Steam), the best performances are achieved at $\rho{=}0.6$ (Beauty) and $\rho{=}0.4$ (Steam), while the datasets with long sequence length (\textit{e.g.}, ML-1m and ML-20m) prefer a small $\rho{=}0.2$.
This is reasonable since, compared with short sequence datasets, a large $\rho$ in long sequence datasets means much more items that need to be predicted. %
Take ML-1m and Beauty as example, $\rho{=}0.6$ means we need to predict $98 {=} \lfloor 163.5{\times} 0.6 \rfloor $ items on average per sequence for ML-1m, while it is only $5 {=} \lfloor 8.8{\times} 0.6 \rfloor$ items for Beauty.
The former is too hard for model training.







\subsection{Impact of Maximum Sequence Length $N$}

\begin{table}[t]
\renewcommand{\arraystretch}{1}
    \centering
    \caption{Performance with different maximum length $N$.}
    \label{tab:seq}
    \begin{adjustbox}{max width=\linewidth}
        \begin{tabular}{l l r r r r r }
        \toprule
         & & \multicolumn{1}{c}{10} & \multicolumn{1}{c}{20} & \multicolumn{1}{c}{30} & \multicolumn{1}{c}{40}  & \multicolumn{1}{c}{50}  \\ \midrule
       \multirow{3}{*}{Beauty} & \#samples/s & 5504 & 3256 & 2284 &  1776 & 1441\\
       & HR@10 & 0.3006 & 0.3061 & 0.3057 & 0.3054 & 0.3047 \\
       & NDCG@10 & 0.1826 & 0.1875 & 0.1837 & 0.1833 & 0.1832 \\
        \bottomrule \toprule
       &  & \multicolumn{1}{c}{10} & \multicolumn{1}{c}{50} & \multicolumn{1}{c}{100} & \multicolumn{1}{c}{200}  & \multicolumn{1}{c}{400}  \\ \midrule
       \multirow{3}{*}{ML-1m} & \#samples/s & 14255 & 8890 & 5711 & 2918 & 1213\\
       & HR@10 & 0.6788 & 0.6854 & 0.6947 & 0.6955 & 0.6898 \\
       & NDCG@10 & 0.4631 & 0.4743 & 0.4758 & 0.4759 & 0.4715 \\
        \bottomrule
    \end{tabular}
    \end{adjustbox}
\end{table}




We also investigate the effect of the maximum sequence length $N$ on model's recommendation performances and efficiency.

Table~\ref{tab:seq} shows recommendation performances and training speed with different maximum length $N$ on Beauty and ML-1m.
We observe that the proper maximum length $N$ is also highly dependent on the average sequence length of the dataset.
Beauty prefers a smaller $N=20$, while ML-1m achieves the best performances on $N=200$.
This indicates that a user's behavior is affected by more recent items on short sequence datasets and less recent items for long sequence datasets.
The model does not consistently benefit from a larger $N$ since a larger $N$ tends to introduce both extra information and more noise.
However, our model performs very stably as the length $N$ becomes larger.
This indicates that our model can attend to the informative items from the noisy historical records.

A scalability concern about BERT4Rec is that its computational complexity per layer is $\mathcal{O}(n^2d)$, quadratic with the length $n$.
Fortunately, the results in Table~\ref{tab:seq} shows that the self-attention layer can be effectively parallelized using GPUs.








\subsection{Ablation Study}


Finally, we perform ablation experiments over a number of key components of BERT4Rec in order to better understand their impacts, including positional embedding (PE), position-wise feed-forward network (PFFN), layer normalization (LN), residual connection (RC), dropout, the layer number $L$ of self-attention, and the number of heads $h$ in multi-head attention. %
Table~\ref{tab:ablation} shows the results of our default version ($L=2, h=2$) and its eleven variants on all four datasets with dimensionality $d=64$ while keeping other hyper-parameters (\textit{e.g.}, $\rho$) at their optimal settings. %




We introduce the variants and analyze their effects respectively:
\begin{enumerate}%
  \item \textbf{PE}. The results show that removing positional embeddings causes BERT4Rec's performances decreasing dramatically on long sequence datasets (\textit{i.e.}, ML-1m and ML-20m). Without the positional embeddings, the hidden representation $\bm{H}_i^L$ for each item $v_i$ depends only on item embeddings.
  In this situation, we predict different target items using the same hidden representation of ``\texttt{[mask]}''. This makes the model ill-posed. This issue is more serious on long sequence datasets since they have more masked items to predict.
  \item \textbf{PFFN}. The results show that long sequence datasets (\textit{e.g.}, ML-20m) benefit more from PFFN. 
  This is reasonable since a purpose of PFFN is to integrate information from many heads which are preferred by long sequence datasets as discussed in the analysis about head number $h$ in ablation study (\ref{itm:head}). %
  \item \textbf{LN}, \textbf{RC}, and \textbf{Dropout}. These components are introduced mainly to alleviate overfitting. 
  Obviously, they are more effective on small datasets like Beauty.
   To verify their effectiveness on large datasets, we conduct an experiment on ML-20m with layer $L{=}4$.
   The results show that NDCG@10 decreases about 10\% w/o RC.
  \item \textbf{Number of layers $L$}. The results show that stacking Transformer layer can boost performances especially on large datasets (\textit{e.g}, ML-20m).
  This verifies that it is helpful to learn more complex item transition patterns via deep self-attention architecture.
  The decline in Beauty with $L=4$ is largely due to overfitting.
  \item\label{itm:head} \textbf{Head number $h$}. We observe that long sequence datasets (\textit{e.g.}, ML-20m) benefit from a larger $h$ while short sequence datasets (\textit{e.g.}, Beauty) prefer a smaller $h$. This phenomenon is consistent with the empirical result in~\cite{Tang:EMNLP2018:Why} that large $h$ is essential for capturing long distance dependencies with multi-head self-attention.
\end{enumerate}
\begin{table}[t]
\renewcommand{\arraystretch}{1}
\setlength{\tabcolsep}{0.75em}
    \centering
    \caption{Ablation analysis (NDCG@10) on four datasets. Bold score indicates performance better than the default version, while $\downarrow$ indicates performance drop more than 10\%.}
    \label{tab:ablation}
    \begin{adjustbox}{max width=\linewidth}
        \begin{tabular}{l r r r r}
        \toprule
     \multirow{2}{*}{Architecture} & \multicolumn{4}{c}{Dataset} \\ 
         \cmidrule(lr){2-5}
          & \multicolumn{1}{c}{Beauty} & \multicolumn{1}{c}{Steam} & \multicolumn{1}{c}{ML-1m} & \multicolumn{1}{c}{ML-20m} \\ \midrule
        $L=2$, $h=2$  & 0.1832 & 0.2241 & 0.4759 & 0.4513 \\ \midrule
        w/o PE  & 0.1741 & 0.2060 & 0.2155$\downarrow$ & 0.2867$\downarrow$ \\
        w/o PFFN  & 0.1803 & 0.2137 & 0.4544 & 0.4296 \\ \midrule
        w/o LN  & 0.1642$\downarrow$ & 0.2058 & 0.4334 & 0.4186 \\
        w/o RC  & 0.1619$\downarrow$ & 0.2193 & 0.4643 & 0.4483 \\
        w/o Dropout  & 0.1658 & 0.2185 & 0.4553 & 0.4471 \\ \midrule
        1 layer \hspace{\fill}($L=1$) & 0.1782 & 0.2122 & 0.4412 & 0.4238 \\
        3 layers \hspace{\fill} ($L=3$) & \textbf{0.1859} & \textbf{0.2262} & \textbf{0.4864} & \textbf{0.4661}\\
        4 layers \hspace{\fill} ($L=4$) & \textbf{0.1834} & \textbf{0.2279} & \textbf{0.4898} & \textbf{0.4732}\\ \midrule
        1 head \hspace{\fill} ($h=1$) & \textbf{0.1853} & 0.2187 & 0.4568 & 0.4402 \\
        4 heads \hspace{\fill} ($h=4$) & 0.1830 & \textbf{0.2245} & \textbf{0.4770} & \textbf{0.4520} \\
        8 heads \hspace{\fill} ($h=8$) & 0.1823 & \textbf{0.2248} & 0.4743 & \textbf{0.4550} \\
        \bottomrule
    \end{tabular}
    \end{adjustbox}
\end{table}








\section{Introduction}





Accurately characterizing users' interests lives at the heart of an effective recommendation system.
In many real-world applications, users' current interests are intrinsically dynamic and evolving, influenced by their historical behaviors.
For example, one may purchase accessories (\textit{e.g.}, Joy-Con controllers) soon after buying a Nintendo Switch, though she/he will not buy console accessories under normal circumstances.

To model such sequential dynamics in user behaviors, various methods have been proposed to make \textit{sequential recommendations} based on users' historical interactions~\cite{Rendle:WWW2010:FPM,Hidasi:ICLR2016:gru4rec,Kang:ICDM2018:SAS}.
They aim to predict the successive item(s) that a user is likely to interact with given her/his past interactions.
Recently, a surge of works employ sequential neural networks, \textit{e.g.}, Recurrent Neural Network (RNN), for sequential recommendation and obtain promising results~\cite{Hidasi:ICLR2016:gru4rec,Yu:sigir2016:DRM,Wu:wsdm2017:RRN,Donkers:recsys2017:SUR,Hidasi:CIKM2018:RNN}.
The basic paradigm of previous work is to encode a user's historical interactions into a vector (\textit{i.e.}, representation of user's preference) using a left-to-right sequential model and make recommendations based on this hidden representation.





Despite their prevalence and effectiveness, we argue that such left-to-right unidirectional models are not sufficient to learn optimal representations for user behavior sequences. %
The major limitation, as illustrated in Figure~\ref{fig:model}c and~\ref{fig:model}d, is that such unidirectional models restrict the power of hidden representation for items in the historical sequences, where each item can only encode the information from previous items.
Another limitation is that previous unidirectional models are originally introduced for sequential data with natural order, \textit{e.g.}, text and time series data.
They often assume a rigidly ordered sequence over data which is not always true for user behaviors in real-world applications.
In fact, the choices of items in a user's historical interactions may not follow a rigid order assumption~\cite{Hu:ijcai2017:Diversifying,Wang:aaai2018:atem} due to various unobservable external factors~\cite{Covington:recsys2016:DNN}. %
In such a situation, it is crucial to incorporate context from both directions in user behavior sequence modeling.














To address the limitations mentioned above, we seek to use a bidirectional model to learn the representations for users' historical behavior sequences.
Specifically, inspired by the success of BERT~\cite{Devlin:2018:BERT} in text understanding, we propose to apply the deep bidirectional self-attention model to sequential recommendation, as illustrated in Figure~\ref{fig:model}b. 
For representation power, the superior results for deep bidirectional models on text sequence modeling tasks show that it is beneficial to incorporate context from both sides for sequence representations learning~\cite{Devlin:2018:BERT}.
For rigid order assumption, our model is more suitable than unidirectional models in modeling user behavior sequences since all items in the bidirectional model can leverage the contexts from both left and right side.


However, it is not straightforward and intuitive to train the bidirectional model for sequential recommendation. %
Conventional sequential recommendation models are usually trained left-to-right by predicting the next item for each position in the input sequence.
As shown in Figure~\ref{fig:model}, jointly conditioning on both left and right context in a deep bidirectional model would cause information leakage, \textit{i.e.}, allowing each item to indirectly ``see the target item''.
This could make predicting the future become trivial and the network would not learn anything useful.

To tackle this problem, we introduce the Cloze task~\cite{Devlin:2018:BERT,Wilson:Cloze} to take the place of the objective in unidirectional models (\textit{i.e.}, sequentially predicting the next item).
Specifically, we randomly mask some items (\textit{i.e.}, replace them with a special token \texttt{[mask]}) in the input sequences, and then predict the ids of those masked items based on their surrounding context. %
In this way, we avoid the information leakage and learn a bidirectional representation model by allowing the representation of each item in the input sequence to fuse both the left and right context.
In addition to training a bidirectional model, another advantage of the Cloze objective is that it can produce more samples to train a more powerful model in multiple epochs. %
However, a downside of the Cloze task is that it is not consistent with the final task (\textit{i.e.}, sequential recommendation).
To fix this, during the test, we append the special token ``\texttt{[mask]}'' at the end of the input sequence to indicate the item that we need to predict, and then make recommendations base on its final hidden vector.
Extensive experiments on four datasets show that our model outperforms various state-of-the-art baselines consistently.

The contributions of our paper are as follows:
\begin{itemize}%
    \item We propose to model user behavior sequences with a bidirectional self-attention network through Cloze task. To the best of our knowledge, this is the first study to introduce deep bidirectional sequential model and Cloze objective into the field of recommendation systems.
    \item We compare our model with state-of-the-art methods and demonstrate the effectiveness of both bidirectional architecture and the Cloze objective through quantitative analysis on four benchmark datasets.
    \item We conduct a comprehensive ablation study to analyze the contributions of key components in the proposed model. %
\end{itemize}








\section{BERT4Rec}
Before going into the details, we first introduce the research problem, the basic concepts, and the notations in this paper.

\subsection{Problem Statement}
In sequential recommendation, let $\mathcal{U}{=}\{u_1,u_2,\dots,u_{\vert\mathcal{U}\vert}\}$ denote a set of users, $\mathcal{V}{=}\{v_1,v_2,\dots,v_{|\mathcal{V}|}\}$ be a set of items, and list $\mathcal{S}_u{=}[v_1^{(u)},\dots,v_t^{(u)},\dots,v_{n_u}^{(u)}]$ denote the interaction sequence in chronological order for user $u \in \mathcal{U}$, where $v_t^{(u)} \in \mathcal{V}$ is the item that $u$ has interacted with at time step\footnote{Here, following~\cite{Rendle:WWW2010:FPM,Kang:ICDM2018:SAS}, we use the relative time index instead of absolute time index for numbering interaction records.} $t$ and $n_u$ is the the length of interaction sequence for user $u$.
Given the interaction history $\mathcal{S}_u$, sequential recommendation aims to predict the item that user $u$ will interact with at time step $n_{u} + 1$.
It can be formalized as modeling the probability over all possible items for user $u$ at time step $n_{u} {+} 1$:
\begin{equation*}
    p\bigl(v_{n_u+1}^{(u)}=v|\ \mathcal{S}_u\bigr)
\end{equation*}


\subsection{Model Architecture}

Here, we introduce a new sequential recommendation model called \textbf{BERT4Rec}, which adopts \textbf{B}idirectional \textbf{E}ncoder \textbf{R}epresentations from \textbf{T}ransformers to a new task, sequential \textbf{R}ecommendation.
It is built upon the popular self-attention layer, ``Transformer layer''. %

As illustrated in Figure~\ref{fig:model}b, BERT4Rec is stacked by $L$ bidirectional Transformer layers.
At each layer, it iteratively revises the representation of every position by exchanging information across all positions at the previous layer in parallel with the Transformer layer.
Instead of learning to pass relevant information forward step by step as RNN based methods did in Figure~\ref{fig:model}d, self-attention mechanism endows BERT4Rec with the capability to directly capture the dependencies in any distances.
This mechanism results in a global receptive field, while CNN based methods like Caser usually have a limited receptive field.
In addition, in contrast to RNN based methods, self-attention is straightforward to parallelize.




Comparing Figure~\ref{fig:model}b,~\ref{fig:model}c, and~\ref{fig:model}d, the most noticeable difference is that SASRec and RNN based methods are all left-to-right unidirectional architecture, while our BERT4Rec uses bidirectional self-attention to model users' behavior sequences.
In this way, our proposed model can obtain more powerful representations of users' behavior sequences to improve  recommendation performances.







\subsection{Transformer Layer}


As illustrated in Figure~\ref{fig:model}b, given an input sequence of length $t$, %
we iteratively compute hidden representations $\bm{h}_i^{l}$ at each layer $l$ for each position $i$ simultaneously by applying the Transformer layer from~\cite{Vaswani:nips2017:Attention}.
Here, we stack $\bm{h}_i^{l} \in \mathbb{R}^d$ together into matrix $\bm{H}^{l} {\in} \mathbb{R}^{t\times d}$ since we compute attention function on all positions simultaneously in practice. 
As shown in Figure~\ref{fig:model}a, the Transformer layer \texttt{Trm} contains two sub-layers, a \textit{Multi-Head Self-Attention} sub-layer and a \textit{Position-wise Feed-Forward Network}.

\textbf{Multi-Head Self-Attention}.
Attention mechanisms have become an integral part of sequence modeling in a variety of tasks, allowing capturing the dependencies between representation pairs without regard to their distance in the sequences.
Previous work has shown that it is beneficial to jointly attend to information from different representation subspaces at different positions~\cite{Vaswani:nips2017:Attention,Li:emnlp2018:Multi,Devlin:2018:BERT}.
Thus, we here adopt the multi-head self-attention instead of performing a single attention function.
Specifically, multi-head attention first linearly projects $\bm{H}^l$ into $h$ subspaces, with different, learnable linear projections, and then apply $h$ attention functions in parallel to produce the output representations which are concatenated and once again projected:
\begin{equation}
    \begin{aligned}
        \mathtt{MH}(\bm{H}^{l}) &= [\text{head}_1; \text{head}_2; \dots; \text{head}_h]\bm{W}^{O} \\
        \text{head}_i &= \mathtt{Attention}\bigl(\bm{H}^l\bm{W}_i^Q, \bm{H}^l\bm{W}_i^K, \bm{H}^l\bm{W}_i^V \bigr)
    \end{aligned}
\label{eq:mh}
\end{equation} %
where the projections matrices for each head $\bm{W}_i^Q \in \mathbb{R}^{d \times d/h}$, $\bm{W}_i^K \in \mathbb{R}^{d \times d/h}$, $\bm{W}_i^V \in \mathbb{R}^{d \times d/h}$, and $\bm{W}_i^O \in \mathbb{R}^{d \times d}$ are learnable parameters. %
Here, we omit the layer subscript $l$ for the sake of simplicity.
In fact, these projection parameters are not shared across the layers.
Here, the $\mathtt{Attention}$ function is \textit{Scaled Dot-Product Attention}: %
\begin{equation}
    \mathtt{Attention}(\bm{Q}, \bm{K}, \bm{V}) = \mathrm{softmax} \biggl(\frac{\bm{Q}\bm{K}^{\top}}{\sqrt{d/h}}\biggr) \bm{V}
    \label{eq:scale_dot}
\end{equation}
where \textit{query} $\bm{Q}$, \textit{key} $\bm{K}$, and \textit{value} $\bm{V}$ are projected from the same matrix $\bm{H}^l$ with different learned projection matrices as in Equation~\ref{eq:mh}. %
The \textit{temperature} $\sqrt{d/h}$ is introduced to produce a softer attention distribution for avoiding extremely small gradients~\cite{Hinton:nips2014:Distilling,Vaswani:nips2017:Attention}.


\textbf{Position-wise Feed-Forward Network}.
As described above, the self-attention sub-layer is mainly based on linear projections.
To endow the model with nonlinearity and interactions between different dimensions, we apply a \textit{Position-wise Feed-Forward Network} to the outputs of the self-attention sub-layer, separately and identically at each position.
It consists of two affine transformations with a Gaussian Error Linear Unit (\texttt{GELU}) activation in between:
\begin{equation}
    \begin{aligned}
      \texttt{PFFN}(\bm{H}^l) & = \bigl[\mathtt{FFN}(\bm{h}_1^{l})^{\top}; \dots; \mathtt{FFN}(\bm{h}_t^{l})^{\top}\bigr]^{\top}\\
       \mathtt{FFN}(\bm{x}) &= \texttt{GELU}\bigl(\bm{x} \bm{W}^{(1)}+\bm{b}^{(1)}\bigr)\bm{W}^{(2)} + \bm{b}^{(2)}\\
       \texttt{GELU}(x) &= x \Phi(x)
    \end{aligned}
    \label{eq:ffn}
\end{equation}
where $\Phi(x)$ is the cumulative distribution function of the standard gaussian distribution, $\bm{W}^{(1)}\in \mathbb{R}^{d\times 4d}$, $\bm{W}^{(2)}\in \mathbb{R}^{4d\times d}$, $\bm{b}^{(1)}\in \mathbb{R}^{4d}$ and $\bm{b}^{(2)}\in \mathbb{R}^{d}$ are learnable parameters and shared across all positions.
We omit the layer subscript $l$ for convenience.
In fact, these parameters are different from layer to layer.
In this work, following OpenAI GPT~\cite{Radford:2018:GPT} and BERT~\cite{Devlin:2018:BERT}, we use a smoother \texttt{GELU}~\cite{Hendrycks:gleu} activation rather than the standard \texttt{ReLu} activation. %


\textbf{Stacking Transformer Layer}.
As elaborated above, we can easily capture item-item interactions across the entire user behavior sequence using self-attention mechanism.
Nevertheless, it is usually beneficial to learn more complex item transition patterns by stacking the self-attention layers.
However, the network becomes more difficult to train as it goes deeper.
Therefore, we employ a residual connection~\cite{He:cvpr2016:resnet} around each of the two sub-layers as in Figure~\ref{fig:model}a, followed by layer normalization~\cite{Lei:Layer}.
Moreover, we also apply dropout~\cite{Srivastava:jmlr15:Dropout} to the output of each sub-layer, before it is normalized. %
That is, the output of each sub-layer is $\texttt{LN}(\bm{x} + \texttt{Dropout}(\text{sublayer}(\bm{x})))$, where $\text{sublayer}(\cdot)$ is the function implemented by the sub-layer itself, $\texttt{LN}$ is the layer normalization function defined in~\cite{Lei:Layer}. %
We use $\texttt{LN}$ to normalize the inputs over all the hidden units in the same layer for stabilizing and accelerating the network training.

In summary, BERT4Rec refines the hidden representations of each layer as follows:
\begin{align}
    \bm{H}^l &= \mathtt{Trm}\bigl(\bm{H}^{l-1}\bigr), \quad \forall i \in [1,\dots, L] \\
    \mathtt{Trm}(\bm{H}^{l-1}) &= \mathtt{LN}\Bigl(\bm{A}^{l-1} +  \mathtt{Dropout}\bigl(\mathtt{PFFN}(\bm{A}^{l-1})\bigr)\Bigr) \\
    \bm{A}^{l-1} &= \mathtt{LN}\Bigr(\bm{H}^{l-1} + \mathtt{Dropout}\bigl(\mathtt{MH}(\bm{H}^{l-1})\bigr)\Bigr) 
\end{align}


\subsection{Embedding Layer}
As elaborated above, without any recurrence or convolution module, the Transformer layer $\mathtt{Trm}$ is not aware of the order of the input sequence.
In order to make use of the sequential information of the input, we inject \textit{Positional Embeddings} into the input item embeddings at the bottoms of the Transformer layer stacks.
For a given item $v_i$, its input representation $\bm{h}_i^0$ is constructed by summing the corresponding item and positional embedding:
\begin{equation*}
    \begin{aligned}
        \bm{h}_{i}^0 &= \bm{v}_i + \bm{p}_i
    \end{aligned}
\end{equation*}
where $\bm{v}_i {\in} \bm{E}$ is the $d-$dimensional embedding for item $v_i$, $\bm{p}_i {\in} \bm{P}$ is the $d-$dimensional positional embedding for position index $i$.
In this work, we use the learnable positional embeddings instead of the fixed sinusoid embeddings in~\cite{Vaswani:nips2017:Attention} for better performances.
The positional embedding matrix $\bm{P} \in \mathbb{R}^{N\times d}$ allows our model to identify which portion of the input it is dealing with.
However, it also imposes a restriction on the maximum sentence length $N$ that our model can handle.
Thus, we need to truncate the the input sequence $[v_1,\dots,v_t]$ to the last $N$ items $[v_{t-N+1}^{u},\dots,v_t]$ if $t>N$.

\subsection{Output Layer}

After $L$ layers that hierarchically exchange information across all positions in the previous layer, we get the final output $\bm{H}^L$ for all items of the input sequence.
Assuming that we mask the item $v_t$ at time step $t$, we then predict the masked items $v_t$ base on $\bm{h}_t^L$ as shown in Figure~\ref{fig:model}b.
Specifically, we apply a two-layer feed-forward network with \texttt{GELU} activation in between to produce an output distribution over target items:
\begin{equation}
    P(v) = \mathrm{softmax}\bigl(\mathtt{GELU}(\bm{h}_t^L \bm{W}^P +\bm{b}^P) \bm{E}^{\top} + \bm{b}^O \bigr)
    \label{eq:prob}
\end{equation}
where $\bm{W}^P$ is the learnable projection matrix, $\bm{b}^P$, and $\bm{b}^O$ are bias terms, $\bm{E}\in \mathbb{R}^{|\mathcal{V}|\times d}$ is the embedding matrix for the item set $\mathcal{V}$.
We use the shared item embedding matrix in the input and output layer for alleviating overfitting and reducing model size.


\subsection{Model Learning}
\label{sec:ml}

\textbf{Training}. 
Conventional unidirectional sequential recommendation models usually train the model by predicting the next item for each position in the input sequence as illustrated in Figure~\ref{fig:model}c and~\ref{fig:model}d.
Specifically, the target of the input sequence $[v_1,\dots,v_{t}]$ is a shifted version $[v_2,\dots,v_{t+1}]$.
However, as shown in Figure~\ref{fig:model}b, jointly conditioning on both left and right context in a bidirectional model would cause the final output representation of each item to contain the information of the target item.
This makes predicting the future become trivial and the network would not learn anything useful.
A simple solution for this issue is to create $t-1$ samples (subsequences with next items like ([$v_1$], $v_2$) and ([$v_1,v_2$], $v_3$)) from the original length $t$ behavior sequence and then encode each historical subsequence with the bidirectional model to predict the target item. 
However, this approach is very time and resources consuming since we need to create a new sample for each position in the sequence and predict them separately.

In order to efficiently train our proposed model, we apply a new objective: \textit{Cloze} task~\cite{Wilson:Cloze} (also known as ``Masked Language Model'' in~\cite{Devlin:2018:BERT}) to sequential recommendation.
It is a test consisting of a portion of language with some words removed, where the participant is asked to fill the missing words.
In our case, for each training step, we randomly mask $\rho$ proportion of all items in the input sequence (\textit{i.e.}, replace with special token ``\texttt{[mask]}''), and then predict the original ids of the masked items based solely on its left and right context.
For example: 
\begin{figure}[h]
\centering
\resizebox{0.97\linewidth}{!}{
\begin{tikzpicture}[decoration={random steps,segment length=3mm, amplitude=0.5pt}]
\node[] (e1) at (0, 0) {\textbf{Input}: $[v_1,v_2,v_3,v_4,v_5]$};
\node[right of=e1, node distance=5.1cm] (e2)  {$[v_1,$ {\small$\mathtt{[mask]}_1$}$, v_3,$ {\small$\mathtt{[mask]}_2$}$, v_5]$};
\node[below of=e1, node distance=0.5cm, xshift=0.68cm] (e3)  {\textbf{Labels}: {\small$\mathtt{[mask]}_1$} $= v_2$, ~~ {\small$\mathtt{[mask]}_2$} $= v_4$};
\draw[FARROW] (e1) -> (e2) ;
\node[right of=e1, node distance=2.45cm, yshift=0.1cm] (e4)  {\scriptsize randomly mask};

\draw[decorate]  ($(e3.south west)+(-0.1, -0.1)$) rectangle ($(e2.north east)+(0.1, 0.1)$);

\end{tikzpicture}}
\end{figure}

\noindent The final hidden vectors corresponding to ``\texttt{[mask]}'' are fed into an output softmax over the item set, as in conventional sequential recommendation.
Eventually, we define the loss for each masked input $\mathcal{S}_u^{\prime}$ as the negative log-likelihood of the masked targets: %
\begin{equation}
    \mathcal{L} = \frac{1}{|\mathcal{S}_u^m|} \sum_{v_m\in \mathcal{S}_u^m} -\log P(v_m=v_m^{*}|\mathcal{S}_u^{\prime} )
    \label{eq:loss}
\end{equation}
where $\mathcal{S}_u^{\prime}$ is the masked version for user behavior history $\mathcal{S}_u$, $\mathcal{S}_u^m$ is the random masked items in it, $v_m^*$ is the true item for the masked item $v_m$, and the probability $P(\cdot)$ is defined in Equation~\ref{eq:prob}.

An additional advantage for Cloze task is that it can generate more samples to train the model.
Assuming a sequence of length $n$, conventional sequential predictions in Figure~\ref{fig:model}c and~\ref{fig:model}d  produce $n$ unique samples for training, while BERT4Rec can obtain $\binom{n}{k}$ samples (if we randomly mask $k$ items) in multiple epochs.
It allows us to train a more powerful bidirectional representation model.




\textbf{Test}.
As described above, we create a mismatch between the training and the final sequential recommendation task since the Cloze objective is to predict the current masked items while sequential recommendation aims to predict the future.
To address this, we append the special token ``\texttt{[mask]}'' to the end of user's behavior sequence, and then predict the next item based on the final hidden representation of this token.
To better match the sequential recommendation task (\textit{i.e.}, predict the last item), we also produce samples that only mask the last item in the input sequences during training.
It works like fine-tuning for sequential recommendation and can further improve the recommendation performances.

\subsection{Discussion}

Here, we discuss the relation of our model with previous related work.

\textbf{SASRec}. Obviously, SASRec is a left-to-right unidirectional version of our BERT4Rec with single head attention and causal attention mask.
Different architectures lead to different training methods.
SASRec predicts the next item for each position in a sequence, while BERT4Rec predicts the masked items in the sequence using Cloze objective.

\textbf{CBOW \& SG}. Another very similar work is Continuous Bag-of-Words (CBOW) and Skip-Gram (SG)~\cite{Mikolov:cbow}.
CBOW predicts a target word using the average of all the word vectors in its context (both left and right).
It can be seen as a simplified case of BERT4Rec, if we use one self-attention layer in BERT4Rec with uniform attention weights on items, unshare item embeddings, remove the positional embedding, and only mask the central item.
Similar to CBOW, SG can also be seen as a simplified case of BERT4Rec following similar reduction operations (mask all items except only one).
From this point of view, Cloze can be seen as a general form for the objective of CBOW and SG.
Besides, CBOW uses a simple aggregator to model word sequences since its goal is to learn good word representations, not sentence representations.
On the contrary, we seek to learn a powerful behavior sequence representation model (deep self-attention network in this work) for making recommendations.



\textbf{BERT}. Although our BERT4Rec is inspired by the BERT in NLP, it still has several differences from BERT:
\begin {enumerate*}[label=\bfseries\itshape\alph*\upshape)]
\item The most critical difference is that BERT4Rec is an end-to-end model for sequential recommendation, while BERT is a pre-training model for sentence representation.
BERT leverages large-scale task-independent corpora to pre-train the sentence representation model for various text sequence tasks since these tasks share the same background knowledge about the language.
However, this assumption does not hold in the recommendation tasks.
Thus we train BERT4Rec end-to-end for different sequential recommendation datasets.
\item Different from BERT, we remove the next sentence loss and segment embeddings since BERT4Rec models a user's historical behaviors as only one sequence in sequential recommendation task.
\end {enumerate*} 


\iffalse
\textbf{CBOW}. Another very similar work is Continuous Bag-of-Words (CBOW) model~\cite{Mikolov:cbow}.
CBOW predicts a target word using the average of all the word vectors in its context (both left and right).
It can be seen as a simplified case of BERT4Rec, if we replace the $L$-layer Transformer layer in BERT4Rec with uniform attention weights on items, use unshared item embeddings, remove the positional embedding, and only mask the central item.
CBOW uses a simple aggregator to model word sequences since its goal is to learn good word representations, not sentence representations.
On the contrary, we use a deep self-attention architecture to model the context since our goal is to learn a powerful sequence representation model for making recommendations.

\textbf{SG}. Similar to CBOW, Skip-Gram (SG)~\cite{Mikolov:nips2013:DRW} can also be seen as a simplified case of BERT4Rec following the similar reduction operations.
The difference is that we mask all items except only one for SG.
From this point of view, Cloze is a general form for the objective of CBOW and SG.

\textbf{FISM}. If we use one self-attention layer with uniform attention weights on items, use unshared item embeddings, and
 remove the position embedding, SASRec is reduced to FISM. 
Thus our model can be viewed as an adaptive, hierarchical, sequential item similarity model for next item recommendation.
\fi







\section{Related Work}

In this section, we will briefly review several lines of works closely related to ours, including general recommendation, sequential recommendation, and attention mechanism.


\subsection{General Recommendation}

Early works on recommendation systems typically use Collaborative  Filtering (CF) to model users' preferences based on their  interaction histories~\cite{Sarwar:www2001:ICF,Koren:ACF:2011}.
Among various CF methods, Matrix Factorization (MF) is the most popular one, which projects users and items into a shared vector space and estimate a user's preference on an item by the inner product between their vectors~\cite{Salakhutdinov:nips2007:PMF,Koren:2009:MFT,Koren:ACF:2011}.
Another line of work is item-based neighborhood methods \cite{Sarwar:www2001:ICF,Linden:ieee2003:ARI,Koren:kdd2008:FMN,Kabbur:kdd2013:FFI}.
They estimate a user's preference on an item via measuring its similarities with the items in her/his interaction history using a precomputed item-to-item similarity matrix.




Recently, deep learning has been revolutionizing the recommendation systems dramatically.
The early pioneer work is a two-layer Restricted Boltzmann Machines (RBM) for collaborative filtering, proposed by \citeauthor{Salakhutdinov:icml2007:RBM}~\cite{Salakhutdinov:icml2007:RBM} in Netflix Prize\footnote{\url{https://www.netflixprize.com}}. %


 One line of deep learning based methods seeks to improve the recommendation performance by integrating the distributed item representations learned from auxiliary information, \textit{e.g.}, text~\cite{Wang:kdd2015:CDL,Kim:recsys2016:CMF}, images~\cite{Wang:www2017:YIR,Kang:icdm2017:Visually}, and acoustic features~\cite{Oord:nips2013:Deep} into CF models. 
Another line of work seeks to take the place of conventional matrix factorization. 
For example, Neural Collaborative Filtering (NCF)~\cite{He:www2017:NCF} estimates user preferences via Multi-Layer Perceptions (MLP) instead of inner product, while AutoRec~\cite{Sedhain:www2015:AAM} and CDAE~\cite{Wu:wsdm2016:CDA} predict users' ratings using Auto-encoder framework.


\subsection{Sequential Recommendation}

Unfortunately, none of the above methods is for sequential recommendation since they all ignore the order in users' behaviors.

Early works on sequential recommendation usually capture sequential patterns from user historical interactions using Markov chains (MCs).
For example, \citeauthor{Shani:jmlr2005:MRS}~\cite{Shani:jmlr2005:MRS} formalized recommendation generation as a sequential optimization problem and employ Markov Decision Processes (MDPs) to address it. 
Later, \citeauthor{Rendle:WWW2010:FPM}~\cite{Rendle:WWW2010:FPM} combine the power of MCs and MF to model both sequential behaviors and general interests by Factorizing Personalized Markov Chains (FPMC).
Besides the first-order MCs, high-order MCs are also adopted to  consider more previous items~\cite{He:icdm16:Fusing,He:recsys2017:TR}. 
 
Recently, RNN and its variants, Gated Recurrent Unit (GRU)~\cite{Cho:emnlp2014:gru} and Long Short-Term Memory (LSTM)~\cite{Hochreiter:LSTM:NC1997}, are becoming more and more popular for modeling user behavior sequences~\cite{Hidasi:ICLR2016:gru4rec,Yu:sigir2016:DRM,Wu:wsdm2017:RRN,Donkers:recsys2017:SUR,Quadrana:recsys2017:PSR,Li:cikm2017:NAS,Hidasi:CIKM2018:RNN}.
The basic idea of these methods is to encode user's previous records into a vector (\textit{i.e.}, representation of user's preference which is used to make predictions) with various recurrent architectures and loss functions, including session-based GRU with ranking loss (GRU4Rec)~\cite{Hidasi:ICLR2016:gru4rec}, Dynamic REcurrent bAsket Model (DREAM)~\cite{Yu:sigir2016:DRM}, user-based GRU~\cite{Donkers:recsys2017:SUR}, attention-based GRU (NARM)~\cite{Li:cikm2017:NAS}, and improved GRU4Rec with new loss function (\textit{i.e.}, \texttt{BPR-max} and \texttt{TOP1-max}) and an improved sampling strategy~\cite{Hidasi:CIKM2018:RNN}.



Other than recurrent neural networks, various deep learning models are also introduced for sequential recommendation~\cite{Chen:wsdm2018:SRU,Tang:WSDM2018:caser,Liu:kdd2018:STAMP,Kang:ICDM2018:SAS}. %
For example, \citeauthor{Tang:WSDM2018:caser}~\cite{Tang:WSDM2018:caser} propose a Convolutional Sequence  Model (Caser) to learn sequential patterns using both horizontal and vertical convolutional filters.
\citeauthor{Chen:wsdm2018:SRU}~\cite{Chen:wsdm2018:SRU} and \citeauthor{Huang:sigir2018:ISR}~\cite{Huang:sigir2018:ISR} employ Memory Network to improve sequential recommendation.
STAMP captures both users' general interests and current interests using an MLP network with attention~\cite{Liu:kdd2018:STAMP}.

 

\subsection{Attention Mechanism}

Attention mechanism has shown promising potential in modeling sequential data, \textit{e.g.}, machine translation~\cite{Bahdanau:iclr2015,Vaswani:nips2017:Attention} and text classification~\cite{Yang:naacl2016:HAN}. 
Recently, some works try to employ the attention mechanism to improve recommendation performances and interpretability~\cite{Li:cikm2017:NAS,Liu:kdd2018:STAMP}.
For example, \citeauthor{Li:cikm2017:NAS}~\cite{Li:cikm2017:NAS} incorporate an attention mechanism into GRU to capture both the user's sequential behavior and main purpose in session-based recommendation.


\input{model_fig}

The works mentioned above basically treat attention mechanism as an additional component to the original models. %
In contrast, Transformer~\cite{Vaswani:nips2017:Attention} and BERT~\cite{Devlin:2018:BERT} are built solely on multi-head self-attention and achieve state-of-the-art results on text sequence modeling.
Recently, there is a rising enthusiasm for applying purely attention-based neural networks to model sequential data for their effectiveness and efficiency~\cite{Lin:iclr2017,Shaw:naacl2018:self,Liu:iclr2018:Generating,Radford:2018:GPT,Radford:2019:Language}.
For sequential recommendation, \citeauthor{Kang:ICDM2018:SAS}~\cite{Kang:ICDM2018:SAS} introduce a two-layer \textit{Transformer decoder} (\textit{i.e.}, Transformer language model) called SASRec to capture user's sequential behaviors and achieve state-of-the-art results on several public datasets.
SASRec is closely related to our work.
However, it is still a unidirectional model using a casual attention mask.
While we use a bidirectional model to encode users' behavior sequences with the help of Cloze task.


