8
8
This is a non-mathematical tutorial on how to use the dbacl Bayesian text
9
9
classifier. The mathematical details can be read <a href="dbacl.ps">here</a>.
10
<i>This tutorial was revised for dbacl 1.11. As dbacl evolves, some statements
11
below may become inaccurate, but reasonable effort is made to keep the tutorial
11
14
<a href="http://www.lbreyer.com/gpl.html">dbacl</a> is a UNIX command
12
15
line tool, so you will need to work at the shell prompt (here written
13
%, even though we use Bash semantics). The program comes with five
16
%, even though we use bash semantics). The program comes with five
14
17
sample text documents and a few scripts. Look for them in the same
15
18
directory as this tutorial, or you can use any other plain text
16
19
documents instead. Make sure the sample documents you will use are in
45
48
category learned from <i>sample2.txt</i>) and more like <i>one</i> (which is the
46
49
category learned from <i>sample1.txt</i>). That's it.
53
Besides giving the best category (note: best means best among available choices only), dbacl can measure how sure it is of being right. Try this:
55
% dbacl -c one -c two sample3.txt -U
58
In this case dbacl is very sure. If the percentage was zero, then it would
59
mean that there is another equally likely category. Try this:
61
% dbacl -c one -c two -c one sample3.txt -U
64
Obviously we've repeated the category <i>one</i> but dbacl treats them separately. dbacl can also print other measures of certainty besides the <i>-U</i> switch, but
65
they take longer to explain.
48
67
You can create as many categories as you want, <i>one</i>, <i>two</i>, <i>three</i>, <i>good</i>, <i>bad</i>, <i>important</i>, <i>jokes</i>, but remember that each one must be learned from a representative
49
68
collection of plain text documents.
139
158
To get a feel for the kinds of features taken into account by dbacl in the example above, you can use the -D option. Retype the above in the slightly changed form
141
160
% dbacl -l justq -g '^([a-zA-Z]*q[a-zA-Z]*)' \
142
-g '[^a-zA-Z]([a-zA-Z]*q[a-zA-Z]*)' sample2.txt -D | head -10
161
-g '[^a-zA-Z]([a-zA-Z]*q[a-zA-Z]*)' sample2.txt -D | grep match
162
match d191e93e []acquired[](1) 1
163
match 8c56f142 []inquire[](1) 1
164
match 7a2ccda2 []inquiry[](1) 1
165
match 38f595f3 []consequently[](1) 1
166
match a52053f2 []questions[](1) 1
167
match 78a0e302 []question[](1) 1
145
This lists the first few matches, one per line, which exist in the <i>sample1.txt</i> document. Obviously, only taking into account features which consist of words with the letter 'q' in them makes a poor model.
170
This command lists the first few matches, one per line, which exist in the <i>sample1.txt</i> document. Obviously, only taking into account features which consist of words with the letter 'q' in them makes a poor model. However, when
171
you are trying out regular expressions, you can compare this output with the
172
contents of the document to see if your expression misses out on words or reads too many.
147
174
Sometimes, it's convenient to use parentheses which you want to throw away. dbacl
148
175
understands the special notation ||xyz which you can place at the end of a regular expression, where x, y, z should be digits corresponding to the parentheses
222
249
% dbacl -l slick -w 2 sample1.txt
225
produces a model <i>slick</i> which is nearly identical to <i>smooth</i> (the difference is that a regular expression cannot straddle newlines, but -w ngrams can).
252
produces a model <i>slick</i> which is nearly identical to <i>smooth</i> (the difference is that a regular expression cannot straddle newlines, but -w ngrams can). Let's look at the first few features: type
254
% dbacl -l slick -w 2 sample1.txt -D | grep match | head -10
255
match 818ad280 []tom[](1) 1
256
match 5d20c0e2 []tom[]no[](1) 2
257
match 3db5da99 []no[](1) 1
258
match 4a18ad66 []no[]answer[](1) 2
259
match eea4a1c4 []answer[](1) 1
260
match 95392743 []answer[]tom[](1) 2
261
match 61cc1403 []answer[]what[](1) 2
262
match 8c953ec2 []what[](1) 1
263
match 4291d86e []what[]s[](1) 2
264
match b09aa375 []s[](1) 1
266
You can see both pairs and single words, all lower case because dbacl
267
converts everything to lower case unless you tell it otherwise. This saves
268
a little on memory. But what did the original document look like?
270
% head -10 sample1.txt
279
"What's gone with that boy, I wonder? You TOM!"
282
Now you see how the pairs are formed. But wait, the pair of words
283
("TOM!", No) occurs twice in the text, but only once in the list of matches?
284
Did we miss one? No, look again at the line
286
match 5d20c0e2 []tom[]no[](1) 2
288
and you will see that the last value is '2', since we've seen it twice.
289
dbacl uses the frequencies of features to build its model.
227
291
Obviously, all this typing is getting tedious, and you will eventually
253
317
The cross entropy is measured in bits and has the following meaning:
254
318
If we use our probabilistic model to construct an optimal compression algorithm,
255
319
then the cross entropy of a text string is the predicted number of bits which is needed on average, after compression, for each separate feature.
256
This rough description isn't complete, since the cross entropy doesn't measure the amount of space also needed for the probability model itself.
320
This rough description isn't complete, since the cross entropy doesn't measure the amount of space also needed for the probability model itself, and moreover
321
what we mean by compression is the act of compressing the features, not the full
322
document, which also contains punctuation and white space which is ignored.
258
324
To compute the cross entropy of category <i>one</i>, type
260
326
% dbacl -c one sample1.txt -vn
261
cross_entropy 7.60 bits complexity 678
264
The cross entropy is the first value returned. The second value essentially
330
The cross entropy is the first value (7.42) returned. The second value essentially
265
331
measures how many features describe the document.
266
332
Now suppose we try other models trained on the same document:
268
334
% dbacl -c slick sample1.txt -vn
269
cross_entropy 4.74 bits complexity 677
270
336
% dbacl -c smooth sample1.txt -vn
271
cross_entropy 5.27 bits complexity 603
274
According to these estimates, both bigram models fit <i>sample1.txt</i> better. This is
340
The first thing to nota is that the complexity terms are not the same. The
341
<i>slick</i> category is based on word pairs (also called bigrams), of
342
which tere are 677 in this document. But there are 678 words, and the
343
fractional value indicates that the last word only counts for half a
344
feature. The <i>smooth</i> category also depends on word pairs, but
345
unlike <i>slick</i>, pairs cannot be counted if they straddle a
346
newline (this is a limitation of line-oriented regular expressions).
347
So in <i>smooth</i>, there are several missing word pairs, and various
348
single words which count as a fractional pair, giving a grand total of
351
The second thing to note is that both bigram models fit <i>sample1.txt</i> better. This is
275
352
easy to see for <i>slick</i>, since the complexity (essentially the number of features)
276
is nearly the same as for <i>one</i>. But <i>smooth</i> looks at fewer features, and actually
277
compresses them just slightly better in this case. Let's ask dbacl which category fits better:
353
is nearly the same as for <i>one</i>, so the comparison reduces to seeing
354
which cross entropy is lowest.
355
Let's ask dbacl which category fits better:
357
% dbacl -c one -c slick sample1.txt -v
361
You can do the same thing to compare <i>one</i> and <i>smooth</i>.
362
Let's ask dbacl which category fits better overall:
279
364
% dbacl -c one -c slick -c smooth sample1.txt -v
368
We already know that <i>slick</i> is better than <i>one</i>, but why is
369
<i>slick</i> better than <i>smooth</i>? While <i>slick</i> looks at more
370
features than <i>smooth</i> (677.5 versus 640.5), it needs just 4.68 bits
371
of information per feature to represent the <i>sample1.txt</i> document,
372
while <i>smooth</i> needs 6.03 bits on average. So <i>slick</i> wins based
373
on economies of scale.
284
WARNING: dbacl doesn't yet cope well with widely different feature sets. Don't try to compare
285
categories built on completely different feature specifications unless you fully understand the
286
statistical implications.
376
WARNING: it is not always appropriate to classify documents whose models
377
look at different feature set like we did above. The underlying statistical
378
basis for these comparisons is the likelihood, but it is easy to
379
compare "apples and oranges" incorrectly. It is safest if you learn and
380
classify documents by using exactly the same command line switches
289
384
<h2>Decision Theory</h2>
409
504
bayesol is a companion program for dbacl which makes the decision calculations
410
505
easier. The bad news is that you still have to write down a prior and loss matrix
411
506
yourself. Eventually, someone, somewhere may write a graphical interface.
507
The good news is that for most classification tasks, you don't need to
508
bother with bayesol at all, and can skip this section. Really.
413
510
bayesol reads a risk specification file, which is a text file containing information about the categories required, the prior distribution and the cost of
414
511
misclassifications. For the toy example discussed earlier, the file <i>toy.risk</i> looks like this:
653
750
Remember that dbacl calculates probabilities about resemblance
654
751
by weighing the evidence for all the features found in the input document.
655
There are 519 features in <i>sample4.txt</i>, and each feature contributes on average 20.25 bits of evidence against category <i>one</i>, 15.24 bits against category <i>two</i> and 20.08 bits against category <i>three</i>. Let's look at what happens if we only look at the first 25 lines of <i>sample4.txt</i>:
752
There are 519 features in <i>sample4.txt</i>, and each feature contributes on average 26.11 bits of evidence against category <i>one</i>, 15.84 bits against category <i>two</i> and 25.97 bits against category <i>three</i>. Let's look at what happens if we only look at the first 25 lines of <i>sample4.txt</i>:
657
754
% head -25 sample4.txt | dbacl -c one -c two -c three -nv
658
one 19.01 * 324 two 14.61 * 324 three 18.94 * 324
755
one 20.15 * 324.0 two 15.18 * 324.0 three 20.14 * 324.0
661
758
There are fewer features in the first 25 lines of <i>sample4.txt</i> than in the full
668
765
dbacl is still very sure, because it has looked at many features (324) and found
669
766
small differences which add up to quite different scores. However, you can see that
670
each feature now contributes less information (19.01, 14.61, 18.98) bits compared
671
to the earlier (20.25, 15.24, 20.08).
767
each feature now contributes less information (20.15, 15.18, 20.14) bits compared
768
to the earlier (26.11, 15.84, 25.97).
673
770
Since category <i>two</i> is obviously the best (closest to zero) choice among the
674
771
three models, let's drop it for a moment and consider the other two categories.
686
783
probabilities are mixed:
688
785
% head -1 sample4.txt | dbacl -c one -c three -nv
689
one 15.47 * 15 three 15.30 * 15
786
one 16.61 * 15.0 three 16.51 * 15.0
692
789
So the interpretation of the probabilities is clear. dbacl weighs the
693
790
evidence from each feature it finds, and reports the best fit among the choices
694
it is offered. Because it sees so many features separately, it believes
695
its verdict is very sure. Of course, whether these
696
features are the right features to look at for best classification is another
697
matter entirely, and it's entirely up to you to decide.
791
it is offered. Because it sees so many features separately (hundreds usually), it believes
792
its verdict is very sure. Wouldn't you be after hundreds of checks?
793
Of course, whether these
794
features are independent, and are the right features to look at for best classification is another
795
matter entirely, and it's entirely up to you to decide. dbacl can't do much
796
about its inbuilt assumptions.
798
Last but not least, the probabilities above are not the same as the
799
confidence percentages printed by the -U switch. The -U switch was developed
800
to overcome the limitations above, by looking at dbacl's calculations
801
from a higher level, but this is a topic for another time.
b'\\ No newline at end of file'
added
removed
doc/tutorial.html
