KR20240046975A - Data-adaptive tensor analysis method and tensor analysis apparatus - Google Patents

Abstract

A data-adaptive tensor analysis method and a tensor analysis apparatus are provided. The tensor analysis apparatus includes an input/output unit configured to receive data and output a result of calculating and processing the data, a storage unit configured to store a program for performing the data-adaptive tensor analysis method, and a control unit including at least one process and configured to analyze a tensor stream received through the input/output unit by executing the program, wherein the control unit outputs a tensor decomposition result calculated through a tensor decomposition method using a complementary matrix from a new tensor slice of the tensor stream, detects a change point of the tensor stream based on the tensor decomposition result, and performs tensor decomposition in different ways according to a degree of change in the change point of the tensor stream.

Description

Data adaptive tensor analysis method and tensor analysis device {DATA-ADAPTIVE TENSOR ANALYSIS METHOD AND TENSOR ANALYSIS APPARATUS}

Embodiments disclosed herein relate to a data adaptive tensor analysis method and device, and more specifically, to a tensor analysis method and device that can improve both the accuracy and computational amount of tensor decomposition by adaptively decomposing a tensor stream. It's about.

Tensor decomposition is one of the methods used to analyze three-dimensional or more data such as video data, sensor data, etc., and extracts factor matrices corresponding to each dimension and a core tensor representing the intensity between each concept.

Existing tensor decomposition techniques omit the time axis update or use the factor matrix of the previous time step for fast execution speed, but these have the disadvantage of drastically decreasing accuracy when the data pattern changes over time.

Therefore, data adaptive tensor analysis technology that can improve the accuracy and processing speed of tensor decomposition is needed.

For reference, Patent Document 1 is an invention related to an interpolation method between a plurality of observed tensors, Patent Document 2 is an invention related to a tensor factor decomposition processing device, and Patent Document 3 is an invention related to a data analysis device. Patent Documents 1 to 1 Patent Document 3 only discloses general information about technologies related to data decomposition and does not provide data adaptive tensor analysis technology that can improve the accuracy and processing speed of tensor decomposition.

US Patent No. 8301379 (announced on October 30, 2012) Japanese Patent Publication No. 2016-173784 (published on September 29, 2016) Japanese Registered Patent No. 6608721 (announced on November 1, 2019)

Embodiments disclosed in this specification reduce the amount of computation of tensor decomposition by introducing a supplementary matrix in the tensor decomposition process of the tensor stream and setting the supplementary matrix to be updated only when there is no change in the time axis, and detecting change points in the tensor stream. The purpose is to provide a data adaptive tensor analysis method and device that improves the accuracy of tensor decomposition results by detecting and re-decomposing data accordingly.

Other objects and advantages of the present invention can be understood from the following description and will be more clearly understood through an example. In addition, it will be readily apparent that the objects and advantages of the present invention can be realized by means and combinations thereof as indicated in the claims.

As a technical means for achieving the above-described technical problem, a tensor analysis device includes an input/output unit for receiving data as input and outputting the results of processing the data; a storage unit storing a program for performing a data adaptive tensor analysis method; and at least one process, including a control unit that analyzes the tensor stream received through the input/output unit by executing the program, wherein the control unit performs a tensor decomposition method using a complementary matrix from a new tensor slice of the tensor stream. The tensor decomposition result calculated through is output, the change point of the tensor stream is detected based on the tensor decomposition result, and the tensor decomposition is performed in different ways depending on the degree of change in the change point of the tensor stream.

According to another embodiment, a data adaptive tensor analysis method using a tensor analysis device includes the steps of outputting a tensor decomposition result calculated from a new tensor slice of a tensor stream through a tensor decomposition method using a complementary matrix; Detecting a change point in the tensor stream based on the tensor decomposition result; and performing tensor decomposition in different ways depending on the degree of change in the change point of the tensor stream.

According to another embodiment, the recording medium is a computer-readable recording medium on which a program for performing an adaptive data tensor analysis method is recorded.

According to another embodiment, the computer program is performed by a tensor analysis device and stored in a recording medium to perform a data adaptive tensor analysis method.

According to any one of the means for solving the above-described problem, a data adaptive tensor analysis method and device that can reduce the computational cost for updating the decomposition factor of the tensor stream can be proposed.

In addition, according to any one of the above-mentioned problem solving means, a data adaptive tensor analysis method and device that can detect themes of data and change points in a tensor stream can be presented.

In addition, according to any one of the above-mentioned problem solving means, a data adaptive tensor analysis method and device that can improve decomposition accuracy by decomposing the tensor stream again when a new topic is detected can be proposed.

The effects that can be obtained from the disclosed embodiments are not limited to the effects mentioned above, and other effects not mentioned are clear to those skilled in the art to which the disclosed embodiments belong from the description below. It will be understandable.

Hereinafter, the attached drawings illustrate preferred embodiments disclosed in the present specification, and serve to further understand the technical idea disclosed in the present specification along with specific details for carrying out the invention, and thus the drawings disclosed in the present specification The contents should not be construed as limited to the matters described in such drawings.
1 is a block diagram of a tensor analysis device according to an embodiment.
Figure 2 is a diagram illustrating the results of decomposition of a tensor stream according to a comparative example.
Figure 3 is a diagram illustrating the results of decomposition of a tensor stream by a tensor analysis device according to an embodiment.
Figure 4 is a diagram illustrating an overall tensor decomposition operation by a tensor analysis device according to an embodiment.
Figure 5 is a flowchart of a data adaptive tensor analysis method according to another embodiment.
Figures 6 to 9 are diagrams illustrating decomposition performance of a tensor stream simulated according to embodiments.

