Semantic compression

• US 9,858,393 B2
• Filed: 04/13/2010
• Issued: 01/02/2018
• Est. Priority Date: 04/13/2010
• Status: Expired due to Fees

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Beckmann, Nathan, Potkonjak, Miodrag
• Primary Examiner(s): Gort, Elaine
• Assistant Examiner(s): RAJ, RAJIV J
• Application Number:
  US12/997,862
• Publication Number:
  US 20120265738A1
• Time in Patent Office: 2,821 Days
• CPC Class Codes: G16H 50/20 for computer-aided diagnosis, e.g. based on medical expert systems
• CPC Class Codes: G16H 50/70 for mining of medical data, e.g. analysing previous cases of other patients
• CPC Class Codes: G16H 50/80 for detecting, monitoring or modelling epidemics or pandemics, e.g. flu
• CPC Class Codes: G16Z 99/00 Subject matter not provided for in other main groups of this subclass
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

Technology for semantic compression is disclosed. In various embodiments, the technology receives data that represents one or more physical attributes sensed by one or more sensors; employs at least one pattern or statistical feature to identify a first region and a second region in the received data; computes a first utility and a first relevant feature for the first region, and a second utility and a second relevant feature for the second region; and identifies based on at least the first utility and the second utility a first compression method to apply to the first region and a second compression method to apply to the second region wherein the first and the second compression methods have different compression rates, different feature preservation characteristics, or both.

Claims

1. A method performed by a computing device to compress medical data, the method comprising:

receiving, by the computing device, the medical data that represents one or more physical attributes;

identifying, by the computing device, a first region and a second region in the received medical data by;

characterizing a utility of different signal segments by analyzing one or more sets of diagnosis results for a first diagnosis, the utility corresponding to how important each of the signal segments is to the first diagnosis compared to other signal segments,

identifying a unique combination of features in each of the signal segments, and

deriving one or more algorithms for automatic feature identification using at least one of a pattern matching technique or a statistical technique to segment the received medical data into the first region and the second region such that each of the first region and the second region has a same utility value;

computing, by the computing device, a first entropy for the first region and a second entropy for the second region;

computing, by the computing device, a first utility value and a first feature for the first region, and a second utility value and a second feature for the second region, wherein the first utility value is representative of a relative measure of how important the first region is to the first diagnosis compared to the second region, and wherein the second utility value is representative of a relative measure of how important the second region is to the first diagnosis compared to the first region;

computing, by the computing device, a first rating for the first region and a second rating for the second region, wherein the first rating is a function of the first utility value and the first entropy, and the second rating is a function of the second utility value and the second entropy, and wherein the first rating is proportional to the first utility value and inversely proportional to the first entropy, and the second rating is proportional to the second utility value and inversely proportional to the second entropy;

determining, by the computing device, whether the first rating is greater than the second rating;

in response to determining that the first rating is greater than the second rating;

compressing, by the computing device, the first region of the received medical data using a first compression technique, and

compressing, by the computing device, the second region of the received medical data using a second compression technique,

wherein the second compression technique is more lossy than the first compression technique; and

in response to determining that the first rating is less than or equal to the second rating;

compressing, by the computing device, the first region of the received medical data using the second compression technique, and

compressing, by the computing device, the second region of the received medical data using the first compression technique,

wherein the first region and the second region are respectively compressed in accordance with a compression technique selected based on at least a measure of how important that region is to the first diagnosis and respective entropy for the first region and the second region.

2. The method of claim 1, wherein at least one of the analyzing or the deriving comprises employing one or more dynamic programming pattern matching or statistical techniques.

3. The method of claim 1 wherein the identifying the unique combination of features in each of the signal segments comprises employing a statistical technique.

4. The method of claim 1, wherein the deriving comprises employing a combinatorial or numerical pattern matching technique.

5. The method of claim 1, further comprising repeating the characterizing, identifying, and deriving until a resulting model does not pass a learn and test criterion.

6. The method of claim 1, further comprising repeating the characterizing, identifying, and deriving until a resulting model does not pass a resubstitution test.

7. The method of claim 6, wherein the resubstitution test includes a jackknife resubstitution test.

8. The method of claim 1, wherein at least one of the first and the second compression techniques is selected by comparing at least one of different compression rates or different feature preservation characteristics after applying the first and second compression techniques to two or more sets of data.

9. The method of claim 8, further comprising building a statistical model based on the application of the first and second compression techniques to the two or more sets of data and employing the statistical model to select the first and second compression techniques.

10. The method of claim 1, wherein the medical data is preprocessed using one or more signal processing techniques.

11. The method of claim 10, wherein the one or more signal processing techniques include at least one of a linear transformation or a difference-based technique.

12. The method of claim 1, wherein the first compression technique is lossless.

13. The method of claim 1, further comprising iteratively identifying additional regions in the received medical data until a stopping criterion is satisfied.

14. The method of claim 13, wherein the stopping criterion includes at least one of a running time of overall procedure or a lack of compression rate improvement.

15. The method of claim 1, wherein the compressing using the first and second compression techniques, respectively for the first region and the second region, comprises applying a dynamic programming technique.

16. The method of claim 1, wherein the compressing using the first compression technique or the second compression technique for the first region is controlled by specifying the first utility value using a joint utility function based on a first utility function and a second utility function, and wherein the joint utility function indicates a relative utility value of the first region if the second utility value of the second region has a particular value.

17. The method of claim 16, wherein the first region relates to a first signal from a first sensor and the second region relates to a second signal from a second sensor.

