Scalable spectral modeling of sparse sequence functions via a best matching algorithm

Abstract

A method for modeling a sparse function over sequences is described. The method includes inputting a set of sequences that support a function. A set of prefixes and a set of suffixes for the set of sequences are identified. A sub-block of a full matrix is identified which has the full structural rank as the full matrix. The full matrix includes an entry for each pair of a prefix and a suffix from the sets of prefixes and suffixes. A matrix for the sub-block is computed. A minimal non-deterministic weighted automaton which models the function is computed, based on the sub-block matrix. Information based on the identified minimal non-deterministic weighted automaton is output.

What is claimed is: 
     
         1 . A method for modeling a sparse function over sequences comprising:
 inputting a set of sequences that support a function;   identifying a set of prefixes and a set of suffixes for the set of sequences;   identifying a sub-block of a full matrix, the sub-block having the full structural rank as the full matrix, the full matrix including an entry for each pair of a prefix and a suffix from the sets of prefixes and suffixes;   computing a matrix for the sub-block;   identifying a minimal non-deterministic weighted automaton which models the function, based on the sub-block matrix; and   outputting information based on the identified minimal non-deterministic weighted automaton,   wherein at least one of the computing of the full matrix, identifying the sub-block of the full matrix, identifying the minimal non-deterministic weighted automaton, and outputting information is performed with a processor.   
     
     
         2 . The method of  claim 1 , wherein each of the input sequences includes a set of symbols drawn from an alphabet. 
     
     
         3 . The method of  claim 2  wherein the symbols in the alphabet comprise characters or words. 
     
     
         4 . The method of  claim 3 , wherein the sequences are extracted from at least one text document. 
     
     
         5 . The method of  claim 1 , wherein the full matrix is a Hankel matrix. 
     
     
         6 . The method of  claim 5 , wherein the method includes inputting a maximum value of the number of symbols in a sequence. 
     
     
         7 . The method of  claim 1 , wherein the identifying a sub-block of the full matrix comprises:
 generating a bipartite graph in which the prefixes form a first part and the suffixes form a second part, pairs of prefixes and suffixes that form the sequences in the set of sequences each being connected by an edge;   computing a longest path in the bipartite graph along the edges, the longest path connecting a first vertex in the first part with a second vertex in the second part;   extracting a set of best matching pairs from the longest path that have no intersecting vertices; and   identifying the sub-block based on the best matching pairs.   
     
     
         8 . The method of  claim 1 , wherein the computing a matrix for the sub-block comprises computing a Hankel matrix. 
     
     
         9 . The method of  claim 1 , wherein the identifying a minimal non-deterministic weighted automaton based on the sub-block matrix comprises performing singular value decomposition on the sub-block matrix. 
     
     
         10 . The method of  claim 9 , wherein performing singular value decomposition on the sub-block matrix comprises computing a non-deterministic weighted automaton for each of a set of singular values and identifying one of the non-deterministic weighted automata as the minimal non-deterministic weighted automaton based on performance. 
     
     
         11 . The method of  claim 1 , wherein the method further includes extracting parameters of the minimal non-deterministic weighted automaton. 
     
     
         12 . The method of  claim 11 , wherein the parameters include a starting vector, an ending vector and, for each symbol in the alphabet, a respective transition matrix. 
     
     
         13 . The method of  claim 1 , wherein the information output includes parameters of the minimal non-deterministic weighted automaton. 
     
     
         14 . The method of  claim 1 , further comprising implementing a process using the minimal non-deterministic weighted automaton and wherein the information output includes information generated in the process. 
     
     
         15 . A system comprising memory which stores instructions for performing the method of  claim 1  and a processor in communication with the memory for executing the instructions. 
     
     
         16 . A computer program product comprising a non-transitory medium storing instructions which, when executed by a computer, perform the method of  claim 1 . 
     
     
         17 . A system for modeling sparse functions over sequences comprising:
 a component which identifies a set of prefixes and a set of suffixes occurring in a set of sequences that support a function;   a component which identifies a sub-block of a full matrix having the full structural rank of the full matrix, the full matrix including an entry for each pair of a prefix and a suffix from the sets of prefixes and suffixes;   a component which computes a matrix for the sub-block;   a component which identifies a minimal non-deterministic weighted automaton which models the function, based on the sub-block matrix;   a component which outputs information based on the identified minimal non-deterministic weighted automaton; and   a processor which implements the components.   
     
     
         18 . The system of  claim 17 , further comprising a component which implements a process based on the minimal non-deterministic weighted automaton. 
     
     
         19 . A method for modeling a sparse function over sequences comprising:
 inputting a set of sequences that support a function, each sequence consisting of a set of symbols from an alphabet;   identifying a set of prefixes and a set of suffixes for the set of sequences;   generating a bipartite graph in which the prefixes form a first part and the suffixes form a second part;   computing a longest path in the bipartite graph by generating edges between vertices representing the prefixes and suffixes, the longest path connecting a first vertex in the first part with a second vertex in the second part;   extracting a set of best matching pairs from the longest path; and   identifying a sub-block based on the best matching pairs;   computing a Hankel matrix for the sub-block;   identifying a minimal non-deterministic weighted automaton which models the function, based on the sub-block Hankel matrix, using singular value decomposition; and   computing parameters of the minimal non-deterministic weighted automaton,   wherein at least one of the generating the bipartite graph, computing the longest path, extracting the set of best matching pairs, identifying the sub-block of the full Hankel matrix, identifying the minimal non-deterministic weighted automaton, and computing parameters is performed with a processor.