extfieldsofstudy:
Computer Science
Physics
Mathematics

text:
A note on the accuracy of the generalized-$\alpha$ scheme for the incompressible Navier-Stokes equations

We investigate the temporal accuracy of two generalized-$\alpha$ schemes for the incompressible Navier-Stokes equations. The conventional approach treats the pressure with the backward Euler method while discretizing the remainder of the Navier-Stokes equations with the generalized-$\alpha$ method. We developed a suite of numerical codes using inf-sup stable higher-order non-uniform rational B-spline (NURBS) elements for spatial discretization. In doing so, we are able to achieve very high spatial accuracy and, furthermore, to perform temporal refinement without consideration of the stabilization terms, which can degenerate for small time steps. Numerical experiments suggest that only first-order accuracy is achieved, at least for the pressure, in this aforesaid approach. Evaluating the pressure at the intermediate time step recovers second-order accuracy, and the numerical implementation, in fact, becomes simpler. Therefore, although the pressure can be viewed as a Lagrange multiplier enforcing the incompressibility constraint, its temporal discretization is not independent and should be subject to the generalized-$\alpha$ method in order to maintain second-order accuracy of the overall algorithm.

Introduction
The generalized-α method was initially proposed for structural dynamics [4] and possesses the desirable numerical properties of implicit schemes, as noted by Hilber and Hughes [12]. The method was later extended to address first-order systems, with an important example being the Navier-Stokes equations [16]. Interestingly, when used in conjunction with the first-order structural dynamics, the generalized-α method has been found not to suffer from the 'overshoot' phenomenon [17], making it an ideal time integration algorithm for low-frequency, inertial type problems. Over the years, this temporal scheme has gained popularity as an implicit scheme for fluid and fluidstructure interaction (FSI) problems. When it was originally introduced to computational fluid dynamics (CFD) problems, Jansen et al. considered the compressible Navier-Stokes equations written in the pressure primitive variables, which were evaluated at the intermediate time step [16]. Later, when dealing with the incompressible Navier-Stokes equations, the time-stepping scheme was used in a slightly different manner: the velocity alone was evaluated at the intermediate time step, while the pressure was treated by the backward Euler scheme. This choice of temporal discretization has in fact become quite popular in both CFD and FSI simulations (see e.g. [1,2,3,5,8,9,19,23]). Indeed, the pressure can be viewed as a Lagrange multiplier enforcing the divergence-free constraint and should therefore "not be subjected to a time integration scheme" [6]. While this may explain the widespread adoption of the backward Euler method for pressure, we note that there exist a few works evaluating the pressure at the intermediate time step [10,15,18,22]. In our view, treating the pressure by the backward Euler method is unnatural and inefficient for the following reasons. First, given that the incompressible Navier-Stokes equations constitute a limiting case of their compressible counterparts, treating the pressure by the backward Euler method is evidently inconsistent with the scheme proposed in [16]. The inconsistency is even more apparent when we recall that the pressure is the hydrostatic part of the Cauchy stress, suggesting that the hydrostatic and deviatoric parts of the Cauchy stress are evaluated differently in time in this conventional approach. Second, in the implementation of CFD algorithms, variables are typically stored in an 'interlaced' pattern, which is cache-friendly for high-performance computing [11]. Using two distinct solution updating strategies in the time integration algorithm necessitates separate extraction of the velocity and pressure degrees-of-freedom from the interlaced solution vector, thereby reducing the overall algorithmic efficiency. In addition to the inconsistency and inefficiency, we may also reasonably expect the backward Euler method to yield a loss of numerical accuracy. Second-order accuracy is one of the most important numerical attributes for a desirable implicit scheme [12], since the error accumulation from first-order schemes may be excessive for practical applications.
In this work, we compare the numerical accuracy of two generalized-α schemes. The first, which we denote as Scheme-1, is the popular choice in which the pressure is integrated by the backward Euler method; the second, denoted as Scheme-2, evaluates the pressure at the intermediate time step. We present the accuracy of quantities of interest in two benchmark cases. The Navier-Stokes equations are discretized in space by inf-sup stable NURBS element pairs. Our rationale behind this choice is twofold. We want to avoid invoking the stabilized formulation, which can degenerate for small time steps when used without special treatment [13] and is therefore not robust for temporal convergence studies. Furthermore, the robustness and exact geometric representation made possible by the NURBS-based isogeometric analysis technique allow us to eliminate the possibility of confounding errors from the spatial discretization and thereby focus on the temporal accuracy. wherein In the above, ρ is the fluid density, v is the velocity field, σ is the Cauchy stress, f is the body force, µ is the dynamic viscosity, ε is the rate-of-strain tensor, p is the pressure, and I is the second-order identity tensor. Both ρ and µ are assumed constant, and the kinematic viscosity is defined as ν := µ/ρ. Given a divergence-free velocity field v 0 , the initial condition is given by v(·, 0) = v 0 (·), inΩ.
The boundary Γ can be partitioned into two non-overlapping subdivisions, that is, Γ = Γ g ∪ Γ h and ∅ = Γ g ∩ Γ h . The subscripts g and h indicate the Dirichlet and Neumann partitions. The unit outward normal vector to Γ is denoted as n. Given the Dirichlet values g and the boundary traction h, the initial-boundary value problem is to solve for v and p that satisfy (1), (2), (4), and

Spline Spaces on the Parametric Domain
We start by reviewing the construction of B-splines and NURBS basis functions. Given the polynomial degree p and the dimensionality of the B-spline space n, the knot vector can be represented by Ξ := {ξ 1 , ξ 2 · · · , ξ n+p+1 }, wherein 0 = ξ 1 ≤ ξ 2 ≤ · · · ≤ ξ n+p+1 = 1. The B-spline basis functions of degree p, denoted as N p i (ξ), for i = 1, · · · , n, can then be defined recursively from the knot vector using the Cox-de Boor recursion formula [14]. Given a set of weights {w 1 , w 2 , · · · , w n }, the NURBS basis functions of degree p can be defined as Importantly, the knots can also be represented with two vectors, one of the unique knots {ζ 1 , ζ 2 , · · · , ζ m } and another of the corresponding knot multiplicities {r 1 , r 2 , · · · , r m }. As is standard in the literature of computer-aided design, we consider open knot vectors in this work, meaning that r 1 = r m = p + 1. We further assume that r i ≤ p for i = 2, · · · , m − 1. Across any given knot ζ i , the B-spline basis functions have α i := p − r i continuous derivatives. The vector α := {α 1 , α 2 , · · · , α m−1 , α m } = {−1, α 2 , · · · , α m−1 , −1} is referred to as the regularity vector. A value of −1 for α i indicates discontinuity of the basis functions at ζ i . We introduce the function space R p α := span{R p i } n i=1 , where the notation R p α is used to indicate that α i = α for i = 2, · · · , m − 1, suggesting continuity C α for the spline function spaces. The construction of multivariate B-spline and NURBS basis functions follows a tensor-product manner. For l = 1, 2, · · · , d, given p l , n l , the knot vectors Ξ l = {ξ 1,l , ξ 2,l , · · · , ξ n l +p l +1,l }, and the weight vectors {w 1,l , w 2,l · · · , w n l ,l }, the univariate NURBS basis functions R p l i l ,l are well-defined. Consequently, the multivariate NURBS basis functions can be defined by exploiting the tensor product structure, , for i l = 1, 2, · · · , n l and l = 1, 2, . . . , d. The tensor product NURBS space is denoted as

Mixed Formulation
In this work, we always consider three-dimensional problems (i.e. d = 3). Two discrete function spacesV h andQ h can be defined on the parametric domainΩ = (0, 1) 3 aŝ Assuming the physical domain can be parametrized by a geometrical mapping ψ :Ω → Ω X , the discrete functions on the physical domain can be defined through the pull-back operations, This pair of elements can be viewed as a smooth generalization of the Taylor-Hood element. We may then define the trial solution spaces for the velocity and pressure as and the corresponding test function spaces are defined as The semi-discrete formulation can be stated as follows. for Here v h0 and p h0 are the L 2 projections of the initial data onto the finite dimensional trial solution spaces.