Below, various embodiments will be described in detail with reference to the attached drawings. The embodiments described below may be modified and implemented in various different forms. In order to more clearly explain the characteristics of the embodiments, detailed descriptions of matters widely known to those skilled in the art to which the following embodiments belong have been omitted. In addition, in the drawings, parts that are not related to the description of the embodiments are omitted, and similar parts are given similar reference numerals throughout the specification.

Throughout the specification, when a configuration is said to be “connected” to another configuration, this includes not only cases where it is “directly connected,” but also cases where it is “connected with another configuration in between.” In addition, when a configuration “includes” a configuration, this means that other configurations may be further included rather than excluding other configurations, unless specifically stated to the contrary.

Hereinafter, embodiments will be described in detail with reference to the attached drawings.

However, before explaining this, we first define the meaning of the terms used below.

Table 1 below defines terms used in one embodiment.

[Table 1]

In this specification means a matrix, means the transpose matrix, means a pseudoinverse matrix. represents the length of the nth mode of the tensor, represents the rank of the tensor. represents the Nth order tensor. represents the decomposition factor matrix for the nth mode of the tensor. is a tensor It represents the Frobenius norm of . is a tensor represents the mode-n unfolding matrix of . Unfolding means matrixing a tensor. represents the Kruskal operator. for example, It can be expressed as: represents the Kronecker product, represents the Khatri-Rao product, represents the element-wise product, that is, the Hadamard product, represents element-wise division.

<tensor>

A tensor is a multidimensional array that generalizes vectors (first-order tensors) and matrices (second-order tensors) to higher orders. In this specification, a vector is a bold lowercase letter (e.g., a), a matrix is a bold uppercase letter (e.g., A), and a tensor is a bold font letter (e.g., ) can be displayed. Nth order tensor has N modes of length I ₁ , ... , I _N respectively. Mode refers to each dimension of the tensor. Tensors can be unfolded or matrixed depending on the modes. Tensor according to the nth mode The unfolding matrix of is It can be expressed as When a tensor is unfolded, its elements are rearranged into a matrix. As shown in Equation 1 below, the tensor The mode-n unfold matrix of silver tensor Unfold the (i ₁ , ... , i _N )th element of the matrix Maps to the (i _n , ... , i _N )th element of .

[Equation 1]

Frobenius norm of a tensor; ) can be expressed as Equation 2 below.

[Equation 2]

We define important matrix multiplications as follows. processions and The Kronecker product of silver size It is a matrix with .

Hadamard product and Khatri-Rao product. is a matrix product that is essentially used in tensor decomposition. Hadamard product is a matrix with the same size and It is the element-wise product of . As shown in Equation 3 below, the Khatri-Rao product represents the column-wise Kronecker product.

[Equation 3]

and Is and represents the column vectors of , respectively.

<Tensor decomposition>

CP(CANDECOMP/PARAFAC) decomposition is a well-known decomposition method in tensor decomposition methods and is treated as a core block in many other variants. CP decomposition factors the tensor into the sum of rank-1 tensors, as shown in Equation 4 below.

[Equation 4]

Here, the number R of the rank-1 tensor set is called the rank of the decomposed tensor. decomposition factor matrix represents a vector combination of rank-1 components as shown in Equation 5 below.

[Equation 5]

tensor The result of CP decomposition is the Kruskal operator. and the unfolding matrix can be expressed as follows. The Kruskal operator provides a shorthand notation for the sum of the cross products of columns in a decomposition factor matrix.

CP decomposition is an estimation error The goal is to find a decomposition factor matrix that minimizes . The estimation error can be defined as Equation 6 below.

[Equation 6]

Alternating Least Square (CP-ALS) is widely used in optimization problems. The main idea of ALS is to divide the original problem into N subproblems, where each subproblem corresponds to updating one factor matrix while keeping the remaining factor matrices fixed. It can be applied to the decomposition factor as shown in Equation 7 below.

[Equation 7]

Tensor data can be broadly divided into dynamic types, whose size and value changes over time, and static types, which do not.

An example of static tensor decomposition is Full-CP, which decomposes the entire tensor data without considering time changes.

<Online tensor decomposition>

Efficient online algorithms for time-evolving tensors can be applied to tensor decomposition. Assume the tensor is a set of "slices" given at each time step. Nth time progress tensor about, It can be expanded in the form of . here is the previous tensor data, is a new tensor slice at one time step. Online tensor decomposition is the result of the previous tensor decomposition Given a tensor The goal is to efficiently decompose.

[Equation 8]

here Is ego, Is am.

Online tensor decomposition produces an estimation error as shown in Equation 9 below: The purpose is to minimize.

[Equation 9]

Tensor stream decomposition based on existing CP decomposition mainly updates only non-temporal factors with pre-computed auxiliary matrices or updates all factors considering previous decomposition results.

The existing decomposition method for dynamic tensor decomposition is as follows.

<Online CP disassembly>