18. The method of claim 16, wherein each of the first utility function, the second utility function, and the joint utility function is defined using probability density functions.

19. The method of claim 18, further comprising:

combining the first utility function and the second utility function using maximum likelihood expectation (MLE), minimal mean-square expected error (MSEE), or multiple explanation variable statistical models.

20. The method of claim 1, further comprising receiving an iteratively updated patient diagnosis, wherein the first utility value is computed based on a previous patient diagnosis and the second utility value is computed based on a current patient diagnosis.

21. The method of claim 20, further comprising receiving external data and modifying the iteratively updated patient diagnosis based on the external data.

22. The method of claim 21, wherein the external data includes at least one of a geolocation, physical time, or a recent activity of a patient.

23. The method of claim 21, wherein the external data includes a statistical or a numerical quantification of a current or recent epidemic.

24. A non-transitory computer-readable storage medium that stores computer-executable instructions that, in response to execution, cause a computing system to perform a method to compress medical data, the method comprising:

identifying a first region and a second region in the medical data, which represents one or more physical attributes, by;

characterizing a utility of different signal segments by analyzing one or more sets of diagnosis results for a first diagnosis, the utility corresponding to how important each of the signal segments is to the first diagnosis compared to other signal segments,

identifying a unique combination of features in each of the signal segments, and

deriving one or more algorithms for automatic feature identification using at least one of a pattern matching technique or a statistical technique to segment the medical data into the first region and the second region such that each of the first region and the second region has a same utility value;

computing a first entropy for the first region and a second entropy for the second region;

computing a first utility value and a first feature for the first region, and a second utility value and a second feature for the second region, wherein the first utility value is representative of a relative measure of how important the first region is to the first diagnosis compared to the second region, and wherein the second utility value is representative of a relative measure of how important the second region is to the first diagnosis compared to the first region;

computing a first rating for the first region and a second rating for the second region,

wherein the first rating is a function of the first utility value and the first entropy, and the second rating is a function of the second utility value and the second entropy,

the first rating being determined by an equation;

R₁(X)=U₁(X)/H₁(X)

wherein R₁(X) is the first rating, U₁(X) is the first utility value, and H₁(X) is the first entropy, and

the second rating being determined by an equation;

R₂(X)=U₂(X)/H₂(X)

wherein R₂(X) is the second rating, U₂(X) is the second utility value, and H₂(X) is the second entropy; and

determining whether the first rating is greater than the second rating;

in response to determining that the first rating is greater than the second rating;

compressing the first region of the medical data using a first compression technique, and

compressing the second region of the medical data using a second compression technique,

wherein the second compression technique is more lossy than the first compression technique; and

in response to determining that the first rating is less than or equal to the second rating;

compressing the first region of the medical data using the second compression technique, and

compressing the second region of the medical data using the first compression technique,

wherein the first region and the second region are respectively compressed in accordance with a compression technique selected based on at least a measure of how important that region is to the first diagnosis and respective entropy for the first region and the second region.

26. The non-transitory computer-readable storage medium of claim 24, wherein the first compression technique includes a lossless compression technique and the second compression technique includes a lossy compression technique, wherein, in response to the determination that the first rating is greater than the second rating, the lossless compression technique is selected to be used to compress the first region and the lossy compression technique is selected to be used to compress the second region, and wherein, in response to the determination that the second rating is greater than the first rating, the lossy compression technique is selected to be used to compress the first region and the lossless compression technique is selected to be used to compress the second region.

25. A system to compress medical data, the system comprising:

a component configured to receive the medical data that represents one or more physical attributes from a plurality of sensors;

a component configured to identify a first region and a second region in the received medical data by;

characterization of a utility of different signal segments by analysis of one or more sets of diagnosis results for a first diagnosis, the utility corresponding to how important each of the signal segments is to the first diagnosis compared to other signal segments,

identification of a unique combination of features in each of the signal segments, and

derivation of one or more algorithms for automatic feature identification using at least one of a pattern matching technique or a statistical technique to segment the received medical data into the first region and the second region such that each of the first region and the second region has a same utility value;

a component configured to compute;

a first entropy for the first region and a second entropy for the second region,

a first utility value and a first feature for the first region, and a second utility value and a second feature for the second region, wherein the first utility value is representative of a relative measure of how important the first region is to the first diagnosis compared to the second region, and wherein the second utility value is representative of a relative measure of how important the second region is to the first diagnosis compared to the first region, and

a first rating for the first region and a second rating for the second region,

wherein the first rating is a function of the first utility value and the first entropy, and the second rating is a function of the second utility value and the second entropy, and

wherein the first rating is proportional to the first utility value and inversely proportional to the first entropy, and the second rating is proportional to the second utility value and inversely proportional to the second entropy;

a component configured to;

compare different compression rates or different feature preservation characteristics for at least a first compression technique and a second compression technique after application of the first compression technique and the second compression technique to two or more sets of the received medical data; and

determine whether there is another compression technique to utilize;

a component configured to;

in response to a determination that the second compression technique is more lossy than the first compression technique and there is no other compression technique to utilize;

determine whether the first rating is greater than the second rating; and

a component configured to;

in response to a determination that the first rating is greater than the second rating;

compress the first region of the received medical data using the first compression technique; and

compress the second region of the received medical data using the second compression technique; and

in response to a determination that the first rating is less than or equal to the second rating;

compress the first region of the medical received data using the second compression technique; and

compress the second region of the received medical data using the first compression technique,

wherein the first region and the second region are respectively compressed in accordance with a compression technique selected based on at least a measure of how important that region is to the first diagnosis and respective entropy for the first region and the second region.