Abstract: This paper considers additive factorial hidden Markov models, an extension to HMMs where the state factors into multiple independent chains, and the output is an additive function of all the hidden states. Inference in these models is NP-hard. We present a novel convex approximation for the MAP inference problem in this model, which we call AFAMAP. Our approach relies on a convex relaxation of the state space, a robust noise model, and a constraint that limits the number of state changes at each time step. We demonstrate the effectiveness of our approach on synthetic data and on the Reference Energy Disaggregation Dataset (REDD).
Introduction
Energy disaggregation, also known as Non-Intrusive Load Monitoring (NILM), is the task of taking a single aggregate energy signal from a household and decomposing it into the power consumption of individual appliances. This problem is traditionally modeled using Factorial Hidden Markov Models (FHMMs), where multiple independent Markov chains (representing appliances) evolve in parallel, and the observed output is the sum of their individual emissions.
While FHMMs provide a natural framework for this task, exact inference is computationally intractable as the state space grows exponentially with the number of chains. Existing approximate inference methods, such as Gibbs sampling or Structured Mean Field (SMF), are non-convex and highly sensitive to initialization, often becoming trapped in local optima. This paper introduces AFAMAP (Additive Factorial Approximate MAP), a convex optimization-based approach that guarantees a global optimum for its objective function.
Methodology: The AFAMAP Algorithm
The authors propose three primary innovations to transform the traditionally NP-hard inference problem into a manageable convex quadratic program:
1. The Difference Model
Rather than relying solely on absolute power levels, AFAMAP incorporates the change in power between time steps ($\Delta y$). This captures the sharp "edges" or transitions when a device toggles between states (e.g., turning on or off). By modeling these transitions, the algorithm can better distinguish between devices with similar absolute power draws but different switching characteristics.
2. Robust Mixture Components and Total Variation
Real-world energy data is often corrupted by "unmodeled" devices—small loads like phone chargers that are not part of the primary HMM chains. To handle this, the authors introduce a robust signal component governed by a Total Variation (TV) penalty. This acts similarly to a Huber loss function, allowing the model to absorb unexplained spikes or noise without skewing the disaggregation of the primary appliances.
3. The One-at-a-Time Constraint
A key insight of the paper is that in a continuous-time system, the probability of two independent appliances switching states at the exact same millisecond is negligible. By enforcing a constraint that at most one HMM can change state at any given time step, the authors can relax the complex integer programming problem into a convex quadratic program. This relaxation ensures that the resulting optimization problem can be solved efficiently using standard tools like CPLEX.
Experimental Results
Synthetic Evaluation
The algorithm was first tested on synthetic data generated from cyclic HMMs to evaluate scalability. As shown in the performance plots below, AFAMAP consistently outperformed the Structured Mean Field (SMF) baseline. While SMF's error increased significantly as the complexity of the model (number of HMMs or states) grew, AFAMAP remained close to the theoretical "Exact MAP" performance.
Real-World Performance on REDD
The method was applied to the Reference Energy Disaggregation Dataset (REDD), which contains high-resolution power data from real homes. AFAMAP achieved a total precision of 87.2%, a massive improvement over the 35.5% achieved by the SMF baseline. Notably, for five out of the nine appliances tested—including high-draw devices like the microwave and furnace—the algorithm achieved precision scores exceeding 90%.
Conclusion and Future Work
AFAMAP demonstrates that by leveraging convexity and structural constraints like the "one-at-a-time" condition, it is possible to achieve state-of-the-art disaggregation accuracy without the initialization issues inherent in non-convex methods.
Future research directions include extending the model to unsupervised settings where appliance models are learned directly from aggregate data. The authors also suggest that specialized solvers for TV-regularization could further improve the computational efficiency of the quadratic programming step, enabling real-time disaggregation on low-power embedded hardware.
Summary updated