Using a Relational Tsetlin Machine (RTM) for analysis of semi-structured data allows the use of inherent relational structures present in natural language text to get an explainable classification of data. A finite Herbrand model derives Horn Clauses from the model, which are simple yet powerful logical tools that can build an abstract view of the world. We use the same to analyze human rights violation data. We show concretely how natural language can be transformed into a relational structure, and further use the Relational Tsetlin Machine to not only classify incidents as serious and non-serious violations but also explore the patterns learned by the RTM in order to arrive that those decisions. Furthermore, the distilled Horn Clauses show a precise understanding of the concepts involved without the drawback of textual ambiguity.
tropy models, and similar statistical approaches, trained
on large amounts of data; (c) Identifying and matching
Training Artificial Intelligence ( AI) to answer natural surface-level patterns with templates for response
generlanguage questions is a crucial part of the quest for en- ation. Often hybrid approaches are preferred for higher
coding a human-equivalent understanding of the world performance. But most QA systems sufer from a lack of
in machines. Massive structured Knowledge Bases (KBs), ability to generalize, and either have restrictive use cases
such as Freebase [
Various methods currently in use for Question An- has provided a smaller memory footprint and faster
inferswering (QA) are broad: (a) Tokenization, POS tagging, ence than more traditional neural network-based
modparsing, and other linguistic approaches to derive a pre- els [
In a “Propositional” TM, a team of base TAs collec- clause strengthens its TA, in turn, depending on the foltively generates propositional formulas using conjunctive lowing criteria: (1) its output (); (2) the TA’s action clauses. Its input is of the vector form = (1, . . . , ), — Include or Exclude; and (3) the value of the literal and the TM learns clauses that decide if an input is to be allocated to the TA. Type I feedback is governed by two in class = 0 or = 1. The learnt clauses are conjunc- rules: tive combinations of elements from a subset of a literal set made of input features and their respective negations ¯ = ¬ = 1 − . Each clause can be represented as: () = ⋀︀∈ = ∏︀∈ .
(1) E.g., the clause () = 1 ∧ 2 = 12 consists of the literals = {1, 2} and outputs 1 if 1 = 2 = 1.
The number of clauses used is a user-defined parameter . Each new configuration of clauses created is subjected to feedback, which controls the distribution of frequently occurring patterns, as well as increasing the discriminating power of individual patterns. Of the total number of clauses, half vote in favor of = 1 i.e., positive polarity clauses (+), whereas the other half vote in favor of = 0 i.e., negative polarity clauses (− ). Classification is performed based on a majority vote using equation 2 and the unit step function: ˆ = () = 1 if ≥ 0 else 0 (for details, see [19]).
= ∑︀=/12 +() − ∑︀=/12 − ().
(2) • When () = 1 and = 1 the Include is rewarded and Exclude is penalized with probability − 1 . This reinforcement is powerful (triggered with high probability) and causes the clause to recall and refine the pattern it detects in .1 • When () = 0 or = 0 the Include is penalized and Exclude is rewarded with probability 1 . This reinforcement is weak (activated with low probability) and coarsens infrequent patterns, hence increasing their frequency.
determines pattern frequency; a larger results in fewer patterns.
When = 0, Type II feedback is supplied stochastically to sentences with positive polarity; when = 1, Type II feedback is given to clauses with negative polarity. Whenever () = 1 and = 0, it penalizes Exclude. Thus, this feedback generates literals for diferentiating between ! = 0 and = 1 by evaluating the clause to 0 when confronted with its rival class.
While this vanilla TM setup operates on propositional input variables = (1 . . . , ), to generate propositional conjunctive clauses, the Relational Tsetlin Machine (RTM), described next, processes relations to generate Horn clauses.
^ = (1¯2 + ¯12 − 12 − ¯1¯2). The TM leverages a team of TA for learning, one TA per literals in . Each TA performs one of two actions - Include or Exclude- and determines whether to include the literal assigned in its clause. TM encompasses an online learning system that processes one training example , at a time. The TA 3. Relational Tsetlin Machine generates a new configuration of clauses 1+, . . . , −/2, before computing a voting total . Following that, feed- The work in [18] introduced the RTM as an extension back is distributed statistically to each TA team. The dif- to the vanilla TM, encoding relations found in natural ference between the clipped voting total and language using a logic-based representation for the TM. a user-defined voting threshold determines the likeli- The notion of RTM is based on a logic program using a hood that each TA team will get feedback. Take note that the voting amount is normalized by clipping the voting 1Tisarkeepnlaocteedthbayt w1.hen true positives are boosted, the probability − 1
Input Sentence The 1992 Anti-terrorist Law suspended the requirement that the police obtain warrants in order to make arrest. Who is Perpetrator?
Who is Victim?
Dataset Relation Extraction
Entity Extraction
Entity
Generalization Generate Feature
Vectors Train TM
Extract Clauses ifnite Herbrand model [21, 22]. The ability to characterize more compact representation than is possible with learning using Horn clauses is particularly beneficial merely propositional clauses. To illustrate this, assume since Horn clauses are both simple and strong enough to = {1, 2, . . . , } be variables representing the describe any logical formula [22]. constants occurring in an observation (˜ , ˜). Here, is
The RTM is a three-step process based on mapping the the maximum number of distinct constants required for learning problem to a pattern recognition problem using each observation (˜ , ˜), each needing its own variable. vanilla TM: We map the atoms to propositional inputs to create a - By mapping relations to propositional inputs, a method vanilla TM learning problem. That is, each propositional for dealing with relations and constants is devised. We input represents a unique atom with a specific varibegin with Horn clauses without variables. Let a set able configuration: ≡ ( 1 , 2 , . . . , ), with of constants = {1, 2, . . . , } be finite and a set being the arity of . As a result, the number of conof relations = {1, 2, . . . , } of arity ≥ 1, ∈ stants in has no efect on the number of propositional {1, 2, . . . , } form the finite Herbrand base HB = inputs required to describe the problem. Rather than {1(1, 2, . . . , 1 ), 1(2, 1, . . . , 1 ), that, this is determined by the number of variables in . . . , (1, 2, . . . , ), (2, 1, . . . , ), . . .} con- as well as the number of relations in . For a particular sisting of all ground atoms that can be expressed observation (˜ , ˜), we first replace the constants in ˜ using and . Additionally, we have a logic program with variables, from left to right. Accordingly, the corre with program rules defined as non-recursive Horn sponding constants in ˜ are also replaced with the same clauses. Each Horn clause has the following form: variables. Remaining constants in ˜ are arbitrarily replaced with additional variables. The propositional input 0 ← 1, 2, · · · , . (3) vector is regenerated.
Here, , ∈ {0, . . . , }, is an atom (1, 2, . . . , ) - A convolution approach with a standard TM as dewith variables 1, 2, . . . , , or its negation scribed in Section 2.1 handles a large number of alterna¬(1, 2, . . . , ). The arity of is denoted by . tive constant-to-variable mappings as a standard pattern We map every atom in HB to a propositional input , recognition problem. getting the propositional input vector = (1, . . . , ) The RTM is summarized in Algorithm 3. (cf. Section 2.1). Decoupling the constants, i.e. step 2 above, serves - The horn clauses with variables are introduced to to generalize the clause-based relations, and to allow decouple the TM from the constants, resulting in a quicker learning with less input. By seeking Horn clauses Algorithm 1 Relational TM
input Convolutional Tsetlin Machine TM, Example pool , Number of training rounds 1: procedure Train(TM, , ) 2: for ← 1, . . . , do 3: (˜ , ˜) ← ObtainTrainingExample() 4: ′ ← ObtainConstants(˜) 5: (˜ ′, ˜′) ← VariablesReplaceConstants(˜ , ˜, ′) 6: ′′ ← ObtainConstants(˜ ′) 7: ← GenerateVariablePermutations(˜ ′, ′′) 8: UpdateConvolutionalTM(TM, , ˜′) 9: end for 10: end procedure that employ variables rather than constants, we can pri- words or phrases to specific parts of judgments and asoritize atoms above variable configurations. If is the pects using the following ontology: largest number of unique constants involved in any particular observation, the number of atoms is bound by (), where is the largest arity of relations in .
Given the possibility of diferent methods to assign variables to constants, the preceding technique may result in duplicate rules. One may wind up with identical rules with just a syntactic variation, i.e., the same rules represented using diferent variable symbols. To prevent the creation of unnecessary rules, the Relational TM generates all feasible permutations of variable assignments.
Finally, we conduct a convolution over the permutations to process them. • Perpetrator - what entity is being judged? • JPr - judgment of presence or absence • JQu - judgment of quantity or intensity • JGT - judgment of giving or taking • SAVP - what is the specific aspect being judged
(protection/violation) • GAHR - general aspect of human rights • Victim - who is the victim of the action? • Negation - words that negate the meaning of the sentence (usually not)
PULSAR (Parsing Unstructured Language into Sentiment-Aspect Representations) aims at parsing human rights reports into sentence-level judgments and linking judgments to specific aspects of human rights. It handles a large corpus of yearly reports from human rights non-governmental organizations (HRNGOs), as well as the State Department and Amnesty International Annual Reports.
The parser uses aspect-based sentiment analysis (ABSA) to separate judgments (sentiments) from things being judged (aspects). As an example, consider the following sentence: • I like (sentiment, judgment) status of human rights in this country (aspect).
• Security forces (Perpetrator) are (JPr) regularly (JQu) participating (JGT) in the abducting (SAVP, GAHR) of minorities (Victim).
We use PULSAR output to produce either a ‘suppress’ or a ‘support’ relation between two entities, followed by a query. The entities are the subject and the object of the relation present in the sentence. In the case of a ‘suppress’ relation, Entity A and B are ‘Perpetrator’ and ‘Victim’. In a ‘support’ relation, they are ‘Supporter’ and ‘Beneficiary’. Based on this relation, one needs to identify whether a violation of rights has occurred.
To assist us in constructing the task, we make the following assumptions: 1. All statements only include information about relation “Support” or “Suppress”. 2. All questions are limited to information on the relation of subject and object. 3. Both “Support” and “Suppress” each entail two entities, such that / (, ) : ∈ {}, ∈ {}
The 1992 Anti-terrorist Law suspended the requirement that the police obtain Support warrants in order to make arrest.
Support (Supporter-Beneficiary) The Government contends disciplinary action against police who are guilty of Suppress violating human rights.
Suppress (Perpetrator-Victim)
Law
Govt.
Police
Police
The first step is to convert the text into a machineunderstandable relational representation. A relation in The relational factor is given by the diference in variance this context refers to a relationship between two (or more) = − , resulting in: elements of a text. Once identified, the entities may be tgheenereralalitzioednsfo(wrfhuertthheerr rreedduuccetdiovniaofgseenaerrcahliszpaaticoen. Foirnnalolyt), RelA = ⎧⎪⎨ iiff >< 00,, (5) are used as input features for a standard TM setup for ⎪⎩ if = 0. the categorization of the text.
Relation Extraction: Our text is composed of simple Entity Extraction: After identifying the relations, we sentences, each of which has a sentence containing only must determine the textual components that contribute one relation. The relations found in the query are deter- to the formation of those relationships. This enables us mined using other features of a dataset and are linguis- to enhance the representation with restrictions, allowtically related. Table 1 illustrates examples of Relation ing the RTM to learn rules that most accurately reflect Extraction on our dataset. Each statement is associated action and consequences in a logical manner. The rewith the relation of either “Support" or “Suppress”, while trieved entities can be combined with the information the query is associated with either the Subject or the about the external world knowledge to create a richer Object. Using the query, we can extract the relation as representation. For example, the concept that the subject well as identify the entity. and object in a ‘Suppress’ relation can also be termed The relation between the entities are calculated based as ‘Perpetrator’ and ‘Victim’, is an example of external knowledge. Notably, as per Fig. 1, it is not feasible to on positive valence count () and negative valence begin answering the query until both Relation Extraction cdoounneta(sshow).nTihneEaqsusiagtinomne4n: t of the relation () is and Entity Extraction have been completed. Additionally, knowledge of the relation enables us to filter down the produced during learning. At the end of the training, the potential entities that will successfully respond to the relations captured by the TM constitute a global picture query. of the learning, i.e. what the model has learned in general.
Entity Generalization: One disadvantage of the Additionally, the global picture can be seen as a descriprelational representation is that as more sentences are tion of the task itself, as understood by the machine. We analyzed, the number of potential relations grows ex- also have access to a local snapshot that is unique to each ponentially. One strategy to limit the spread is to rel- input instance. This contains just the clauses that deegate particular entities to a more generic identifica- scribe the relations associated with a particular instance. tion. Consider the following two instances from Table We use instances from a human rights dataset to 1: “Text: The 1992 Anti-terrorist Law suspended the showcase our work. The dataset contains human requirement that the police obtain warrants in order rights-related sentences. Each sentence constitutes a to make an arrest. Q1: Who is Supporter? Q2: Who perpetrator, a victim, and a query related to them. The is Beneficiary?" and “Text: The Government contends relation that exists between them is either support or disciplinary action against police who are guilty of vi- suppress. Based on this relation we determine whether olating human rights. Q1: Who is Perpetrator? Q2: the rights of the victim are violated and we put them in Who is Victim?". Processing the texts as per the pre- the respective label of “severity” or “non-severity”. We vious section, we end up with six distinct relations: Sup- show the clauses obtained for one such example chosen port(Law, Police), Supporter(Law), Beneficiary(Police), from the dataset: Suppress(Government, Police), Perpetrator(Government), Input: The Government maintained that this waiting Victim(Police). However, in order to answer any of the period was necessary to determine whether a woman may queries, we simply need the relations associated with still be carrying the child of her former spouse. that query. As a result, we can reduce both sentences Output: no violation to four relations: Support(subj1, obj1), Suppress(subj2, obj2), Subj(subj1 / subj2), and Obj(obj1 / obj2). Prioriti- To assist us in constructing the task, we make the zation requires that the entities included in the query following assumptions: relation be generalized first. Any instances of those entities in the relations before the query are substituted.
The entities present in other relations are subsequently substituted with variables irrelevant for answering the query (Table 2). 4.1. Classification Having reduced the text into a relational feature set, we now proceed to the classification task. We train RTM with 650 clauses, threshold = 600, and specificity = 25 for 200 epochs. The LSTM with 100 memory units, 100 embedding sizes, spatial dropout, and softmax activation is used. The CNN with 32-dimensional embedding, convolution layer with max pooling, and sigmoid activation is used. Table 3 shows that the RTM outperforms LSTM, CNN, and vanilla TM considerably over 10 independent runs. The vanilla TM, due to its disregard for the relationship between variables, exhibits poor performance as it lacks the ability to generalize these relationships. Both LSTM and CNN demonstrate comparable performance.
However, the utilization of the Herbrand model and horn clause in RTM enhances its robustness and generalization capability, surpassing the performance of other methods by approximately 20%. 4.2. Explainability One of the major reasons for choosing TMs for this task is the inherent explainable structure built into the clauses 1. All statement sentences include just information
about the relation “Support” or “Suppress”. 2. All questions are limited to information on the
relation between perpetrator and victim. 3. Relation “Support” entails two entities, such that / (, ) : ∈ {}, ∈ {} 4. Relation “Suppress” entails two entities, such that / (, ) : ∈ {}, ∈ {} 5. “Support” or “Suppress” is a time-bound relation, its impact is overtaken by a subsequent comparable action.
Input => Support(Govt., woman), Support(Govt., child), NotSuppress(Govt., woman), Not Suppress(Govt., child), Query (Subject), Query (Object). 2 Clauses Without Entity Generalization: The complexity of tasks depends upon the collection of sentences from which the model has to identify the relations. For our experiment, we number each input for two potential relations (i.e., support or suppress). Based on this relation the classification is done into one
transformed to a vector with each element representing the existence (or lack) of the relationship instances. of two labels (i.e., severe or non-severe). The initial stage (, ) ← in preparing data for the TM is to reduce the input to (), (), relation-entity bindings. These bindings comprise the (, ). feature set against which the TM is trained.
Clauses are of the form: Support(Govt, woman) AND Characterizing learning using Horn clauses is interSupport(Govt, child) AND NotSuppress(Govt, woman) esting because they are simple but powerful enough to AND Query(Govt) AND Query(Child). describe any logical formula [22]. Multiple learned Horn Clauses can form a deductive framework on a dataset.
Clauses With Entity Generalization: We follow the same procedure for making relation-entity binding for relational input features as explained above. Following that, we group the features by entity type to generalize the information. After all, entities are replaced with general placeholders, we train TM with binary features having general entities as features.
Input => Support(Subj1, Obj1), Support(Subj2, Obj2), NotSuppress(Subj1, Obj1), NotSuppress(Subj1, Obj2), Q(Subj1), Q(Obj1 / Obj2).
Clauses are of the form: Query(Subj1) AND Query(Obj2) AND Support(Subj1, Obj1) AND Support(Subj1, Obj2) AND NotSuppress(Subj1, Obj2) AND NotSuppress(Subj1, Obj1).
These clauses ofer a more compact view of the task without distractions from unimportant constants.
to relational input and classify human rights violations. In many real-world datasets, especially those with polarizing information such as human rights, it is imperative to gain a deeper understanding of the classification logic behind the actual classes. While the information can hide behind ambiguous language, the framework must have mechanisms to reduce the ambiguity as much as possible, so that the resultant classification is easy and straightforward to interpret. The use of RTM allows us to obtain precise explanations in terms of Horn Clauses that can form the basis of extended logical frameworks, without compromising on accuracy.