Applying Machine Learning to Improve apropos(1)Abhinav Upadhyay<abhinav@NetBSD.org>

Abstract
In 2011 NetBSD acquired a new implementation of
apropos(1). This new implementation is capable ofdoing full text search using the Sqlite backend.
One of the core components of this new implementation of apropos(1) is its ranking algorithm, whichallows apropos(1) to show more relevant results at the
top of the search results. This ranking algorithm uses aterm weighting scheme called tf-idf. Its performance haslargely proven to be quite satisfactory, however, there is
still much room of improvement.
Playing around with the ranking model requires adataset in order to evaluate and compare the performanceof various models. This paper discusses the creationof a dataset in order to evaluate the performance ofranking models. It also discusses results of training
machine learning models on this dataset with the taskof improving the existing ranking algorithm used in
apropos(1).

1Introduction

The classical version of apropos(1) [2] worked by justsearching the NAME section of man pages. This was afine compromise considering the computing power ofthe machines when apropos(1) was first implemented.
However, on present day machines much more interesting things can be achieved. As mentioned in [5],in 2011 NetBSD replaced its old apropos(1) with a
new implementation. The new implementation [1] wasdesigned to search over the complete body of man pages.
With the increased search area, the number of search
results also increased in the same proportion and in orderto make apropos(1) a useful tool, it was important tofigure out which of the matches are the most relevantto the user query and show them in the beginning. To
do this apropos(1) employs a sophisticated ranking
algorithm. The algorithm computes a relevance scorefor each of the search results and apropos(1) sorts theresults in decreasing order of this relevance score.
The first section of this paper briefly discusses thedesign of the new apropos(1) in NetBSD and thedetails of its ranking scheme. In later sections it talks
about machine learning and how does it plug into theexisting ranking algorithm of apropos(1) to improve
its performance. Namely, it discusses the details of
the regression and classification models from machinelearning and analyses their impact on the performanceof apropos(1).

2Implementation of NetBSD’s apropos(1)The new apropos(1) for NetBSD was developed In
2011 as part of Google Summer of Code 2011. This new
implementation uses mandoc’s [11] library interface totraverse the abstract syntax tree representation of theman pages to extract the text out of the man pages, andindexes it using Sqlite’s FTS module [12]. Listings 1
and 2 show the differences in the outputs of the oldapropos(1) and the new implementation in NetBSD.

2.1

How the new apropos(1) works

makemandb(8) [3] is the tool which was designed toreplace makewhatis(8) [4]. It is used to parse andindex man pages. makemandb(8) uses mandoc’s AST
library interface to parse man pages and stores them inan Sqlite table. The schema of this table is shown intable 1.

$apropos ls
intro (9) - introduction to kernel internals
rump (7) - The Anykernel and Rump Kernels
NLS (7) - Native Language Support Overview
usermgmt .conf (5) - user management tools configuration fileshells (5) - shell database
protocols (5) - protocol name data base
pkg_install .conf (5) - configuration file for package installation tools
uslsa (4) - USB support for Silicon Labs CP210x series serial adapters
mpt (4) - LSI Fusion -MPT SCSI/ Fibre Channel driver
mpls (4) - Multiprotocol Label Switching$apropos "how to compare two strings "how to compare two strings : nothing appropriate

Listing 1: Old apropos output$apropos ls
ls (1)
list directory contents
nslookup (8)query Internet name servers interactively
curses_border (3) curses border drawing routines
column (1)columnate lists
dmctl (8) manipulate device - mapper driver commandgetbsize (3)get user block size
chflags (1)change file flags
symlink (7)symbolic link handling
string_to_flags (3)Stat flags parsing and printing functions
stat (1) display file status$apropos ``how tostrcmp (3)memcmp (9)memcmp (3)bcmp (3)bcmp (9)ldapcompare (1)strcasecmp (3)wcscasecmp (3)msgcmp (1)strcoll (3)compare two strings ''compare strings
compare byte string
compare byte string
compare byte string
compare byte string
LDAP compare toolcompare strings , ignoring casecompare wide - character strings , ignoring casecompare message catalog and templatecompare strings according to current collation

Listing 2: New apropos output

2

