## 2 Related Work and Problem Description  
The goal of the NILM disaggregation algorithm is to estimate the power of each appliance that contributes to the total power consumption that was measured by smart meter in a household. The problem can be described as:  
\[\overline{P_{t}}=\sum_{i=1}^{N}p_{t}^{i}+e_{t} \tag{1}\]  
where \(\overline{P_{t}}\) is the total power consumption at time \(t\), \(p_{t}^{i}\) is the consumption of appliance \(i\) at time \(t\), \(N\) equals the number of appliances, and \(e_{t}\) the measurement noise. For FSM (Finite State Machine) with multiple power states, assuming that each appliance has \(M\) power states, the power consumption of \(i\)-th appliance, for time \(t\), is described as follows:  
\[ \begin{split}& p_{t}^{i}=A^{i}X_{t}^{i}+e_{t}^{i}\\ & A^{i}=\left[a^{i,1},a^{i,2},...,a^{i,M}\right]\quad i=1,2,...,N \\ & X_{t}^{i}=\left[x_{t}^{i,1},x_{t}^{i,2},...,x_{t}^{i,M}\right]^ {T}i=1,2,...,N\end{split}  \tag{2}\]where \(A^{i}\) is a vector containing the power consumption \(a^{ij}\) for appliance \(i\) in every state \(j\), and \(X^{i}_{t}\) is a binary-valued vector, composed by the ON/OFF status of each power state for appliance \(i\) at time \(t\). If appliance \(i\) is in state \(j\) at time \(t\), \(x^{ij}_{t}=1\); Otherwise, \(x^{ij}_{t}=0\). Obviously, appliance \(i\) is in only one state, so \(\sum_{j=1}^{M}x^{ij}_{t}=1,\forall i\), \(t\). \(e^{i}_{t}\) is the measurement noise for appliance \(i\) at time \(t\). Based on the above introduction, the load disaggregation is transformed into the optimization problem seeking operating state of each appliance \(X_{t}\) at time \(t\), so that the difference between the estimated and the measured total power is minimized, which can be described as follows for a given time step \(H\) and the measured total power \(P_{t}\) at time \(t\):  
\[\text{argmin}[\sum_{t=1}^{H}(P_{t}-P_{t})^{2}] \tag{3}\]  
Problem described in Equation (3) can be solved by using optimization algorithms such as genetic algorithms [22], integer optimization [23], sparse optimization [24; 25; 26], or differential evolution [27], which are applied to search the best matched combination of appliances making the calculated total power equal to the measured total power. The techniques are not suitable for more types of appliances and need complex computation. Another solution for load disaggregation is the so-called pattern recognition method, which extracts transient or steady-state features of appliances, then to match with the signature model in database. Pattern recognition techniques, such as artificial neural networks (ANN) [12; 28; 29] or Hidden Markov Models (HMM) [30; 31] have been tested and show their ability in learning the consumption pattern of appliances. In particular, HMMs and their extensions were used in many data disaggregation models The hidden states chain in HMMs represents the operating state/states of a device and the emission or observation sequences represent the measured total power consumption [30]. However, as the number of appliances increases, the computation complexity of HMM increases exponentially (see the computational complexity analysis in Section 4.3.2) [31]. Time series subsequence data mining is using to study and classify the transient operations of typical appliances [32]. K-means method is applied to denoise the measured consumption sequence [31], and in some literature, FCM, fuzzy version of the K-means, is running to divide appliances turn-on events or spectral into several categories, and then each category is labeled [33; 34]. In literature [35], X-means algorithm is used to cluster the power levels, and shows good performance on real data in an industrial application for smart houses. However, the appliances with similar power ranges may be misidentified. Another pattern recognition method proposed recently relies on Dynamic Time Warping (DTW), used in the field of speech recognition to match between traces of difference length [36].