The Generalized-α Schemes Under Comparison
In this section, we present the two generalized-α schemes to be compared as time integration schemes for the semidiscrete formulation in (6) and (7). Let the time interval [0, T ] be divided into a set of N ts subintervals delimited by a discrete time vector {t n } Nts n=0 . The time step size is defined as ∆t n := t n+1 − t n . The discrete approximations to the velocity, its time derivative, and pressure at the time step t n are denoted as v n ,v n , and p n . Let N A and M B represent basis functions for the velocity and pressure spaces, respectively, and let e i be the Cartesian basis vector with i = 1, 2, 3. We may define the residual vectors as follows, With these residual definitions, we may introduce the two generalized-α schemes as follows.
Scheme-1 At time step t n , givenv n , v n , p n and the time step size ∆t n , findv n+1 , v n+1 , and p n+1 such that, Although the quantityṗ n+1 does not appear explicitly in the above formulation, we may still obtain a consistent definition asṗ n+1 := (p n+1 − p n ) /∆t n .
Scheme-2 At time step t n , givenv n , v n , p n , and the time step size ∆t n , findv n+1 , v n+1 , and p n+1 such that, In this scheme, givenṗ n ,ṗ n+1 is given bẏ The definitions of the above two schemes can be completed by assigning values to the parameters α m , α f , and γ. It has been demonstrated that, for linear problems, second-order accuracy, unconditionally stability, and optimal high frequency dissipation can be achieved via the parametrization is the spectral radius of the amplification matrix at the highest mode [16]. In this study, ∞ is fixed to be 0.5.

Remark 1.
In conventional CFD calculations, it is unnecessary to calculateṗ. In hemodynamic simulations, however, bothv andṗ can be used as inputs to reduced-order models of the upstream and downstream vasculature, which are commonly used as boundary conditions coupled to the three-dimensional domain [20]. We therefore examine the accuracy ofv andṗ in addition to v and p.

Numerical Examples
The parameters and results reported below are presented in the centimeter-gram-second units.
Consistent with the original design of the benchmark, the domain is a cube Ω = (−1, 1) 3 . The constants are fixed as a = π/4 and d = π/2, and the fluid density ρ and viscosity µ are fixed to be 1.0 and 0.1. Traction boundary conditions are enforced on all faces, and initial conditions are obtained from the exact solution. Prior to examination of the temporal accuracy, a spatial convergence study was first performed, and the code was verified to yield optimal convergence rates. In the following, we report the errors for a fixed mesh with 25 elements along each dimension, polynomial degree p = 4, and continuity α = 3. The problem is simulated up to T = 1.0 with various uniform time step sizes. The relative errors of the velocity, pressure, and their time derivatives in the L 2 -and H 1 -norms at time t = 1.0 for Scheme-1 and Scheme-2 are presented in Tables 1 and 2, respectively. Based on the numerical results, we make the following salient observations. First, the pressure converges linearly with respect to the time step size in Scheme-1 and quadratically in Scheme-2. Second, both schemes exhibit first-order temporal accuracy for the time derivative of pressureṗ h , yet Scheme-2 yields significantly smaller errors forṗ h . Third, the velocity errors are identical in the two schemes, signifying that the degraded accuracy for pressure does not affect the accuracy for velocity. This phenomenon may, however, be attributed to the use of inf-sup stable elements. We do not rule out the possibility for velocity errors to be polluted by the use of Scheme-1 in stabilized formulations.  Table 1: Temporal convergence rates for the Ethier-Steinman benchmark using Scheme-1.

Pulsatile Flow in a Rigid Pipe
In the second example, we utilize the Womersley solution to evaluate the two schemes for flows under more physiological settings. The Womersley solution describes axisymmetric, fully developed flow subject to a periodically oscillating pressure gradient in a rigid cylindrical pipe with circular cross section [24,25]. Here, we consider the z-axis to be oriented along the length of the pipe and express the pressure in the following Fourier series, where p ref is the reference pressure at z = 0, k 0 is the steady component of the pressure gradient, k n is the amplitude of the oscillatory component of the pressure gradient at the n-th Fourier mode, ι is the solution of the equation ι 2 = −1, ω := 2π/T p is the fundamental frequency of the pressure wave, and T p is the period of the pressure. Per the assumptions of axisymmetric and fully developed flow, the velocity is identically zero in the radial and circumferential directions and takes the following analytical form in the axial direction, wherein r := x 2 + y 2 , R is the radius of the pipe, J 0 is the zeroth-order Bessel function of the first kind, and α n := R nω/ν is the Womersley number for the n-th Fourier mode. The complex form of the solutions indicates the existence of two sets of real independent solutions. We use the real parts of (8) and (9)     benchmark solution. In this study, the pipe radius R is 0.3, and the pipe length is 1.0. The fluid density ρ and viscosity µ are fixed to be 1.0 and 0.04, respectively, and the period T p is set as 1.1. The fundamental frequency ω and the corresponding Womersley number α 1 are approximately 5.71 and 3.59, respectively. The reference pressure p ref is 0. We choose to use a single mode in the Fourier series to represent the oscillatory part of the pressure (i.e. N = 1), and the values of k 0 and k 1 are −21.0469 and −33.0102 + 42.9332ι. The parameters above are chosen to represent physiological flows in arteries. The circular cross section is exactly represented by NURBS, and the parametrization is based on quadratic basis functions, which can be found in Example 6.2 of [21]. Using k-refinement, the spatial mesh for analysis consists of 10 × 10 elements in the x-y plane and 16 elements along the z axis, with polynomial degree p = 4 and continuity α = 3. We apply the no-slip boundary condition on the wall and traction boundary conditions on both ends of the pipe. The analytical forms of the tractions as well as the initial conditions are obtained from the exact solution in (8) and (9). Simulations are performed with uniform time step sizes ∆t n = ∆t = 1.00 × 10 −1 , 5.00 × 10 −2 , 2.50 × 10 −2 , 1.25 × 10 −2 , 5.00 × 10 −3 , 2.50 × 10 −3 , and 1.25 × 10 −3 . Similar to the previous example, we observed that the velocity errors in all norms are identical for the two schemes.
The velocity profiles at various time instances are illustrated in Figure 1. The relative errors of p h andṗ h in the L 2 -and H 1 -norms at time t = 0.8 are plotted in Figure 2. We observe that the pressure converges linearly in Scheme-1 and quadratically in Scheme-2 in both norms. Importantly, when ∆t = 1.25 × 10 −3 , the pressure errors in Scheme-2 are more than two orders of magnitude smaller than those in Scheme-1. Finally, while both schemes exhibit first-order temporal accuracy forṗ h , we again find thatṗ h calculated from Scheme-2 is more accurate.

Concluding Remarks
In this work, we implemented and compared two generalized-α schemes for the incompressible Navier-Stokes equations using inf-sup stable higher-order NURBS elements for spatial discretization. In the widely adopted scheme that is used in numerous existing CFD and FSI implementations, we have observed only first-order accuracy for pressure. While we have not observed degraded accuracy for velocity in these schemes, we cannot rule out this possibility for other spatial discretization methods, such as the stabilized method. By evaluating the pressure at the intermediate time step in the temporal scheme, second-order temporal accuracy for pressure is recovered. Moreover, the time derivative of the pressure is computed much more accurately. Considering pressure is one of the most important quantities for CFD and FSI, we recommend the use of Scheme-2 as the generalized-α scheme of choice for integrating the incompressible Navier-Stokes equations.


Special Issue: Accident Analysis and Prevention: Experimental and Numerical Approaches