Columnname (NAME)
name_desc
desc (DESCRIPTION)
library
return_values
environment
files
exit_status
diagnostics
errorsmachineWeight
2.0
2.0
0.55
0.10
0.001
0.20
0.01
0.001
2.0
0.05
1.0

Algorithm 1 Compute Relevance Weight of a Document
for a Given User Query
Require: User query q
Require: Document d whose weight needs to be computed
Require: An array weights consisting of preassigned
weights for different columns of the FTS table
1: tf ← 0.0
2: idf ← 0.0
3: k ← 3.5. k is an experimentally determinedparameter
4: doclen ← length of the current document
5: ndoc ← Total number of documents in the corpus
6: for each phrase p in q do
7:
for each column c in the FTS table do8:w ← weights[c]. weight for column c
ndoc
)×w
9:
id f ← id f + log( ndocshitcount(nhitcount×w)
10:t f ← t f + (nglobalhitcount×doclen)
11:
end for
12: end for(t f ×id f )13: score ← (k+t f )14: return score

Table 1: Sections indexed and their associated weights
The design of the database has been described indetail in [2]. The key part of the design is that the content
of the man pages is split across multiple columns in thetable. Each column in the table represents a section of
the man page. There are columns for prominent sections
like NAME, DESCRIPTION, RETURN VALUES, LIBRARY,ENVIRONMENT, FILES and so on. Table-1 shows the listof columns which are part of the database table at thistime.

of the weights. The set of values of these weights forwhich apropos(1) was producing best results werechosen as the final values. However, these values are notnecessarily the best possible values of those weights,
they worked well for those fixed set of queries, but theymight not necessarily produce the expected results for adifferent set of queries.

The split of the content into multiple columns is an
important part of the design of the ranking algorithm
used by apropos(1). Each of these sections is assigned
a weight. The higher the weight for a section, the higher
is the importance for a match found in that section.
Algorithm-1 shows the ranking algorithm as used byapropos(1). It shows how those weights are usedwhile computing the relevance score for a document
for a given query. To lookup the details of the ranking
algorithm, please refer [5].

We want to obtain the optimum values of theseweights which will work well for all possible set of
queries representing the man page corpus in NetBSD.
We can use machine learning models to optimise theseweights.

The quantities tf and idf as shown in Algorithm-1
are term frequency and inverse document frequency respectively [7]. Term frequency of a term t in a documentd is defined as the number of times the term occurs in that
document. Whereas the document frequency is definedas the number of documents in which that term occurs
at least once. Inverse document frequency is an inverse
quantity of document frequency, it is used to dampen theeffect of words which are very common, i.e., have highterm frequencies and occur in a large number of documents. Therefore, the product t f × id f tends to boost
matches of the terms having high frequencies within adocument but at the same time discouraging matches ofthe very common words, such as “and”, “the”, “or” etc.

3

Machine Learning - how does it help

Machine learning [8] has been defined as the field ofstudy that gives computers the ability to learn without
being explicitly programmed. Machine learning models
are trained on a set of example inputs (called trainingdata) in order to learn a function which can be used to
predict the output of such inputs. These set of input examples is called a dataset, and it consists of the featuresof the input data, along with the expected output. For
example, for the problem of predicting housing prices,
the input features could be number of bedrooms, thearea of the plot, and the output would be the actual pricefor those houses. Given enough number of examples of

The weights as shown in Table-1 were obtained bymanually running a fixed set of queries and inspecting
the output produced by apropos(1) for various values
3Area (Sqft.)
500
937
1372
1812
2250
2687
3125
3562
4000

this data, the machine learning model would try to learn
a function which could predict the price of the house.
Machine learning models are themselves divided into
two broad categories:
1. Supervised machine learning [8] is used forproblems where we have labelled dataset. The
housing price example mentioned above falls under
the category of supervised learning. Similarly,
a dataset consisting of images along with labels
about whether they contain cats or not, can be used
to train a model to recognize cats in images

Price ($)
14375
22450
26220
31360
42535
46195
54060
61540
67700

Table 2: Sample housing price data set
Figure 1: Area vs Housing Prices

2. Unsupervised machine learning [8] models areused for problems where the output in the dataset
is not labelled. Clustering is an example of unsupervised machine learning where the model learns
to identify clusters in the input dataset without
any labels in the dataset or human supervision.
Intrusion detection is also an example which comesunder unsupervised learning. The amount of data
produced by the devices and appliances runningin a production environment is so massive that
it is impossible for humans to label it. Instead,
unsupervised learning techniques allow building
models which can learn to identify events whichsignify normal operations in the system and events
which signify an abnormality.

3.1

Supervised Machine Learning

For the task of learning the weights of the ranking algorithm, we are only concerned with supervised learningmodels. Supervised machine learning consists of two
broad categories of models: regression and classification [8]. Regression models are used for problems where
we want to predict a continuous range of values. Predicting the price of a house, or predicting the temperature of
the day are examples of regression problems. Classification models are used for problems where the model needs
to learn to predict one of the fixed set of discrete values.
Examples of classification problems include predicting
whether the image contains a cat or not, or whether asearch result is relevant to the query or not.

3.2

function such as:

y = w0 + w1 x

(1)

Where y represents the output of the model (price ofthe house in this example), x represents the input data
(size of the house in case of this example), and w0 and
w1 are the weights to be learned by the model. Equation(1) can be rewritten as:

Understanding Regression

y = w0 x0 + w1 x1

In this section we see in detail how does a regression
model work. Table-2 shows a sample training dataset
consisting of house sizes in square feet and prices of thehouses in $. In order to learn to predict the price of ahouse given its size, we start by defining a hypothesis(2)

where x0 is always 1, it is just added for notational
convenience.
4

Where c is the column in the Sqlite table, representing
the sections of man pages. wc is the weight associatedwith column c, t fc is the term frequency for column cand id fc is the inverse document frequency for column c.
Comparing this to the hypothesis function above, it canbe seen that this function can easily be fit into a regression model to learn the optimum value of the weights.

This hypothesis function presented in (2) is good for
representing only one input feature x1 . It can easily
be extended to represent an arbitrary number of input
features, as shown below:

y = w0 x0 + w1 x1 + w2 x2 + w3 x3 + · · · + wN xN

(3)

3.3

In order to train a regression model for learning theweights for the ranking algorithm of apropos(1) atraining dataset is needed. Lack of an existing dataset
makes this a difficult problem. In order to build thisdataset, query logs from man-k.org1 [10] have been used.

The equation in (3) can be compactly represented as:

y=

N
X

wi xi

(4)
The query logs of man-k.org provided about 1100
unique queries. Those queries were run on apropos(1)and for each of those queries the top 5 results were
sampled. Along with the top 5 results, the column wise
tf-idf weights were also produced for each of thoseresults. While generating these tf-idf weights it wasmade sure that those were pure tf-idf scores and thatthey were not multiplied by the existing weights being
used in apropos(1). Not using the original weights
while generating the scores for this dataset was animportant part of the process. If those weights were partof the scores present in the dataset, the machine learningmodels trained on that dataset would end up learning thesame weights again.

i=1

The equation presented in (4) represents the final hypothesis function, which can be used to predict the priceof a house given its size as input to the function. In orderto evaluate the performance of the model’s prediction, anerror function is required, which quantifies how far aremodel’s prediction from actual values. The model trainson the training data to minimize this error. One of themost common error function used for regression is theresidual sum of squares (RSS) [8], which is defined below:
N

E=

1X 0
(y − yi )22 i=1 i

(5)

Finally, each row of the dataset thus generated was
manually labelled, by assigning a relevance score on ascale of 0 to 4, where 0 represents least relevant resultand 4 represents most relevant result to the query. At
the end of this process, a small dataset of around 2500
records was generated. The dataset is available on thegithub repository of the project [3].

0Here, yi represents the value predicted by the regression model and yi represents the real value for input0
i as present in the training data. The quantity yi − yirepresents the difference between the output predictedby the model and the actual output, which is essentiallythe error made by the model. Squaring this error
ensures that it will always remain positive. Optimization
algorithms such as gradient descent [8] are used in orderto minimize this error over the input dataset. The valuesof w at which the error function is minimized represent the optimum values of the model weight parameters.

3.4

N
X

wc × t fc × id fc

Result of Ranking as Regression

For training regression models, the final relevance score(column w_total in the dataset) was used as the target
feature while the column wise tf-idf weights wereused as the input features to the model. Before training
the models, the value of the w_total column for therows which were labelled with a relevance value of 4
(most relevant to the query), was set to 0.67, which
was the maximum value of w_total in the complete
dataset. While for the rows which were labeled as 0
(least relevant to the query), their w_total was set to0.62, which was the minimum value of w_total in the

As shown in Algorithm-1, apropos(1) uses aranking function which is very similar to the hypothesis
function shown in (4). The function to calculate therelevance score is shown below:

score =

Generation of a dataset for apropos(1)1 man-k.org is a web based interface to NetBSD’s apropos(1),(6)

built by the author.

c=1

5

dataset. Doing this was necessary because this indicatesto the model that it needs to learn weights so that search
results with features similar to the rows having relevance
score of 4 are pushed up in the ranks, while documents
having features similar to that of the rows with relevance
score of 0 are pushed down. If this was not done, themodel would not have anything to learn and all theweights learned by it would be close to 1. For example,
consider a query like “list files” and the top two results
found by apropos(1): ls(1) and file(1). While
file(1) shows up at rank one and ls(1) at two, themodel should learn to rank ls(1) as number one for thisquery.

to note here that even though the random forest model
outperforms the ridge regression model, the function
learned by the random forest model might not be strictly
linear and thus those weights may not work well withthe linear ranking model used in apropos(1).

4Ranking can also be treated as classification problem
where the task is to classify the search results as either
relevant or not-relevant.
There are a variety of classification models which
are available, such as logistic regression, support vector
machines, neural networks and so on. However, out of
all these models, logisitc regression closely resembles
the form of the ranking function used by apropos(1),as described in the previous section.

Various regression models were trained and theirperformance was measured on this task. In order toobjectively measure the performance of these models,
the dataset was split into three parts - training set,
validation set, and test set. Models were trained on
the training set and the validation set was used to tune
their hyper parameters. Their final performance wasmeasured on the test set.

Logistic regression model is essentially an extensionof the linear regression model described in the previous
section. Since the output of a linear regression model
is continuous, while a classification model needs to predict one of the fixed set of classes as its output, an additional step is required. The output as produced by the
regression model is passed to a function called the sigmoid function, which scales down this value in the rangeof [0, 1].

It is a good practice to not to test the performanceof the model on the same data on which it was trained,
because instead of learning to generalize from data, themodel can simply memorize the training data and give
100% performance, but when tested on unseen data it
would perform very badly. For this purpose a validation
set is used. Based on the performance of the model on
the validation set the hyper parameters of the model are
tuned and it is retrained until the performance on thevalidation set becomes satisfactory. The test set is heldback for evaluating the final performance of the model.

1(8)
1 + e−z
Where z is the output produced by the linear regression model (as shown in (4)).
sigmoid(z) =In order to measure the performance of the regression
models, mean squared error [8] was used as the metric.
Mean squared error is one of the standard metrics formeasuring the performance of regression models and iscomputed as shown below:

The scaled down value essentially represents theprobability of the input belonging to one of output
classes. For a binary classification problem, usually avalue > 0.5 is used to classify the input as belonging toclass 1, or otherwise the input is classified as belonging
to class 2. For a multiclass classification task, something
more complicated is needed. Usually a technique called
one-vs-all is used for doing multiclass classification,
where one binary classifier is trained per class inthe training data, and each binary classifier learns toclassify the input as either belonging to that class or
belonging to one of the other classes. If the input data
has k + 1 classes, then k number of binary classifiers
are trained. When doing prediction, the input is passed
through each of the classifiers and the classifier predicting the maximum probability is chosen as the winner.

N

MS E =

1X 0(y − yi )2
N i=1 i

Ranking as Classification Problem(7)0Here again, yi is the value predicted by the modelfor the ith input example and yi is the actual value ofthat example. N is the total number of examples in thedataset.
A Ridge regression model gave a mean squared error
value of approximately 1.9 × 10−4 . Whereas a random
forest model obtained an error of about 1.6 × 10−4 . The
random forest model used here was trained using 300
estimators, with a maximum depth of 15. It is important

The same dataset as used in the regression model wasused for training classification models. The w_total
6

$ # output with old weights$ apropos -n 10 -C fork
fork (2) create a new process
perlfork (1)Perls fork () emulation
cpu_lwp_fork (9) finish a fork operation
pthread_atfork (3) register handlers to be called when process forks
rlogind (8)remote login server
rshd (8) remote shell server
rexecd (8)remote execution server
script (1)make typescript of terminal session
moncontrol (3)control execution profile
vfork (2) spawn new process in a virtual memory efficient way$ # output with new weights$ apropos -n 10 -C fork
fork (2) create a new process
perlfork (1) Perls fork () emulation
cpu_lwp_fork (9) finish a fork operation
pthread_atfork (3) register handlers to be called when process forks
vfork (2) spawn new process in a virtual memory efficient way
clone (2) spawn new process with options
daemon (3) run in the background
script (1) make typescript of terminal session
openpty (3) tty utility functions
rlogind (8) remote login server }Listing 3: Comparison of output with old and new weights$ # output with old weights$ apropos -n 10 create new process
init (8) process control initialization
fork (2) create a new process
fork1 (9) create a new process
timer_create (2) create a per - process timer
getpgrp (2)get process groupsupfilesrv (8)sup server processes
posix_spawn (3)spawn a process
master (8)Postfix master processpopen (3) process I/O_lwp_create (2)create a new light - weight process$ # output with new weights$ apropos -n 10 create new process
fork (2) create a new process
fork1 (9) create a new process_lwp_create (2) create a new light - weight process
pthread_create (3) create a new thread
clone (2) spawn new process with options
timer_create (2) create a per - process timer
UI_new (3) New User Interface
init (8) process control initialization
posix_spawn (3) spawn a process
master (8) Postfix master process }Listing 4: Comparison of output with old and new weights

