💻 computer science

Probabilistic Multi-dimensional Classification with Incomplete Data

This paper proposes a novel, scalable, and robust probabilistic approach for multi-dimensional classification with mixed and incomplete data, providing theoretical foundations for its algorithms and empirical evidence of its effectiveness across various missingness scenarios.

Original authors: Thu Ha Do, Kim-Dung Tran, Vu-Linh Nguyen, Yves Grandvalet, Sébastien Destercke

Published 2026-09-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Thu Ha Do, Kim-Dung Tran, Vu-Linh Nguyen, Yves Grandvalet, Sébastien Destercke

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of data science, computers are often asked to make predictions based on patterns they have learned from past examples. Imagine a doctor trying to diagnose a patient. The doctor looks at a list of symptoms, blood test results, and medical history to predict several things at once: the specific type of disease, its severity level, and how the patient might respond to different treatments. This is a complex task because the data is mixed; some information is numerical, like a temperature reading, while other information is categorical, like a diagnosis that falls into one of several distinct categories. Furthermore, real-world data is rarely perfect. A patient might forget to report a symptom, or a lab test might fail to return a result. When a computer model tries to learn from such incomplete records, it often struggles, especially when the missing pieces are the categorical ones that define the categories themselves.

This challenge sits at the heart of a field known as multi-dimensional classification. Unlike simpler tasks where a computer predicts a single outcome, multi-dimensional classification asks the machine to predict a whole set of outcomes simultaneously. The difficulty is amplified when the data is incomplete. If a model has never seen a specific combination of missing information during its training, it may fail to make a reliable guess when that situation arises later. Researchers have long sought a way to build models that can handle this messiness without losing their ability to find subtle connections between different pieces of information.

A team of researchers at the Université de Technologie de Compiègne in France has developed a new approach to solve this problem. They created a system called a Hybrid Probabilistic Multi-Dimensional Classifier. Think of this system as a flexible map that the computer builds to understand how different pieces of information relate to one another. In previous methods, the computer was often forced to choose between two difficult options: either it could handle complex relationships between variables but would crash if data was missing, or it could handle missing data but would have to ignore the subtle connections between variables to stay simple. The new method bridges this gap. It allows the computer to learn from data even when some categorical values are missing during the training phase, and it allows the computer to make predictions even when those same values are missing during the testing phase.

The researchers tested their system on three real-world datasets containing mixed types of data. One dataset involved information about adults, such as their income and education level, to predict various demographic categories. Another focused on credit defaults, and the third dealt with thyroid disease diagnoses. In their experiments, they deliberately removed information from the records, simulating scenarios where up to 80 percent of the categorical features were missing, or where entire categories of outcomes were unknown. They compared their new method against older techniques that simply guessed the most common answer for missing data or tried to fill in the blanks with estimates.

The results showed that the new hybrid approach was significantly more robust. When the computer was asked to predict outcomes with missing information, the new method consistently outperformed the older baselines. It was particularly effective at handling the "optimistic" and "averaging" strategies, which are ways of dealing with uncertainty. Instead of giving up or guessing blindly, the model used the relationships it learned from the available data to infer the most likely missing pieces. For instance, on the thyroid dataset, where one outcome was overwhelmingly common, the new method still managed to improve predictions for the rarer outcomes, which are often the most critical to get right. The researchers found that their system could maintain high accuracy even when the training data itself was incomplete, a scenario that had previously been very difficult to manage.

A key finding was that the system did not need to be overly complex to work well. By limiting the number of connections the model tried to learn between variables, the researchers kept the calculations manageable while still capturing the essential dependencies. They also discovered that a specific type of mathematical scoring rule, known as the Bayesian Information Criterion, helped the model choose the right level of complexity, preventing it from overfitting to the noise in the data. While the system is not perfect and still faces computational challenges when the number of missing variables becomes extremely large, it represents a substantial step forward. It provides a practical tool for situations where data is messy and incomplete, allowing machines to make better decisions in fields ranging from healthcare to finance, where missing information is the rule rather than the exception.

Technical Summary: Probabilistic Multi-dimensional Classification with Incomplete Data

Problem Definition

Multi-dimensional classification (MDC) involves the simultaneous prediction of multiple class variables for each instance, generalizing both multi-class and multi-label classification. While probabilistic graphical models (Bayesian Networks) are a standard approach for MDC, they face significant challenges when applied to mixed data (containing both discrete and continuous attributes) and incomplete data (where features or class labels are missing).

Existing discriminative MDC (DMDC) approaches handle mixed data effectively but are not natively designed to manage missing discrete variables, particularly at prediction time. Conversely, generative approaches struggle with the computational complexity of mixed data and often fail to provide discriminative performance. Furthermore, the combination of mixed data types, multiple class variables, and missingness creates a setting that remains largely underexplored, specifically regarding the scalability and robustness required for practical applications.

Methodology: Hybrid Multi-dimensional Classifiers (HMDCs)

The authors propose Hybrid Multi-dimensional Classifiers (HMDCs), a novel probabilistic framework that extends DMDC to handle incomplete data while maintaining efficiency with mixed features.

