{'fraction_non_alphanumeric': 0.023373008254943366, 'fraction_numerical': 0.0037435208293338453, 'mean_word_length': 4.643824485373782, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Nonspecific Evidence

When simultaneously reasoning with evidences about several different events it is necessary to separate the evidence according to event. These events should then be handled independently. However, when propositions of evidences are weakly specified in the sense that it may not be certain to which event they are referring, this may not be directly possible. In this paper a criterion for partitioning evidences into subsets representing events is established. This criterion, derived from the conflict within each subset, involves minimising a criterion function for the overall conflict of the partition. An algorithm based on characteristics of the criterion function and an iterative optimisation among partitionings of evidences is proposed.


I. INTRODUCTION
A problem of major importance when reasoning with uncertainty is that in many situations evidences will not only be uncertain but their propositions may also be weakly specified in the sense that it may not be certain to which event a proposition is referring. In some cases the propositions may not carry any such information, making it impossible to differentiate between different events. Furthermore, the domain knowledge regarding events may be uncertain. For instance, our knowledge of the current number of events may only be probabilistic.
When reasoning about some proposition it is crucial not to combine evidences about different events in the mistaken belief that they are referring to the same event. For this reason every proposition's action part must be supplemented with an event part describing to which event the proposition is referring. The event part may be more or less weakly specified dependent on the evidence. If the evidences could be clustered into subsets representing events that should be handled separately from the others the situation would become manageable.
A simple example will illustrate the terminology. Let us consider the burglaries of two bakers' shops at One and Two Baker Street, event 1 (E 1 ) and event 2 (E 2 ), i.e., the number of events is known to be two. One witness hands over an evidence, specific with respect to event, with the proposition: "The burglar at One Baker Street," event part: E 1 , "was probably brown haired (B)," action part: B. A second anonymous witness hands over a nonspecific evidence with the proposition: "The burglar at Baker Street," event part: E 1 , E 2 , "might have been red haired (R)," action part: R. That is, for example: The aim of this paper is to establish, within the framework of Dempster− Shafer theory, 1−3 a criterion function 4 of overall conflict when reasoning with multiple events. With this criterion we may handle evidences whose proposition is weakly specified in its event part. We will use the minimizing of overall conflict as the method of partitioning the set of evidences into subsets representing the events. This method will also handle the situation when the number of events are uncertain.
An algorithm for minimizing the overall conflict will be proposed. The proposed algorithm is based on the one hand on characteristics of the criterion function for varying number of subsets and on the other hand on an iterative optimization among partitionings of evidence for a fixed number of subsets.
This algorithm was developed as a part of a multiple-target tracking algorithm for an antisubmarine intelligence analysis system. 5, 6 In this application a sparse flow of intelligence reports arrives at the analysis system. These reports carry a proposition about the occurrence of a submarine at a specified time and place, a probability of the truthfulness of the report and may contain additional information such as velocity, direction and type of submarine.
The intelligence reports are never labeled as to which submarine they are referring to but it is of course possible to differentiate between two different submarines of two intelligence reports if the reports are known to be referring to different types of submarines. Moreover, times and positions of two different reports may be such that it is impossible to travel between the two positions at their respective times and therefore possible to differentiate between the two submarines. However, when this is not the case differentiation will not be possible. Instead we will use the conflict between the two intelligence reports as a probability that the two reports are referring to different submarines.
Before analysing the possible tracks for an unknown number of submarines we want to separate the intelligence reports into subsets according to which submarine they are referring to and then analyse the possible tracks for each submarine separately. The most probable partition of reports into subsets is done by minimizing the criterion function of overall conflict.
In this application the action part of the intelligence report proposition states that a submarine was at the indicated time and position while the event part of a report is informal, often weakly specified and contained in the information that to some degree separates reports, such as time and position of the other reports, nonfiring sensors placed between reports, etc.
In Sec. II we will discuss how to use the overall conflict for separating nonspecific evidences. Following this, the criterion function for overall conflict of multiple events will be investigated (Sec. III). We then discuss the behaviour of the criterion function in iterative optimization (Sec. IV). Finally, we propose an algorithm for partitioning evidences into subsets (Sec. V), based on the criterion function and a hill-climbing−like iterative optimization. We conclude with a detailed example (Sec. VI).

II. SEPARATING NONSPECIFIC EVIDENCE
When we have evidences with conflicting event parts we would like to separate them into disjoint subsets. After this, the reasoning should take place with the evidences in each subset treated separately. However, when the event part of a proposition is weakly specified with respect to which of many different events it is referring, it may be difficult if not impossible to directly judge whether or not it and a second proposition are referring to the same event. If, for instance, the first proposition is referring to events one or two and the second proposition is referring to events two or three it is uncertain whether or not they are referring to the same event. Thus, it will not be possible to separate evidences based only on their proposition's event parts.
Instead we will separate evidences by their conflict. This is an obvious choice since the conflict measures the lack of compatibility among evidences and the action parts of propositions are more likely compatible when they are referring to the same event as compared to the situation when they are referring to different events where the actions are also most likely different. Evidences are considered conflicting when they have empty intersections between representations of the proposition action parts with identical specific proposition event parts, i.e. propositions certainly referring to one and the same event. However, since all calculations take place within subsets where the evidences are presumed to be referring to the same event, we will have a conflict in two different situations. Firstly, we have a conflict if the proposition action parts are conflicting regardless of the proposition event parts since they are presumed to be referring to the same event. Secondly, if the proposition event parts are conflicting then, regardless of the proposition action parts, we have a conflict with the presumption that they are referring to the same event. In order to avoid that evidences with specific and identical event parts end up in different subsets we may precombine these evidences and henceforth handle them as one evidence. The idea of using the conflict as distance measure between bodies of evidence has been suggested earlier by Lowrance and Garvey 7 and by Lesh. 8 The conflict within each subset will not only be seen as a measure of the lack of compatibility among evidences within the subset but also as an evidence against the current partitioning of the set of evidences, χ, into the subsets, χ i . This is an intuitively correct definition since a critique against a part of the partitioning, the lack of compatibility among evidences, is a critique against the entire partitioning, i.e. an evidence against the partitioning. A zero conflict is no evidence against the partitioning and a conflict of one is an evidence that the partitioning is impossible. The frame of discernment is here Θ = { Partition, ¬Partition}. That is, the basic probability assignment against the partitioning from subset χ i is where {e j  e j ∈ χ i } is the set of evidences belonging to subset χ i and Conf( . ) is the conflict, k, in Dempster's rule.
When the evidences are not simple support functions the conflict measure might, at first glance, seem odd as a distance measure between bodies of evidence, since two nonsimple support functions with identical sets of focal elements may have a nonzero conflict. However, this need not be nonintuitive, as shown by the case of four simple support functions, the two first identical and in conflict with the two identical remaining simple support functions. If the two first and the two last functions are combined then a conflict measure with the intuitive properties of a distance measure is obtained, when the two resulting simple support functions are combined. If, on the other hand, we combine the first with the third and the second with the fourth, we receive two identical nonsimple support functions whose combination will result in a nonzero conflict. Clearly, if the conflict measure was intuitive as distance measure in the first combination order then it is also intuitive in the second. Then, at least for support functions that are derivable from simple support functions, it is not nonintuitive to have a nonzero distance measure for support functions with identical sets of focal elements.
In addition there will also be a domain dependent conflict from a probability distribution about the number of subsets, E, conflicting with the actual current number of subsets, #χ i . This conflict will also be seen as an evidence against the current partitioning of the set of evidences into the subsets, Fusing these evidences with Dempster's rule yields with belief and plausibility of the partitioning being Finding the most probable partitioning of evidences into disjoint subsets representing different events will then be the problem of maximizing the plausibility of possible partitionings, or the dual problem of minimizing one minus the plausibility. The difference, one minus the plausibility of a partitioning will be called the metaconflict of the partitioning.

III. METACONFLICT AS A CRITERION FUNCTION
Let us define the metaconflict function, derived in the previous section, whose minimization per definition leads to the optimal partioning of evidences into disjoint subsets.
DEFINITION. Let the metaconflict function, Some characteristics of the metaconflict function will be useful when choosing the number of subsets of χ for which we must find an optimal partitioning of evidences.
The first theorem below states that if we have an optimal partitioning for r subsets, then we need never consider any solutions with fewer than r subsets when the basic probability number for r subsets is greater than the basic probability number for fewer subsets. These solutions need never be considered because the nondomain part of the metaconflict function always increases with fewer subsets and when the basic probability number for fewer subsets is smaller than the basic probability number for r subsets, then the domain part of the metaconflict function for fewer subsets has also increased, yielding an overall increase in the metaconflict. The significance of this theorem is that it can be applied iteratively. If we first find the optimal partitioning for the number of subsets where m(E r ) is greatest, we need never consider any solutions with fewer subsets than r, and if we then find the optimal partitioning for the greatest m(E j ) where j > r, then we need never consider any further solutions where the number of subsets are fewer than j, etc.
The second theorem states that if we have an optimal partitioning for some number of subsets we need never consider any solutions for some other number of subsets where the domain part of the metaconflict function is greater than the metaconflict of our present partitioning. This theorem will also be used iteratively as we gradually find better optimizations, step by step eliminating some of the possible solutions where the number of subsets is greater than with our present partitioning.
Together, these two theorems will significantly reduce the number of iterative optimizations we must carry through for different numbers of subsets. It is sufficient to show that the partition into j subsets that yields the maximum is less than or equal to any partition into j + 1 subsets. Let the partition into the j first of the j + 1 disjoint subsets be unchanged from the optimal partition into j subsets with the exception that one evidence is moved from one of the subsets with more than one evidence, say χ k , to subset χ j+1 . There is, with only one evidence, no conflict in χ j+1 , c j+1 = 0. Then since the conflict in χ k after moving out an evidence , c k , is always less than or equal to the conflict before moving, . Proof. From the condition of the theorem and by (1) we have There are also two theorems regarding the stability of an optimal solution, i.e. that the partion of the optimal solution can not self-splinter into new subsets, Theorem 3, and that the partition is invariant with respect to evidence incompatible with the partition, Theorem 4.
Since the nondomain part of the metaconflict function decreases with the number of subsets it is only the domain conflict part of the metaconflict that prevents the number of subsets to be equal to the number of evidences. Thus, whether or not a partitioning of evidences is stable depends on the relation between these conflicts. THEOREM 3. A partitioning is stable, i.e. the metaconflict increases if any evidence is removed from its subset to form a new subset, if the relative change in domain conflict is higher than all relative conflict changes of the subsets.
Proof. If an evidence eq is removed from ci and included into a new subset χ r+1 the metaconflict would change to 1 minMcf j e 1 e 2 … e n , , , , Finally, a new evidence which is uncompatible with all subsets and introduced into its own subset will not change the partition. THEOREM 4. If P is a unique optimal partition of the set of evidences, χ , and e n+1 a new evidence which is highly conflicting with each subset χ i is introduced into its own subset χ r+1 . Then the optimal partition of is P / { e n+1 }.
Proof. The optimal partition of the new set of evidences is found by minimizing Mcf*(r + 1, e 1 , e 2 , . . ., e n+1 ). However, since e n+1 is introduced into its own subset χ r+1 , a subset without conflict, this can be rewritten as a function of the minimization of the old metaconflict, Mcf(r, e 1 , e 2 , ..., e n ); That is, finding the optimal partition of when e n+1 is introduced into its own subset is done by finding an optimal partition of χ . Since there is only one such partition, P, the optimal partition of is P / {e n+1 }.

IV. CONDITION FOR ITERATIVE OPTIMIZATION
For a fixed number of subsets a minimum of the metaconflict function can be found by an iterative optimization among partitionings of evidences into different subsets. This approach is proposed in order to avoid the combinatorial problem in } are the focal elements before the transfer. That is, we find the basic probability assignment of the focal elements as if the evidence was not included in χ i and calculate the additional conflict created by transferring the evidence to χ i . This additional conflict is then deducted from the conflict, c i , to calculate the conflict after having transferred the evidence from χ i , c i * . Given this, the metaconflict is changed to Finally, we conclude that the transfer of e q from χ i to χ j is favourable if  Let us call these quotients ρ q j and ρ q i respectively, i.e., it is favourable to transfer e q from χ i to χ j if ρ q j < ρ q i . It is, of course, most favourable to transfer e q to χ k , , if . It should be remembered that this analysis concerns the situation where only one evidence is transferred from one subset to another. It may not be favourable at all to simultaneously transfer two or more evidences which are deemed favourable for individual transfer. It can easily be shown that when several different evidences are favourable to transfer it will be most favourable to transfer the evidence e q that maximizes (1 − ρ q k )/(1 − ρ q i ).