7$ # output with old weights
apropos -n 10 -C remove packages #old weights
groff_mdoc (7)reference for groffs mdoc implementation
pkg_add (1)a utility for installing and upgrading software package distributions
pkg_create (1)a utility for creating software package distributions
pkg_delete (1)a utility for deleting previously installed software package distributions
deroff (1)remove nroff /troff , eqn , pic and tbl constructs
pkg_admin (1)perform various administrative tasks to the pkg system
groff_tmac (5)macro files in the roff typesetting systemci (1)
check in RCS revisions
update - binfmts (8)maintain registry of executable binary formats
rpc_svc_reg (3)library routines for registering servers$ # output with new weights
apropos -n 10 -C remove packages
pkg_create (1) a utility for creating software package distributions
pkg_add (1) a utility for installing and upgrading software package distributions
pkg_delete (1) a utility for deleting previously installed software package distributions
deroff (1) remove nroff /troff , eqn , pic and tbl constructs
groff_mdoc (7) reference for groffs mdoc implementation
groff_tmac (5) macro files in the roff typesetting systemci (1) check in RCS revisions
pkg_admin (1) perform various administrative tasks to the pkg system
update - binfmts (8) maintain registry of executable binary formats
rpc_svc_reg (3) library routines for registering servers

Listing 5: Comparison of output with old and new weights

