On hash functions application in cryptography vs feature

Question

I have only started learning feature hashing so I need help in understanding if I can apply the hash function expressed mathematically as https://en.wikipedia.org/wiki/Tent_map.

and one such application of Tent map is in cryptography -- Paper 1: Implementation of Hash Function Based On Neural Cryptography download link.

In feature hashing, Let x be a data point of D dimension i.e., it has D number of elements. In feature hashing, a linear hash function is used to transform the D dimensional data point to a lower k dimensional data point in such a way that the distances in reduced dimension feature space is preserved. The hash bit k is obtained through the operation, h_k(x) = sign(y(x)) = sign(f(w_k^Tx +b)). The output h(x) is 0 or 1 bit.

In essence, we are classifying whether the data point x belongs to 0 or 1 class by creating random hyperplanes.

There are various choices of hash functions in feature hashing for dimensionality reduction : f = tanh() or simply random sampling to obtain the hyperplanes. Another choice is to use kernel functions when the data is not linearly separable. Such a hashing function /technique is implemented using Kernels and one popular choice is to use the Gaussian RBF as the kernel function.

---

• Question : In paper 1, the Authors have used the Asymmetric Tent Map https://en.wikipedia.org/wiki/Tent_map which is piecewise linear on the unit interval as the transfer function. To me the formulation of hashing in this paper using Tent Map appears similar to the hash equation (1). How can I apply the piecewise linear function i.e., apply this map to create hyperplanes in order to do feature hashing?

  Or am I mixing the two concepts?

Answer 1

Feature hashing needs a hash function, so that it will be able to do ... its hashing trick!

It will hash every image, thus you want a hash function that will take an image (i.e. a feature/vector of D dimensions) and produce a single integer value.

---

Note: I think you are confused with the second single-bit output hash function ξ, w.r.t. to the fact that the result will be binary. ξ() is easy to grasp, once you get the flow of the initial approach, since this is just an optimization to decrease hash collisions.

---

Now let's take a look at how Tent_map_2 behaves:

which as you see, is a real-valued function.

It takes one number as input and gives one number as output. As a result a naive Tent Map cannot hash a vector (an image in our case). There are many ways to augment the Tent Map to handle a vector, with the simplest to be:

Implement a Tent Map function, e.g. tentMap(), that will implement the logic of Tent Map. You could treat the returned values of Tent Map that are less than 0.5 as 0 and the rest (i.e. >= 0.5) as 1, but you could do more complex things if you like.

Now for an image, you could do:

def tentMapVector(image):
    results = []
    for i in image:
        results.append(tentMap(i))
    # now 'results' contains D integers
    # it needs to be hashed to a single integer
    # you could treat 'results' as a string and
    # use one of the numerous hash function to hash that string
    return hashString(results)

and you are ready to go! tentMapVector() should replace hash() in Wikipedia's implementation. You may want to read its example, really helpful.

---

It doesn't seem like Feature requires a dimensionality reduction, it should work without a reduction, but when you are data leave in a high dimensional space, which is usually the case with images, you should try reducing the dimensions (for example fro 256 to 128).

You could, for example, use the PCA() from scikit-learn, or any other library.