Many of the papers that you can find on the internet are what are called "preprints". A preprint is a manuscript prepared by the author (usually before the paper is submitted for publication, but it can sometimes also include corrections that were made during the review process, in which case it may be called a "postprint.")
When a paper is eventually published in a journal or conference proceedings volume, the publisher will often reformat the paper and typically add headers or footers to the pages that list the journal, volume, page numbers, etc. These headers/footers also typically include a copyright notice from the publisher. These published versions of papers are often unavailable to the public and can only be read by people who have personal or institutional subscriptions to the journal or conference proceedings.
Because of this problem of lack of access, many authors leave preprints up on their web sites so that anyone can read the paper. Thus you'll often find that a paper exists in a published version (with full citation information in the headers and footers) and a preprint version (usually without this information.)
The particular example that you linked to is a paper that was published in the NIPS 2012 conference proceedings. The published version is also available from the NIPS web site. Surprisingly, NIPS didn't format the paper with information about its being from the NIPS 2012 conference proceedings- this is a bit unusual in my experience but not unheard of.