V. AN ALGORITHM FOR MINIMIZING METACONFLICT
The algorithm for finding the partitioning of evidences among subsets that minimizes the metaconflict is based on Theorems 1 and 2 of the metaconflict function for finding the optimal number of subsets and an iterative optimization among partitionings of evidences for a fixed number of subsets. The iterative part of the algorithm, step 4 in the algorithm below, guarantees, like all hill-climbing algorithms, local but not global optimum.
Algorithm. Let S be the set of natural numbers less or equal to the number of evidences and T the empty set.

Calculate
, the conflict against a partitioning of the evidences into r subsets.

VI. AN EXAMPLE
Let us, as an illustration of the problem solved in this paper, consider a simple example of two possible burglaries, with a couple of evidences with simple support functions and some of the evidence weakly specified in the sense that it is uncertain to which possible burglary their propositions are referring. Assume that a baker´s shop at One Baker Street has been burglarized, event 1. Let there also be some indication that a baker´s shop across the street, at Two Baker Street, might have been burglarized, although no burglary has been reported, event 2. An experienced investigator estimates that a burglary has taken place at Two Baker Street with a probability of 0.4. We have received the following evidences. A credible witness reports that "a brown-haired man who is not an employee at the baker´s shop committed the burglary at One Baker Street," evidence 1. An anonymous witness, not being aware that there might be two burglaries, has reported "a brown-haired man who works at the baker´s shop committed the burglary at Baker Street," evidence 2. Thirdly, a witness reports having seen "a suspicious-looking red-haired man in the baker´s shop at Two Baker Street," evidence 3. Finally, we have a fourth witness, this witness, also anonymous and not being aware of the possibility of two burglaries, reporting that the burglar at the Baker Street baker´s shop was a brown-haired man. That is, for example: elds: domain probability distribution: Let us use the algorithm in Sec. V to investigate whether we have a one or two event problem and possibly separate the set of evidences into two disjoint subsets.
Algorithm: Let S = {1, 2, 3, 4}, T = Ø, where S are possible numbers of subsets and T different numbers of subsets for which we have minimized Mcf.
Step 1: We calculate the domain conflict from the probability distribution, Step 2: The domain conflict is minimal for one subset, r = 1.
Step 4.2: t = 1. Since we only have one subset, r = 1, no transfers are possible, we go to 4.5.
Step 4.5: No evidences has been transferred, Mcf and c 1 is unchanged.
Step 4.6: Since Mcf was unchanged in step 4.5 we go to 5.
Step 6: Since S ≠ Ø there might exist better solutions, we go to 2.
Step 5: S := Ø, there are no further possible solutions.

VII. CONCLUSIONS
A criterion function of overall conflict has been established within the framework of Dempster−Shafer theory. An algorithm has been proposed for partitioning nonspecific evidence into subsets, each subset representing a separate event. The algorithm has a theoretical foundation in the minimizing of overall conflict of the partition when viewing the conflict within each subset as an evidence against the partition. The algorithm will not only be able to reason about the optimal partition of nonspecific evidence for a fixed number of events, it will also be able to reason simultaneously about the optimal number of events, which may be uncertain. An obvious drawback is the algorithm's inability to guarantee global optimality I would like to thank Stefan Arnborg, Ulla Bergsten and Per Svensson for their helpful comments regarding this article