Accidents are a daily occurrence in our lives, in many different activities and scenarios, from sports to traffic, from home to work environments, from non-intentional to criminal offences [...]

Introduction
Accidents are a daily occurrence in our lives, in many different activities and scenarios, from sports to traffic, from home to work environments, from non-intentional to criminal offences. The usual outcome is some kind of injury, which can range from minor, soft injuries to severe, lethal injuries.
Numerical and experimental methods have been continuously improved in order to provide better analysis of accident scenarios, evaluate their outcomes, and provide effective frameworks for their prevention.
This publication encloses a set of contributions on topics that include studies of human and environmental aspects prior to accidents; the type and severity of accidents; the design and implementation of passive and active protective devices; the biomechanics of impact and resulting injuries; and statistics and decision-making tools. The book highlights the importance of numerical and experimental methods, which can serve as a powerful tool to study and enhance safety.

Special Issue Papers
The topics just referred to were addressed in several chapter of the book. Regarding road and traffic aspects, Yim et al. discuss the "Development of Navigator Behavior Models for Evaluation of Collision Avoidance Behavior in the Collision-Prone Navigation Environment" [1] whereas Ptak addressed a "Method to Assess and Enhance Vulnerable Road User Safety During Impact Loading" [2] using numerical modeling and proposing some countermeasures for Vulnerable Road Users.
The role of numerical modeling was also addressed by Tierney and Simms, regarding the "Predictive Capacity of the MADYMO Multibody Human Body Model Applied to Head Kinematics During Rugby Union Tackles" [3].
Occupational and work-related accidents were addressed by Shafique and Rafiq, "An Overview of Construction Occupational Accidents in the Hong Kong: A Recent Trend and Future Perspectives" [4], whereas Kakhki and co-workers discussed the "Use of Logistic Regression to Identify Factors Influencing the Post-Incident State of Occupational Injuries in Agribusiness Operations" [5]. Also on the civil construction domain, Derlukiewicz discussed the "Application of a Design and Construction Method Based on a Study of User Needs In The Prevention of Accidents Involving Operators of Demolition Robots" [6].
Head protection devices to save lives deserved particular attention as demonstrated in Jamroziak et al., "The Ballistic Head Protection in the Light of Injury Criteria on the Example of the Wz.93 Model Combat Helmet" [7] and also by Fernandes et al. "Helmet Design Based on the Optimization of Biocomposite Energy Absorbing Liners Under Multi-Impact Loading" [8]. Sławiński et al. outlined the problem regarding the development of soldiers' injuries, caused as a result of strong effects of pulse forces, inside armored vehicles [9].
In the world of sports, this book presents the contribution "Mortality of NBA players: Risk Factors and Comparison with the General US Population", by Martinez et al. [10].
Finally, because traffic accidents may also happen in other environments besides streets and highways, Youn and co-workers contributed with the work "Analysis of Lookout Activity in a Simulated Environment to Investigate Maritime Accidents Caused by Human Error" [11].
It becomes evident that the field of traffic safety is huge, and with plenty of room for continuous development. The present book sheds some light on some of its subtopics of relevance.


Enhanced fuzzy finite state machine for human activity modelling and recognition

A challenging key aspect of modelling and recognising human activity is to design a model that can deal with the uncertainty in human behaviour. Several machine learning and deep learning techniques are employed to model the Activity of Daily Living (ADL) representing the human activity. This paper proposes an enhanced Fuzzy Finite State Machine (FFSM) model by combining the classical FFSM with Long Short-Term Memory (LSTM) neural network and Convolutional Neural Network (CNN). The learning capability in the LSTM and CNN allows the system to learn the relationship in the temporal human activity data and to identify the parameters of the rule-based system as building blocks of the FFSM through time steps in the learning mode. The learned parameters are then used for generating the fuzzy rules that govern the transitions between the system’s states representing activities. The proposed enhanced FFSMs were tested and evaluated using two different datasets; a real dataset collected by our research group and a public dataset collected from CASAS smart home project. Using LSTM-FFSM, the experimental results achieved 95.7% and 97.6% for the first dataset and the second dataset, respectively. Once CNN-FFSM was applied to both datasets, the obtained results were 94.2% and 99.3% , respectively.

Introduction
Monitoring and recognising human activities within a home environment are investigated in order to support the independent living of older adults in Ambient Intelligence (AmI) environments (Chen et al. 2012;Medina-Quero et al. 2018). Several techniques are used to gather the information that represents the Activity of Daily Living (ADL) from a real environment for the monitored user (Cook et al. 2013;Langensiepen et al. 2014). This information is commonly gathered from the signals that are collected from ambient sensors such as door entry sensors, movement and occupancy sensors etc., (Hassan et al. 2018). The information can also be extracted based on vision sensors such as cameras that capture images or video streams (Cook et al. 2013), although, for privacy concerns, recent attention has predominantly focused on data collected by ambient sensors, which are more acceptable to users (Aicha et al. 2017). The gathered information is then processed and analysed in a useful format to be used in many different applications, including anomaly detection in daily human activities, energy consumption optimisation, addressing health and safety concerns, leading to an improved level of comfort and quality of life (Langensiepen et al. 2014;Lotfi et al. 2012).
One of the promising techniques to model dynamic processes when data changes over time is the Finite State Machine (FSM) (Mohmed et al. 2018b;Alvarez-Alvarez et al. 2012). The FSM contains several states representing different actions and the mechanism of transitions between them. Many researchers have considered using the FSM to model and represent human activities. Since humans behaviour is not restricted to a single state at any time and there are uncertainties associated with each state, it is reasonable to consider some degree of fuzziness within the FSM, thereby creating a more powerful tool to model dynamic processes that may change over time (Langensiepen et al. 2014;Mohmed et al. 2018a;Medina-Quero et al. 2018). The classical version of FSM is enhanced by incorporating fuzzy states/transitions leading to Fuzzy Finite State Machine (FFSM). Both inputs and outputs are treated as fuzzy sets instead of being treated as crisp values. This allows the system to handle and process the input information with a degree of belonging, which often provides more flexibility and human comprehensibility (Unal and Khan 1994). The FFSM is one of the most suitable technique to deal with a large amount of uncertain data gathered from low-level sensory devices in AmI environments. In this case, the system can assign a degree of truth to the occurrence of each activity. The transitions between the system's states in the FFSM are triggered by fuzzy values rather than crisp values used in the classical FSM. This provides a realistic model supported by a fuzzy reasoning mechanism, represented by a degree of truth related to each state transition. Therefore, more than one state can be in an active mode at any time based on the membership values of each state (Langensiepen et al. 2014;Alvarez-Alvarez et al. 2011;Sridhar et al. 2019).
By nature, several activities can be undertaken by a single user at the same time (Cook et al. 2013). For example, people can watch TV while they are eating their meal. In this particular scenario, it is not necessary to know which activity started first. However, it is essential to know the degree of involvement in each activity at that time. That means the existence of simultaneous activities when an activity (e.g., eating) starts while the other activity is already started (e.g., watching TV). A specialised approach is required to recognise these non-sequential behaviours. One of the most promising technique to deal with such uncertainties that associated with human activities is using fuzzy sets. Hence, the classical FSM is integrated with a fuzzy logic system to address these uncertainties. This paper is an extension of the authors' research work in developing an FFSM used for modelling and recognising human activity. In this work, the FFSM is introduced as a means of defining daily human activities and the transition between the states (here, the activities). There are many unknown parameters in the FFSM which needs to be identified in order to represent a model for the ADL. The aim of the research reported here is to identify the parameters to represent the real activities of a human subject in an AmI environment accurately. The research presented in this paper addresses only the challenges in modelling and recognising a single-occupancy at a real-home environment based on a dataset collected from ambient sensory devices. Anther research exploring the domain of modelling and recognising human activities within multi-occupancy environments are currently ongoing with other researchers in our research group. The research reported in this paper has made the following contributions:

