Text classification based on joint complexity and compressed sensing

Patent metadata

Field	Value
Publication number	US-2016140409-A1
Application number	US-201414540770-A
Country	US
Kind code	A1
Filing date	Nov 13, 2014
Priority date	Nov 13, 2014
Publication date	May 19, 2016
Grant date	—

Abstract

A server computes a sparsifying matrix from a set of reference blocks that is selected from first blocks of text based on joint complexities of each pair of the first blocks of text. The server determines one of the set of reference blocks that is most similar to a second block of text based on the sparsifying matrix, a measurement matrix, and a measurement vector formed by compressing the second block of text using the measurement matrix. The server transmits a signal representative of the one of the set of reference blocks to indicate a classification of the second block of text.

First claim

What is claimed is:

1 . A method comprising:
computing, at a first server, a sparsifying matrix from a set of reference blocks that is selected from first blocks of text based on joint complexities of each pair of the first blocks of text; determining, at the first server, one of the set of reference blocks that is most similar to a second block of text based on the sparsifying matrix, a measurement matrix, and a measurement vector formed by compressing the second block of text using the measurement matrix; and transmitting, from the first server, a signal representative of the one of the set of reference blocks to indicate a classification of the second block of text.

2 . The method of claim 1 , further comprising:
requesting the first blocks of text from a second server, wherein the first blocks of text are associated with a plurality of classes used for the classification of the second block of text.

3 . The method of claim 1 , further comprising:
generating suffix trees representative of the first blocks of text; and computing the joint complexities of each pair of the first blocks of text as a cardinality of a set of factors that are common to pairs of suffix trees that represent each pair of the first blocks of text.

4 . The method of claim 1 , further comprising:
generating a fully-connected edge-weighted graph including nodes corresponding to the first blocks of text, wherein the weights of edges of the graph are determined by the joint complexities of a pair of first blocks of text corresponding to the nodes connected by the edge; and selecting the set of reference blocks from the first blocks of text that have the highest sums of weights of edges connected to the corresponding nodes.

5 . The method of claim 1 , wherein determining the one of the set of reference blocks that is most similar to the second block of text comprises determining a vector representative of the second block of text in a transform domain associated with the sparsifying matrix by optimizing an objective function of the sparsifying matrix, the measurement matrix, and the measurement vector formed by compressing the second block of text using the measurement matrix.

6 . The method of claim 1 , further comprising:
receiving the measurement vector from user equipment that formed the measurement vector using the measurement matrix and the second block of text stored by the user equipment, and wherein transmitting the signal representative of the one of the set of reference blocks comprises transmitting a signal from the server to the user equipment.

7 . The method of claim 1 , further comprising:
predicting a classification of a third block of text based on the classification of the second block of text by applying a Kalman filter to the classification of the second block of text.

8 . The method of claim 1 , wherein the first blocks of text and the second block of text are strings of up to 140 characters.

9 . An apparatus comprising:
a processor to compute a sparsifying matrix from a set of reference blocks that is selected from first blocks of text based on joint complexities of each pair of the first blocks of text and determine one of the set of reference blocks that is most similar to a second block of text based on the sparsifying matrix, a measurement matrix, and a measurement vector formed by compressing the second block of text using the measurement matrix; and a transceiver to transmit a signal representative of the one of the set of reference blocks to indicate a classification of the second block of text.

10 . The apparatus of claim 9 , wherein the transceiver is to transmit a request for the first blocks of text to a second server, wherein the first blocks of text are associated with a plurality of classes used for the classification of the second block of text.

11 . The apparatus of claim 9 , wherein the processor is to generate suffix trees representative of the first blocks of text and compute the joint complexities of each pair of the first blocks of text as a cardinality of a set of factors that are common to pairs of suffix trees that represent each pair of the first blocks of text.

12 . The apparatus of claim 9 , wherein the processor is to generate a fully-connected edge-weighted graph including nodes corresponding to the first blocks of text, wherein the weights of edges of the graph are determined by the joint complexities of the pair of first blocks of text corresponding to the nodes connected by the edge, and wherein the processor is to select the set of reference blocks from the first blocks of text that have the highest sums of weights of edges connected to the corresponding nodes.

13 . The apparatus of claim 9 , wherein the processor is to determine a vector representative of the second block of text in a transform domain associated with the sparsifying matrix by optimizing an objective function of the sparsifying matrix, the measurement matrix, and the measurement vector formed by compressing the second block of text using the measurement matrix.

14 . The apparatus of claim 9 , wherein the transceiver is to receive the measurement vector from user equipment that formed the measurement vector using the measurement matrix and the second block of text stored by the user equipment, and wherein the transceiver is to transmit a signal to the user equipment.

15 . The apparatus of claim 9 , wherein the processor is to predict a classification of a third block of text based on the classification of the second block of text and update an estimate of the classification of the third block of text by applying a Kalman filter to the predicted classification of the third block of text.

16 . The apparatus of claim 9 , wherein the first blocks of text and the second blocks of text are strings of up to 140 characters.

17 . An apparatus comprising:
a processor to form a measurement vector using a measurement matrix and a first block of text; and a transceiver to transmit the measurement vector to a server and, in response, receive a signal representative of one of a set of reference blocks to indicate a classification of the first block of text, wherein the set of reference blocks is selected from second blocks of text based on joint complexities of each pair of the second blocks of text, and wherein the one of the set of reference blocks is determined to be most similar to the first block of text based on a sparsifying matrix determined based on the set of reference blocks, the measurement matrix, and the measurement vector.

18 . The apparatus of claim 17 , wherein the processor is to form the measurement vector by multiplying the measurement matrix and a character string of up to 140 characters.

19 . The apparatus of claim 17 , wherein the processor is to form the measurement vector so that the measurement vector is compressed relative to the first block of text.

20 . The apparatus of claim 17 , wherein the apparatus is a user equipment.

Assignees

• Milioris Dimitrios
• Alcatel Lucent

Inventors

• Milioris Dimitrios

Classifications

• G06F16/35 Primary

  Clustering; Classification · CPC title

• G06F18/2323

  based on graph theory, e.g. minimum spanning trees [MST] or graph cuts · CPC title

• G06K9/6267

  Physics · mapped topic

• G06K9/4604

  Physics · mapped topic

• G06T11/206

  Physics · mapped topic