Online CP decomposition preserves the previous time factor to efficiently decompose new tensor slices. After updating the non-time factors and partial time factors, we simply add part of the time factor matrix to the previous matrix. Online CP decomposition introduces an auxiliary matrix to avoid double computation with the Khatri-Rao product and Hadamard product. Before ALS iteration, the complementary matrix is calculated and a new decomposition is generated. Even with low computational costs, accurate decomposition cannot be achieved due to lack of consideration of subject changes in the data.

Online CP decomposition applies the same time factor across all time steps. The length of the time factor along the horizontal axis increases for each time step. Unlike static tensor decomposition, online CP decomposition uses an approximation with additional constraints to reduce computational cost. Update only non-timed modes and reuse the same time argument for all time steps. There is a significant loss of accuracy if the incoming tensor has a different topic than the previous tensor, such as when the topic of the tensor stream changes from A->B, B'->C, or C->D. Online CP decomposition cannot achieve accurate decomposition due to lack of consideration of subject changes in the data.

To solve this problem, this embodiment tracks local errors in the tensor stream and detects change points in the data subject, enabling accurate decomposition even when the data has inconsistent temporal patterns.

<Dynamic tensor decomposition DTD>

Dynamic Tensor Decomposition (DTD) was introduced as part of Multi-Aspect Streaming Tensor (MAST), a low-rank tensor completion method that fills in missing entries in incomplete multi-aspect tensor streams. This method reduces time complexity by reusing previous decompositions to approximate the accumulated tensor until a new slice comes in. In particular, for an N-order tensor stream, the DTD splits the data into 2 ^N sub-tensors for each time step and binary tuples Use to represent the sub-tensor. then second Approximating to , the estimation error of online tensor decomposition is can be reformulated as in Equation 10 below.

[Equation 10]

here is a forgetting factor that mitigates the effects of previous decomposition errors. DTD is an efficient method, but it is less accurate as it still tries to reuse previous decomposition results when the incoming tensor has a completely different pattern than the previous tensor.

To solve this problem, this embodiment quickly adapts to rapid changes in data through a “re-decomposition” process and greatly improves decomposition accuracy.

This embodiment performs online tensor decomposition adaptively and accurately to data changes, and is efficient in terms of time and memory. When decomposing tensors that change over time, it is necessary to increase accuracy without sacrificing speed and memory usage. Considering that data themes change over time, changes in themes are detected and different strategies are used depending on the degree of change.

This embodiment largely improves the problem in three aspects.

First, it reduces computational costs. To reduce the arithmetic cost for updating decomposition factors of tensor streams, we build an updatable framework for tensor streams. The complement matrix and previous decomposition results are used recursively, and the complement matrix is updated only when there is a change in the non-temporal factor, which can reduce redundant operations.

Second, topics are identified in the data stream. Detect potential topics in the tensor stream and track errors to detect change points. It continuously tracks errors in data slices coming into the tensor stream, considers them as change points in the topic, and detects rapid decreases in accuracy based on standardized score analysis.

Thirdly, the decomposition accuracy is improved. To utilize detected topic changes and improve decomposition accuracy, the tensor stream is decomposed again when a new topic is detected. When a rapid change in the topic is detected, it selects whether to reuse or split the tensor stream depending on the degree of change. A recall ratio is introduced to improve the reuse process. These technical factors determine how much information should be retained from previous decomposition results while maintaining a balance between accuracy and speed.

1 is a functional block diagram of a tensor analysis device according to an embodiment.

Referring to FIG. 1, the tensor analysis device 100 according to an embodiment includes an input/output unit 110, a storage unit 120, and a control unit 130.

The input/output unit 110 may include an input unit for receiving input from a user and an output unit for displaying information such as a task performance result or the status of the tensor analysis device 100. In other words, the input/output unit 110 is configured to receive data as input and output the results of processing the data. The tensor analysis device 100 according to the embodiment may receive an input tensor and a request for analysis of the input tensor through the input/output unit 110.

The storage unit 120 is a component in which files and programs can be stored, and can be configured using various types of memory. In particular, the storage unit 120 may store data and programs that enable the control unit 130, which will be described later, to perform operations for tensor analysis according to the algorithm presented below.

The control unit 130 is a component that includes at least one processor such as CPU, GPU, Arduino, etc., and can control the overall operation of the tensor analysis device 100. That is, the control unit 130 may control other components included in the tensor analysis device 100 to perform operations for tensor analysis. The control unit 130 can perform an operation to analyze a tensor according to the algorithm presented below by executing a program stored in the storage unit 120.

The control unit 130 introduces a supplementary matrix to reduce the amount of computation of the tensor decomposition algorithm during the tensor decomposition process and sets the supplementary matrix to be updated only when there is no change in the time axis. The control unit 130 outputs a tensor decomposition result calculated from a new tensor slice of the tensor stream through a tensor decomposition method using a complement matrix.

The control unit 130 detects data change points with respect to the previous decomposition result of the tensor stream and performs data re-decomposition accordingly to improve the accuracy of the tensor decomposition result. The control unit 130 detects change points in the tensor stream based on the tensor decomposition results. The control unit 130 performs tensor decomposition in different ways depending on the degree of change in the change point of the tensor stream.

