A central problem in knowledge-based tasks is to provide a collection of reusable knowledge samples extracted from a textual corpus. Often, such corpora are structured into diferent documents or topics, respectively. The samples need to be proven for usability and adapted by a domain expert requiring a certain processing time for each sample taken. The goal is to achieve an optimal retrieval and adaptation success meeting the time budget of the domain expert. In this work, we formulate this task as a constrained multi-armed bandit model. We combine it with the model of a configurable data-driven case-based learning agent. A case study evaluates the theoretical considerations in a scenario of regulatory knowledge acquisition. Therefore, a data set is constructed out of a corpus of nuclear safety documents. We use the model to optimize the evaluation process of sample generation of adaptational knowledge. The corresponding knowledge graph has been created in an information extraction step by automatically identifying semantic concepts and their relations.
Let us consider the following situation: a domain expert needs to write a new safety document. He has a corpus available with a collection of documents similar to a safety domain. So he may reuse knowledge contained in the corpus and collect new safety knowledge by searching the existent corpus. He adapts promising textual passages to his needs and drops others. In complex domains an unknown document is like a black box which has to be understood, even for domain experts. Therefore, he has to analyze and interpret passages of the documents in the corpus, assess their quality, and adapt them to his specific domain. In the end, if the expert finds the knowledge he is looking for, he is satisfied with the selection of documents he made. This simple process is complicated by various factors.
The expert has special characteristics. He has some prior knowledge and he has limited time. Subsequently, he expects to find the knowledge in the corpus
Call ambulance Safety Guide
Police
Med
Fire
Gov he is searching for, within the time budget he has available. Additionally to the time budget the expert is characterized by a certain preference. He is interested in certain topics. Despite that, the expert hopes to find new helpful knowledge he does not yet know. A fact, that leverages his task, is that the corpus is structured by domain experts into documents representing a self-contained knowledge scheme as illustrated in Figure 1. In summary, every document of the corpus has a certain quality which is initially unknown to the reader and comes up step by step with every textual sample processed. The following exemplary textual sample is taken from a document for nuclear safety which is part of the evaluating case study presented in Section 4.
(1)
Example: The staf assigned the responsibility for carrying out such reviews for issues of fire safety should be suitably qualified to evaluate the potential efect of any modification on fire safety and should have suficient authority to prevent or suspend modification work, if necessary, until any issues identified have been satisfactorily resolved.
The task of retrieving good new adaptation candidates inherits two
competing goals. On the one hand, the expert needs to distribute his search in the
corpus to find the documents that fit his expectations ( explore corpus ). On the
other hand, when he found a good document, he does not want to waste time
(exploit good document ) searching for other documents, that may fit his
expectations better. A well accepted strategy to model the before described scenario
of sequential resource (time) distribution amongst competing alternatives
(documents) is the bandit model [
Safety Guide
Police
Med
Fire
Gov The described scenario is connected with the solving or mitigating of the following problems. The exploration-exploitation dilemma of using already visited ”good” documents for sample generation rather than sampling completely unknown or allegedly ”bad” documents. How can a sequential reward model be constructed that bases solely on the existent data. Can the model be used to calculate the quality of a retrieved sample depending on the characteristics of the agent and thus defining ”good” and ”bad” quality of documents. 1.2
We facilitate and formulate the scenario as a constrained multi-armed bandit model which ofers strategies to mitigate the exploration-exploitation dilemma in a configurable way. We use case-based reasoning (CBR) strategies incorporating an initial agent setup (initial case base) together with a learning goal (optimum case solutions ) to construct a configurable reward model on the base of similarity assessment. We use statistical language models to calculate similarity components of the retrieved information for sample adaptation. 1.3
With the presented approach we aim to answer the following research question. Is it possible to formulate the sampling process of a textual corpus as a multiarmed bandit problem in combination with a data-driven agent characterization. Can the phrases (samples), documents (bandit arms), and corpus (agent environment ) thereby be considered as discrete semantic unities even though they are interrelated. Do the documents have a mean quality and variance of quality regarding the sampling process of contained phrases as depicted in Figure 2.
There exist several works describing document retrieval or ranking using the
strategy of multi-armed bandits. Perotto et al. [
Related work that supports the construction of a convenient agent model
treated the following topics. A resource oriented variation of the multi-armed
bandit problem is presented by Bengs and Hu¨llermeier [
Concerning variants of multi-armed bandit modeling an outstanding
approach is the hierarchical structuring of the action space of the agent. As
documents are most often structured into a hierarchy of topics this can yield
significant improvements in the overall performance. Especially, as the here presented
case study relies on hierarchical structuring of semantic concepts synergies should
not be neglected. Hong et al. [
We will address, integrate, and extend diferent aspects of these related approaches into a new combination of agent-bandit model which is explained in the following.
In the following we will formalize the introduced problem description. We start with assumptions that are made to facilitate the scenario. We present and explain the ideas behind formal definitions of the learning agent and the reward model. We outline solution strategies using the presented setting. 3.1
The textual corpus is analyzed in a natural language processing step. The documents are chunked into uniform informational pieces of a certain meaningful size. Such units can be retrieved as samples, for instance, a paragraph or sentence. The textual corpus is enriched by semantic meta knowledge identifying and annotating safety related semantic concepts and their relations. We assume a closed world, namely, the textual corpus together with its semantic representation. This means that the learning agent is provided with some prior knowledge that is part of the textual corpus and its semantic representation. We assume a given learning goal which is also part of the textual corpus but is hidden to the agent. The preferences of the agent are provided by a set of semantic concepts defined on base of the semantically annotated textual corpus saved in a knowledge graph O. It is unknown what would be an ideal learning goal. Therefore, we assume a subset of the corpus as learning goal. The agent is informed about the fulfillment of the goal by similarity information given to him by a hypothetic teacher. There are some flaws in this modeling: The prior knowledge increases with every sample processed by the agent and the learning goal decreases if partially met. This would lead to a non stationary reward model which changes over time. For simplification we assume a stationary model with the same reward configuration over the whole sampling process. 3.2
We consider a corpus C = {D1, ..., Dm} divided into m documents each consisting of In, n ∈ {1, .., m} information units with ii ∩ij = ∅ ∀ ̸ i = j. Let IC = {I1, .., Im} be the set of all information units contained in the corpus. This corpus is represented as a K-armed bandit K = {1, ..., K}, K = |C| with a set of K arms where each arm stands for one document. The agent is willing to read a number of b retrieved passages of text. By the action ai of pulling the arm k at time t a sample piece of the document k is provided which is denoted as At. The quality of the sample piece generated by this action is the reward Rk ∈ {0, 1} (with Rk = 0 meaning sample rejected and Rk = 1 meaning sample accepted). With ongoing time steps a sequence of actions (A1, A2, .., Ab) with according rewards (R1, R2, .., Rb) is produced. The (discrete) time goes on until the budget of the expert is consumed and he is not willing to take more sampling actions. What we are searching for is the optimal combination of actions to make the best out of the experts budget. The ”expert” is formalized as an agent with the following characteristics.
Definition 1 (Learning Agent Scenario). Let E = ⟨P, G, L, b⟩ be an agent that is modeling an expert with a prior knowledge P ⊂ I C, with the preferences L ⊂ O regarding topics he is interested in. We define a learning goal aligned to the agent as a subset G ⊂ I C. The agent has a budget of b samples that he is willing to take, meaning the bandit game goes T rounds (T = b). The environment of the agent is the textual corpus. The agent has the actions of pulling a bandit arm, accepting a sample, and rejecting a sample.
Altogether, the information units that define the agent are considered as the initial case base. Each sample is considered as a new case, potentially representing a (partial) solution for the agent’s task. If samples are indeed adaptable, is decided by comparing the new solutions to the existing case base. Finally, the agent is capable of solving his problem of creating the new document. (2)
Example: An exemplary corpus consists of four diferent safety documents. With the topics ”fire safety”, ”police guidelines”, ”medical guidelines”, and ”governmental security” as depicted in the Figures 1 and 2. Each document consists of 1,000 relevant phrases and the expert has a budget of 100 samples, which he is capable of reading and analyzing. His preferences are ”transportation” and ”mobile fire safety” and he wants to create a document for the safety of utility vehicles in factories. He is a governmental fire safety expert and his prior knowledge is a subset of 50 phrases each of the fire safety and the governmental document. How does he distribute his 100 samples over the 4,000 existing phrases providing the best sampling success to him.
Prior knowledge 1
Corpus
Expert Accept / Reject
2 Preference features
Teacher 3 Learning Goal 4
Retrieved Sentence Use a fire extinguisher
Similarity Assesment
5
Fig. 3: Case-based cycle of corpus sample retrieval with joined agent-teacher
similarity assessment. The expert has some prior knowledge (1) and preference
features (2). The teacher defines a learning goal (3) which is hidden to the expert
but gives him feedback about the quality of retrieved samples (4). Via a similarity
assessment (5) the expert accepts or rejects the sample, then adapts it to his
needs and retains it in the new corpus as a new case.
For every sampling action the agent is rewarded. To create a model for this
reward we exploit the case-based paradigm that similar problems have similar
solutions [
Definition 2 (Reward Function). Let sim(At,G) be the similarity of the retrieved sample as action At with the learning goal, sim(At,L) the similarity between the retrieved sample and the preferences of the agent, and sim(At,P) the similarity between the sample and the prior knowledge. Then the reward function R(At) ∈ {0, 1} with α, β, γ ≥ 0 is defined as: (1) (2) (3) (4) simR(At) = αsim X (At, G) + βsim X (At, L) + γ (1 − simX (At, P))
α + β + γ R(At) = (1 for simR(At) ≥ δ
0 for simR(At)<δ simX (At, X) = max(SimSLMF (At, I)∀I ∈ X) simSLMF (At, I) = simSLM (
Pm km=1 fj ∀f ∈ At,
Pn l=1 gl ∀g ∈ I) n
We define a stacked reward function basing on the similarity assessment
weighting and averaging the similarities to preferences, learning goal, and the
dissimilarity to the prior knowledge. The reward model is constructed in a
heuristic way. The local similarities simX (At, G) and simX (At, L) add to each other
because both a similarity to the learning goal and the preferences of the agent
are desirable. If there is a similarity to the prior knowledge of the agent this is
considered as not desirable because the agent prefers to learn new knowledge. If
simX (At, P) is zero then R is not influenced, a high similarity of At and P leads
to a reward of 0 adjustable by the weights γ and δ . The similarities between
At and G, L, P are calculated using a statistical language model with feature
focus (SLMF) [
Epsilon-Greedy Strategy A baseline strategy to address the
explorationexploitation dilemma is the epsilon-greedy strategy (EG) [
The spark for this work developed out of the task of evaluating the quality of an automatically populated ontology. The available time budget allowed for a maximum analyzation capacity of some hundred annotated textual samples. Compared to a dataset size of more than 200,000 samples a better strategy than random sampling was necessary. Additionally, a configurable sampling setup was desired depending on the task and user profile.
For the present experimental evaluation we use a dataset created from a
textual corpus published in the domain of nuclear safety. This corpus was
previously annotated and transformed into an according dataset of about 222,000
sentences. The corpus consists of publicly available 143 documents containing in
total about 14,000 pages of English text. These documents were published by the
IAEA (International Atomic Energy Association), which is a sub organization of
the United Nations [
Number Document Title
(1091) “Fire Safety in the Operation of Nuclear Power Plants”
(1159) “External Events Excluding Earthquakes in Nuclear Power Plants”
(1191) “Protection against Internal Hazards other than Fires”
(1798) “Regulations for the Safe Transport of Radioactive Material ...”
(1368) “Predisposal Management of Radioactive Waste”
(1546) “Nuclear Security Systems and Measures for Major Public Events”
Additionally to the plain documents, a terminology is published and maintained
by the IAEA covering about 1,500 semantic concepts of the domain using the
RDF data model [
Example 3 shows a phrase extracted from the Document 1191 listed in Table 1. Because of the concepts ”vessel” and ”fuel” this phrase is similar to the ”utility vehicle” scenario described in Example 2. This example points out the time-consuming and pseudo-stochastic nature of the adaptational process. The success of having retrieved a good passage is not guaranteed. For instance, ”vessel” is here used in the sense of a ”container” and not a vehicle-like object. Nevertheless, concepts seem similar and the phrase might be promising. To proof and adapt this phrase the expert needs to research, what should be done in this context for the incident of a ”missile”, what is meant by ”special design features”, then proof whether this would be a good strategy for his own scenario, maybe consult other experts, and finally rewrite the phrase.
(3)
Example: For reactors equipped with vessel closure plugs to retain the fuel in position, special design features should be provided to ensure that the probability of ejection of the closure plug is low. In the absence of such special features, the consequences of the failure or the ejection of a single closure plug should be evaluated as for a missile.
Beyond that, the semantic knowledge can be used for the purpose of
document filtering. It is not necessary to use all information units in a document. In
a filter step only those units relevant for a certain task can be pre-selected. For
instance, only sentences that contain a certain type of relation, that fall under
a certain topic, and show other distinct characteristics. A second benefit is the
availability of meta-knowledge about features to calculate similarity functions
and adapt retrieved information units to diferent scenarios [
In the following we present a collection of experiments that describe determination of hyper-parameters, individual characteristics of each solution policy, and comparable aspects of the bandit problem solution strategies. We compare the experiments against a baseline of random sampling and use the concept of regret for performance evaluation. The dataset was divided into an experimental data environment with training, validation, and test splits, leaving 10% of all sentences for each; validation and testing. We initially tested the algorithms with a small selection of 3 documents, that where known in terms of document content to investigate the behavior with human insight. We then scaled the algorithms to a number of 10 and 100 documents. We used two diferent agent configurations A1 and A2 as described in Figure 4.
the UCB algorithms we initialize all arms with a mean reward of 1. This ensures that each arm is visited at least once. For the same reason for the TS policy Fig. 4: The figure shows the mean of the reward for each document together with the standard deviation for a fixed reward configuration for ten documents of the corpus amongst which the documents mentioned in Table 1. With α = 1, β =0, γ =0, δ =0.8 for Configuration A1 where just the learning goal was defined as a ifxed single sentence with G = 1, P = 0 sentences and L = []. For Configuration A2 and α = 1, β =1, γ =1, δ =0.5, a fixed set of G = 17 random sentences sampled from three documents, P = 1 fixed sentence , and L the preferred semantic concepts :fire, :transportation, and :leakage. the distribution of each arm is initialized with a count of positives = 1 and negatives = 1. These starting values determine a wide spread initial distribution. To determine a reasonable range of time steps a human expert would accept, we considered the following. We estimated about five minutes of time to manually execute the adaptational steps needed in case of Example 3. The documents Fig. 5: The left shows the frequency histogram of continuous similarity values for one document. The right displays the beta distribution for three diferent documents constrained to binary values with δ and configuration A2. in the corpus consist of about 500 to 1,500 phrases. According to this, 1,000 time steps would meet the mean of the document length in the present corpus. Furthermore, this would lead to a net time budget of about 10 working days of eight hours. Which seems a reasonable efort for the research to create a sophisticated document.
The fully informed scenario calculated as explained in Section 3.4 is shown in Figure 4. It visualizes which strategy would be statistically optimal. The agent would then only use a selection of the best ranked documents with the highest mean. Figure 5 shows how the threshold turns the documents at random retrieval into a stochastic unit with a beta distribution of positive and negative action rewards. This distribution we interpret as the characteristic of the according bandit arms.
Epsilon Greedy Before applying complicated strategies we wanted to investigate how a simple mixture of greedy and random ratio would behave. We therefore let the epsilon greedy algorithm run with epsilon values from 0 to 1 in steps of 0.1. With ε = 0 having a complete greedy approach and ε = 1 having a fully random algorithm. We then compared the average reward of 10 epochs of 1000 simulations for the agent configurations A1 and A2. The graphical representation for a selection of epsilon values is shown in Figure 6.
Upper Confidence Bound The UCB approach was optimized but even so
showed the worse performance of all algorithms. We see the reason for this
in the high variance of the document similarity distribution. Additionally, the
configuration of the hyper-parameters to determine the confidence interval and
bias model requires eforts if applied to new corpora [
Comparative Evaluation It turned out that the way of using a textual similarity to create a data-driven bandit model leads to a scenario of high variance. Combined with a constrained number of time steps this has significant influence on the solution policies. The EG approach has the advantage of being easily understandable and configurable. Additionally, the volatile scenario mitigates the shortcoming of revisiting ”bad” arms. The high variance might also be the reason for the in total worst performance of the UCB approach as shown in Table 2. The Thompson algorithm showed good results and achieved in most experiments a higher reward in less time steps compared to the other algorithms. All algorithms are capable of approximately recreating the fully informed ranking of documents induced by each mean calculated in Figure 4. To pay respect to the aspects of configurability we suggest a combined approach of EG and TS. For instance, to randomly explore all arms for some steps and then start to use the Thompson Sampling approach. Fig. 7: Performance for 10 and 100 documents for agent configuration A2.
This work addressed the problem of distributing a limited budget of textual sampling over a corpus of documents. The lack of real life experts is mitigated by a data-driven agent model with special characteristics to estimate the quality of the samples for adaptational purposes. Therefore, we presented an approach to consider the documents of a corpus as bandit arms in a (constrained) multi-armed bandit setting. A case-based agent model was presented that can be configured together with a reward model to adjust the approach to diferent application scenarios. Hyper-parameters have been partially optimized in a learning phase. An evaluation was presented on a corpus of nuclear safety documents.
The evaluation showed that documents can be indeed considered as a kind of stochastically distributed entities with a mean reward under variation regarding a similarity-based reward model. The experiments showed that the characteristics of sample retrieval out of documents varies from a ”real” stochastic bandit environment in severals aspects which leaves space for the following future work.
Several variations of the setting seem promising and other application domains are worth to investigate. This would give insight to the needs of other user groups with diferent requirements and possibly improve the performance of the present setting. The following aspects became obvious in the stage of development but eventually exceeded this work.
The underlying data has an inherent structure which can be exploited to create a more distinct bandit architecture. Even though the documents are discrete semantic objects, most likely, there will be a strong correlation amongst them if they belong to the same corpus. On the base of the correlation the reward could be adjusted for every bandit arm. The agent-teacher relationship could have an adversarial character. The teacher wants to challenge the agent. This could be implemented by reducing the reward of certain bandit arms.
An improvement of the agent model would be to switch from a stationary
reward to a non-stationary setting that adapts the agent step by step to the
character of the data. This could be used to learn agent models from the data.
A further benefit would be to set up a contextual bandit model basing on this
scenario to find correlations between the agent model and the data [
The calculation of textual similarities can be quite resource consuming. This might be an issue for complex similarity configurations of the agents, larger corpora, and applications with time pressure. In that case the complexity of algorithms will surely contain potential for improvement.
Finally, a case study with real life experts would help to refine the model. On the one hand it would be good to observe how real experts would choose an agent configuration according to their preferences and task characterization. A survey to determine hyper-parameters should yield insight into human behavior. For instance, taken the parameter δ which determines the threshold when to drop and when to keep a sample. At which similarity threshold does a real life expert tend to drop a sample?