FAIR : Filtering of Automatically Induced Rules (2024)

Abstract: The availability of large annotated data can be a critical bottleneck in training machine learning algorithms successfully, especially when applied to diverse domains. Weak supervision offers a promising alternative by accelerating the creation of labeled training data using domainspecific rules. However, it requires users to write a diverse set of high-quality rules to assign labels to the unlabeled data. Automatic Rule Induction (ARI) approaches circumvent this problem by automatically creating rules from features on a small labeled set and filtering a final set of rules from them. In the ARI approach, the crucial step is to filter out a set of a high-quality useful subset of rules from the large set of automatically created rules. In this paper, we propose an algorithm FAIR (Filtering of Automatically Induced Rules) to filter rules from a large number of automatically induced rules using submodular objective functions that account for the collective precision, coverage, and conflicts of the rule set. We experiment with three ARI approaches and five text classification datasets to validate the superior performance of our algorithm with respect to several semi-supervised label aggregation approaches. Further, we show that FAIR achieves statistically significant results in comparison to existing rule-filtering approaches. The source code is available at https://github.com/ ayushbits/FAIR-LF-Induction.

## introduction machine learning applications rely on large amounts of labeled training data to obtain state-ofthe-art performance on downstream tasks such as text classification, machine translation, image captioning, etc. however, it is expensive to obtain highquality labeled training data. therefore, several methods such as crowdsourcing @xcite , self-supervision @xcite , distant supervision @xcite and semi-supervision * outcome of research while pursuing phd at iit bombay. @xcite techniques have been proposed to reduce the human annotation efforts. another popular technique, viz, weak supervision, aims to quickly create labeled data by leveraging expert defined rules. these rules are generic patterns developed by assessing a few exemplars from the corpus. typically, users encode supervision as rules in the form of labeling functions (lfs), where each rule assigns a noisy label to an instance. however, these different rules can assign different labels to an instance. weak supervision approaches aggregate and resolves these conflicting rules to assign a weak label to an instance. although weak supervision methods reduce the data annotation effort, they still require human experts to frame and encode rules. automatic rule induction (ari) approaches circumvent this problem by automatically inducing rules from the data. ari methods use a small labeled set to extract rules either by using decision tree approaches @xcite or weights of a classifier @xcite . other ari approaches such as grasp @xcite extract rich linguistic patterns from a given set of positive and negative examples. these approaches initially find and filter a list of patterns to find the top-k patterns. these patterns are transformed into rules that yield noisy labels. the rules are then fed to the unsupervised @xcite or semisupervised aggregation approaches to @xcite aggregate noisy labels. current ari approaches select a final set of useful rules without considering explicit interdependencies between the rules. classifier weights @xcite and m-grasp @xcite greedily select top-k patterns having the highest weights assigned by the classifier. in this approach, any interdependence among lfs is not captured as lfs are based on the topranked features and not on their labeling properties. figure 1 : the flow of our approach. we first generate rules in the candidate rule generation block and then filter them using different respective approaches (such as with snuba @xcite , @xcite and classifier weights) as also with fair. the final committed rule set is passed on to the semi-supervised label aggregation approaches for the final performance on the downstream task. snuba @xcite chooses a rule in every iteration that maximizes the weighted sum of the f1 score on the labeled set and jacard score. then snuba reduces the labeled set size by removing instances labeled by added rule. since lfs are generated only on the partially labeled set, the dependency of the rules set is not explicitly captured. further, snuba is computationally involved since new lfs need to be generated iteratively depending upon the verifier's feedback. also, this can lead to similar lfs getting added to the committed set, thereby causing instability. as an illustration, for the question classification dataset which classifies a given question into five different classes, snuba selects the following rules: how, how many, and many for the class numeric while fair (filtering of automatically induced rules) (section 3.2) selects only the how rule in conjunction with other independent rules foot_0 . clearly, derived rules for how, belonging to the same class, are dependent on the parent rule. due to its iterative procedure of working with new induced rules from the uncovered labeled set, snuba selects lfs showing high overlap amongst themselves. our algorithm captures explicit interdependence among lfs, thus selecting diverse and representative rules. in this work, we propose a method, fair to select a subset of lfs (committed set) from a fixed set of automatically induced lfs (candidate set). firstly, we consider a natural objective function defined as a weighted sum of precision, coverage, and agreement. then, we optimize it over all possible subsets of sizes to obtain a final committed set. though natural, this objective function is not submodular, and hence establishing its performance guarantees is not straightforward. we consider another objective function based on graph cut submodular function @xcite . our algorithm, fair, maximizes the objective function based on a greedy approach to obtain the final committed set from a large set of noisy rules. the algorithm works iteratively by selecting patterns having the highest incremental precision and marginal coverage with smaller conflicts over the unlabeled set to determine the top-k rules. our setup favors the selection of a committed set in which the lfs do not mutually contradict while maintaining overall good accuracy and precision. most label aggregation models built with such committed sets should consequently yield lower noise in the labeling assigned to the unlabeled set. fair can be used to filter rules produced by any rule generation approach and is robust to any label aggregation approach because it only uses the characteristics of rules. to the best of our knowledge, such an approach of selecting a committed set has not been addressed in erstwhile approaches. we perform experiments with several ari, pattern filtering, and label aggregation approaches as shown in figure 1 . for generating candidate rules, we use approaches such as decision tree @xcite , classifier weights @xcite , and a modified version of grasp @xcite . subsequently, we filter the large set of rules using the corresponding candidate generation approaches and our algorithm fair. finally, over the selected committed set of rules, we leverage semi-supervised label aggregation algorithms, viz, spear @xcite , astra @xcite , implyloss @xcite and learning to reweight @xcite . we observe that our approach yields rules more refined than the other approaches by virtue of its analyzing (i) coverage and agreement over the unlabeled set and (ii) precision on the test set. we observe that rules filtered using fair perform better on label aggregation approaches, providing gains between 2 -20% across different datasets. it implies that the filtering of rules is a crucial element that was not explored earlier. prior work has emphasized on lfs defined by experts based on observations in a few instances from the dataset. unsupervised approaches like @xcite use a generative model to determine the correct probability for labels in accord with noisy and conflicting labels assigned by lfs. @xcite proposed a graphical model, cage, which extends to continuous lfs with scores obtained using cosine similarities of word vectors, tf-idf score, the distance among entity pairs, etc. while semi-supervised approaches additionally use a small labeled set to guide the discovery of lfs for classification @xcite and information extraction tasks @xcite . recent methods @xcite proposed a bi-level optimization wherein parameters are optimized on the validation set in a semi-supervised manner. we use semi-supervised aggregation methods in our experiments. ## problem setup we begin by defining key metrics used throughout the experiments. a) precision of a rule on a labeled set is the ratio of the number of correctly assigned labels over the total assigned labels, b) coverage of a rule is the percentage of points covered over unlabeled set, c) conflicts between rules r j and r i , j ̸ = i, is the percentage of points that are assigned different labels by rule r i and r j and d) agreement between rules r i and r j is defined as the percentage of points that are assigned same labels by rules r i and r j . note that, conflicts and agreements are related as both rules on a particular instance will either conflict or agree. we consider different submodular functions reflecting precision, coverage, and conflicts of the rules as objectives. we also explore their combinations as objective functions. ## experiments we select five text classification datasets and compare rules induced by fair with the rules generated output: f by three ari approaches (c.f., section 3.2). we measure the efficacy of these rules by aggregating the assigned labels using four semi-supervised label aggregation approaches. it takes around approximately 2 -6 gpu hours to complete all experiments except sst which takes around 12 hours to complete. we performed all our experiments on a single nvidia rtx 2070. datasets : (1) trec @xcite is a multi-class question classification dataset consisting of open-domain, fact-based questions divided into broad semantic categories. the dataset has the following six labels: abbreviation, description, entities, human, locations and numeric values. (2) youtube comment classification (alberto et al., 2015) is a spam comment classification dataset. (3) imdb genre classification foot_1 is a binary moviegenre classification dataset from a movie plot summary. the labels are romantic and action. (4) sms spam classification (almeida et al., 2011) is a binary classification dataset to classify a given sms as spam or not spam. (5) stanford sentiment treebank (sst) @xcite is a collection of written or spoken texts with fully labeled parse trees for a complete analysis of the compositional effects of sentiment in language. the output labels for this dataset are negative, somewhat negative, neutral, somewhat positive and positive. ## conclusion we propose fair, a rule-filtering approach that selects a useful subset of rules from a given large candidate set of rules by leveraging implicit interdependencies among the rules. we introduce an objective function that maximizes precision, coverage, and agreement among rules and augments the function by designing a submodular function providing convergence guarantees. we conduct extensive experiments and demonstrate the importance of selecting high-quality and diverse rules with very few labeled instances. we qualitatively analyze the rules generated by fair and existing approaches. further, we show that fair outperforms existing filtering approaches in terms of end-model performance using different label aggregation methods which makes fair robust to different aggregation as well as rule generation approaches.