Hereinafter, an operation of the tensor analysis device 100 to adaptively update the tensor decomposition result and the complement matrix using the complement matrix will be described.

<Update rules>

tensor If is the Nth time progress tensor, then is the previous tensor data, is a new tensor slice. It can be assumed that the first mode of the tensor is the time mode.

The tensor analysis device 100 is a result of the previous decomposition. Given a tensor An update rule can be designed to efficiently decompose.

The tensor analysis device 100 is similar to the previous part and new part Using the time factor matrix second It can be separated into the old part and the new part as shown. here means the decomposition rank.

The tensor analysis device 100 sets a memory rate to consider the degree of data subject change. Apply. The recall ratio determines the weight assigned to the decomposition of previous tensor data.

estimation error is defined as in Equation 11 below. The non-time mode of the tensor stream is fixed and the estimation error of DTD is limited.

[Equation 11]

The tensor analysis device 100 estimates error based on CP-ALS. Optimize. Since there are changes only in time mode, we simplify the estimation error of DTD by setting changes in non-time modes to 0. Estimation error in each decomposition factor matrix The update rule to minimize can be expressed as follows.

The tensor analysis device 100 may update the previous time factor to further increase the accuracy of decomposition. If the previous time factor is not updated, it is only optimized for the previous topic of the data and therefore loses accuracy every time the topic changes. Applying this recursive process directly increases the amount of computation. To solve the problem of increasing the amount of computation, two complementary matrices G and H are introduced as shown in Equation 12 below.

[Equation 12]

Here, the first complementary matrix G is defined as an element-wise product based on the transpose matrix of the kth mode previous matrix and the kth mode matrix, and the second complementary matrix H is defined as an element-wise product based on the transpose matrix of the kth matrix and the kth matrix. It is defined as the star product. The first complement matrix G and the second complement matrix H are updated only when there is a change in the non-temporal factor, thereby reducing redundant calculations. It can be expressed as a modified update rule as shown in Equations 13 to 15 below.

[Equation 13]

The time factor matrix, that is, the previous part of the first mode matrix, can be calculated based on the transpose matrices of the first mode transfer matrix, the first complement matrix, and the second complement matrix.

[Equation 14]

The time factor matrix, that is, the new part of the first mode matrix, can be calculated based on the new part of the new tensor slice, the Katri-Rao product with the k order mode matrix, and the transpose matrix of the second complement matrix.

[Equation 15]

For non-temporal factor matrices, i.e. non-1 i-th mode matrices, the i-th mode old matrix, the old part of the first-order mode matrix and the new one, taking into account the memory ratio corresponding to the weight assigned to the decomposition of the previous tensor data. It can be calculated based on a relational expression including the partial, first complement matrix, and second complement matrix.

The tensor decomposition method using a supplementary matrix updates the decomposition factors that make up the tensor decomposition result. If the decomposition factor corresponds to the time factor, the supplementary matrix is applied to calculate it, and if the decomposition factor does not correspond to the time factor, the previous tensor decomposition is performed. Update the decomposition factor and update the complement matrix by considering the weight of the result.

The algorithm for the update rule can be expressed in pseudocode as shown in Table 2.

[Table 2]

The algorithm for the update rule can be called DAO (Data Adaptive Online)-CP (CANDECOMP/PARAFAC)-ALS (Alternating Least Square), and the algorithm for the update rule uses the decomposition factor that is the result of the previous tensor decomposition. , new tensor slices , the memory ratio ρ, and the number of repetitions n _iter are input, and the updated decomposition factor is output.

Initialize the first complementary matrix G and the second complementary matrix H using Equation 12.

Updates are performed according to the number of iterations. New part of the time factor matrix using Equation 14 Update . Non-temporal factor matrix The non-time factor matrix using Equation 15 for , update the first complementary matrix G , and the second complementary matrix H. Previous part of the time factor matrix using Equation 13 Update .

Below, an operation of the tensor analysis device 100 to detect data change points in a tensor stream will be described.

<Change point detection>

The tensor analysis device 100 tracks errors between new tensor slices and tensor decomposition results, converts the tracked errors into scores, and detects change points in the tensor stream based on the scores.

The tensor analysis device 100 detects change points in the subject in the tensor stream and quickly adapts to rapid changes in data. To achieve this, we continuously track the decomposition error of the tensor stream and detect any sudden decrease in accuracy, which we consider to be a change point in the topic. This decrease in accuracy is due to the local error norm for the new tensor slice and the decomposition results of the new tensor slice, as shown in Equation 16 below: It can be captured by measuring .

[Equation 16]

Standardized score analysis can be applied to continuously track the local error of the decomposition result of the tensor stream and calculate the score. Standardized score analysis has the advantage of being able to quickly process real-time data and detecting minute levels of change by changing the threshold.

The tensor analysis device 100 is a local error norm. This normal distribution Assume that follows. average and variance Detect outliers by tracking. Since we need to update the mean and variance online, we can use the Welford algorithm, which provides accurate estimates of the mean and variance without having to maintain the entire data. The known Welford algorithm requires only one pass through the given data to calculate the sample mean and variance. Using the Welford algorithm, outliers are detected in the current local error norm through standardized score (z-score) analysis as shown in Equation 17 below.

[Equation 17]

here is the ideal threshold. By changing the value, you can fine-tune the criteria for whether a new tensor slice is similar to a previous tensor.

