Why aren't the diagonal counts used in McNemar's test? In reviewing McNemar's test, I see that the diagonal counts aren't used in computing the test statistic. However, since the test is testing the null that the row and column marginals are equal, testing $H_0\! : p_b \stackrel ? = p_c$ seems to be testing a different hypothesis.
Why are the counts in cell "a" just ignored? For instance, compare these two separate scenarios which McNemar's test would treat identically:


*

*Little data in cell "a"
 3  10
20   0


*Lots of data in cell "a"
 1e+6  10
   20   0

As background on my actual task, I am comparing the performance of two classification algorithms, A and B, on a held-out set of examples. In my experiment's contingency table, cell "a" contains the number of examples both algorithms get right; cell "b" contains the number of examples A gets right which B gets wrong; cell "c" contains the number of examples A gets wrong but B gets right; and cell "d" contains the number of examples both algorithms get wrong.
Now consider the contingency tables I drafted above. The first one has a small number of counts in cell "a" while the other has a ton of counts in "a". The difference in number of misclassifications between A and B seems large in table #1, but small in table #2. Thus, McNemar's test seems unsuitable for determining whether A and B's performance is significantly different since it ignores the counts in cell "a".
What my contingency table examples are trying to illustrate is that a difference of (b - c) = (10 - 20) seems large when the total number of observations equals 33 (table #1). But the difference looks a lot like noise if the total number of observations is 1MM (table #2). I understand intuitions can be misleading, especially w.r.t. probability and statistics, but this seems to indicate that McNemar's test is inappropriate for assessing whether the difference between two classification algorithms is significant. Can anyone highlight where my intuition is failing?
 A: The tag info for McNemar's test (once supplied by me, and later possibly modified):

A repeated-measures test for categorical data. Given that two
  variables with the same 2 categories (McNemar test) or k categories
  (McNemar-Bowker test) form a square contingency table, the test's
  question is whether population proportion in every off-diagonal cell
  is equal to that in the symmetric cell. The 2x2 McNemar's test can be seen also as a "marginal homogeneity" test.

Please note first of all that McNemar's / McNemar-Bowker is generally not meant to be the test of marginal homogeneity. There exist a marginal homogeneity test for CxC table which is not the same as McNemar-Bowker test of axial symmetry in CxC table.
But in the specific case of 2x2 table the symmetry McNemar's test becomes also the test of marginal homogeneity. (To add, the above mentioned CxC marginal homogeneity test is actually based internally on repeated application of McNemar's test to all possible 2x2 subtables). (To add yet another info: 2x2 McNemar's test is equivalent to Sign test performed on dichotomous data; and both can be made to return exact or asymptotic p-value.)
So, you are both right (in a specific case) and not so right (generally) saying that McNemar's test is a marginal homogeneity test. First of all, it is the axial symmetry test.
It is used in pre-post studies or match-pair studies to compare symmetric frequencies in the table; the row and the column categories must be same entities. The H0 is that in population all off-diagonal proportions are equal to their symmetric cell proportions vs H1 that at least one proportion differs from its symmetric one.
It is not strange therefore that an off-diagonal symmetry test ignores diagonal entries altogether.
But there is another repeated measures categorical test for CxC contingency table with the same row/column categories - which does take the diagonal entries into account - the well-known Cohen's kappa statistic & test. Use it if you want to consider diagonal. But it tests different hypothesis: H0 = diagonal and off-diagonal proportions even vs H1 = off-diagonal proportions dominate (diagonal is canyon) or diagonal proportions dominate (ridge). Kappa does not consider specifically symmetric cells.

@ted's intuition about McNemar's

But the difference looks a lot like noise if the total number of
  observations is 1MM

is misplaced. To repeat it: the diagonal entries in McNemar's (they would be called "ties", in terminology of Sign test) is conceptually outside of its test hypothesis. The hypothesis is about the binomial question "who wins statistically more often, A or B? or are they about draw by account?". So diagonal, ties, are treated as if "no answer, or don't know" response and thence the observations irrelevant to the experiment. They should be excluded from the sample at the time of testing. Despite they are irrelevant to the H0/H1 they are relevant to the test's power - since being excluded they diminish the effective sample size on which the test is based. Instead of exclusion, you might choose to randomly assign the ties under 1/2 probability either to "A wins" or "B wins", i.e. to treat ties as "chance lost data". This approach will not bias NcNemar's test but will weaken its power (see it).
But if you need to include the diagonal into your test concept (specifically, that under H0 there is even chance to fall into any off-diagonal as well as in any diagonal cell) - then McNemar's test shouldn't interest you. Choose kappa for example, or some other criterion/test. There are a number of them designed specifically to compare classification performances.
Comparing two classifiers is like comparing two rates. Inclusion an observation in a diagonal cell such as a is an effective result of the works of the classifiers. Logically, it should be taken into account. As in kappa. But McNemar is primarily for repeated measures settings for the same set of observations. Those found themselves in cell a just remained indifferent to the effects of the factor; and as long as the test issue is what is the direction of the effect whenever it exists - the cell can't help answer it.
A: Intuitively, since "Cell $a$" is in the first row and first column, including $a$ in your test wouldn't help to assess the difference between the row marginal and the column marginal.  If your row is $a+b$ and your column is $a+c$, to test if $a+b=a+c$, you only need to test $b=c$.  Including $a$ is irrelevant to the extent that we want to test for equality of the row and column marginals.
McNemar's test is used to detect a difference in paired data - often (but not always) this is applied to before and after data.  When you describe "Cell $a$" above, that would be the cell corresponding to the same state before and after.  For example, if you are testing whether or or not dogs fetch a stick better after a training session, $a$ would indicate the number of dogs who fetched a stick before the training session and who fetched a stick after the training session.  Cell $d$ would indicate the number of dogs who did not fetch a stick before training and who did not fetch a stick after training.  If we're interested in seeing the difference between the "before" and "after" results, then we only care about cells $b$ and $c$.
A: Your intuition is reasonable, but incorrect.  (As you note, that state of affairs is very common in probability and statistics.)
Statistical significance vs. effect size / practical significance
You state:

The difference in number of misclassifications between A and B seems large in table #1, but small in table #2. Thus, McNemar's test seems unsuitable for determining whether A and B's performance is significantly different since it ignores the counts in cell "a".

Let me change that to:

The difference in number of misclassifications between A and B seems large in table #1, but small in table #2. Thus, McNemar's test seems unsuitable for determining whether A and B's performance is significantly meaningfully different since it ignores the counts in cell "a".

In general, hypothesis tests are intended to let us determine if we can be confident that there is, in fact, a difference.  This does not mean that the difference is terribly important.  The magnitude of a difference is the effect size.  Whether that effect size is something you would care about (under the assumption you believed it), is a question of practical significance.