Related work
Most of the research related to human activity recognition is carried out using statistical techniques including Support Vector Machine (SVM) (Khemchandani and Sharma 2017;Anguita et al. 2012) and Finite State Machine (FSM) (Trinh et al. 2011) are used to find the relationship between the real action (activity) and the temporal data gathered from sensors. The ultimate goal of these techniques is to identify the activity of the user. Several graphical techniques are introduced to recognise and model human activities, for example, Hidden Markov Model (HMM) can represent random variables, actions and temporal variation within the collected data (Chung and Liu 2008;Kong and Fu 2018). Relatively new research in Aicha et al. (2017) and Malasinghe et al. (2019) have presented a new model based on the Markov Modulated Poisson Process (MMPP) which promises to come up with a model to represent multi-visitor recognition with more accuracy. The only issue with this approach is the difficulty in processing a large amount of low-level data such as the data gathered from ambient sensory devices. In Langensiepen et al. (2014), the authors used FSM for locating and modelling the activity of a single user in an apartment. The FSM is a powerful technique for modelling dynamic events, that is, the events that change over time, such as human activity. The FSM model is enhanced by being integrated with a fuzzy system, which is used to increase the efficiency of the FSM by proposing the Fuzzy Finite-State Machine (FFSM), where transitions between the states are triggered by the sense of fuzziness instead of using crisp values. This has the advantage of smooth modelling and reasoning with a degree of truth, which proves to be more accurate. Thus, the system can be in more than one state at a time, based on the truth degree for each state (Alvarez-Alvarez et al. 2011;Langensiepen et al. 2014). The main advantage of using the fuzzy state is that it can deal with uncertain data and can be represented in more than one state at the same time as membership degrees.
Computational intelligence techniques are also widely used to recognise and model human activities, as an alternative or in combination with other statistical methods. Neural Networks (NNs) are used to deal with and process pattern recognition based on numerical data that is gathered from sensors in an AmI environment (Benmansour et al. 2017;Subramanian and Suresh 2012). Recurrent Neural Networks (RNNs) are proven to be a powerful tool to solve the difficulties of the temporal relationships of inputs and outputs at different time steps (Medina-Quero et al. 2018;Tran et al. 2018). In Medina-Quero et al. (2018), authors created fuzzy temporal windows for the collated binary data representing the human activities, and then applied them to an ensemble classifier based on LSTM neural networks. The LSTM is used in Jenckel et al. (2018) for annotating historical documents, where authors are used fuzzy ground truth to represent the input data to provide all possible annotations for each input variable, instead of just one. The LSTM neural networks prove their ability to be a good approach to model sequential forms of data such as human activity data (Yulita et al. 2017a). Moreover, the LSTM can save past information by looping it inside its architecture, which reuses the information from the previously learned iteration. The main purpose of using the LSTM is to reduce the risk of vanishing gradients in the sequential temporal data. In some of the recent works in human activity recognition Arifoglu and Bouchachia (2019); Gochoo et al. (2019), researchers focused on employing the CNN with binary datasets to recognise human activities and to detect any abnormal activities in the users' behavioural pattern based on a trained CNN model.
A widely used method for feature representation is the fuzzy feature representation approach. In Deng et al. (2017), the authors proposed a fuzzy computational approach to extract features from one-dimensional input vectors. They employed a deep neural network with the extracted features for classifying the given data. A fuzzy temporal windows approach is proposed in Medina-Quero et al. (2018);Yulita et al. (2017a) to define temporal-sequence representations to aggregate information from binary sensors for real-time recognition of human activities. The methods in Deng et al. (2017); Medina-Quero et al. (2018) have been successful in capturing features that improved the performance of the classification tasks for human activity recognition.
Based on the literature review conducted for this research, the fuzzy feature representation approach is used to fuzzify the data representing human activities. Two different deep learning techniques, namely LSTM and CNN are integrated with the FFSM for enhancing the learning process of the parameters that are used to generate the fuzzy rules governing the states' transitions.

Methodologies
In this section, the Fuzzy Finite State Machine (FFSM) incorporating fuzzy feature representation is introduced initially. Then, two proposed, enhanced FFSM approaches are introduced. Fig. 1 illustrates the schematic diagram of the proposed FFSM. This consists of three different stages; data collection process, fuzzy feature representation, and the fuzzy finite state machine model. In the data collection stage, the data from sensors in an AmI environment representing the ADL is collected. The fuzzy feature representation stage is designed to transform the data into fuzzy features to be used as inputs to the proposed FFSM model. In the third stage, the proposed FFSM model will generate the fuzzy rules employing the capabilities of learning algorithms in LSTM and CNN to representing the states' transitions.

Fuzzy feature representation
Fuzzy feature representation approach is designed to convert the collected information into their relevant membership degrees (Yulita et al. 2017b). The resulting membership degrees are taken as features to be used as inputs to train the proposed model. Therefore, fuzzy feature representation is applied to determine the number of Membership Functions (MFs) representing the input data as membership degrees. By replacing each value in the input data with their corresponding degree of memberships; thus, each value in the input data is represented as fuzzified values obtained for each MF as follows: X uj is the fuzzified set of the input variable u j . P is the last value in the input variable u j . A is the degree of MF associated with each linguistic label. The Fuzzy feature representation process can be summarised as follows: j = 1, ..., P 1. Apply the input data to the fuzzifier algorithm consists of M MFs that are represented with the linguistic labels. 2. Define the degree of fuzziness A that corresponds to each MF. 3. Determine the maximum degree of fuzziness for the variable u j in each iteration. 4. Create a matrix q = r × z to store the degree of MFs for each variable u j . Where r is the total number of activ-ity instances in the input data u j , and z is the number of fuzzified values for the variable u j . 5. Update the matrix q after each iteration with the new fuzzified values that corresponding to the next input value.
T h e f i n a l s e t o f t h e f u z z i f i e d fe a t u r e s , will be used as inputs to train the proposed model for learning the relations between the inputs and output data, as it is explained in the next sections. The process of fuzzy feature representation is elaborated in Sect. 5 when modelling and recognising human activity datasets are presented.

Fuzzy finite state machine
Fuzzy Finite State Machine (FFSM) is an extended version of the classical FSM. The FSM can be presented as a model made of two or more states; each state represents one event from a sequence of events in a dynamic process (Mohmed et al. 2018b). Only one single state of this model can be active at a time. The model is moved from one state to another by triggering crisp values. In human activity recognition and modelling, a user may be associated with multiple states. This would require to be quantified with a degree of belonging (degree of fuzziness). Once the fuzziness aspect is added to the state transitions in the classical FSM, the transitions are not triggered based on crisp values, but using fuzzy variables (Langensiepen et al. 2014;Alvarez-Alvarez et al. 2012;Unal and Khan 1994). This implies that the current activated state of the model is not necessarily one state, but it could be more than one state at any given time with belonging degrees (Unal and Khan 1994).
In an FFSM, the system's states are represented as a set of linguistic variables where N is the number of states. For a non-sequential system at a time t, the system's states are represented as a state vector S(t). When the system evolves in time, the next state is represented as a vector S(t + 1).
In general, as in Alvarez-Alvarez et al. (2012); Langensiepen et al. (2014), the FFSM is defined as a tuple of param- is presenting a vector identifying the system's states at time t and N is the number of states. Each individual state at time t is s i (t);i = 1...N is a numerical value that is in fact the membership grade (between 0 and 1) given to each linguistic variable s i (t) within the set of FFSM's states is the input vector at time t representing the associated value to the linguistic variables that are generally obtained after a fuzzification process for the input data. P are the number of input variables. This input data could be a sensors' data, a combination of different signals, or any other calculation to numerical data. The fuzzification process that is designed based on experts' view to translating the numerical input values to a set of membership grades given to each linguistic label that defines all the acceptable values in the input vector. The labels that are associ-ated with the input u j (t) is represented as where M is the number of the associated linguistic labels (Alvarez-Alvarez et al. 2011). • Transition Function, f is the state transition function that is mainly used to calculate the next state vector S(t + 1) , at each time instant t. The transition function f controls the allowed transitions between the defined system's states. Also, it is implemented as a set of fuzzy rules.
There are different ways to define the rules, e.g., using the human expert knowledge (Mohmed et al. 2019) or learning from the numerical input-output data by applying machine learning algorithms such as Artificial Neural Network (ANN) and Genetic Algorithm (GA) (Bombardier and Schmitt 2010; Wang et al. 2012;Wang and Mendel 1992). A combination of these approaches can also be implemented to have one framework containing the rules that are generated by learning from the numerical data and those assigned by the human experts' knowledge (Wang and Mendel 1992). The states' transition mechanism between two exemplary states s m and s n in the FFSM is illustrated in Fig. 2. Considering the complexity of modelling a large scale dataset, it may be impossible to analytically identify the functions f and g. This complexity will be even harder when it is used for timeinvariant models (Langensiepen et al. 2014;Alvarez-Alvarez et al. 2012). Therefore, a rule R mn is used to establish the relationship between states s m and s n . These states' transitions can be expressed as a general fuzzy rule format (Unal and Khan 1994), as follows: where the fuzzy rule has the following parts: (2) -The Antecedent Part: is a combination of two terms; the first term, (S(t) is s m ) is used to determine if the state s m is an activated state in time instant t. Therefore, the system can change from state s m to state s n or remains in state s m , only if m = n , the second term of the antecedent part is H mn which represents all constraints imposed on the input variables that are required to either remain in state s m (when, m = n ) or change to state s n , e.g., about the transition function elements and how they can be enhanced by integrating them with different learning techniques based on fuzzy rules are explained in the following sections.