Hereinafter, an operation in which the tensor analysis device 100 determines whether to re-decompose based on the data change point of the tensor stream and selectively performs tensor decomposition among a plurality of tensor decomposition strategies will be described.

<Re-decomposition>

When a rapid change in a data subject is detected through standardized score analysis, the tensor analysis device 100 uses change information to increase decomposition accuracy. As new tensor slices are accumulated for each time step, the decomposition factor matrix is updated according to the optimization method described in the algorithm for update rules (see Table 2). Next, calculate the standardized score from the local error norm distribution and perform a "redecomposition" according to the score.

The tensor analysis device 100 tracks the distribution of local error norms, sets a standardization score standard, and automatically selects the best strategy between the first tensor decomposition strategy or the second tensor decomposition strategy depending on the degree of change. The first tensor decomposition strategy is a tensor decomposition initialization strategy and corresponds to the split process, and the second tensor decomposition strategy is a strategy for reusing previous decomposition results and corresponds to the refinement process.

FIG. 2 is a diagram illustrating the results of decomposition of a tensor stream according to a comparative example, and FIG. 3 is a diagram illustrating the results of decomposition of a tensor stream by a tensor analysis device according to an embodiment.

Referring to Figure 2, the existing online CP decomposition is performed when the subject of the tensor stream changes from A to B (210), when it changes from B to B' (220), and when it changes from B' to C (230). , When changing from C to D (240), the same time factor is reused, so it can be confirmed that it is vulnerable to topic changes.

Referring to Figure 3, the tensor analysis device according to this embodiment is changed from A to B (310), when changed from B' to C (330), and when changed from C to D (340). 1 The Split process, which is a tensor decomposition strategy, is performed, and when B is changed to B' (220), the second tensor decomposition strategy, the Refinement process, is performed. Since the tensor analysis device according to this embodiment adaptively selects a plurality of tensor decomposition strategies, it can be confirmed that it is robust to subject changes.

Table 3 illustrates the scoring criteria for adaptively selecting multiple tensor decomposition strategies.

[Table 3]

The tensor analysis device 100 scores the degree of data change in the tensor stream and determines whether the score of the change point satisfies the first critical range or the second critical range. The first threshold range is the first threshold This means that it is larger, and if the first critical range is satisfied, the division process proceeds. The second threshold range is the second threshold greater than the first threshold This means that it is less than or equal to, and if the second critical range is satisfied, the purification process proceeds. second threshold If it is smaller or equal, the division process and purification process are not performed.

<Split process>

If the incoming tensor slices have completely different topics compared to previous tensors, reusing previous results from the decomposition will result in significant loss of accuracy. To solve this problem, the first threshold We design a partitioning process that divides the tensor stream into tensors with different topics. Reinitialization requires additional costs in space and time, but unexpected accuracy degradation can be completely avoided through the segmentation process.

<Purification process>

The refinement process is used to update the decomposition results if there are only slight differences in the topics compared to the previous tensor. Second threshold as hyperparameter Use to fine-tune the refinement criteria for whether an incoming tensor slice is similar to the previous tensor.

Since the refinement process needs to focus more on new slices, we use a memory ratio (1-ρ). The memory ratio (1-ρ) is Because of It has a range.

In the ALS process, the score (e.g., standardized score) used to detect change points is applied to the number of repetitions. Because a higher standardized score means there is a more drastic change in the data, the number of iterations is set to perform additional iterations accordingly.

Ultimately, these technical factors determine how much information should be retained from previous decompositions, controlling the trade-off between accuracy and execution time.

Figure 4 is a diagram illustrating an overall tensor decomposition operation by a tensor analysis device according to an embodiment.

In step S410, the tensor analysis device 100 inputs the tensor stream, memory ratio, number of repetitions, first threshold, and second threshold. A tensor stream is a tensor that changes over time and can correspond to a given set of slices at each time step. The memory ratio refers to the weight assigned to the decomposition of previous tensor data, and different values can be applied to the memory ratio when decomposing a new tensor slice and performing the refining process. When performing a refinement process rather than tensor decomposition of a new tensor slice, an increased number of iterations can be applied. The first threshold is used as a standard for determining whether to proceed with the division process, and the first and second thresholds are used as standards for determining whether to proceed with the refining process.

In step S420, the tensor analysis device 100 tensor decomposes a new tensor slice of the tensor stream. The tensor analysis device 100 decomposes a new tensor slice by applying a tensor decomposition method using a complement matrix.

In step S430, the tensor analysis device 100 calculates the error between the new tensor slice and the tensor decomposition result and calculates the degree of change. The tensor analysis device 100 tracks errors between new tensor slices and tensor decomposition results, converts the tracked errors into scores, and detects change points in the tensor stream based on the scores.

In step S440, the tensor analysis device 100 compares whether the degree of change is greater than the first threshold. The range larger than the first threshold is called the first critical range, and if the first critical range is satisfied, the division process, which is the first tensor decomposition strategy, is performed in step S445.

In step S450, the tensor analysis device 100 compares whether the degree of change is greater than the second threshold. A range that is greater than the second threshold and less than or equal to the first threshold is called the second critical range, and if the second critical range is satisfied, the refining process proceeds in step S455.

