# Attribute Relevance Score: A Novel Measure for Identifying Attribute Importance
## 2 Proposal: Attribute Relevance Score  
In this work, within the framework of the all-relevant problem, we introduce a novel univariate approach for evaluating attribute relevance, designed to tackle the inherent challenges of feature selection in high-dimensional datasets. Our approach builds upon the concept of shadow attributes, introduced by [PERSON] and later used by [PERSON] in the Boruta algorithm, to create a more robust measure of individual attribute importance. Unlike traditional methods, which may produce biased results due to specific data splits or data assumptions, our technique systematically evaluates each attribute's contribution by comparing it against its permuted versions. This process ensures that the relevance identified for each feature truly reflects underlying patterns in the data rather than artifacts from specific data splits or model configurations, enhancing both the reliability and interpretability of the results. Consider an attribute matrix \(\mathbf{X}\in\mathbb{R}^{n\times m}\), where \(n\) represents the number of samples and \(m\) denotes the number of attributes, along with its corresponding labels \(\mathbf{y}\in\mathbb{R}^{n}\). To evaluate a specific attribute \(\mathbf{x}=[x_{1},x_{2},\ldots,x_{n}]^{T}\), where each \(x_{i}\) represents an observation, we begin by partitioning \(\mathbf{x}\) into training and testing subsets, denoted as \(\mathbf{x}_{\text{train}}\) and \(\mathbf{x}_{\text{test}}\), respectively, such that \(\mathbf{x}=\mathbf{x}_{\text{train}}\cup\mathbf{x}_{\text{test}}\) and \(\mathbf{x}_{\text{train}}\cap\mathbf{x}_{\text{test}}=\emptyset\). A model \(\mathcal{M}\) (e.g., a decision tree) is then trained using the training subset \(\mathbf{x}_{\text{train}}\) and its corresponding labels \(\mathbf{y}_{\text{train}}\). Subsequently, a shadow model, \(\mathcal{M}_{s}\), is trained using a permutation of \(\mathbf{x}_{\text{train}}\), denoted as \(\mathbf{x}_{s}\), with the same labels \(\mathbf{y}_{\text{train}}\). We then consider a performance measure \(F\) that results from evaluating the output of a model on the test subset \(\mathbf{x}_{\text{test}}\), compared to the correct labels \(\mathbf{y}_{\text{test}}\). The choice of \(F\) should be made according to the specific problem at hand. The core premise of our approach is that the performance measure \(F\) of the model \(\mathcal{M}\), trained on the original attribute \(\mathbf{x}_{\text{train}}\), should consistently be superior to that of the shadow model \(\mathcal{M}_{s}\), trained on the permuted attribute \(\mathbf{x}_{s}\), when both are evaluated on the same test subset \(\mathbf{x}_{\text{test}}\) with labels \(\mathbf{y}_{\text{test}}\). \[\text{Opt}(F(\mathcal{M}))>\text{Opt}(F(\mathcal{M}_{s})), \tag{1}\]  
where \(\text{Opt}(\cdot)\) represents an optimization criterion for \(F\). Depending on the nature of \(F\), this criterion could aim to maximize or minimize its value. To minimize biases from specific test subsets, which could distort evaluations, we employ random sampling across multiple test subsets. This ensures a comprehensive and robust assessment of attribute relevance, capturing the magnitude of the observed effects and articulating them with a level of detail that supports precise and actionable conclusions. We propose Equation (2) to calculate the attribute relevance score (ARS) for performance metrics \(F\), where \"the closer to 1, the better\", such as those commonly used in classification tasks (e.g., accuracy, F1 score, recall, and precision). \[\text{ARS}=\text{max}\left(0,\frac{\overline{F}(\mathcal{M})-\left(\overline{ F}(\mathcal{M}_{s})+\epsilon\right)}{1-\left(\overline{F}(\mathcal{M}_{s})+ \epsilon\right)}\right), \tag{2}\]  
where \(\overline{F}(\mathcal{M})\) represents the median performance of model \(\mathcal{M}\) across multiple test subsets, \(\overline{F}(\mathcal{M}_{s})\) is the median performance of the shadow model over the same subsets, and \(\epsilon\) is a small positive constant indicating the minimum acceptable effect size threshold.