Document (#39723)

Author

Borodin, Y.
Polishchuk, V.
Mahmud, J.
Ramakrishnan, I.V.
Stent, A.

Title

Live and learn from mistakes : a lightweight system for document classification

Source

Information processing and management. 49(2013) no.1, S.83-98

Year

2013

Abstract

We present a Life-Long Learning from Mistakes (3LM) algorithm for document classification, which could be used in various scenarios such as spam filtering, blog classification, and web resource categorization. We extend the ideas of online clustering and batch-mode centroid-based classification to online learning with negative feedback. The 3LM is a competitive learning algorithm, which avoids over-smoothing, characteristic of the centroid-based classifiers, by using a different class representative, which we call clusterhead. The clusterheads competing for vector-space dominance are drawn toward misclassified documents, eventually bringing the model to a "balanced state" for a fixed distribution of documents. Subsequently, the clusterheads oscillate between the misclassified documents, heuristically minimizing the rate of misclassifications, an NP-complete problem. Further, the 3LM algorithm prevents over-fitting by "leashing" the clusterheads to their respective centroids. A clusterhead provably converges if its class can be separated by a hyper-plane from all other classes. Lifelong learning with fixed learning rate allows 3LM to adapt to possibly changing distribution of the data and continually learn and unlearn document classes. We report on our experiments, which demonstrate high accuracy of document classification on Reuters21578, OHSUMED, and TREC07p-spam datasets. The 3LM algorithm did not show over-fitting, while consistently outperforming centroid-based, Naïve Bayes, C4.5, AdaBoost, kNN, and SVM whose accuracy had been reported on the same three corpora.

Content

Vgl.: doi:10.1016/j.ipm.2012.02.001.

Theme

Automatisches Klassifizieren

Similar documents (content)

1. Wang, J.: ¬An extensive study on automated Dewey Decimal Classification (2009) 0.19

   0.19162904 = sum of:
     0.19162904 = product of:
       0.53230286 = sum of:
         0.05888518 = weight(abstract_txt:distribution in 159) [ClassicSimilarity], result of:
           0.05888518 = score(doc=159,freq=2.0), product of:
             0.11903672 = queryWeight, product of:
               1.2782131 = boost
               5.5966744 = idf(docFreq=447, maxDocs=44421)
               0.016639782 = queryNorm
             0.4946808 = fieldWeight in 159, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.5966744 = idf(docFreq=447, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.046982087 = weight(abstract_txt:classes in 159) [ClassicSimilarity], result of:
           0.046982087 = score(doc=159,freq=1.0), product of:
             0.12901548 = queryWeight, product of:
               1.3307109 = boost
               5.8265367 = idf(docFreq=355, maxDocs=44421)
               0.016639782 = queryNorm
             0.36415854 = fieldWeight in 159, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.8265367 = idf(docFreq=355, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.04869079 = weight(abstract_txt:class in 159) [ClassicSimilarity], result of:
           0.04869079 = score(doc=159,freq=1.0), product of:
             0.13212495 = queryWeight, product of:
               1.3466514 = boost
               5.8963327 = idf(docFreq=331, maxDocs=44421)
               0.016639782 = queryNorm
             0.3685208 = fieldWeight in 159, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.8963327 = idf(docFreq=331, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.050165374 = weight(abstract_txt:accuracy in 159) [ClassicSimilarity], result of:
           0.050165374 = score(doc=159,freq=1.0), product of:
             0.13477923 = queryWeight, product of:
               1.3601108 = boost
               5.9552646 = idf(docFreq=312, maxDocs=44421)
               0.016639782 = queryNorm
             0.37220404 = fieldWeight in 159, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.9552646 = idf(docFreq=312, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.038480047 = weight(abstract_txt:over in 159) [ClassicSimilarity], result of:
           0.038480047 = score(doc=159,freq=2.0), product of:
             0.10261191 = queryWeight, product of:
               1.4534742 = boost
               4.242705 = idf(docFreq=1734, maxDocs=44421)
               0.016639782 = queryNorm
             0.37500566 = fieldWeight in 159, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.242705 = idf(docFreq=1734, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.037615124 = weight(abstract_txt:document in 159) [ClassicSimilarity], result of:
           0.037615124 = score(doc=159,freq=1.0), product of:
             0.14015393 = queryWeight, product of:
               1.9614644 = boost
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.016639782 = queryNorm
             0.26838437 = fieldWeight in 159, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.099957064 = weight(abstract_txt:classification in 159) [ClassicSimilarity], result of:
           0.099957064 = score(doc=159,freq=7.0), product of:
             0.15141769 = queryWeight, product of:
               2.279403 = boost
               3.9921594 = idf(docFreq=2228, maxDocs=44421)
               0.016639782 = queryNorm
             0.6601413 = fieldWeight in 159, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               3.9921594 = idf(docFreq=2228, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.088206664 = weight(abstract_txt:algorithm in 159) [ClassicSimilarity], result of:
           0.088206664 = score(doc=159,freq=1.0), product of:
             0.24737997 = queryWeight, product of:
               2.6059139 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.016639782 = queryNorm
             0.35656348 = fieldWeight in 159, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
         0.06332053 = weight(abstract_txt:learning in 159) [ClassicSimilarity], result of:
           0.06332053 = score(doc=159,freq=1.0), product of:
             0.21364692 = queryWeight, product of:
               2.707579 = boost
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.016639782 = queryNorm
             0.29637933 = fieldWeight in 159, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.0625 = fieldNorm(doc=159)
       0.36 = coord(9/25)
   

2. Li, Y.; Shawe-Taylor, J.: Advanced learning algorithms for cross-language patent retrieval and classification (2007) 0.19

   0.1856798 = sum of:
     0.1856798 = product of:
       0.58024937 = sum of:
         0.014362924 = weight(abstract_txt:based in 1931) [ClassicSimilarity], result of:
           0.014362924 = score(doc=1931,freq=1.0), product of:
             0.057757173 = queryWeight, product of:
               1.0904641 = boost
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.016639782 = queryNorm
             0.24867775 = fieldWeight in 1931, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
         0.014689781 = weight(abstract_txt:which in 1931) [ClassicSimilarity], result of:
           0.014689781 = score(doc=1931,freq=1.0), product of:
             0.06453081 = queryWeight, product of:
               1.3309488 = boost
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.016639782 = queryNorm
             0.2276398 = fieldWeight in 1931, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
         0.044152867 = weight(abstract_txt:documents in 1931) [ClassicSimilarity], result of:
           0.044152867 = score(doc=1931,freq=2.0), product of:
             0.09691849 = queryWeight, product of:
               1.4125758 = boost
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.016639782 = queryNorm
             0.455567 = fieldWeight in 1931, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
         0.07356703 = weight(abstract_txt:learn in 1931) [ClassicSimilarity], result of:
           0.07356703 = score(doc=1931,freq=1.0), product of:
             0.14992328 = queryWeight, product of:
               1.4344894 = boost
               6.2809324 = idf(docFreq=225, maxDocs=44421)
               0.016639782 = queryNorm
             0.49069786 = fieldWeight in 1931, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.2809324 = idf(docFreq=225, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
         0.047018904 = weight(abstract_txt:document in 1931) [ClassicSimilarity], result of:
           0.047018904 = score(doc=1931,freq=1.0), product of:
             0.14015393 = queryWeight, product of:
               1.9614644 = boost
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.016639782 = queryNorm
             0.33548045 = fieldWeight in 1931, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
         0.066786624 = weight(abstract_txt:classification in 1931) [ClassicSimilarity], result of:
           0.066786624 = score(doc=1931,freq=2.0), product of:
             0.15141769 = queryWeight, product of:
               2.279403 = boost
               3.9921594 = idf(docFreq=2228, maxDocs=44421)
               0.016639782 = queryNorm
             0.44107544 = fieldWeight in 1931, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.9921594 = idf(docFreq=2228, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
         0.110258326 = weight(abstract_txt:algorithm in 1931) [ClassicSimilarity], result of:
           0.110258326 = score(doc=1931,freq=1.0), product of:
             0.24737997 = queryWeight, product of:
               2.6059139 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.016639782 = queryNorm
             0.44570434 = fieldWeight in 1931, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
         0.20941295 = weight(abstract_txt:learning in 1931) [ClassicSimilarity], result of:
           0.20941295 = score(doc=1931,freq=7.0), product of:
             0.21364692 = queryWeight, product of:
               2.707579 = boost
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.016639782 = queryNorm
             0.9801824 = fieldWeight in 1931, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.078125 = fieldNorm(doc=1931)
       0.32 = coord(8/25)
   

3. Wolfram, D.; Zhang, J.: ¬An investigation of the influence of indexing exhaustivity and term distributions on a document space (2002) 0.16

   0.16301434 = sum of:
     0.16301434 = product of:
       0.6792264 = sum of:
         0.022980679 = weight(abstract_txt:based in 238) [ClassicSimilarity], result of:
           0.022980679 = score(doc=238,freq=4.0), product of:
             0.057757173 = queryWeight, product of:
               1.0904641 = boost
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.016639782 = queryNorm
             0.3978844 = fieldWeight in 238, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.0625 = fieldNorm(doc=238)
         0.05888518 = weight(abstract_txt:distribution in 238) [ClassicSimilarity], result of:
           0.05888518 = score(doc=238,freq=2.0), product of:
             0.11903672 = queryWeight, product of:
               1.2782131 = boost
               5.5966744 = idf(docFreq=447, maxDocs=44421)
               0.016639782 = queryNorm
             0.4946808 = fieldWeight in 238, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.5966744 = idf(docFreq=447, maxDocs=44421)
               0.0625 = fieldNorm(doc=238)
         0.01661959 = weight(abstract_txt:which in 238) [ClassicSimilarity], result of:
           0.01661959 = score(doc=238,freq=2.0), product of:
             0.06453081 = queryWeight, product of:
               1.3309488 = boost
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.016639782 = queryNorm
             0.25754502 = fieldWeight in 238, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.0625 = fieldNorm(doc=238)
         0.035322294 = weight(abstract_txt:documents in 238) [ClassicSimilarity], result of:
           0.035322294 = score(doc=238,freq=2.0), product of:
             0.09691849 = queryWeight, product of:
               1.4125758 = boost
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.016639782 = queryNorm
             0.3644536 = fieldWeight in 238, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.0625 = fieldNorm(doc=238)
         0.112845376 = weight(abstract_txt:document in 238) [ClassicSimilarity], result of:
           0.112845376 = score(doc=238,freq=9.0), product of:
             0.14015393 = queryWeight, product of:
               1.9614644 = boost
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.016639782 = queryNorm
             0.80515313 = fieldWeight in 238, product of:
               3.0 = tf(freq=9.0), with freq of:
                 9.0 = termFreq=9.0
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.0625 = fieldNorm(doc=238)
         0.43257326 = weight(abstract_txt:centroid in 238) [ClassicSimilarity], result of:
           0.43257326 = score(doc=238,freq=2.0), product of:
             0.51492876 = queryWeight, product of:
               3.2559822 = boost
               9.504243 = idf(docFreq=8, maxDocs=44421)
               0.016639782 = queryNorm
             0.8400643 = fieldWeight in 238, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               9.504243 = idf(docFreq=8, maxDocs=44421)
               0.0625 = fieldNorm(doc=238)
       0.24 = coord(6/25)
   

4. Hofferer, M.: Heuristic search in information retrieval (1994) 0.14

   0.13520336 = sum of:
     0.13520336 = product of:
       0.56334734 = sum of:
         0.022980679 = weight(abstract_txt:based in 1138) [ClassicSimilarity], result of:
           0.022980679 = score(doc=1138,freq=1.0), product of:
             0.057757173 = queryWeight, product of:
               1.0904641 = boost
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.016639782 = queryNorm
             0.3978844 = fieldWeight in 1138, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.125 = fieldNorm(doc=1138)
         0.0865216 = weight(abstract_txt:documents in 1138) [ClassicSimilarity], result of:
           0.0865216 = score(doc=1138,freq=3.0), product of:
             0.09691849 = queryWeight, product of:
               1.4125758 = boost
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.016639782 = queryNorm
             0.8927254 = fieldWeight in 1138, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.125 = fieldNorm(doc=1138)
         0.07523025 = weight(abstract_txt:document in 1138) [ClassicSimilarity], result of:
           0.07523025 = score(doc=1138,freq=1.0), product of:
             0.14015393 = queryWeight, product of:
               1.9614644 = boost
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.016639782 = queryNorm
             0.53676873 = fieldWeight in 1138, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.125 = fieldNorm(doc=1138)
         0.07556044 = weight(abstract_txt:classification in 1138) [ClassicSimilarity], result of:
           0.07556044 = score(doc=1138,freq=1.0), product of:
             0.15141769 = queryWeight, product of:
               2.279403 = boost
               3.9921594 = idf(docFreq=2228, maxDocs=44421)
               0.016639782 = queryNorm
             0.49901992 = fieldWeight in 1138, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.9921594 = idf(docFreq=2228, maxDocs=44421)
               0.125 = fieldNorm(doc=1138)
         0.17641333 = weight(abstract_txt:algorithm in 1138) [ClassicSimilarity], result of:
           0.17641333 = score(doc=1138,freq=1.0), product of:
             0.24737997 = queryWeight, product of:
               2.6059139 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.016639782 = queryNorm
             0.71312696 = fieldWeight in 1138, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.125 = fieldNorm(doc=1138)
         0.12664106 = weight(abstract_txt:learning in 1138) [ClassicSimilarity], result of:
           0.12664106 = score(doc=1138,freq=1.0), product of:
             0.21364692 = queryWeight, product of:
               2.707579 = boost
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.016639782 = queryNorm
             0.59275866 = fieldWeight in 1138, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.125 = fieldNorm(doc=1138)
       0.24 = coord(6/25)
   

5. Krulwich, B.; Burkey, C.: Jack and the InfoFinder agent (1997) 0.13

   0.13403368 = sum of:
     0.13403368 = product of:
       0.5584737 = sum of:
         0.17335834 = weight(abstract_txt:heuristically in 4262) [ClassicSimilarity], result of:
           0.17335834 = score(doc=4262,freq=1.0), product of:
             0.18660042 = queryWeight, product of:
               1.1316291 = boost
               9.909708 = idf(docFreq=5, maxDocs=44421)
               0.016639782 = queryNorm
             0.9290351 = fieldWeight in 4262, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.909708 = idf(docFreq=5, maxDocs=44421)
               0.09375 = fieldNorm(doc=4262)
         0.017627735 = weight(abstract_txt:which in 4262) [ClassicSimilarity], result of:
           0.017627735 = score(doc=4262,freq=1.0), product of:
             0.06453081 = queryWeight, product of:
               1.3309488 = boost
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.016639782 = queryNorm
             0.27316773 = fieldWeight in 4262, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.9137893 = idf(docFreq=6552, maxDocs=44421)
               0.09375 = fieldNorm(doc=4262)
         0.08377419 = weight(abstract_txt:documents in 4262) [ClassicSimilarity], result of:
           0.08377419 = score(doc=4262,freq=5.0), product of:
             0.09691849 = queryWeight, product of:
               1.4125758 = boost
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.016639782 = queryNorm
             0.86437774 = fieldWeight in 4262, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               4.123322 = idf(docFreq=1954, maxDocs=44421)
               0.09375 = fieldNorm(doc=4262)
         0.056422688 = weight(abstract_txt:document in 4262) [ClassicSimilarity], result of:
           0.056422688 = score(doc=4262,freq=1.0), product of:
             0.14015393 = queryWeight, product of:
               1.9614644 = boost
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.016639782 = queryNorm
             0.40257657 = fieldWeight in 4262, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.29415 = idf(docFreq=1647, maxDocs=44421)
               0.09375 = fieldNorm(doc=4262)
         0.13231 = weight(abstract_txt:algorithm in 4262) [ClassicSimilarity], result of:
           0.13231 = score(doc=4262,freq=1.0), product of:
             0.24737997 = queryWeight, product of:
               2.6059139 = boost
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.016639782 = queryNorm
             0.53484523 = fieldWeight in 4262, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7050157 = idf(docFreq=401, maxDocs=44421)
               0.09375 = fieldNorm(doc=4262)
         0.0949808 = weight(abstract_txt:learning in 4262) [ClassicSimilarity], result of:
           0.0949808 = score(doc=4262,freq=1.0), product of:
             0.21364692 = queryWeight, product of:
               2.707579 = boost
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.016639782 = queryNorm
             0.444569 = fieldWeight in 4262, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.7420692 = idf(docFreq=1052, maxDocs=44421)
               0.09375 = fieldNorm(doc=4262)
       0.24 = coord(6/25)