In step S460, the tensor analysis device 100 stores the decomposition factor in a decomposition factor set. The decomposition factors calculated along the three paths are stored in the decomposition factor set. That is, (i) a decomposition factor calculated by performing a splitting process according to the first critical range, (ii) a decomposition factor calculated by performing a refining process according to the second critical range, or (iii) the first critical range and the second critical range. 2 Because the critical range is not satisfied, the division and purification process is not performed and the calculated decomposition factors are stored in the decomposition factor set.

In step S470, the tensor analysis device 100 determines whether decomposition is complete for all slices. If decomposition of all tensor slices is not completed, the process is repeated starting from step S420. When decomposition of all tensor slices is completed, the tensor analysis device 100 outputs a set of stored decomposition factors in step S480.

The algorithm for the entire tensor decomposition operation can be expressed in pseudocode as shown in Table 4.

[Table 4]

The algorithm for the entire tensor decomposition operation can be called DAO (Data Adaptive Online)-CP (CANDECOMP/PARAFAC) decomposition, and the algorithm for the entire tensor decomposition operation can be called tensor stream , the memory ratio ρ, the number of iterations of ALS n _iter , and the set of decomposition factors. Outputs . DAO (Data Adaptive Online)-CP (CANDECOMP/PARAFAC)-ALS (Alternating Least Square) is an algorithm for update rules and is described in Table 2.

New Tensor Slice By tensor decomposition, the decomposition factor is the result of tensor decomposition. Initialize . New Tensor Slice and decomposition factor error between the liver Calculate . error bastard Initialize the parameters of the Welford algorithm regarding mean/variance based on .

tensor stream Tensor decomposition is performed on . Previous tensor decomposition results , new tensor slices , the memory ratio ρ, and the number of iterations n _iter using an algorithm for update rules to decompose factors. Calculate . New Tensor Slice and decomposition factor error between the liver Calculate .

error bastard Standardized score and first threshold and compare the error norm The standardized score of is the first threshold If it is larger than that, a division process is performed. set the previous decomposition factor to the decomposition factor Save it to New Tensor Slice By tensor decomposing , the decomposition factor is the result of the previous tensor decomposition. Initialize . New Tensor Slice and decomposition factor error between the liver Calculate . error bastard Initialize the parameters of the Welford algorithm regarding mean/variance based on .

error bastard The first threshold is the standardized score of and a second threshold Compare with and the error norm The standardized score of is the first threshold Less than or equal to the second threshold If it is larger than that, proceed with the purification process. Previous tensor decomposition results , new tensor slices , the memory ratio 1-ρ, and the number of iterations (1+standardized score)*n _iter using an algorithm for update rules to decompose factors. Calculate . New Tensor Slice and decomposition factor error between the liver Calculate .

error bastard Initialize the parameters of the Welford algorithm regarding mean/variance based on . Decomposition factors that are the result of previous decomposition factors decompose into factors Replace with

set the previous decomposition factor to the decomposition factor Save it to Set of stored decomposition factors Outputs .

Figure 5 is a flowchart of a data-adaptive online (DAO) tensor analysis method according to another embodiment.

The data adaptive tensor analysis method according to the embodiment shown in FIG. 5 includes steps processed in a time-series manner in the tensor analysis device shown in FIG. 2. Therefore, even if the content is omitted below, the content described above regarding the tensor analysis device shown in FIG. 2 can also be applied to the data adaptive tensor analysis method according to the embodiment shown in FIG. 5.

In step S510, the tensor analysis device 100 outputs a tensor decomposition result calculated through a tensor decomposition method using a complementary matrix from a new tensor slice of the tensor stream. The tensor decomposition method using a complementary matrix updates the decomposition factors that make up the tensor decomposition result. If the decomposition factor corresponds to the time factor, the complementary matrix is applied to calculate it. If the decomposition factor does not correspond to the time factor, the previous tensor decomposition result is calculated. Update the decomposition factor and update the complement matrix by considering the weights of .

In step S520, the tensor analysis device 100 detects a change point in the tensor stream based on the tensor decomposition result. In the step of detecting change points in the tensor stream (S520), the error between the new tensor slice and the tensor decomposition result is tracked, the tracked error is converted into a score, and the change point in the tensor stream is detected based on the score.

In step S530, the tensor analysis device 100 performs tensor decomposition in different ways depending on the degree of change in the change point of the tensor stream. In the step of performing tensor decomposition in a different way (S530), if the degree of change satisfies the first critical range, the tensor decomposition initialization strategy, which is the first tensor decomposition strategy, is selected to proceed with the division process according to re-decomposition, and the degree of change is 2 If the critical range is satisfied, the second tensor decomposition strategy, the reuse of previous decomposition results, is selected and a refinement process is performed to update the tensor decomposition results using the previous tensor decomposition results.

Figures 6 to 9 are diagrams illustrating decomposition performance of a tensor stream simulated according to embodiments.

Figure 6 is a diagram related to topic change identification performance of a tensor stream.

The subject of a tensor stream refers to factors that encompass or are common to the stream data. Topic change means that the main factor covering a specific time section of stream data changes to a different factor from another specific point in time. For example, subject changes include the start of object movement in CCTV data and scene changes in movie data. Although the experiment was conducted mainly on images, other types of tensor data other than images are also possible.