five classes to two classes increases the accuracy,
since there are only two classes, even a blind guesshas a 50% chance of being correct. But in reality,
the small number of examples result in a very
confused model. An example which was labelled
as 2 in the training data, would be classified as 0,
which is not really correct for real search results.
On increasing the number of classes in the dataset,a sharp drop in the accuracy of the models wasobserved, which again suggests that the dataset
was too small and not enough number of examples
were observed for the model to properly learn todistinguish between different classes.

feature was ignored for the classification models, and instead the relevance feature was used as the target output for training the models.

4.1

Performance of Classification Models

Mean accuracy was used as a metric to measure theperformance of the logistic regression models. On thetask of classifying the relevance of the results on a scaleof 0 to 4 (with 0 being least relevant while 4 being most
relevant), the classification models obtained an accuracyof about 53.06%. On reducing the number of classes
to 3, the accuracy improved to about 62.04%. Finally,
on reducing the number of classes to 2, namely, relevant or not-relevant, the accuracy jumped up to 80.41%.

2. The second reason for the bad performance of theweights learned by logistic regression models on the
output of apropos(1) is that the fact that logistic
regression needs to learn k number of classifiers if
the input data contains k + 1 classes. And this meansthat the model ends up learning k sets of weights.
But the ranking model used by apropos(1) cannot use multiple sets of weights, therefore training
the model to predict more than two classes is futile
unless suitable changes are made in the ranking algorithm as well. Reducing the number of classes
to 2 ensures that the model only learns a single setof weights, but as noted previously, binary classification is a poor fit for the problem, unless more
examples are added in the dataset.