Enhanced fuzzy finite state machine
Defining the relationship between states of a system based on fuzzy rules comes with its shortcomings. An FFSM can represent the system's states and the transition between them, assuming that all parameters are known. In this research, the aim is to enhance the performance of the FFSM by identifying optimum values for parameters of fuzzy rules. In our previous publication (Mohmed et al. 2018b), the FFSM was integrated with standard NNs to learn and adapt the parameters based so the FFSM model could represent the states' transitions and the output of each state accurately. The work presented in this paper improves the performance of FFSM even further by integrating it with Long Short-Term Memory and Convolutional Neural Networks leading to two new models referred to as Long Short-Term Memory Fuzzy Finite State Machine (LSTM-FFSM) and Convolutional Fuzzy Finite State Machine (CNN-FFSM). The details of both enhanced FFSM is provided in the consequent sections.

Long short-term memory-fuzzy finite state machine
To improve the learning capability of the FFSM, an integration of Long Short-Term Memory and Fuzzy Finite State Machine is proposed. A brief explanation about the LSTM is provided first, and then the enhanced LSTM-FFSM is introduced. The LSTM is a particular kind of RNNs designed to solve vanishing and gradients problems in the standard RNNs (Yulita et al. 2017a;Jenckel et al. 2018). The LSTM is a powerful tool for learning the sequential tasks that are represented as temporal data. It can also remember previous information for long periods. These characteristics make LSTM especially useful for temporal data classification problems (Medina-Quero et al. 2018). The LSTM cell consists of three gating mechanisms to provide the ability to remove or add information to the memory cell. These three gates are used to regulate the impact of the input through an input gate, the previous cell state through a forget gate and an output through the output gate. The essential gate in the LSTM cell is the forget gate as it decides if the information is going to be remembered or be forgotten from the previous states.
The LSTM-FFSM is an enhancement version of FFSM, allowing the system to learn the temporal relations in the data by storing the information through the time-sequential steps. The learned relations are then used to formulate the fuzzy rules that control the transitions between the system's states and identify the current activated states at any given time t. In this approach, the experts are also allowed to introduce their knowledge over the whole system by defining the following aspects: • Defining the system states. • Specifying the general structure of the fuzzy rules that represent the state transitions. • Specifying the number of linguistic labels that are associated with each input variable.
In a typical FFSM, a rule to identify the transition between state m and state n is presented as R mn in Sect. 3.2. This demonstrates the relation between the system's current state S(t) and the input variables that are represented as H mn to identify the next state S(t + 1) . Each input variable involved in the term H mn is fuzzified in order to convert the numerical data into their relevant membership degrees as it is explained in Sect. 3.1. These membership degrees for each input X uj are represented as where M is the number of associated linguistic labels that represented as membership degrees A M uj . At this point, LSTM is employed to learn the temporal relations in the data by storing the previous information in a time-sequential manner. Thus the term H mn will be represented as: where Z is current output of the LSTM at time t and M is the number of membership degrees A that are associated with the input uj. Based on the explanation introduced in the proceeding sections, LSTM-FFSM is proposed to generate the fuzzy rules representing the transition based on learning the relations in the sequential temporal data. Therefore, the term H mn is computed based on the proceeding explanation, and then the obtained parameters are used to demonstrate the fuzzy rule R mn that governs the transition between state m and state n.

Convolutional-fuzzy finite state machine
The integration of CNN with FFSM is also proposed for enhancing the learning capabilities of the FFSM. This is achieved by selecting the most effective features to learn the relationship between the inputs and outputs data. In this section, a brief explanation about CNN is provided first, and then the enhanced Convolutional-Fuzzy Finite State Machine (CNN-FFSM) is produced (Flagel et al. 2018).
(6) H mn = X uj (t) + Z t Generally, the input data to a CNN is a matrix c in dimensions of h × w × d , where h, w and d are the height, width and the number of channels in the input matrix c (Arifoglu and Bouchachia 2019; Gochoo et al. 2019). When the input window has only one class, the number of channel d is 1.
The common use of CNN architecture has two conventional layers or more and one fully-connected layer. Each convolutional layer contains multiple feature filters to optimise the values during the training phase. Each convolutional layer is followed by a max-pooling layer that has a window in a certain size to ensure the outputs from each conventional layer are smaller than the inputs. Rectified Linear Unit (ReLU) is added after each convolutional layer that operates as an activation function. The used fully-connected layer in this architecture is a traditional Multi-Layer Perceptron (MLP) that operates a softmax activation function for the output layer. By using the softmax activation function for the output layer, the CNN classifier model will be able to classify the input features into various classes based on the learned relations during the training stage.
In case of expecting highly complex input data, the CNN architecture can contain more than one pair of the convolutional and max-pooling layers with different sizes of border filters to process such data (Arifoglu and Bouchachia 2019). Also, the top convolutional layer is followed by one or more fully-connected layers for the final classification purpose. During the training phase, the standard forward and backward propagation algorithms are used to estimate the values of the CNN parameters. The selected features are mapped by the convolutional operator (Arifoglu and Bouchachia 2019) as follows: where denotes the convolutional operator, is the convolutional filter for the -th input, V t is the generated -th output feature map which is achieved by selecting the most effective features over the non-overlapping pooling regions from the input data x and d denotes the bias.
Based on the provided explanation about the CNN in this section and the FFSM in the previous section, the CNN-FFSM may be considered as an enhancement version of FFSM by employing CNN that is allowing the system to select the most effective features from the input dataset and then learn the temporal relations from the selected features by storing the information through the time-sequential steps. The learned relations are used for formulating the fuzzy rules that are used to control the system's state transitions and identify the current activated states at any given time t. In this approach, the experts are also allowed to introduce their knowledge over the whole system. Defining the (7) system's states, the general structure of the fuzzy rules, and the number of associated linguistic labels where each input variable are the aspects that are specified by experts. As mentioned earlier, the rule R mn used to control the transition between state m and n involves the relation between the system's current state S(t) and the input variables that are represented as H mn . The final value obtained from this calculation is used to identify the next state S(t + 1) . As each input variable involved in the term H mn is fuzzified to convert the numerical data into their relevant membership degrees A M uj . At this stage, CNN is employed to learn the relations in the inputs (features) and outputs (labels) data by selecting and mapping the most effective features. Therefore, the term H mn will be represented as: where V t is the generated -th output feature map using CNN at time t and X uj (t M is the number of membership degrees A that are associated with the input uj. Based on that, CNN is used as state-of-the-art to select the most effective features from the input dataset and learn the relations between the inputs (selected features) and the outputs (labels). The learned parameters are used essentially in this work to generate the fuzzy rules R mn representing the transition between the system's states in the proposed CNN-FFSM.
The proposed LSTM-FFSM and CNN-FFSM are employed to learn the unknown parameters for generating the fuzzy rules representing the transition between the FFSM's states. The next section introduces experiments with the proposed approaches, which integrates the learning abilities of the LSTM and CNN by selecting and mapping the (8) H mn = X uj (t) + V t most effective features in the temporal dataset representing daily human activities.

