Our junior research group in the EP-KI team develops solutions at the interface of business administration and artificial intelligence (AI). In the new blog post, our application example revolves around smart algorithms that support the automated assignment of emails, for example.
© iStockphoto
In any application that uses artificial intelligence (AI), the first step is the data. The second step is to apply an algorithm and thus develop an AI application. We want to take a closer look at this process in today's blog entry.
Author: Dr. Stefanie Schwaar
Let's look at a current example from the administration: Every administration gets a special electronic government mailbox (beBPO), i.e., a mailbox where e-mails are received for this administration. Hypothetically, we consider the case of a city where communication is completely digitized and takes place via a mailbox, i.e., via a specific e-mail address. The incoming e-mails should now be assigned to the appropriate offices directly when they arrive, such as registering a marriage at the registry office or reporting a suspected case of Corona at the health department. This assignment must be learned, which means: our data are the e-mails and the classes are our offices. How can an algorithm learn this association?
We start with our data and assume that the information we are interested in comes from that data – a basic assumption not to be forgotten. Specifically, this means that all the data needed to make a good enough prediction or detection or processing is available. However, the context is unknown or too complex to describe with a simple model. Graphically, we imagine it like this:
The function f describes the context. Depending on the problem, the information X to be used and the knowledge Y to be determined must be selected. Let's take the example with objects from the last blog entry.
The balls in the example are described by the following properties:
The classifier (definition in the last blog post), which assigns the balls to the colors, must therefore recognize the relevance of the information - in this case surface structure and weight - and learn a relationship A = f(B, C).
Observation Number |
Weight | Surface Structure | Color |
1 |
heavy |
rough |
green |
2 |
heavy |
smooth |
green |
3 |
medium |
rough |
green |
4 |
medium |
rough |
green |
5 |
medium |
smooth |
red |
6 |
medium | smooth |
red |
7 |
medium |
smooth |
red |
8 |
light |
rough |
red |
9 |
light |
smooth | red |
10 |
light | rough | red |
Classical approaches assume that we can describe the correlation by formulating a rule set. In our example, we have already done that. The rules are:
If the data is very extensive (e.g., in medicine or in company accounting systems), a description with rules becomes very extensive. Every exception must be included.
Artificial intelligence methods start here and learn the rules from the data by means of repetition. This is where the use of a decision tree comes in handy. Here it is to be noted: In order to learn by repetition, an evaluation method must exist by which it can be measured how good the function f is and where improvements are necessary.
This is the so-called »objective function« (sometimes also called »criterion«).
In the example of the decision tree, a further division is then made as long as there is an information gain. To determine the information content, the misclassification error is used. If the misclassification rate is reduced by splitting, the information content increases.
How do we determine the information content or the misclassification rate?
A decision tree always assigns data from each group to the class that is most represented in it. The rules in the example above would determine a decision tree as follows. First, it is determined on the total data D fall on red, since 6 out of 10 (6/10 = 3/5) examples have the color red. Thus, the accuracy or goodness of the prediction is 6/10, so the misclassification rate E(D) is 4/10. We would now like to minimize this successively by subdividing the dataset.
Let us consider the first step and thus the first separation of the data: For a chosen characteristic (x_j), a subset is determined for each expression (v) (D_v). To determine the total error for this partition, the flag classification rate is calculated for each subset and weighted by the share of the subclass in the total data set, i.e.
where |D_v| or |D| denotes the number of elements of the subclass or the entire data set.
Separation by weight:
In the group of light and heavy balls, only one color is represented in each case, so for these we get an error of 0; for medium-heavy we have 3 red and 2 green, so the tree would make an error in 2/5 of the cases.
Mathematically, this results in a total error of
Separation by surface:
Five elements that are rough are predicted to be green with an error of 2/5, Five smooth elements are predicted to be red with an error of 1/5.
Accordingly, the entire error lies with
Thus, the error becomes smaller in the first setting, i.e., when separating by weight. Equivalently, the information gain increases in this subdivision. The formula for the information gain is therefore:
Further subdivisions are performed until no more information gain can be achieved.
Of course, depending on the application, the data structure is somewhat more complicated and thus not so easy to classify. For our e-mails, the first step is therefore to prepare the textual information in such a way that a classifier, such as the decision tree, can work with this data. Whoever is interested in this in detail can already look forward to a next blog entry on the preprocessing of texts.
Fraunhofer Institute for Industrial Mathematics ITWM