  We consider principled alternatives to unsupervised learning in data mining
by situating the learning task in the context of the subsequent analysis task.
Specifically, we consider a query-answering (hypothesis-testing) task: In the
combined task, we decide whether an input query formula is satisfied over a
background distribution by using input examples directly, rather than invoking
a two-stage process in which (i) rules over the distribution are learned by an
unsupervised learning algorithm and (ii) a reasoning algorithm decides whether
or not the query formula follows from the learned rules. In a previous work
(2013), we observed that the learning task could satisfy numerous desirable
criteria in this combined context -- effectively matching what could be
achieved by agnostic learning of CNFs from partial information -- that are not
known to be achievable directly. In this work, we show that likewise, there are
reasoning tasks that are achievable in such a combined context that are not
known to be achievable directly (and indeed, have been seriously conjectured to
be impossible, cf. (Alekhnovich and Razborov, 2008)). Namely, we test for a
resolution proof of the query formula of a given size in quasipolynomial time
(that is, "quasi-automatizing" resolution). The learning setting we consider is
a partial-information, restricted-distribution setting that generalizes
learning parities over the uniform distribution from partial information,
another task that is known not to be achievable directly in various models (cf.
(Ben-David and Dichterman, 1998) and (Michael, 2010)).