Reference numeral 610 represents original CCTV data, reference numeral 620 represents subject change detection results for CCTV data according to this embodiment, and reference numerals 630, 640, and 650 represent full-data corresponding to comparative examples for CCTV data. The topic change detection results according to CP, DTD, and online CP are shown, respectively.

Reference numeral 615 represents sample video data, reference numeral 625 represents the subject change detection result for the sample video data according to the present embodiment, and reference numerals 635, 645, and 655 correspond to comparative examples for the sample video data. The topic change detection results according to Full-CP, DTD, and Online CP are shown, respectively.

Looking at the subject change detection results according to this embodiment, it can be seen that a clear image is provided because subject changes are automatically detected and re-disassembly is performed according to the degree of change.

Figure 7 is a diagram regarding reconstruction error performance of a tensor stream.

To measure reconstruction error regarding decomposition accuracy, local error norm and global error norm are used, but local fitness score and global fitness score are used through the equation below.

Regional Fit Score represents the goodness of fit for the incoming data slice at each time step, and is the global fit score. represents the goodness of fit for all tensors. Local fit score and global fit score are normalized versions of the error norm for data size, designed to compare decomposition accuracy for multiple data sets of different sizes. The average local fitness score is calculated at each time step.

Reference numerals 710 and 715 represent global fitting scores and average local fitting scores performed on sample video data, respectively. Reference numerals 720 and 725 represent global fitting scores and average local fitting scores performed on stock price data, respectively. Reference numerals 730 and 735 represent the global fitting score and the average local fitting score performed on the airport hall data, respectively. Reference numerals 740 and 745 represent the global fit score and average regional fit score performed on domestic air quality data, respectively. Reference numerals 750 and 755 represent global fitting scores and average local fitting scores performed on virtual data, respectively.

Looking at the decomposition accuracy results according to this embodiment, it can be seen that the decomposition accuracy is excellent and increases even though the decomposition rank is diversified because the change point of the subject is detected.

Figure 8 is a diagram regarding processing time performance of a tensor stream.

Reference numerals 810, 820, 830, 840, and 850 indicate processing speeds performed on sample video data, stock price data, airport hall data, domestic air quality data, and virtual data, respectively, in that order. Since the static decomposition method (Full-CP) is not an online method, it is assumed that the entire tensor is decomposed each time a new data slice comes in.

Looking at the processing time results according to this embodiment, the characteristics of the data are used and change points are detected to enable accurate tensor decomposition, and the execution time is slightly longer due to the re-decomposition process. It has a running time between the static and dynamic decomposition methods, and shows processing speeds comparable to other dynamic algorithms (DTD and online CP), and is much faster than the static method (Full-CP).

Figure 9 is a diagram showing performance improvement according to re-decomposition of the tensor stream.

Reference numerals 910, 940, and 960 represent division processes, respectively, and reference numerals 920, 930, and 950 represent purification processes, respectively.

Looking at the re-decomposition results according to this embodiment, the scene 910 in which an object emerges from a cave in the image data shows similar results to the comparative examples (Full-CP, DTD, and Online CP). However, it can be seen that subject changes are accurately detected in the background transition scene 940 and the scene 960 in which another object appears, unlike other comparative examples. It takes slightly more processing time than other dynamic algorithms (DTD and online CP), but unlike other dynamic algorithms (DTD and online CP), it improves decomposition accuracy through the segmentation process.

The term '~unit' used in the above embodiments refers to software or hardware components such as FPGA (field programmable gate array) or ASIC, and the '~unit' performs certain roles. However, '~part' is not limited to software or hardware. The '~ part' may be configured to reside in an addressable storage medium and may be configured to reproduce on one or more processors. Therefore, as an example, '~ part' refers to components such as software components, object-oriented software components, class components, and task components, processes, functions, properties, and procedures. , subroutines, segments of program code, drivers, firmware, microcode, circuits, data, databases, data structures, tables, arrays and variables.

The functions provided within the components and 'parts' may be combined into a smaller number of components and 'parts' or may be separated from additional components and 'parts'.

In addition, the components and 'parts' may be implemented to regenerate one or more CPUs within the device or secure multimedia card.

Meanwhile, the tensor analysis method according to an embodiment described through this specification may also be implemented in the form of a computer-readable medium that stores instructions and data executable by a computer. At this time, instructions and data can be stored in the form of program code, and when executed by a processor, they can generate a certain program module and perform a certain operation. Additionally, computer-readable media can be any available media that can be accessed by a computer and includes both volatile and non-volatile media, removable and non-removable media. Additionally, computer-readable media may be computer recording media, which are volatile and non-volatile implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. It can include both volatile, removable and non-removable media. For example, computer recording media may be magnetic storage media such as HDDs and SSDs, optical recording media such as CDs, DVDs, and Blu-ray discs, or memory included in servers accessible through a network.

Additionally, the tensor analysis method according to an embodiment described through this specification may be implemented as a computer program (or computer program product) including instructions executable by a computer. A computer program includes programmable machine instructions processed by a processor and may be implemented in a high-level programming language, object-oriented programming language, assembly language, or machine language. . Additionally, the computer program may be recorded on a tangible computer-readable recording medium (eg, memory, hard disk, magnetic/optical medium, or solid-state drive (SSD)).