1. Model Structure

HMDCs are defined as Bayesian Networks with specific structural constraints:

Hybrid Nature: Unlike standard DMDCs, which forbid arcs from class variables or continuous features to discrete features, HMDCs relax this constraint. They allow arcs from class variables or continuous features into discrete features.
Constraint Preservation: Arcs from discrete variables to continuous features remain prohibited.
Rationale: This design ensures that every potentially missing discrete variable has at least one observed parent (either a continuous feature or a class variable). This allows the model to predict missing features directly rather than relying on imputation, improving robustness in Maximum A Posteriori (MAP) inference.

2. Learning Phase

The model is trained by maximizing the conditional log-likelihood of the joint distribution of class variables and discrete features given continuous features:
$p(y, x_D | x_C) = p(y | x_D, x_C) p(x_D | x_C)$
This objective decomposes the problem into independent local learning tasks for each discrete variable $Z_j$ (including class variables and discrete features).

Optimization: The learning process involves finding an optimal Directed Acyclic Graph (DAG) structure and parameters. The authors utilize GOBNILP (a globally optimal structure learning framework using integer linear programming) combined with a pruning strategy based on the BIC score to manage the hypothesis space.
Handling Missing Data (Training): For incomplete training data, the paper proposes two main approaches based on decision principles:
- Optimistic Principle (HMDC-OP): Maximizes the likelihood over the best possible completion of missing data. This is equivalent to a "Hard EM" approach.
- Averaging Principle (HMDC-AV): Maximizes the average likelihood over all possible completions. The authors prove that this can be achieved by training on an extended dataset where missing instances are expanded into all possible completions, weighted by their probability.
Local Classifiers: For each local node, the conditional distribution is modeled using a base classifier (e.g., Logistic Regression) that takes continuous features as input, conditioned on the discrete parent configurations.

3. Inference Phase

Prediction for instances with missing discrete features or class variables is performed using MAP inference on the learned DAG.

Optimistic Prediction (HMDC-OP): Selects the prediction that maximizes the utility under the most favorable completion of missing values.
Averaging Prediction (HMDC-AV): Selects the prediction that maximizes the expected utility averaged over all completions.
Approximation (HMDC-MI): To address the computational cost of HMDC-OP when missing variables have high cardinality, an approximation is proposed where missing discrete features are first imputed using their most probable levels, followed by standard MAP inference.

Theoretical results (Propositions 10 and 11) demonstrate that for standard loss functions (Hamming loss and 0/1 subset loss), these optimal predictors reduce to standard MAP queries on the discrete sub-graph of the Bayesian Network.

Key Contributions

Framework Extension: The paper introduces HMDCs, a model that bridges the gap between generative and discriminative approaches, specifically tailored for MDC with mixed data and missing discrete observations.
Theoretical Foundations: The authors derive theoretical results proving that the learning problem decomposes into local learning tasks and that optimal inference under missing data (for specific loss functions) reduces to MAP inference.
Algorithms for Incomplete Data: The paper details specific algorithms (Algorithms 1 and 2) for learning HMDCs from both complete and incomplete training data, utilizing the averaging and optimistic principles.
Comprehensive Evaluation: The study provides an extensive experimental evaluation covering various missingness scenarios (during training and inference) and missing rates (up to 100% for class variables) on three real-world datasets (Adult, Default, Thyroid).

Experimental Results

The experiments were conducted on the Adult, Default, and Thyroid datasets using 10-fold cross-validation.

Performance: HMDC-based methods (specifically HMDC-OP and HMDC-AV) consistently outperformed baseline methods, including Mode Imputation (MI) and Binary Relevance (BR).
Robustness: The proposed methods demonstrated robustness across varying missingness rates. HMDC-OP and HMDC-AV achieved performance close to a "Reference Classifier" (RefC) that has access to the true values of missing features, occasionally surpassing it.
Efficiency vs. Accuracy: While HMDC-OP and HMDC-AV showed indistinguishable predictive scores, HMDC-AV was noted to be computationally cheaper.
Impact of Dependencies: The results indicated that modeling conditional dependencies among discrete variables (via the DAG structure) significantly improved balanced accuracy, particularly for minority classes, by alleviating bias toward majority outcomes.
Base Classifiers: Logistic Regression (LR) was found to be the most effective base classifier, offering a balance of performance and computational efficiency compared to bagged variants or other classifiers like Random Forests.

Significance and Claims

The paper claims that HMDCs provide a scalable and robust solution for probabilistic multi-dimensional classification in the presence of mixed and incomplete data. By relaxing structural constraints on discrete-continuous links, the model enables direct prediction of missing features without imputation, addressing a critical gap in existing DMDC literature.

The authors emphasize that their work extends previous contributions (Do et al., 2026) by introducing a learning framework for incomplete training data (not just inference-time missingness) and providing a more comprehensive evaluation. The significance lies in offering a principled, theoretically grounded approach that maintains computational tractability while handling the complexities of real-world data scenarios where missingness is common and data types are heterogeneous. The work suggests that HMDCs are a viable framework for practical MDC applications where data quality and completeness cannot be guaranteed.