Experimental setup
To evaluate the performance of the proposed approached, experimental works are conducted where Activity of Daily Living (ADL) for a single user is used for modelling and recognising the user's activities. The experimental setup is presented below and all results are presented in the next section.

Datasets
Two datasets referred to as Dataset A and Dataset B are used to evaluate the proposed approaches for human activity modelling and recognition. Details of these datasets are provided below.
Dataset A: The dataset was collected by our research group from a real home environment representing the ADL of a single user. The dataset was collected at the Smart Home facilities within Nottingham Trent University. A floor plan of the house is shown in Fig. 3. A list of the used sensors for collecting this dataset is listed in Table 1. There are seven activities, which are Sleeping, Toilet, Kitchen, Dining-room, Living-room, Garden, and Leaving. Dataset B: This is a publicly available dataset known as Aruba representing ADL for a single user was collected using the Centre for Advanced Studies in Adaptive System (CASAS) at Washington State University (Cook 2010). They used motion, door, and temperature sensors. However, as this work focuses on the ADL, the temperature sensors are excluded, and the other 34 sensors (3 door sensors and 31 Fig. 3 Floor plan layout and location of the installed sensors used for data collection in dataset A motion sensors) are used. A single elderly woman lived in the Aruba testbed, and she had received regular visits from her children and grandchildren during the data collection period. The final dataset is saved as a list of sensor-ID, timestamp, and sensor status.
In this dataset, there are 11 activities performed by the women who was living in the apartment and the data were collected over a period of 224 days. These activities are Sleeping (401 instances), Meal Preparation (1606 instances), Relaxing (2910 instances), Bed-to-toilet (157 instances), Leaving home (431 instances), Entering home (431 instances), Housekeeping (33 instances), Eating (257 instances), Washing dishes (65 instances), Work (171 instances) and Resperate (6 instances). The Resperate activity is excluded from the dataset as it has only 6 instances.

Feature fuzzification
Extracting the numerical information from acquired raw sensor data is crucial to any learning system as raw data does not provide adequate information that can be used as inputs to the model. The collected data was gathered from low-level ambient sensory devices; it will be saved to a database as time-stamped binary data. This gathered raw data would be represented and interpreted using the ontology data representation approach in Wongpatikaseree et al. (2012) to convert it into an occupancy data for chunking the activity-windows as it is shown in Fig. 4. To fuzzify the activity data for each activity-window start time, end time, duration, an activity count and activity sequential order are extracted. Therefore, the activity data are extracted for each activity window and represented as a matrix where rows are the length of the activity window and columns are the number of recorded information from the sensors in the window.
The extracted information from each activity-window is mapped into a numerical activity data representing the input variables U(t) = [u 1 (t), … , u j (t), … , u P (t)] . An overall framework of the used approach for representing the activity data as fuzzy features is illustrated in Fig. 5. Each value in the input variable u j is represented with the relevant membership values to each fuzzy set. The final set of the fuzzified features X uj = [ A 1 uj , A 2 uj , … , A M uj ] , will be used as inputs to train the proposed models for modelling and recognising the activities, as it is explained in the next sections.

System definition
The collected datasets represent 7 and 11 different activities in dataset A and dataset B, respectively. Each activity is represented as one state in the FFSM model. These states are defined based on the experts' knowledge. This is easily  Fig. 4 An illustration of activity windows for 1-day activities represented using the proposed state diagram illustrated in Fig. 6. These states in datasets A and B are defined as follows:

States representing activities in dataset A
States representing the dataset A are as follows: • s 1 ∶ The sleeping state represents the sleeping activity, either night sleeping or daytime napping. • s 2 ∶ The toilet state represents the time when the user is using the toilet. • s 3 ∶ The kitchen state represents when the user is using the kitchen for preparing food or cleaning, e.g., dishwashing. • s 4 ∶ The dining state, which usually comes after the kitchen state, represents the time when the user is in the dining room to eat the prepared meal. • s 5 ∶ The living room state represents the time spent in the living room for either relaxing or watching TV. • s 6 ∶ The leaving home state represents when the user is leaving home through the front door. • s 6.1 ∶ The garden state. This state is part of the leaving state S 6 , which represents the time when the user is leaving to go to the garden through the back door.

States representing activities in dataset B
States representing the dataset B are as follows: • s 1 ∶ Sleeping states to represent the sleeping activities.
• s 2 ∶ Bed-to-Toilet state to represent the times of using the toilet within in the sleeping time. • s 3.1 ∶ Meal preparation state to represent the event of preparing food. This state is the first part of the kitchen state. • s 3.2 ∶ Washing dishes state to represent the event of washing dishes in the kitchen area. This state is the second part of the kitchen state. • s 4.1 ∶ Eating state to represent the time when the user at the dining room. This state is usually activated after the Meal preparation state. • s 5.1 ∶ Relaxing state to represent the time spent in the living room. • s 6 ∶ Leaving state to represent the time when the user leaves the house. As the house has three different doors, this state will be activated when any of these doors are used. • s 7 ∶ Entering home state to represent the time when the user comes back home. • s 8 ∶ Housekeeping state to represent cleaning work, e.g., hoovering the carpet. • s 9 ∶ Office-work state to represent the event of doing some homework in the office room.
Once the system's states are created, the activity data is extracted as numerical values for each activity-window. Five different numerical values are used in this experiment, representing the start time u 1 , end time u 2 , activity duration u 3 , activity count u 4 and activity sequential order u 5 . These extracted numerical values are then fuzzified using Gaussian MFs. Five different MF degrees are used to convert each value in the start u 1 time, end time u 2 and duration u 3 variables into their relevant membership degrees as it is illustrated in Fig. 5. Therefore, every single value from these variable is represented with the relevant number of belonging degrees to each MF. The linguistic labels associated with each input are represented as MFs. These MFs are described as follows: where X U is the input vector of fuzzified variables {X u1 , X u2 , X u3 } to the system at time t. The linguistic labels that are associated with the MFs are explained as: The other two variables representing the activity data (activity count u 4 and activity sequential order u 5 ) will not be fuzzified with the other activity data. They will be normalised and then added to the fuzzy represented features before the entire set of input data X U (t) is fed into the proposed models. A set of fuzzy rules is required to control the transition between the system's states. In the standard FFSM, these rules are defined based on the experts' knowledge only. In this contribution, as the generated data is temporal data representing sequential order events, LSTM and CNN are employed to learn the relations in the data through the time steps. The learned relations are used to generate fuzzy rules in the system. The final output for this model, Y(t), is represented as the degree of belonging to each state in the system.