However, the weights learned from classification
models, do not show as great improvements in the output
of apropos(1), which suggests a disconnect between
the problem and model. There are two main reasons
behind the poor performance of classification models on
this task.
1. While the accuracy on the binary classification task
was good, it was too broad a category, with too
few examples. The inputs in the dataset having
relevance as 1 or 2 were clubbed with inputs having
relevance as 0, while inputs having relevance as 3
were relabelled as 4. Reducing the examples from8

5

Comparison
WeightsofResults

With

New

7

The datasets generated as part of this project and the associated models are available on the following github
repository:
https://github.com/abhinav-upadhyay/
man-nlp-experiments

Listings 3, 4 and 5 compare the differences in the
rankings of the results produced by apropos(1) withold weights and with the new weights learned from theregression model as described previously.

References

Listing 5 shows that for the query “fork”, the output
with old weights contains results like rshd(8) andrexecd(8), while in the output produced with thelearned weights, it can be seen that rshd(8) disappears
from the top 10 results and rlogind(8) moves to thebottom. At the same time, more relevant results like
vfork(2) and clone(2) move further up, which is asignificant improvement.

[1] Manual page for new apropos(1) in NetBSD 7.0
http://netbsd.gw.com/cgi-bin/man-cgi?apropos++NetBSD-7.0[2] Manual page for old apropos(1) in NetBSD 5.0
http://netbsd.gw.com/cgi-bin/man-cgi?apropos++NetBSD-5.0[3] Manual page for makemandb(8) in NetBSD 7.0
http://netbsd.gw.com/cgi-bin/man-cgi?makemandb+8+NetBSD-7.0