Accordingly, the tensor analysis method according to an embodiment described through this specification can be implemented by executing the above-described computer program by a computing device. The computing device may include at least some of a processor, memory, a storage device, a high-speed interface connected to the memory and a high-speed expansion port, and a low-speed interface connected to a low-speed bus and a storage device. Each of these components is connected to one another using various buses and may be mounted on a common motherboard or in some other suitable manner.

Here, the processor can process instructions within the computing device, such as displaying graphical information to provide a graphic user interface (GUI) on an external input or output device, such as a display connected to a high-speed interface. These may include instructions stored in memory or a storage device. In other embodiments, multiple processors and/or multiple buses may be utilized along with multiple memories and memory types as appropriate. Additionally, the processor may be implemented as a chipset consisting of chips including multiple independent analog and/or digital processors.

Additionally, memory stores information within a computing device. In one example, memory may be comprised of volatile memory units or sets thereof. As another example, memory may consist of non-volatile memory units or sets thereof. The memory may also be another type of computer-readable medium, such as a magnetic or optical disk.

Additionally, the storage device can provide a large amount of storage space to the computing device. A storage device may be a computer-readable medium or a configuration that includes such media, and may include, for example, devices or other components within a storage area network (SAN), such as a floppy disk device, a hard disk device, an optical disk device, Or it may be a tape device, flash memory, or other similar semiconductor memory device or device array.

The above-described embodiments are for illustrative purposes, and those of ordinary skill in the technical field to which the above-described embodiments belong will recognize that they can be easily modified into other specific forms without changing the technical idea or essential features of the above-described embodiments. You will understand. Therefore, the embodiments described above should be understood in all respects as illustrative and not restrictive. For example, each component described as unitary may be implemented in a distributed manner, and similarly, components described as distributed may also be implemented in a combined form.

The scope sought to be protected through this specification is indicated by the patent claims described later rather than the detailed description above, and all changes or modified forms derived from the meaning and scope of the claims and their equivalent concepts are included in the scope of the present invention. It should be interpreted as being

100: tensor analysis device
110: input/output unit
120: storage unit
130: control unit

Claims (10)

An input/output unit for receiving data and outputting the results of processing the data;
a storage unit storing a program for performing a data adaptive tensor analysis method; and
It includes at least one process, and includes a control unit that analyzes the tensor stream received through the input/output unit by executing the program,
The control unit,
Output the tensor decomposition result calculated through a tensor decomposition method using a complement matrix from the new tensor slice of the tensor stream,
Detect change points in the tensor stream based on the tensor decomposition results,
A tensor analysis device that performs tensor decomposition in different ways depending on the degree of change in the change point of the tensor stream. According to claim 1,
The tensor decomposition method using the complement matrix is,
Update the decomposition factors constituting the tensor decomposition result,
If the decomposition factor corresponds to the time factor, it is calculated by applying the supplementary matrix,
If the decomposition factor does not correspond to the time factor, the tensor analysis device updates the decomposition factor and updates the complement matrix by considering the weight of the previous tensor decomposition result. According to claim 1,
The control unit,
A tensor analysis device that tracks the error between the new tensor slice and the tensor decomposition result, converts the tracked error into a score, and detects a change point in the tensor stream based on the score. According to claim 1,
The control unit,
If the degree of change satisfies the first critical range, select the tensor decomposition initialization strategy, which is the first tensor decomposition strategy, and proceed with the division process according to re-decomposition;
If the degree of change satisfies the second critical range, the tensor analysis device selects the previous decomposition result reuse strategy, which is the second tensor decomposition strategy, and performs a refining process of updating the tensor decomposition result using the previous tensor decomposition result. In a data adaptive tensor analysis method using a tensor analysis device,
Outputting a tensor decomposition result calculated from a new tensor slice of the tensor stream through a tensor decomposition method using a complement matrix;
Detecting a change point in the tensor stream based on the tensor decomposition result; and
A data adaptive tensor analysis method comprising performing tensor decomposition in different ways depending on the degree of change in the change point of the tensor stream. According to claim 5,
The tensor decomposition method using the complement matrix is,
Update the decomposition factors constituting the tensor decomposition result,
If the decomposition factor corresponds to the time factor, it is calculated by applying the supplementary matrix,
If the decomposition factor does not correspond to the time factor, the data adaptive tensor analysis method updates the decomposition factor and updates the complement matrix by considering the weight of the previous tensor decomposition result. According to claim 5,
The step of detecting change points in the tensor stream is,
A data adaptive tensor analysis method that tracks the error between the new tensor slice and the tensor decomposition result, converts the tracked error into a score, and detects change points in the tensor stream based on the score. According to claim 5,
The step of performing tensor decomposition in the above different ways is,
If the degree of change satisfies the first critical range, select the tensor decomposition initialization strategy, which is the first tensor decomposition strategy, and proceed with the division process according to re-decomposition;
If the degree of change satisfies the second critical range, the second tensor decomposition strategy, the previous decomposition result reuse strategy, is selected and a refinement process is performed to update the tensor decomposition result using the previous tensor decomposition result. A data adaptive tensor analysis method. . A computer-readable recording medium on which a program for performing the method according to claim 5 is recorded. A computer program stored in a recording medium for performing the method according to claim 5, which is performed by a tensor analysis device.