Experimental results
The results obtained from the conducted experiments are presented here. As humans behave with some unpredictability and uncertainty in their environment, datasets representing the human activities are usually imbalanced, where some activities appear more dominant than the other activities.
In that case, if the dominant activities are identified with a high degree of accuracy, the performance over the whole system will be high even if the other activities are not well identified. Therefore, each activity will be evaluated separately, and then the performance over the whole system will be calculated. Both proposed models, LSTM-FFSM and CNN-FFSM, are tested and evaluated using the two earlier mentioned datasets A and B. The confusion matrix in Figs. 7 and 8 shows the recall (known as sensitivity) and precision scores obtained using the proposed LSTM-FFSM and CNN-FFSM models for each activity. As well as the accuracy over the whole models. Fig. 7 shows the obtained results when the proposed   Fig. 7a, b respectively.
The results based on the application of the proposed LSTM-FFSM and CNN-FFSM models to dataset B are shown in Fig. 8a, b, respectively. As it can be seen from these figures, CNN-FFSM model is more efficient when it is applied to a larger dataset containing confusion activities such as those activities that could occur at the same place (e.g., Meal Preparation activity and Washing Dishes activity), both of them undertaking at the kitchen. In Fig. 8b, nine out of ten activities, including in dataset B, are recognised with 100% scores of precision.
The information given in the confusion matrix is explained as follows: -The rows represent the output activities, and columns represent the target activities. The expressions that are used to calculate accuracy, precision and recall for each activity are given below: where TP i , TN i , FN i and FP i are the number of true positives, true negatives, false negatives and false positives of i th activity respectively. N is the number of the values TP i + TN i + FP i + FN i for i th activity. C is the activity of which its recall, precision and accuracy are calculated.
Considering the interpretability point of view, the most commonly used approaches for modelling and recognising human activities are the approaches based on mathematical, e.g., NNs and SVM. These models are well known as blackbox approaches because of the complexity of understanding their underlying calculations and concepts. This complexity will be more challenging when a large number of input and output variables are expected. As well as designing a model only based on the linguistic information assigned by human experts is not enough for a successful and robust human activities modelling and recognition model. Therefore, the advantages of integrating the experts' knowledge with the learning capabilities in LSTM and CNN can be integrated into the proposed LSTM-FFSM and CNN-FFSM models for generating a successful and robust model that can be used for modelling and recognising human activities.
The obtained results are compared with some previous works, such as the research presented in (Rashidi et al. 2010). They have used a dataset that was collected using ambient sensory devices to discover 5 different activities; Telephone use, Hand washing, Meal preparation, Eating, and Cleaning. A new mining method, called Discontinuous Varied-Order Sequential Miner (DVSM), is used in this research with the collected dataset to find frequent patterns that may be discontinuous and might have variability in the ordering of this activities. The achieved results based on the DVSM is 77.3%. In a recent publication for recognition of interleaved human activities, researchers have proposed a new human activity model containing three phases, namely Preprocessing, Discovery Method for Varying Patterns (DMVP) and Predictive Modelling (Raeiszadeh et al. 2019). The first phase is used to convert the collected raw sensor data into event sequences, which are then fed to DMVP in the second phase to discover frequent activities that naturally happen during the normal daily routine, and then a classification model is applied to predict the activities in the third phase. The achieved results from this approach is 87.94% once it is evaluated with the CASAS dataset.

Conclusion
The work presented in this paper has proposed two new methods for improving modelling and recognising human activities using data gathered from low-level sensory devices. Considering the results obtained from the conducted experiments, it can be concluded that the LSTM-FFSM and CNN-FFSM models exhibit a high score for accuracy, recall, and precision when its performance is tested for each activity separately. Also, the overall activity recognition performance, when it is over the whole system, demonstrates the effectiveness of the proposed approaches.
The CNN-FFSM model shows more robust and reliable performance once applied to a larger dataset (e.g., dataset B) representing ten activities over 240 days. In particular, when this dataset contains some activities that could be happening at the same place (such as Washing Dishes activity and Meal Preparation activity in the kitchen). In real-life scenarios, it is hard to know which activity is the current activity based on the data collected from the PIR sensory devices. Thus using a fuzzy feature representation approach with CNN-FFSM will be used to deal with such cases as it can detect the changes in the fuzzy feature patterns. The essential feature of the proposed approach is that it integrates the available expert's knowledge with the learned information from the deep learning techniques. The LSTM-FFSM has shown better performance for a simple scenario once it is applied to a short period dataset (e.g., dataset A). The CNN-FFSM achieved more accurate results to detect the ADL activities for a longer period dataset (e.g., dataset B). Besides, it can be seen how the proposed models can follow the proper sequence of states with the correct state activation degree.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creat iveco mmons .org/licen ses/by/4.0/.


extfieldsofstudy:
Computer Science
Mathematics

text:
An Algorithm for Consensus Trees