Similarly Listing 4 compares the outputs for thequery “create new process”. It can be seen that theoutput with old weights contains irrelevant results likesupfileserv(8) and init(8) at the top. Howeverwith the new weights the most relevant result to thequery, fork(2), moves to the top. More relevant results
such as pthread_create(3) and clone(2) also show
up in the top 10, while they were not present in output
with the old weights, this is again a great change.

6

Availability[4] Manual page for makewhatis(8) in NetBSD 5.0
http://netbsd.gw.com/cgi-bin/man-cgi?
makewhatis++NetBSD-5.0[5] Upadhyay A.; Sonnenberger J. Apropos Replacement: Development of a full text search tool for
man pages AsiaBSDCon, Tokyo p. 011-023, 2012.
[6] The github repository containing datasets andpython code for training models
https://github.com/abhinav-upadhyay/
man-nlp-experiments

Further Work

There is still much scope in this area left to be explored.
More data needs to be collected, which covers wider
range of queries and man pages, a dataset more representative of the corpus would certainly help get better
results.

[7] Jones; K. S. A statistical interpretation of term
specificity and its application in retrieval Journalof documentation, 28(1) p 011-021, 1972.
[8] Tom Mitchell Machine Learning McGraw Hill,
1997.

Only classification and regression models were tried
so far. There is a third variety of models, called ranking
models. These models are specifically developed inorder to learn a ranking function. It would be interesting
to see the results of training these models on this dataset.

[9] Manning, Raghavan, Schütze Introduction to Information Retrieval Cambridge University press,
2008.
[10] A web interface to NetBSD’s apropos(1)https://man-k.org

Another open avenue on this front is to try out different
ranking algorithms. With the availability of a dataset it ismuch easier to try out new ranking algorithms and evaluate their performance. Metrics like precision and recall[9] can be computed to compare the performance of different ranking algorithms and to decide whether a newalgorithm improves the search performance or not. Investigating different ranking algorithms in combination
with the machine learning models is also an open area.

[11] The mandoc project
http://mdocml.bsd.lv/[12] The FTS module documentation for Sqlite
https://www.sqlite.org/fts3.html

9