PsiVision

Encrypted Search Indices and Multi-Key PKI

2010-11-05T09:05:00.000-07:00

As an example of encrypted space operations, consider search indices which are encrypted / hashed.

1. User enters clear text query. Client encrypts and sends to server.
2. Server matches encrypted query to encrypted index. Returns pointers to client indicating result set.
3. Client displays result set.

The pointers, or references to documents, can also be encrypted.

The beauty of this is that the server doesn't suffer so much from the risks associated with aggregation of valuable content. The search server with its index and document pointers is not useful to anyone with inappropriate access to it.

This does raise an interesting question for PKI - can we have a set of data that is encrypted once, but can be decrypted by distinct keys, 1 per distinct authorised client.

You may suggest a simpler solution - why not have an encrypted server disk, with SSL encrypted communication between client and server. The aim here is to have no plain text material at all on the server or on the communication link - not even in memory.

Data Operations in Encryption Space

2010-03-10T05:53:00.000-08:00

A key problem with encrypted data is that it needs to be temporarily decrypted before it can be operated on. This opens up an opportunity for security breach, and more sophisticated attacks do take advantage of data in its decrypted form in a CPU, in memory or in transit across a data bus. It isn't enough for the data to be encrypted on a hard disk.

This raises the question of whether data can be operated on meaningfully whilst still in encryption space.

This would mean operators would need to be transformed from unencrypted space to encrypted space. An advantage of this is that the operations are then also encrypted, reducing the amount of information that can be gleaned by eavesdropping on the operations.

Is there a limited class of operators than can be transformed to encryption space? Is this class sufficiently wide enough to be useful? Is this constrained by the type of encryption?

Interpretation of Latent Semantic Indexing

2007-10-07T17:29:00.000-07:00

Latent Semantic Indexing is the leading approach to information retrieval which aims to uncover some of the underlying meaning of documentsthrough a transformation in the vector document-term model.

The results are indeed better than simple rerieval based on term matching. In particular you may return relevant documents which happen to contain none of the query terms.

But what is the intuitive interpretation of Latent Smenatic Indexing. What is the meaning of the transformed space?

Deduction, Abduction & Induction

2007-06-26T20:36:00.000-07:00

Wikipedia concisely clarifies the distinction between the three forms of inference:

Deductive inference - finding the effect, given the cause and the rule.
Abductive inference - finding the cause, given the rule and the effect.
Inductive inference - finding the rule, given the cause and the effect.


   [ cause ] → → → [ rule ] → → → [ effect ]
  (abduction)     (induction)     (deduction)

Wikipedia gives an example using Hooke's law F=k.x (rule) which relates the force applied (cause) to a spring and its extension (effect). If the force and Hooke's law are known, the elongation of the beam can be deducted. If the elongation and Hooke's law are known, the force acting on the beam can be abducted. If the elongation and the force are known, Hooke's law can be inducted.

Semantic & Syntactic Entailment

2006-12-06T04:12:00.000-08:00

Semantic entailment is the same as the implication that we have seen earlier. If all truth assignments that satisfy a set of forumulae S also satisfy A, then S semantically entails A. That is, S→A.

Syntactic entailment is slighly different. If A can be derived from S using a finite application of the propositional inference rules, then S syntactically entails A.

What does it mean if only one of the above applies?

Calculus of Propositional Logic

2006-12-05T17:10:00.000-08:00

Propositional logic indeed has a calculus which allows us to verify arguments and prove theorems.

Common algebra has axiomatic inference rules which allow the derivation of new true formulae from assumed true formulae, either as continuations of an existing formula, or as a combination of multiple formulae. Similarly, the propositional calculus provides inference rules for propositional logic.

Inference Rules

The text Schaum's Outline of Logic presents these rules and provides worked examples of their use.

The following summarises the 10 rules of propositonal inference rules. All these rules either introduce or eliminate a propositional logic operator.

The first eight are non-hypothetical:

* Negation Elimination
   From ¬¬p, infer p.
* Conjunction Elimination
   From (p ∧ q), infer p
   From (p ∧ q), infer q.
* Conjunction Introduction
   From p, q, infer (p ∧ q).
* Disjunction Introduction
   From p, infer (p ∨ q)
   From p, infer (q ∨ p).
* Disjunction Elimination
   From (p ∨ q), (p → r), (q → r), infer r.
* Biconditional Introduction
   From (p → q), (q → p), infer (p ↔ q).
* Biconditional Elimination
   From (p ↔ q), infer (p → q)
   From (p ↔ q), infer (q → p).
* Conditional Elimination
   From p, (p → q), infer q.

The final two are hypothetical inference rules in that they temporarily assume the truth of a hypothesis.

* Negation Introduction
   If hypothesis (p→q) leads to (p→ ¬q), infer ¬p.
* Conditional Introduction
   If hypothesis p allows a proof of q, infer (p → q).

Truth Table for Implication

2006-11-28T09:10:00.000-08:00

I was surprised the binary implication operator (→), also called the conditional, has a truth table, just as the AND and OR logical operators do. It is as follows:

That is, we can only say something about B if A is true. There is a similar table for the binary biconditional operator (↔):

This means we can determine truth tables for compound statements such as A→(B→C).

Entailment, Implication, Induction

2006-05-04T17:36:00.000-07:00

What is the difference between logical and semantic entailment? How is it different from equality and implication? Induction, unlike deduction, generates new knowledge, but how can we best approximate human induction algorithmically?

The Geometry of Information Retrieval fails to make clear its discussion of logic and how logical relations are related to information retrieval. As such, I'll be working through Logic for Mathematicians and Logic, Induction and Sets, before returning to The Geometry of Information Retrieval.

Human - Computer Agreement

2006-04-11T08:47:00.000-07:00

Speaking with a friend it became clear that there might be a limit to the performance from any computer algorithm aiming to emulate intelligence.

Disagreement

Two or more humans can disagree on, for example, the relevance of an information retrieval operation, or the semantic content of a visual image. If human minds have trouble agreeing on the semantic content of what they observe, can we then expect a computer algorithm to produce results that generate more agreement than a set of human judges?

The Geometry of Information Retrieval

2006-03-20T08:51:00.000-08:00

Currently reading through The Geometry of Information Retrieval which promises a much needed theoretical unification of the logical, probabilistic and vector space models of information retrieval. It provides this foundation using the language of quantum mechanics, where documents are objects in Hilbert space, and where interactions/measurements are Hermitian operators on this space, and where state vectors collapse upon interaction.

The derivation of probability is not that surprising - distribute probability over the number/magnitude of eigenvectors of the interaction operators. However, of much more interest will be how the structure of the, possibly non-Boolean, logic is derived from this space and how this relates to measurements on the space.

The Nature of the Problem

2006-03-10T04:14:00.000-08:00

Structured Data

Chatting with a friend yesterday, it became apparent that what is meant by structured data is not clear. As yet, there is no set of sample data to illustrate what is meant by this.

What is clear is that the structured data is richer than simple multi-dimensional vectors. For example, it is hoped that the data structure or its description allows for the expression of orderings on attributes; short < medium < long.

An established process that works with rich and structured data instances is Inductive Logic Programming (ILP), a process for inducing descriptive statements for a set of logical clauses. An explanation of this working with the well known trains data set is given by this presentation by Peter Flach. Another example is the determination of carcinogenic compounds, and a worked example is presented here.

Minimal Expressiveness

As a general word of caution it should be noted that the language to describe the data or the constraints, should be minimally expressive. Too much expressiveness leads to weak results or uncessary computational complexity.

Distance Metric

The core of the problem then, is not the particular clustering algorithm to be used, but rather the notion of distance between instances of such rich or structured data. Such a metric must take into account the additional constraints such as orderings, or more general relations between attributes, and other constraints that can be expressed. In ILP the expression of such constraints is with logical clauses, the same language for desribing the data instances themselves.

So in general, what is required is a data structure and an associated representation language that allows for the general expression of relations or constraints over the elements of that data structure, as well as the usual value of those elements.

Partitional or Hierarchical Clustering?

2006-03-07T04:13:00.000-08:00

Previously most work related to clustering in the image domain has been partitional (or fuzzy partitional). I've not yet thought through the merits of hierarchical clustering as applied to the image domain or to the clustering of structured data.

Partitional clustering simply slices the data space into clusters. However, hierarchical clustering provides more information. It tells you what clusters there would be depending on the level of granularity asked for. You can have one big cluster that covers all the data instances, and as you increase the granularity you see the sub-clusters separating off. This information is usually and naturally presented in the form of a dendogram.

See wikipedia for more information on these distinctions: http://en.wikipedia.org/wiki/Data_clustering

Truly Unsupervised Clustering Algorithm

2006-02-06T14:57:00.000-08:00

The first problem is the clustering algorithm itself. The most widely used algorithms need to be told how many clusters they are searching for and this means the algorithm is not entirely unsupervised.

Refinements

The classic algorithm is the k-means and many are variants of this simple procedure. Some of these are simply refinements which effectively lower the margin of error on the results. Some refinements have the side effect of producing correct clusters in a robust manner, even if the initial number of clusters sought is set to the wrong value. I confirmed this positive behaviour in the Fayyad set of refinements to the basic k-means algorithm.

Beneficial Noise

Another surprising result was that the accuracy of clustering results was significantly improved if the, possibly multi-dimensional, data was extended by another dimension with random values. The reasoning behind this effect is that the random noise actually smooths the objective functions, down which the clustering algorithm descends.

I'll investigate this affect again to confirm its validity. I've not seen others refer to it, despite a quick search at the time.

Truly Unsupervised Clustering Algorithms

However the academic publications have started mentioning other methods which don't require the number of clusters to be preset, and i'll have a look at these.

Introduction

2006-02-04T16:08:00.000-08:00

This blog will act as a diary and notebook of my aim to create a method to perform clustering of structured data, incorporating domain knowledge into the algorithm or data structures, and with particular application to the clustering of images.