We consider the tree consensus problem, an important problem in bioinformatics. Given a rooted tree $t$ and another tree $T$, one would like to incorporate compatible information from $T$ to $t$. This problem is a subproblem in the tree refinement problem called the RF-Optimal Tree Refinement Problem defined by in Christensen, Molloy, Vachaspati and Warnow [WABI'19] who employ the greedy algorithm by Gawrychowski, Landau, Sung, and Weimann [ICALP'18] that runs in time $O(n^{1.5}\log n)$. We give a faster algorithm for this problem that runs in time $O(n\log n)$. Our key ingredient is a bipartition compatibility criteria based on amortized-time leaf counters. While this is an improvement, the fastest solution is an algorithm by Jansson, Shen, and Sung [JACM'16] which runs in time $O(n)$.

Introduction
We consider the tree consensus problem, an important problem in bioinformatics. Given a rooted tree t and another rooted tree T , we would like to combine "information" from T into t. More over, we would like to only greedily take information that is currently consistent with our current t. (See definitions below.) This problem is a subproblem in the tree refinement problem called RF-Optimal Tree Refinement Problem defined by in Christensen, Molloy, Vachaspati and Warnow [1] who employ the greedy algorithm by Gawrychowski, Landau, Sung, and Weimann [2] that runs in time O(n 1.5 log n). We give a faster algorithm for this problem that runs in time O(n log n). Our key ingredient is a bipartition compatibility criteria based on amortizedtime leaf counters. While this is an improvement, the fastest solution is an algorithm by Jansson, Shen, and Sung [3] which runs in time O(n).
The algorithm by Gawrychowski et al [2] works in a more general case where the goal is the find the greedy consensus trees from k trees. In this case, their algorithm runs in time O(kn 1.5 log n), an improvement over O(kn 2 ) of Jansson et al [3]. For this problem, Sung [4] also present an algorithm that runs in time O(k 2 n), improving over Gawrychowski et al [2] when k = O( √ n log n). In an earlier version, we erroneously claimed that our algorithm works for the case with many trees. We thank Pawel Gawrychowski and Oren Weiman for pointing this out. Jittat Fakcharoenphol who help advising the author on this manuscript would like to take the full responsibility for this mistake.

Definitions
We start with definitions related to trees and consistency.
Let V (T ), E(T ) and R(T ) be vertex set, edge set and the root of tree T . For every vertex u ∈ V (T ) − {R(T )}, let par(u) be parent node of node u. For every vertex u ∈ V (T ), let depth(u) be depth of node u. We can denote as depth(u) = depth(par(u)) + 1, for every vertex u ∈ V (T ) − {R(T )} and depth(R(T )) = 1. For every vertex u ∈ V (T ), let L(u) be set of all leaves on subtree u. Let size(u) = |L(u)| for each u ∈ V (T ). For each node u ∈ V (T ) − {R(T )}, we call Λ(u) be set of bipartition at edge (u, par(u)). For each bipartition, Λ(u), we can represent into two clusters, A = L(u) and B = L(R(T ))−L(u), and denoted by A|B. The set of bipartitions of T can denoted by C(T ) = {Λ(u) : u ∈ V (T ) − {R(T )}}. Let RF (T a , T b ) be Robinson-Foulds distance between trees T a and T b . RF-distance can denoted by RF (T a , The set S of bipartitions is compatible if there exists tree T such that C(T ) = S. leaves set A is compatible with t ′ when have node u that for all In this section, we describe a simpler version of the algorithm and prove its correctness and its running time (in Subsection 3.1). We improve its running time in Section 4 We assume that both T and the current t ′ are equipped with a data structure that given an id of a bipartition b, find vertex u in the trees such that Λ(u) = b. Since t ′ changes over time, we assume that our data structures can handle the tree update efficiently. We discuss this in Subsection 3.2.
The main loop of the algorithm iterates over all bipartition of T recursively and, if possible, add each bipartition to t ′ .
We define variables used in the main loop. Let z be the node that have minimum depth in tree t ′ for each bipartition in T . The main loop is described below.
Step, referred to in Section 4 4: if IsCompatible(t, u, z) then 5: The main loop uses the following function.
⊲ After this step we say that v has been added. 4: if z = null or depth(p) < z then 5: z ← p 6: end if 7: end for 8: return z Our algorithm maintains variable counter for each vertex in t ′ . We also keep a list of dirty vertices so that ClearCounter can run in O(1) time. Variable counter is updated in function UpdateCounterLeaf. Note that counter changes over time as UpdateCounterSubtree keeps adding leaves in L(u). The algorithm ensures that counter(u) is exactly as follows. If u is a leaf vertex, we let For other internal vertex u, we let For each call this function, it can take amortized O(1) time (to be proved later). The following algorithm describes function UpdateCounterLeaf.
Next, we have algorithm that check that add from previous algorithm is compatible to t ′ . We can track the node u that have minimum depth and have counter(u) > 0 in the while loop at the previous algorithm.
We prove the correctness of the algorithm. We note that it considers all bipartitions.

Lemma 1. The main loop considers all bipartitions in T .
Proof. From definition, Λ(u) can represent all bipartitions of T and for each bipartition, we have consider all node in Λ(u). From this, we can consider all bipartitions in T .
For clarity, for each vertex w ∈ t ′ we denote by L t ′ (w) its leaf set in t ′ . Note each call to UpdateCoun-terLeaf increases counter for each vertex by at most 1, and we call UpdateCounterLeaf exactly |L(u)| times. This implies the next lemma, which can be formally proven by induction.
i.e., the counter attains its maximum.
The following the key lemma. Proof. Note that after the call to UpdateCounterSubtree(u), we have called UpdateCounterLeaf(v) for every leaf v in L(u). From Claim 1, we only need to consider the case when counter(z ′ ) ≤ |L(u)|.
The algorithm maintains vertex z, which is the vertex closest to the root that UpdateCounterLeaf has touched. We first consider the case that z = z ′ .
On the other hand, if L(u) is compatible with t ′ , we show that counter(z ′ ) = |L(u)|. We prove a stronger statement: if L(u) is compatible with t ′ for every vertex v ∈ t ′ in the subtree rooted at z ′ , i.e., the upper bound in Claim 1 attains its maximum. To do so, we prove inductively on the structure of t ′ . Clearly, the claim is true when v is a leaf. Consider vertex v = z ′ in the subtree of t ′ rooted at z ′ . If L t ′ (v) ∩ L(u) = ∅, counter(v) = 0; thus the property follows. Now, consider v such that L t ′ (v) ∩ L(u) = ∅. Let w be a child of z ′ such that v belongs to subtree rooted at w.
Finally, consider z ′ . Note that since z ′ is the common ancestor of leaves in L(u), L t ′ (z ′ ) ⊇ L(u). For each child w of z ′ , when L t ′ (w) ∩ L(u) = ∅, w is complete and propagate |L t ′ (w) ∩ L(u)| to counter(z ′ ). Summing all children of z ′ , we have that counter(z ′ ) = |L(u)|.
This completes the proof of the lemma.

Lemma 3. Tree compatibility condition works
From above condition, our algorithm have add function counter(u). for each subtree L(u) have fully resolved when counter(u) = |L(u)|

Running time analysis
We first analyze the running time of the algorithm except the calls to UpdateCounterSubtree. We show that this part runs in linear time.
We start with UpdateCounterLeaf.
Proof. We use the potential method. Our data structure consists of variables counter for all vertices in t ′ . Denote the data structure at time i by D i . We say that a vertex u ∈ t ′ is incomplete if 0 < counter(u) < |L(u)|. Let potential function Φ(D i ) be the number of incomplete vertices in t ′ time i. Using the potential method, when the data structure changes from D i−1 to D i , the amortized cost of an operation isĉ = c + ∆Φ, where c is an actual cost, and ∆Φ = Φ(D i )−Φ(D i−1 ). Let D 0 be initial data structure after ClearCounter is called; thus Φ(D 0 ) = 0. Note that Φ(D i ) ≥ Φ(D 0 ) = 0 for any i. When invoking UpdateCounterLeaf at time i, let k be number of times the while loop in Lines 2 -6 is executed. Clearly, the actual cost c of the operation is k + 1.
We claim that Φ(D i ) = Φ(D i−1 ) − k + 1, i.e., the number of incomplete vertices decreases by k − 1. Let v ′ be the actual leaf that UpdateCounterLeaf is called on. Note that each time the loop is executed, counter(v) = size(v) = |L(v)|. Except when v = v ′ , previously at time i − 1, we know that 0 < counter(v) < |L(v)|, because v is an internal vertex with at least 2 children; hence v was incomplete at time i − 1. Since counter(v) = |L(v)| at time i, v is no longer incomplete; thus the number of incomplete vertices decreases by k − 1 as claimed.
We now analyze the running time of UpdateCounterSubtree.

Updating t
In this section, we show that when the bipartition defined by L(u) is compatible with t ′ , we can update t ′ to include that bipartition efficiently in time deg(u). When t ′ is compatible with a bipartition defined by L(u) for u ∈ T , to update t ′ we have to create a new child of z that consists of only children of z that corresponds to the bipartition L(u). Note that these children are those "full" counter that also propagate the counter to z. Therefore, when a child propagate a counter to any vertex, we keep a list of them. When we need to update t ′ at z, we can take every vertex in this list, and create a new child z ′ of z with these vertices as z ′ 's children and update their counter accordingly. This can be done in time O(deg(u)).

The faster algorithm: heavy child optimization
In this section, we describe a simple method to speed up the algorithm from the previous section. Note that the only bottle-neck to a nearly linear time algorithm is the counting procedure.
As a preprocessing, we assume that for each vertex u ∈ T , we know |L(u)|. This can be computed in O(n) time. The improved algorithm is described below.

Algorithm 5 Solve(u)
if u is not leaf then let c 1 , c 2 be children of u ⊲ There are exactly two children, since T is binary if |L(c 1 )| > |L(c 2 )| then swap node c 1 and node c 2 end if Solve(c 1 ) ⊲ Solve smaller subtree ClearCounter() Solve(c 2 ) ⊲ Solve larger subtree end if z ← UpdateCounterSubtree(c 1 ) ⊲ Update the counter for the smaller subtree if IsCompatible(t, u, z) then update t ′ end if To see that this algorithm is the correct implementation of the Main loop, we essentially need to show that at the end of Solve(u), variable counter is exactly equal to variable counter right after the "Update Step" in Line 3 in the Main loop while processing u, i.e., variable counter is exactly equal to the case when every leaf in L(u) has been added while no other leaves have been added. This can be shown by induction on the calls of Solve. We omit the proof in this version of the manuscript.
We are left to analyze its running time. Note that UpdateCounterSubtree(u) for u ∈ T runs in time linearly in the number of leaves, |L(u)|, from Lemma 5. Hence, we can charge the cost to these leaves.
We analyze the running time by counting the number of times each leaf is involved in this charging scheme. Note that we only call UpdateCounterSubtree at c 1 , which is the lighter subtree. Clearly, each leaf u belongs to at most O(log n) light subtrees; hence, it is charged by at most O(log n) time. Summing all leaves, we have that the total running time for UpdateCounterSubtree is O(n log n).