text:
A Memory-Efficient Sketch Method for EstimatingHigh Similarities in Streaming Sets

A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets

Pinghui Wang, Yiyan Qi, Yuanming Zhang, Qiaozhu Zhai, Chenxu Wang,  and  John C.S. Lui, Xiaohong Guan NSKEYLAB, Xi’an Jiaotong University, Xi’an, ChinaShenzhen Research Institute of Xi’an Jiaotong University, Shenzhen, ChinaThe Chinese University of Hong Kong, Hong KongDepartment of Automation and NLIST Lab, Tsinghua University, Beijing, China
Abstract.

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases, machine learning, and information retrieval. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications such as similarity search and large scale learning. Its two compressed versions, -bit MinHash and Odd Sketch, can significantly reduce the memory usage of the original MinHash method, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion and cardinality is unknown or even infinite, unfortunately, -bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we design a memory efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared to MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. We also provide a simple yet accurate estimator for inferring Jaccard similarity from MaxLogHash sketches. In addition, we derive formulas for bounding the estimation error and determine the smallest necessary memory usage (i.e., the number of registers used for a MaxLogHash sketch) for the desired accuracy. We conduct experiments on a variety of datasets, and experimental results show that our method MaxLogHash is about 5 times more memory efficient than MinHash with the same accuracy and computational cost for estimating high similarities.

Streaming algorithms;Sketch;Jaccard coefficient similarity
Pinghui Wang and Yiyan Qi contributed equally to this work.
Corresponding Author.
copyright: acmcopyrightjournalyear: 2019copyright: acmcopyrightconference: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; August 4–8, 2019; Anchorage, AK, USAbooktitle: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’19), August 4–8, 2019, Anchorage, AK, USAprice: 15.00doi: 10.1145/3292500.3330825isbn: 978-1-4503-6201-6/19/08ccs: Mathematics of computing Probabilistic algorithmsccs: Information systems Similarity measuresccs: Theory of computation Sketching and sampling

1. Introduction

Data streams are ubiquitous in nature. Examples range from financial transactions to Internet of things (IoT) data, network traffic, call logs, trajectory logs, etc. Due to the nature of these applications which involve massive volume of data, it is prohibitive to collect the entire data streams, especially when computational and storage resources are limited (Li2018Approximate, ). Therefore, it is important to develop memory efficient methods such as sampling and sketching techniques for mining large streaming data.

Many datasets can be viewed as collections of sets and computing set similarities is fundamental for a variety of applications in areas such as databases, machine learning, and information retrieval. For example, one can view each mobile device’s trajectory as a set and each element in the set corresponds to a tuple of time and the physical location of the device at time . Then, mining devices with similar trajectories is useful for identifying friends or devices belonging to the same person. Other examples are datasets encountered in computer networks, mobile phone networks, and online social networks (OSNs), where learning user similarities in the sets of users’ visited websites on the Internet, connected phone numbers, and friends on OSNs is fundamental for applications such as link prediction and friendship recommendation.

One of the most popular set similarity measures is the Jaccard similarity coefficient, which is defined as for two sets and . To handle large sets, MinHash (or, minwise hashing) (Broder2000, ) is a powerful set similarity estimation technique, which uses an array of registers to build a sketch for each set. Its accuracy only depends on the value of and the Jaccard similarity of two sets of interest, and it is independent from the size of two sets. MinHash has been successfully used for a variety of applications, such as similarity search (BroderSEQUENCES1997, ), compressing social networks (ChierichettiKDD2009, ), advertising diversification (GollapudiWWW2009, ), large scale learning (LiNIPS2011, ), and web spam detection (UrvoyTOW2008, ). Many of these applications focus on estimating similarity values close to 1. Take similar document search in a sufficiently large corpus as an example. For a corpus, there may be thousands of documents which are similar to the query document, therefore our goal is not just to find similar documents, but also to provide a short list (e.g., top-10) and ranking of the most similar documents. For such an application, we need effective methods that are very accurate and memory-efficient for estimating high similarities. To achieve this goal, there are two compressed MinHash methods, -bit MinHash (PingWWW2010, ) and Odd Sketch (MitzenmacherWWW14, ), which were proposed in the past few years to further reduce the memory usage of the original MinHash by dozens of times, while to provide comparable estimation accuracy especially for large similarity values. However, we observe that these two methods fail to handle data streams (the details will be given in Section 3).

To solve the above challenge, recently, Yu and Weber (YuArxiv2017, ) develop a method, HyperMinHash. HyperMinHash consists of registers, whereas each register has two parts, an FM (Flajolet-Martin) sketch (Flajolet1985, ) and a -bit string. The -bit string is computed based on the fingerprints (i.e., hash values) of set elements that are mapped to the register. Based on HyperMinHash sketches of two sets and , HyperMinhash first estimates and then infers the Jaccard similarity of and from the number of collisions of -bit strings given . Later in our experiments, we demonstrate that HyperMinHash not only exhibits a large bias for high similarities, but it is also computationally expensive for estimating similarities, which results in a large estimation error and a big delay in querying highly similar sets. More importantly, it is difficult to analytically analyze the estimation bias and variance of HyperMinHash, which are of great value in practice–the bias and variance can be used to bound an estimate’ error and determine the smallest necessary sampling budget (i.e., ) for a desired accuracy. In this paper, we develop a novel memory efficient method, MaxLogHash, to estimate Jaccard similarities in streaming sets. Similar to MinHash, MaxLogHash uses a list of registers to build a compact sketch for each set. Unlike MinHash which uses a 64-bit (resp. 32-bit) register for storing the minimum hash value of 64-bit (resp. 32-bit) set elements, our method MaxLogHash uses only 7-bit register (resp. 6-bit register) to approximately record the logarithm value of the minimum hash value, and this results in 9 times (resp. 5 times) reduction in memory usage. Another attractive property is that our MaxLogHash sketch can be computed incrementally, therefore, MaxLogHash is able to handle streaming-sets. Given any two sets’ MaxLogHash sketches, we provide a simple yet accurate estimator for their Jaccard similarity, and derive exact formulas for bounding the estimation error. We conduct experiments on a variety of publicly available datasets, and experimental results show that our method MaxLogHash reduces the amount of memory required for MinHash by 5 folds to achieve the same desired accuracy and computational cost.

The rest of this paper is organized as follows. The problem formulation is presented in Section 2. Section 3 introduces preliminaries used in this paper. Section 4 presents our method MaxLogHash. The performance evaluation and testing results are presented in Section 5. Section 6 summarizes related work. Concluding remarks then follow.

2. Problem Formulation

For ease of reading and comprehension, we say that each set belongs to a user, elements in the set are items (e.g., products) that the user connects to. Let denote the set of users and denote the set of all items. Let denote the user-item stream of interest, where is the element of occurred at discrete time , and are the element’s user and item, which represents a connection from user to item . We assume that has no duplicate user-item pairs111Duplicated user-item pairs can be easily checked and filtered using fast and memory-efficient techniques such as Bloom filter (BloomACMCommun1970, )., that is, when . Let be the item set of user , which consists of items that user connects to before and including time . Let denote the union of two sets and , that is, Similarly, we define the intersection of two sets and as Then, the Jaccard similarity of sets and is defined as

 J(t)u1,u2=|∩(t)(u1,u2)||∪(t)(u1,u2)|,

which reflects the similarity between users and . In this paper, we aim to develop a fast and accurate method to estimate for any two users and over time, and to detect pairs of high similar users. When no confusion arises, we omit the superscript to ease exposition.

3. Preliminaries

In this section, we first introduce MinHash (Broder2000, ). Then, we elaborate two state-of-the-art memory-efficient methods -bit MinHash (PingWWW2010, ) and Odd Sketch (MitzenmacherWWW14, ) that can decrease the memory usage of the original MinHash method. At last, we demonstrate that both -bit MinHash and Odd Sketch fail to handle streaming sets.

3.1. MinHash

Given a random permutation (or hash function222MinHash assumes no hash collisions.) from elements in to elements in , i.e., a hash function maps integers in to distinct integers in at random. Broder et al. (Broder2000, ) observed that the Jaccard similarity of two sets equals

 JA,B=|∩(A,B)||∪(A,B)|=P(min(π(A))=min(π(B))),

where . Therefore, MinHash uses a sequence of independent permutations and estimates as

 ^JA,B=∑ki=11(min(π1(A))=min(π1(B))k,

where is an indicator function that equals 1 when the predicate is true and 0 otherwise. Note that is an unbiased estimator for , i.e., , and its variance is

 Var(^JA,B)=JA,B(1−JA,B)k.

Therefore, instead of storing a set in memory, one can compute and store its MinHash sketch , i.e.,

 SA=(min(π1(A)),…,min(πk(A))),

which reduces the memory usage when . The Jaccard similarity of any two sets can be accurately and efficiently estimated based on their MinHash sketches.

3.2. b-bit MinHash

Li and König (PingWWW2010, ) proposed a method, -bit MinHash, to further reduce the memory usage. -bit MinHash reduces the memory required for storing a MinHash sketch from or bits333A 32- or 64-bit register is used to store each , . to bits. The basic idea behind -bit MinHash is that the same hash values give the same lowest bits while two different hash values give the same lowest bits with a small probability . Formally, let denote the lowest bits of the value of for a permutation . Define the -bit MinHash sketch of set as

 S(b)A=(min(b)(π1(A)),…,min(b)(πk(A))).

To mine set similarities, Li and König (PingWWW2010, ) first compute for each set , and then store its -bit MinHash sketch . At last, the Jaccard similarity is estimated as

 ^J(b)A,B=∑ki=11(min(b)(πi(A))=min(b)(πi(B)))−k/2bk(1−1/2b).

is also an unbiased estimator for , and its variance is

 Var(^J(b)A,B)=1−JA,Bk(JA,B+12b−1).

3.3. Odd Sketch

Mitzenmacher et al. (MitzenmacherWWW14, ) developed a method Odd Sketch, which is more memory efficient than -bit MinHash when mining sets of high similarity. Odd Sketch uses a hash function that maps each tuple , , to an integer in at random. For a set , its odd sketch consists of bits. Function maps tuples into bits of at random. , , is the parity of the number of tuples that are mapped to the bit of . Formally, is computed as

 S(Odd)A[j]=⊕i=1,…,k1(h(i,min(πi(A)))=j),1≤j≤z.

The Jaccard similarity is then estimated as

 ^J(Odd)A,B=1+z4kln⎛⎝1−2∑zi=1S(Odd)A[j]⊕S(Odd)B[j]z⎞⎠.

Mitzenmacher et al. demonstrate that is more accurate than under the same memory usage (refer to (MitzenmacherWWW14, ) for details of the error analysis of ).

3.4. Discussion

MinHash can be directly applied to stream data. We can easily find that MinHash sketch can be computed incrementally. That is, one can compute the MinHash sketch of set from the MinHash sketch of set as

 min(π(A∪{v}))=min(min(π(A)),π(v)).

Variants -bit MinHash and Odd Sketch cannot be used to handle streaming sets. Let denote the lowest bits of . Then, one can easily show that

 min(b)(π(A∪{v}))≠min(min(b)(π(A)),π(b)(v)).

It shows that computing requires the hash value of each . In addition, we observe that cannot be approximated as , which can be computed incrementally, because equals 0 with a high probability when . Similarly, we cannot compute the odd sketch of a set incrementally. Therefore, both -bit MinHash and Odd Sketch fail to deal with streaming sets.

4. Our Method

4.1. Basic Idea

Let be a function that maps any element in to a random number in range . i.e., . Define the log-rank of with respect to hash function as We compute and store

 MaxLog(h(A))=maxv∈Ar(v)=maxv∈A⌊−log2h(v)⌋.

Let us now develop a simple yet accurate method to estimate Jaccard similarity of streaming sets based on the following properties of function .
Observation 1. can be represented by an integer of no more than bits with a high probability. For each , we have , and thus supported on the set , that is,

 P(r(v)=j)=12j+1,P(r(v)

Then, one can easily find that

 P(MaxLog(h(A))≤2⌈log2log2|I|⌉−1)=(1−122⌈log2log2|I|⌉)|A|.

For example, when and , we only require 6 bits to store with probability at least 0.999.

Observation 2. can be computed incrementally. This is because

 MaxLog(h(A∪{v}))=max(MaxLog(h(A)),⌊−log2h(v)⌋).

Observation 3. can be easily estimated from and with a little additional information. We find that

 γ=P(MaxLog(h(A))≠%MaxLog(h(B)))=+∞∑j=1|A∖B|2j+1(1−12j+1)|A∖B|−1(1−12j)|B|++∞∑j=1|B∖A|2j+1(1−12j+1)|B∖A|−1(1−12j)|A|.

Due to the limited space, we omit the details of how is derived. Similar to MinHash, we have . Therefore, we have . Although can be estimated similar to MinHash using hash functions , that is,

 E(γ)=∑ki=11(MaxLog(hi(A))≠MaxLog(hi(B)))k,

unfortunately, it is difficult to compute from . To solve this problem, we observe

 P(MaxLog(h(A))≠MaxLog(h(B))∧δA,B=1)≈0.7213(1−JA,B),

where indicates that there exists one and only one element in of which log-rank equals .

Based on the above three observations, we propose to incrementally and accurately estimate the value of using hash functions . Then, we easily infer the value of .

4.2. Data Structure

The MaxLogHash sketch of a user , i.e., , consists of bit-strings, where each bit-string , has two components, and , i.e., At any time , records the maximum hash value of items in with respect to hash function , i.e., , where refers to the set of items that user connected to before and including time ; consists of 1 bit and its value indicates whether there exists one and only one item such that . As we mentioned, we can use bits to record the value of with a high probability (very close to 1). When , we use a hash table to record tuples for all users.

4.3. Update Procedure

For each user , when it first connects with an item in stream , we initialize the MaxLogHash sketch of user as where . That is, we set indicator and register . For any other item that user connects to after the first item , i.e., an user-item pair occurring on stream after the user-item pair , we update it as follows: We first compute the log-rank of item , i.e., , . When is smaller than , we perform no further operations for updating the user-item . When , it indicates that at least two items in has a log-rank value . Therefore, we simply set . When , we set .

4.4. Jaccard Similarity Estimation

Define variables

 χu1,u2[i]=1(mu1[i]≠mu2[i]),i=1,…,k,
 ψu1,u2[i]=⎧⎪⎨⎪⎩su1[i],mu1[i]>mu2[i]su2[i],mu1[i]

Let . Note that indicates that there exists one and only one element in set of which log-rank equals with respect to function . Then, we have the following theorem.

Theorem 1 ().

For non-empty sets and , we have , , when . Otherwise, we have

 P(δu1,u2[i]=1)=α|∪(u1,u2)|(1−Ju1,u2),i=1,…,k,

where

Proof. Let be the maximum log-rank of all items in . When two items and in or has the log-rank value , we easily find that . When only one item in and only one item in have the log-rank value , we easily find that . Let

 Δ(u1,u2)=(Iu1∖Iu2)∪(Iu2∖Iu1)=∪(u1,u2)∖∩(u1,u2).

Then, we find that event happens (i.e., ) only when one item in has a log-rank value larger than all items in . For any item , we have and so , supported on the set . Based on the above observations, when , we have

 P(δu1,u2[i]=1∧r∗=j)=∑w∈Δ(u1,u2)P(ri(w)=j)∏v∈∪(u1,u2)∖{w}P(ri(v)

Therefore, we have

 P(δu1,u2[i]=1)=+∞∑j=0P(δi=1∧r∗=j)=∑w∈Δ(u1,u2)P(rw=j)∏v∈∪(u1,u2)∖{w}P(rv

where the last equation holds because .

Define variable From Theorem 1, the expectation of is computed as

 (1) E(^k) = E(k∑i=11(δu1,u2[i]=1)) = k∑i=1E(1(δu1,u2[i]=1)) = kα|∪(u1,u2)|(1−Ju1,u2).

Therefore, we have

 Ju1,u2=1−E(^k)kα|∪(u1,u2)|.

Note that the cardinality of set (i.e. ) is unknown. To solve this challenge, we find that

 αn=n2+∞∑j=112j(1−12j)n−1=n2+∞∑j=112jn−1∑l=0(n−1l)(−12j)n−l−1=n2n−1∑l=0(−1)n−l−1(n−1l)+∞∑j=112j(n−l)=n2n−1∑l=0(−1)n−l−1(n−1l)12n−l−1.

Figure 1 shows that the value of , We easily find that when . Therefore, we estimate as

 ^Ju1,u2=1−^kkα.

4.5. Error Analysis

The error of our method MaxLogHash is shown in the following theorem.

Theorem 2 ().

For any users , we have

 E(^Ju1,u2)−Ju1,u2=(1−β|∪(u1,u2)|)(1−Ju1,u2),

where . The variance of is computed as

 Var(^Ju1,u2)=β|∪(u1,u2)|(1−Ju1,u2)(α−1−β|∪(u1,u2)|(1−Ju1,u2))k.

When , we have , and so and .

Proof. From equation (1), we easily have

 E(^Ju1,u2)=E(1−^kkα)=1−kα|∪(u1,u2)|(1−Ju1,u2)kα=β|∪(u1,u2)|Ju1,u2+1−β|∪(u1,u2)|.

To derive , we first compute

 E(^k2) = E⎛⎝(k∑i=11(δu1,u2[i]=1))2⎞⎠ = k∑i=1E((1(δu1,u2[i]=1))2) +∑i≠j,1≤i,j≤kE(1(δu1,u2[i]=1)1(δu1,u2[j]=1)) = kα|∪(u1,u2)|(1−Ju1,u2)+k(k−1)α2|∪(u1,u2)|(1−Ju1,u2)2.

Then, we have

 Var(^k)=E(^k2)−(E(^k))2 (2) =kα|∪(u1,u2)|(1−Ju1,u2)(1−α|∪(u1,u2)|(1−Ju1,u2)).

From the definition of , we have

 Var(^Ju1,u2)=Var(1−^kkα)=Var(^k)k2α2.

Then, we easily obtain a closed-form formals of from equation (4.5).

4.6. Reduce Processing Complexity

Inspired by OPH (one permutation hashing) (Linips2012, ), which significantly reduces the time complexity of MinHash for processing each element in the set, we can use a hash function which splits items in into registers at random, and each register , , records as well as the value of indicator , which is similar to the regular MaxLogHash method. We name this extension as MaxLogOPH. MaxLogOPH reduces the time complexity of processing each item from to . When , our experiments demonstrate that MaxLogOPH is comparable to MaxLogHash in terms of accuracy.

5. Evaluation

The algorithms are implemented in Python, and run on a computer with a Quad-Core Intel(R) Xeon(R) CPU E3-1226 v3 CPU 3.30GHz processor. To demonstrate the reproducibility of the experimental results, we make our source code publicly available.

5.1. Datasets

For simplicity, we assume that elements in sets are 32-bit numbers, i.e., . We evaluate the performance of our method MaxLogHash a variety of datasets.

1) Synthetic datasets. Our synthetic datasets consist of set-pairs and with various cardinalities and Jaccard similarities. We conduct our experiments on the following two different settings:

Balanced set-pairs (i.e., ). We set and vary in . Specially, we generate set by randomly selecting different numbers from and generate set by randomly selecting different numbers from set and different numbers from set . In our experiments, we set by default.

Unbalanced set-pairs (i.e., ). We set and , where we vary . Specially, we generate set by randomly selecting different numbers from and generate set by selecting different elements from .

2) Real-world datasets. Similar to (MitzenmacherWWW14, ), we evaluate the performance of our method on the detection of item-pairs (e.g., pairs of products) that always appear together in the same records (e.g., transactions). We conduct experiments on two real-world datasets: MUSHROOM and CONNECT, which are also used in (MitzenmacherWWW14, ). We generate a stream of item-record pairs for each dataset, where a record can be viewed as a transaction and items in the same record can be viewed as products bought together. For each record in the dataset of interest and every item in , we append an element to the stream of item-record pairs. In summary, MUSHROOM and CONNECT have and records, and distinct items, and and item-record pairs, respectively.

5.2. Baselines

Our methods use -bit registers to build a sketch for each set. We compare our methods with the following state-of-the-art methods: MinHash (Broder2000, ). MinHash builds a sketch for each set. A MinHash sketch consists of 32-bit registers.
HyperLogLog (FlajoletAOFA07, ). A HyperLogLog sketch consists of 5-bit registers, and is originally designed for estimating a set’s cardinality. One can easily obtain a HyperLogLog sketch of by merging the HyperLogLog sketches of sets and and then use the sketch to estimate . Therefore, HyperLogLog can also be used to estimate by approximating .
HyperMinHash (YuArxiv2017, ). A HyperMinHash sketch consists of -bit registers and -bit registers. The first -bit registers can be viewed as a HyperLogLog sketch. To guarantee the performance for large sets (including up to elements), we set .

5.3. Metrics

We evaluate both efficiency and effectiveness of our methods in comparison with the above baseline methods. For efficiency, we evaluate the running time of all methods. Specially, we study the time for updating each set element and estimating set similarities, respectively. The update time determines the maximum throughput that a method can handle, and the estimation time determines the delay in querying the similarity of set-pairs. For effectiveness, we evaluate the error of estimation with respect to its true value using metrics: bias and root mean square error (RMSE), i.e., and . Our experimental results are empirically computed from independent runs by default. We further evaluate our method on the detection of association rules, and use precision and recall to evaluate the performance.

5.4. Accuracy of Similarity Estimation

MaxLogHash vs MinHash and HyperMinHash. From Figures 2 (a)-(d), we see that our method MaxLogHash gives comparable results to MinHash and HyperMinHash with . Specially, the RMSEs of these three methods differ within and continually decrease as the similarity increases. The RMSE of HyperMinHash with significantly increases as increases. We observe that the large estimation error occurs because HyperMinHash exhibits a large estimation bias. Figures 2 (e)-(h) show the bias of our method MaxLogHash in comparison with MinHash and HyperMinHash. We see that the empirical biases of MaxLogHash and MinHash are both very small and no systematic biases can be observed. However, HyperMinHash with shows a significant bias and its bias increases as the similarity value increases. To be more specific, its bias raises from to when the similarity increases from to . One can increase to reduce the bias of HyperMinHash. However, HyperMinHash with large desires more memory space. For example, HyperMinHash with has comparable accuracy but requires times more memory space compared to our method MaxLogHash. Compared with MinHash, MaxLogHash gives a times reduction in memory usage while achieves a similar estimation accuracy. Later in Section 5.6, we show that our method MaxLogHash has a computational cost similar to Minhash, but is several orders of magnitude faster than HyperMinHash when estimating set similarities.

MaxLogHash vs HyperLogLog. To make a fair comparison, we allocate the same amount of memory space, bits, to each of MaxLogHash and HyperLogLog. As discussed in Section 4, the attractive property of our method MaxLogHash is its estimation error is almost independent from the cardinality of sets and , which does not hold for HyperLogLog. Figure 3 shows the RMSEs of MaxLogHash and HyperLogLog on sets of different sizes. We see that the RMSE of our method MaxLogHash is almost a constant. Figures 3 (a) and (b) show the performance of HyperLogLog suddenly degrades when and the cardinalities of and are around , because HyperLogLog uses two different estimators for cardinalities within two different ranges respectively (FlajoletAOFA07, ). As a result, our method MaxLogHash decreases the RMSE of HyperLogLog by up to . As shown in Figures 3 (c) and (d), similarly, the RMSE of our method MaxLogHash is about 2.5 times smaller than HyperLogLog when and the cardinalities of and are around .

MaxLogHash vs MaxLogOPH. As discussed in Section 4.6, the estimation error of MaxLogOPH is comparable to MaxLogHash when is far smaller than the cardinalities of two sets of interest. We compare MaxLogOPH with MaxLogHash on sets with increasing cardinalities to provide some insights. As shown in Figure 4, MaxLogOPH exhibits relatively large estimation errors for small cardinalities. When and the cardinality increases to (about ), we see that MaxLogOPH achieves similar accuracy to MaxLogHash. Later in Section 5.6, MaxLogOPH significantly accelerates the speed of updating elements compared with MaxLogHash.

5.5. Accuracy of Association Rule Learning

In this experiment, we evaluate the performance of our method MaxLogHash, MinHash, and HyperMinHash on the detection of items (e.g., products) that almost always appear together in the same records (e.g., transactions). We conduct the experiments on real-world datasets: MUSHROOM and CONNECT. We first estimate all pairwise similarities among items’ record-sets, and retrieve every pair of record-sets with similarity . As discussed previously (results in Figure 3), HyperLogLog is not robust, because it exhibits large estimation errors for sets of particular sizes. Therefore, in what follows we compare our method MaxLogHash only with MinHash and HyperMinHash. As shown in Figure 5, MaxLogHash gives comparable precision and recall to MinHash and HyperMinHash with . We note that MaxLogHash gives up to and times reduction in memory usage in comparison with MinHash and HyperMinHash respectively.

5.6. Efficiency

We further evaluate the efficiency of our method MaxLogHash and its extension MaxLogOPH in comparison with MinHash and HyperLogLog. Specially, we present the time for updating each coming element and computing Jaccard similarity, respectively. We conduct experiments on synthetic balanced datasets. We omit the similar results for real-world datasets and synthetic unbalanced datasets. Figure 6 (a) shows that the update time of MaxLogOPH and HyperLogLog is almost a constant and our method outperforms other baselines. The update time of HyperMinHash is almost irrelevant to its parameter and thus we only plot the curve for . Specially, MaxLogOPH is about and times faster than HyperMinHash and MinHash. Figure 6 (b) shows that our methods MaxLogHash and MaxLogOPH have estimation time similar to MinHash, while they are about times faster than HyperLogLog and 4 to 5 orders of magnitude faster than HyperMinHash.

6. Related Work

Jaccard similarity estimation for static sets. Broder et al. (Broder2000, ) proposed the first sketch method MinHash to compute the Jaccard similarity of sets, which builds a sketch consisting of registers for each set. To reduce the amount of memory space required for MinHash, (PingWWW2010, ; MitzenmacherWWW14, ) developed methods -bit MinHash and Odd Sketch, which are dozens of times more memory efficient than the original MinHash. The basic idea behind -bit MinHash and Odd Sketch is to use probabilistic methods such as sampling and bitmap sketching to build a compact digest for each set’s MinHash sketch. Recently, several methods (Linips2012, ; ShrivastavaUAI2014, ; ShrivastavaICML2014, ; ShrivastavaICML2017, ) were proposed to reduce the time complexity of processing each element in a set from to .

Weighted similarity estimation for static vectors. SimHash (or, sign normal random projections) (CharikarSTOC2002, ) was developed for approximating angle similarity (i.e., cosine similarity) of weighted vectors. CWS (Manasse2010, ; HaeuplerMT2014, ), ICWS (IoffeICDM2010, ), 0-bit CWS (LiKDD2015, ), CCWS (WuICDM2016, ), Weighted MinHash (ShrivastavaNIPS2016, ), PCWS (WuWWW2017, ), and BagMinHash (Ertl2018, ) were developed for approximating generalized Jaccard similarity of weighted vectors666The Jaccard similarity between two positive real value vectors and is defined as


text:
The Production of Electric Bulbs in Different Factories is Shown in the Following Table. Find the Median of the Productions. - Algebra

Sum

The production of electric bulbs in different factories is shown in the following table. Find the median of the productions.

 No. of bulbs produced (Thousands) 30 - 40 40 - 50 50 - 60 60 - 70 70 - 80 80 - 90 90 - 100 No. of factories 12 35 20 15 8 7 8

Solution

 Class (Number of bulbs produced in thousands) Frequency(Number of factories)fi Cumulaive frequencyless than theupper limit 30 - 40 12 12 40 - 50 35 47 50 - 60(Median Class) 20 67 60 - 70 15 82 70 - 80 8 90 80 - 90 7 97 90 - 100 8 105 N = 105

From the above table, we get
L (Lower class limit of the median class) = 50
N (Sum of frequencies) = 105
h (Class interval of the median class) = 10
f (Frequency of the median class) = 20
cf (Cumulative frequency of the class preceding the median class) = 47
Now, Median = $L + \left( \frac{\frac{N}{2} - cf}{f} \right) \times h$
$= 50 + \left( \frac{\frac{105}{2} - 47}{20} \right) \times 10$
= 50 + 2.75
= 52.75 thousand lamps
= 52750 lamps
Hence, the median of the productions is 52750 lamps.

Concept: Tabulation of Data
Is there an error in this question or solution?

APPEARS IN

Balbharati Mathematics 1 Algebra 10th Standard SSC Maharashtra State Board
Chapter 6 Statistics
Practice Set 6.2 | Q 4 | Page 146

format: plain


text:
The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings

Krzysztof Choromanski
equal contribution
Mark Rowland 11footnotemark: 1
University of Cambridge
mr504@cam.ac.uk
University of Cambridge and Alan Turing Institute
aw665@cam.ac.uk
Abstract

We examine a class of embeddings based on structured random matrices with orthogonal rows which can be applied in many machine learning applications including dimensionality reduction and kernel approximation. For both the Johnson-Lindenstrauss transform and the angular kernel, we show that we can select matrices yielding guaranteed improved performance in accuracy and/or speed compared to earlier methods. We introduce matrices with complex entries which give significant further accuracy improvement. We provide geometric and Markov chain-based perspectives to help understand the benefits, and empirical results which suggest that the approach is helpful in a wider range of applications.

1 Introduction

Embedding methods play a central role in many machine learning applications by projecting feature vectors into a new space (often nonlinearly), allowing the original task to be solved more efficiently. The new space might have more or fewer dimensions depending on the goal. Applications include the Johnson-Lindenstrauss Transform for dimensionality reduction (JLT, Johnson and Lindenstrauss, 1984) and kernel methods with random feature maps [Rahimi and Recht, 2007]. The embedding can be costly hence many fast methods have been developed, see §1.1 for background and related work.

We present a general class of random embeddings based on particular structured random matrices with orthogonal rows, which we call random ortho-matrices (ROMs); see §2. We show that ROMs may be used for the applications above, in each case demonstrating improvements over previous methods in statistical accuracy (measured by mean squared error, MSE), in computational efficiency (while providing similar accuracy), or both. We highlight the following contributions:

• In §3: The Orthogonal Johnson-Lindenstrauss Transform (OJLT) for dimensionality reduction. We prove this has strictly smaller MSE than the previous unstructured JLT mechanisms. Further, OJLT is as fast as the fastest previous JLT variants (which are structured).

• In §4: Estimators for the angular kernel [Sidorov et al., 2014] which guarantee better MSE. The angular kernel is important for many applications, including natural language processing [Sidorov et al., 2014], image analysis [Jégou et al., 2011], speaker representations [Schmidt et al., 2014] and tf-idf data sets [Sundaram et al., 2013].

• In §5: Two perspectives on the effectiveness of ROMs to help build intuitive understanding.

In §6 we provide empirical results which support our analysis, and show that ROMs are effective for a still broader set of applications. Full details and proofs of all results are in the Appendix.

1.1 Background and related work

Our ROMs can have two forms (see §2 for details): (i) a is a random Gaussian matrix conditioned on rows being orthogonal; or (ii) an -product matrix is formed by multiplying some number of blocks, each of which is highly structured, typically leading to fast computation of products. Here is a particular structured matrix, and is a random diagonal matrix; see §2 for full details. Our block generalizes an block, where is a Hadamard matrix, which received previous attention. Earlier approaches to embeddings have explored using various structured matrices, including particular versions of one or other of our two forms, though in different contexts.

For dimensionality reduction, Ailon and Chazelle [2006] used a single block as a way to spread out the mass of a vector over all dimensions before applying a sparse Gaussian matrix. Choromanski and Sindhwani [2016] also used just one block as part of a larger structure. Bojarski et al. [2017] discussed using blocks for locality-sensitive hashing methods but gave no concrete results for their application to dimensionality reduction or kernel approximation. All these works, and other earlier approaches [Hinrichs and Vybíral, 2011, Vybíral, 2011, Zhang and Cheng, 2013, Le et al., 2013, Choromanska et al., 2016], provided computational benefits by using structured matrices with less randomness than unstructured iid Gaussian matrices, but none demonstrated accuracy gains.

Yu et al. [2016] were the first to show that -type matrices can yield improved accuracy, but their theoretical result applies only asymptotically for many dimensions, only for the Gaussian kernel and for just one specific orthogonal transformation, which is one instance of the larger class we consider. Their theoretical result does not yield computational benefits. Yu et al. [2016] did explore using a number of blocks empirically, observing good computational and statistical performance for , but without any theoretical accuracy guarantees. It was left as an open question why matrices formed by a small number of blocks can outperform non-discrete transforms.

In contrast, we are able to prove that ROMs yield improved MSE in several settings and for many of them for any number of dimensions. In addition, -product matrices can deliver computational speed benefits. We provide initial analysis to understand why can outperform the state-of-the-art, why odd yields better results than even , and why higher values of deliver decreasing additional benefits (see §3 and §5).

2 The family of Random Ortho-Matrices (ROMs)

Random ortho-matrices (ROMs) are taken from two main classes of distributions defined below that require the rows of sampled matrices to be orthogonal. A central theme of the paper is that this orthogonal structure can yield improved statistical performance. We shall use bold uppercase (e.g. ) to denote matrices and bold lowercase (e.g. ) for vectors.

Gaussian orthogonal matrices. Let be a random matrix taking values in with iid elements, which we refer to as an unstructured Gaussian matrix. The first distribution for generating ROMs we consider produces orthogonal variants of and may be viewed as the regular conditional probability measure associated with conditioned on the event that all rows of the matrix are orthogonal. Realizations of can be generated by, for example, performing a Gram-Schmidt process on the rows of to obtain a set of orthonormal rows, and then randomly independently scaling each row so that marginally it has the distribution of a Gaussian vector. The orthogonality of the rows of this matrix has been observed to yield improved statistical properties for randomized algorithms built from the matrix in a variety of applications.

-product matrices. Our second class of distributions is motivated by the desire to obtain similar statistical benefits of orthogonality to , whilst gaining computational efficiency by employing more structured matrices. We call this second class -product matrices. These take the more structured form , where has orthogonal rows, ; and the are independent diagonal matrices described below. By , we mean the matrix product . This class includes as particular cases several recently introduced random matrices (e.g. Andoni et al., 2015, Yu et al., 2016), where good empirical performance was observed. We go further to establish strong theoretical guarantees, see §3 and §4.

A prominent example of an matrix is the normalized Hadamard matrix , defined recursively by , and then for , Importantly, matrix-vector products with are computable in time via the fast Walsh-Hadamard transform, yielding large computational savings. In addition, matrices enable a significant space advantage: since the fast Walsh-Hadamard transform can be computed without explicitly storing , only space is required to store the diagonal elements of . Note that these matrices are defined only for a power of 2, but if needed, one can always adjust data by padding with s to enable the use of ‘the next larger’ H, doubling the number of dimensions in the worst case.

Matrices are representatives of a much larger family in which also attains computational savings. These are -normalized versions of Kronecker-product matrices of the form for , where stands for a Kronecker product and blocks have entries of the same magnitude and pairwise orthogonal rows each. For these matrices, matrix-vector products are computable in time Z. et al. [2015].

S includes also the Walsh matrices , where and , are binary representations of and respectively.

For diagonal , we mainly consider Rademacher entries leading to the following matrices.

Definition 2.1.

The -Rademacher random matrix with blocks is below, where are diagonal with iid Rademacher random variables [i.e. ] on the diagonals:

 M(k)SR=k∏i=1SD(R)i. (1)

Having established the two classes of ROMs, we next apply them to dimensionality reduction.

3 The Orthogonal Johnson-Lindenstrauss Transform (OJLT)

Let be a dataset of -dimensional real vectors. The goal of dimensionality reduction via random projections is to transform linearly each by a random mapping , where: for , such that for any the following holds: . If we furthermore have then the dot-product estimator is unbiased. In particular, this dimensionality reduction mechanism should in expectation preserve information about vectors’ norms, i.e. we should have: for any .

The standard JLT mechanism uses the randomized linear map , where is as in §2, requiring multiplications to evaluate. Several fast variants (FJLTs) have been proposed by replacing with random structured matrices, such as sparse or circulant Gaussian matrices Ailon and Chazelle [2006], Hinrichs and Vybíral [2011], Vybíral [2011], Zhang and Cheng [2013]. The fastest of these variants has time complexity, but at a cost of higher MSE for dot-products.

Our Orthogonal Johnson-Lindenstrauss Transform (OJLT) is obtained by replacing the unstructured random matrix with a sub-sampled ROM from §2: either , or a sub-sampled version of the -Rademacher ROM, given by sub-sampling rows from the left-most matrix in the product. We sub-sample since . We typically assume uniform sub-sampling without replacement. The resulting dot-product estimators for vectors are given by:

 ˆK basem(x,y)=1m(Gx)⊤(Gy)[unstructured iid baseline, previous % state-of-the-art accuracy], (2)

We contribute the following closed-form expressions, which quantify precisely the MSEs for these three estimators. See the Appendix for detailed proofs of these results and all others in this paper.

Lemma 3.1.

The MSE of the unstructured JLT dot-product estimator of using -dimensional random feature maps is unbiased, with

Theorem 3.2.

The estimator is unbiased and satisfies

 MSE(ˆKortm(x,y))=n(m−1)4m∥x∥2∥y∥2∫π20fn(ϕ)cos2(ϕ)Q(ϕ)dϕ+MSE(ˆKbasem(x,y)) (3)

where stands for the density function of the random variable that measures the angle between an -dimensional mean-zero Gaussian vector with identity covariance matrix and a fixed (arbitrary) -dimensional linear subspace and , where stands for an angle between and .

Theorem 3.3 (Key result).

The OJLT estimator with blocks, using -dimensional random feature maps and uniform sub-sampling policy without replacement, is unbiased with

 MSE(ˆK(k)m(x,y))=1m(n−mn−1)( ((x⊤y)2+∥x∥2∥y∥2)+ (4) k−1∑r=1(−1)r2rnr(2(x⊤y)2+∥x∥2∥y∥2)+(−1)k2knk−1n∑i=1x2iy2i).
Proof (Sketch).

For , the random projection matrix is given by sub-sampling rows from , and the computation can be carried out directly. For , the proof proceeds by induction. The random projection matrix in the general case is given by sub-sampling rows of the matrix . By writing the MSE as an expectation and using the law of conditional expectations conditioning on the value of the first random matrices , the statement of the theorem for block and for blocks can be neatly combined to yield the result. ∎

To our knowledge, it has not previously been possible to provide theoretical guarantees that -product matrices outperform iid matrices. Combining Lemma 3.1 with Theorem 3.3 yields the following important result.

Corollary 3.4 (Theoretical guarantee of improved performance).

Estimators (subsampling without replacement) yield guaranteed lower MSE than .

It is not yet clear when is better or worse than , we explore this empirically in §6. Theorem 3.3 shows that there are diminishing MSE benefits to using a large number of blocks. Interestingly, odd is better than even: it is easy to observe that . These observations, and those in §5, help to understand why empirically was previously observed to work well [Yu et al., 2016].

If we take to be a normalized Hadamard matrix , then even though we are using sub-sampling, and hence the full computational benefits of the Walsh-Hadamard transform are not available, still achieves improved MSE compared to the base method with less computational effort, as follows.

Lemma 3.5.

There exists an algorithm (see Appendix for details) which computes an embedding for a given datapoint using with set to and uniform sub-sampling policy in expected time .

Note that for or if , the time complexity is smaller than the brute force . The algorithm uses a simple observation that one can reuse calculations conducted for the upper half of the Hadamard matrix while performing computations involving rows from its other half, instead of running these calculations from scratch (details in the Appendix).

An alternative to sampling without replacement is deterministically to choose the first rows. In our experiments in §6, these two approaches yield the same empirical performance, though we expect that the deterministic method could perform poorly on adversarially chosen data. The first rows approach can be realized in time per datapoint.

Theorem 3.3 is a key result in this paper, demonstrating that -product matrices yield both statistical and computational improvements compared to the base iid procedure, which is widely used in practice. We next show how to obtain further gains in accuracy.

3.1 Complex variants of the OJLT

We show that the MSE benefits of Theorem 3.3 may be markedly improved by using -product matrices with complex entries . Specifically, we consider the variant -Hybrid random matrix below, where is a diagonal matrix with iid random variables on the diagonal, independent of , and is the unit circle of . We use the real part of the Hermitian product between projections as a dot-product estimator; recalling the definitions of §2, we use:

 M(k)SH=SD(U)kk−1∏i=1SD(R)i,ˆKH,(k)m(x,y)=1mRe[(¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯M(k),subSHx)⊤(M(k),subSHy)]. (5)

Remarkably, this complex variant yields exactly half the MSE of the OJLT estimator.

Theorem 3.6.

The estimator , applying uniform sub-sampling without replacement, is unbiased and satisfies: .

This large factor of improvement could instead be obtained by doubling for . However, this would require doubling the number of parameters for the transform, whereas the -Hybrid estimator requires additional storage only for the complex parameters in the matrix . Strikingly, it is straightforward to extend the proof of Theorem 3.6 (see Appendix) to show that rather than taking the complex random variables in to be , it is possible to take them to be and still obtain exactly the same benefit in MSE.

Theorem 3.7.

For the estimator defined in Equation (5): replacing the random matrix (which has iid elements on the diagonal) with instead a random diagonal matrix having iid elements on the diagonal, does not affect the MSE of the estimator.

It is natural to wonder if using an -product matrix with more complex random variables (for all blocks) would improve performance still further. However, interestingly, this appears not to be the case; details are provided in the Appendix §A.7.

3.2 Sub-sampling with replacement

Our results above focus on -product matrices where rows have been sub-sampled without replacement. Sometimes (e.g. for parallelization) it can be convenient instead to sub-sample with replacement. As might be expected, this leads to worse MSE, which we can quantify precisely.

Theorem 3.8.

For each of the estimators and , if uniform sub-sampling with (rather than without) replacement is used then the MSE is worsened by a multiplicative constant of .

4 Kernel methods with ROMs

ROMs can also be used to construct high-quality random feature maps for non-linear kernel approximation. We analyze here the angular kernel, an important example of a Pointwise Nonlinear Gaussian kernel (PNG). Random feature maps for PNGs can be computed by first applying random linear projections based on unstructured Gaussian matrices , and then pointwise some function which depends on the PNG.

Definition 4.1.

For a given function , the Pointwise Nonlinear Gaussian kernel (PNG) is defined by , where is a Gaussian vector with i.i.d entries.

Many prominent examples of kernels [Williams, 1998, Cho and Saul, 2009] are PNGs. Wiener’s tauberian theorem shows that all stationary kernels may be approximated arbitrarily well by sums of PNGs [Samo and Roberts, 2015]. In future work we hope to explore whether ROMs can be used to achieve statistical benefit in estimation tasks associated with a wide range of PNGs; here we focus one kernel in particular.

The nonlinear mapping corresponds to the PNG which is the angular kernel defined by , where is the angle between and .

Estimators of the PNGs we consider are of the form:

 ˆKm(x,y)=1mf(Mx)⊤f(My), (6)

where is a random matrix, and given , means . Such estimation procedures are heavily used in practice [Rahimi and Recht, 2007], as they allow fast approximate linear methods to be used Joachims [2006]. If , the unstructured Gaussian matrix, then we obtain the standard random feature estimator. Instead, we shall use matrices from the ROMs family.

When constructing random feature maps for kernels, very often . In this case, our structured mechanism can be applied by concatenating some number of independent structured blocks. Our theoretical guarantees will be given just for one block, but can easily be extended to a larger number of blocks since different blocks are independent.

The standard random feature approximation for approximating the angular kernel is defined by taking to be in Equation (6), and satisfies the following.

Lemma 4.2.

The estimator is unbiased and .

Our main result regarding angular kernels states that if we instead take in Equation (6), then we obtain an estimator with strictly smaller MSE, as follows.

Theorem 4.3.

Estimator is unbiased and satisfies:

 MSE(ˆKang,ortm(x,y))

We also derive a formula for the MSE of an estimator of the angular kernel which replaces with an arbitrary random matrix and uses random feature maps. The formula is helpful to see how the quality of the estimator depends on the probabilities that the projections of the rows of are contained in some particular convex regions of the -dimensional space spanned by datapoints and . For an illustration of the geometric definitions introduced in this Section, see Figure 1. The formula depends on probabilities involving events , where stands for the row of the structured matrix. Notice that , where stands for the projection of into and is the union of two cones in , each of angle .

Theorem 4.4.

Estimator satisfies the following, where: :

 MSE(ˆKang,Mm(x,y))=1m2[m−m∑i=1(1−2P[Ai])2]+4m2⎡⎣m∑i=1(P[Ai]−θx,yπ)2+∑i≠jδi,j⎤⎦.

Note that probabilities and depend on the choice of . It is easy to prove that for unstructured and we have: . Further, from the independence of the rows of , for . For unstructured we obtain Lemma 4.2. Interestingly, we see that to prove Theorem 4.3, it suffices to show , which is the approach we take (see Appendix). If we replace with , then the expression does not depend on . Hence, the angular kernel estimator based on Hadamard matrices gives smaller MSE estimator if and only if . It is not yet clear if this holds in general.

5 Understanding the effectiveness of orthogonality

Here we build intuitive understanding for the effectiveness of ROMs. We examine geometrically the angular kernel (see §4), then discuss a connection to random walks over orthogonal matrices.

Angular kernel.

As noted above for the -mechanism, smaller MSE than that for unstructured is implied by the inequality , which is equivalent to: . Now it becomes clear why orthogonality is crucial. Without loss of generality take: , , and let and be the first two rows of .

Consider first the extreme case (middle of left part of Figure 1), where all vectors are -dimensional. Recall definitions from just after Theorem 4.3. If is in then it is much less probable for also to belong to . In particular, if then the probability is zero. That implies the inequality. On the other hand, if is perpendicular to then conditioning on does not have any effect on the probability that belongs to (left subfigure of Figure 1). In practice, with high probability the angle between and is close to , but is not exactly . That again implies that conditioned on the projection of into to be in , the more probable directions of are perpendicular to (see: ellipsoid-like shape in the right subfigure of Figure 1 which is the projection of the sphere taken from the -dimensional space orthogonal to into ). This makes it less probable for to be also in . The effect is subtle since , but this is what provides superiority of the orthogonal transformations over state-of-the-art ones in the angular kernel approximation setting.

Markov chain perspective.

We focus on Hadamard-Rademacher random matrices , a special case of the -product matrices described in Section 2. Our aim is to provide intuition for how the choice of affects the quality of the random matrix, following our earlier observations just after Corollary 3.4, which indicated that for -product matrices, odd values of yield greater benefits than even values, and that there are diminishing benefits from higher values of . We proceed by casting the random matrices into the framework of Markov chains.

Definition 5.1.

The Hadamard-Rademacher process in dimensions is the Markov chain taking values in the orthogonal group , with almost surely, and almost surely, where is the normalized Hadamard matrix in dimensions, and are iid diagonal matrices with independent Rademacher random variables on their diagonals.

Constructing an estimator based on Hadamard-Rademacher matrices is equivalent to simulating several time steps from the Hadamard-Rademacher process. The quality of estimators based on Hadamard-Rademacher random matrices comes from a quick mixing property of the corresponding Markov chain. The following demonstrates attractive properties of the chain in low dimensions.

Proposition 5.2.

The Hadamard-Rademacher process in two dimensions: explores a state-space of orthogonal matrices, is ergodic with respect to the uniform distribution on this set, has period , the diameter of the Cayley graph of its state space is , and the chain is fully mixed after time steps.

This proposition, and the Cayley graph corresponding to the Markov chain’s state space (Figure 1 right), illustrate the fast mixing properties of the Hadamard-Rademacher process in low dimensions; this agrees with the observations in §3 that there are diminishing returns associated with using a large number of blocks in an estimator. The observation in Proposition 5.2 that the Markov chain has period 2 indicates that we should expect different behavior for estimators based on odd and even numbers of blocks of matrices, which is reflected in the analytic expressions for MSE derived in Theorems 3.3 and 3.6 for the dimensionality reduction setup.

6 Experiments

We present comparisons of estimators introduced in §3 and §4, illustrating our theoretical results, and further demonstrating the empirical success of ROM-based estimators at the level of Gram matrix approximation. We compare estimators based on: unstructured Gaussian matrices , matrices , -Rademacher and -Hybrid matrices with and different sub-sampling strategies. Results for do not show additional statistical gains empirically. Additional experimental results, including a comparison of estimators using different numbers of blocks, are in the Appendix §C. Throughout, we use the normalized Hadamard matrix for the structured matrix .

6.1 Pointwise kernel approximation

Complementing the theoretical results of §3 and §4, we provide several salient comparisons of the various methods introduced - see Figure 2 top. Plots presented here (and in the Appendix) compare MSE for dot-product and angular and kernel. They show that estimators based on , -Hybrid and -Rademacher matrices without replacement, or using the first rows, beat the state-of-the-art unstructured G approach on accuracy for all our different datasets in the JLT setup. Interestingly, the latter two approaches give also smaller MSE than -estimators. For angular kernel estimation, where sampling is not relevant, we see that and -Rademacher approaches again outperform the ones based on matrices .

6.2 Gram matrix approximation

Moving beyond the theoretical guarantees established in §3 and §4, we show empirically that the superiority of estimators based on ROMs is maintained at the level of Gram matrix approximation. We compute Gram matrix approximations (with respect to both standard dot-product, and angular kernel) for a variety of datasets. We use the normalized Frobenius norm error as our metric (as used by [Choromanski and Sindhwani, 2016]), and plot the mean error based on 1,000 repetitions of each random transform - see Figure 2 bottom. The Gram matrices are computed on a randomly selected subset of data points from each dataset. As can be seen, the -Hybrid estimators using the “no-replacement” or “first rows” sub-sampling strategies outperform even the orthogonal Gaussian ones in the dot-product case. For the angular case, the -approach and -Rademacher approach are practically indistinguishable.

7 Conclusion

We defined the family of random ortho-matrices (ROMs). This contains the -product matrices, which include a number of recently proposed structured random matrices. We showed theoretically and empirically that ROMs have strong statistical and computational properties (in several cases outperforming previous state-of-the-art) for algorithms performing dimensionality reduction and random feature approximations of kernels. We highlight Corollary 3.4, which provides a theoretical guarantee that -product matrices yield better accuracy than iid matrices in an important dimensionality reduction application (we believe the first result of this kind). Intriguingly, for dimensionality reduction, using just one complex structured matrix yields random features of much better quality. We provided perspectives to help understand the benefits of ROMs, and to help explain the behavior of -product matrices for various numbers of blocks. Our empirical findings suggest that our theoretical results might be further strengthened, particularly in the kernel setting.

Acknowledgements

We thank Vikas Sindhwani at Google Brain Robotics and Tamas Sarlos at Google Research for inspiring conversations that led to this work. We thank Jiri Hron, Matej Balog, Maria Lomeli, and Dave Janz for helpful comments. MR acknowledges support by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/L016516/1 for the University of Cambridge Centre for Doctoral Training, the Cambridge Centre for Analysis. AW acknowledges support by the Alan Turing Institute under the EPSRC grant EP/N510129/1, and by the Leverhulme Trust via the CFI.

References

• Ailon and Chazelle [2006] N. Ailon and B. Chazelle. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In STOC, 2006.
• Andoni et al. [2015] A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn, and L. Schmidt. Practical and optimal LSH for angular distance. In NIPS, 2015.
• Bojarski et al. [2017] M. Bojarski, A. Choromanska, K. Choromanski, F. Fagan, C. Gouy-Pailler, A. Morvan, N. Sakr, T. Sarlos, and J. Atif. Structured adaptive and random spinners for fast machine learning computations. In AISTATS, 2017.
• Cho and Saul [2009] Y. Cho and L. K. Saul. Kernel methods for deep learning. In NIPS, 2009.
• Choromanska et al. [2016] A. Choromanska, K. Choromanski, M. Bojarski, T. Jebara, S. Kumar, and Y. LeCun. Binary embeddings with structured hashed projections. In ICML, 2016.
• Choromanski and Sindhwani [2016] K. Choromanski and V. Sindhwani. Recycling randomness with structure for sublinear time kernel expansions. In ICML, 2016.
• Hinrichs and Vybíral [2011] A. Hinrichs and J. Vybíral. Johnson-Lindenstrauss lemma for circulant matrices. Random Structures & Algorithms, 39(3):391–398, 2011.
• Jégou et al. [2011] H. Jégou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2011.
• Joachims [2006] T. Joachims. Training linear SVMs in linear time. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’06. ACM, 2006.
• Johnson and Lindenstrauss [1984] W. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189–206, 1984.
• Le et al. [2013] Q. Le, T. Sarlós, and A. Smola. Fastfood - approximating kernel expansions in loglinear time. In ICML, 2013.
• Rahimi and Recht [2007] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In NIPS, 2007.
• Samo and Roberts [2015] Y.-L. K. Samo and S. Roberts. Generalized spectral kernels. CoRR, abs/1506.02236, 2015.
• Schmidt et al. [2014] L. Schmidt, M. Sharifi, and I. Moreno. Large-scale speaker identification. In International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2014.
• Sidorov et al. [2014] G. Sidorov, A. Gelbukh, H. Gómez-Adorno, and D. Pinto. Soft similarity and soft cosine measure: Similarity of features in vector space model. Computación y Sistemas, 18(3), 2014.
• Sundaram et al. [2013] N. Sundaram, A. Turmukhametova, N. Satish, T. Mostak, P. Indyk, S. Madden, and P. Dubey. Streaming similarity search over one billion tweets using parallel locality-sensitive hashing. Proceedings of the VLDB Endowment, 6(14):1930–1941, 2013.
• Vybíral [2011] J. Vybíral. A variant of the Johnson-Lindenstrauss lemma for circulant matrices. Journal of Functional Analysis, 260(4):1096–1105, 2011.
• Williams [1998] C. Williams. Computation with infinite neural networks. Neural Computation, 10(5):1203–1216, 1998.
• Yu et al. [2016] F. Yu, A. Suresh, K. Choromanski, D. Holtmann-Rice, and S. Kumar. Orthogonal random features. In NIPS, 2016.
• Z. et al. [2015] Xu Z., F. Yu, R. Guo, S. Kumar, S. Wang, and S. Chang. Fast orthogonal projection based on Kronecker product. In 2015 IEEE International Conference on Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, 2015.
• Zhang and Cheng [2013] H. Zhang and L. Cheng. New bounds for circulant Johnson-Lindenstrauss embeddings. CoRR, abs/1308.6339, 2013.

Appendix: The Unreasonable Effectiveness of Random Orthogonal Embeddings

We present here details and proofs of all the theoretical results presented in the main body of the paper. We also provide further experimental results in §C.

We highlight proofs of several key results that may be of particular interest to the reader:

• The proof of Theorem 3.3; see §A.3.

• The proof of Theorem 3.6; see §A.5.

• The proof of Theorem 4.3; see §B.2.

In the Appendix we will use interchangeably two notations for the dot product between vectors and , namely: and .

Appendix A Proofs of results in §3

a.1 Proof of Lemma 3.1

Proof.

Denote , where stands for the row of the unstructured Gaussian matrix . Note that we have:

 ˆKbasem(x,y)=1mm∑i=1Xi. (7)

Denote . Notice that from the independence of s and the fact that: , , we get: , thus the estimator is unbiased. Since the estimator is unbiased, we have: . Thus we get:

 MSE(ˆKbasem(x,y))=1m2∑i,j(E[XiXj]−E[Xi]E[Xj]). (8)

From the independence of different s, we get:

 MSE(ˆKbasem(x,y))=1m2∑i(E[X2i]−(E[Xi])2). (9)

Now notice that different s have the same distribution, thus we get:

 MSE(ˆKbasem(x,y))=1m(E[X21]−(E[X1])2). (10)

From the unbiasedness of the estimator, we have: . Therefore we obtain:

 MSE(ˆKbasem(x,y))=1m(E[X21]−(x⊤y)2). (11)

Now notice that

 E[X21]=E[∑i1,j1,i2,j2gi1gj1gi2gj2xi1yj1xi2yj2]=∑i1,j1,i2,j2xi1yj1xi2yj2E[gi1gj1gi2gj2], (12)

where stands for the first row of . In the expression above the only nonzero terms corresponds to quadruples , where no index appears odd number of times. Therefore, from the inclusion-exclusion principle and the fact that and , we obtain

 E[X21] =∑i1=j1,i2=j2xi1yj1xi2yj2E[gi1gj1gi2gj2]+∑i1=i2,j1=j2xi1yj1xi2yj2E[gi1gj1gi2gj2] (13) \-+∑i1=j2,i2=j1xi1yj1xi2yj2E[gi1gj1gi2gj2]−∑i1=j1=i2=j2xi1yj1xi2yj2E[gi1gj1gi2gj2] (14) =((x⊤y)2−n∑i=1x2iy2i+3n∑i=1x2iy2i)+((∥x∥2∥y∥2)2−n∑i=1x2iy2i+3n∑i=1x2iy2i) (15) \-+((x⊤y)2−n∑i=1x2iy2i+3n∑i=1x2iy2i)−3⋅2n∑i=1x2iy2i (16) =(∥x∥2∥y∥2)2+2(x⊤y)2. (17)

Therefore we obtain

 MSE(ˆKbasem(x,y))=1m((∥x∥2∥y∥2)2+2(x⊤y)2−(x⊤y)2)=1m(∥x∥22∥y∥22+(x⊤y)2), (18)

which completes the proof. ∎

a.2 Proof of Theorem 3.2

Proof.

Fix two different rows of and denote them as and . We will use the following notation:

• - an angle between and the plane,

• - angle between the projection of into plane (the -axis of the plane) and vector ,

• - an angle between and

The unbiasedness of the Gaussian orthogonal estimator comes from the fact that every row of the Gaussian orthogonal matrix is sampled from multivariate Gaussian distribution with entries taken independently at random from .

Note that:

 Cov(Xi,Xj)=E[XiXj]−E[Xi]E[Xj], (19)

where: , and stand for the and row of the Gaussian orthogonal matrix respectively. From the fact that Gaussian orthogonal estimator is unbiased, we get:

 E[Xi]=x⊤y. (20)

Let us now compute . Taking , and applying the density function of directions of the projection of into the plane conditioned on , we get:

 E[XiXj]=E[(r⊤ix)(r⊤iy)(r⊤jx)(r⊤jy)]=n⋅nn−1∫π20f(ϕ)cos2(ϕ)(sin2(ϕ)+1)dϕ∫2π0⋅dψ2πcos(ψ)cos(ψ+θ)∥x∥2∥y∥2⋅∫2π0g(t)cos(t−ψ)cos(t−θ−ψ)∥x∥2∥y∥2dt, (21)

where: stands for the density function of the angle between and the plane, and is a density function of the direction of the projection of vector into plane conditioned on and . Notice that due to the isotropic property of the Gaussian vectors, we know that the density function of is .

After simplification we get

 E[XiXj]=∥x∥22∥y∥22n2n−1∫π20f(ϕ)cos2(ϕ)(sin2(ϕ)+1)dϕ∫2π0⋅dψ2πcos(ψ)cos(ψ+θ)⋅sin(ϕ)2π∫2π0cos(t−ψ)cos(t−θ−ψ)cos2(t)+sin2(ϕ)sin2(t)dt (22)

Note that we have

 E[Xi]E[Xj]=2n∥x∥22∥y∥22∫π20f(ϕ)cos2(ϕ)dϕ∫2π0dψ2πcos(ψ)cos(ψ+θ)⋅∫2π0dψ2πcos(ψ)cos(ψ+θ) (23)

Therefore we obtain

 E[XiXj]−E[Xi]E[Xj]=∥x∥22∥y∥22n2n−1∫π20f(ϕ)cos2(ϕ)(sin2(ϕ)+1)dϕ∫2π0⋅dψ2πcos(ψ)cos(ψ+θ)⋅sin(ϕ)2π∫2π0cos(t−ψ)cos(t−θ−ψ)cos2(t)+sin2(ϕ)sin2(t)dt−2n∥x∥22∥y∥22∫π20f(ϕ)cos2(ϕ)dϕ∫2π0dψ2πcos(ψ)cos(ψ+θ)⋅∫2π0dψ2πcos(ψ)cos(ψ+θ) (24)

Let us denote .

We have

 F(ϕ,ψ,θ)=∫2π0(sin(ψ)sin(t)+cos(ψ)cos(t))(sin(ψ+θ)sin(t)+cos(ψ+θ)cos(t))1−(1−sin2(ϕ))sin2(t)dt. (25)

Now we use the substitution:


text:
# If (X, 3) and (3, 5) Are the Extremities of a Diameter of a Circle with Centre at (2, Y), Then the Values of X and Y Are - Mathematics

MCQ

If (x, 3) and (3, 5) are the extremities of a diameter of a circle with centre at (2, y), then the values of x and y are

#### Options

• (3, 1)

• x = 4, y = 1

• x = 8, y = 2

• none of these

#### Solution

none of these

The end points of the diameter of a circle are (x, 3) and (3, 5).
According to the question, we have:

$\frac{x + 3}{2} = 2, y = \frac{5 + 3}{2}$

$\Rightarrow x = 1, y = 4$

Concept: Circle - Standard Equation of a Circle
Is there an error in this question or solution?

#### APPEARS IN

RD Sharma Class 11 Mathematics Textbook
Chapter 24 The circle
Q 21 | Page 40


text:
36 Distribution

# 36.1.0 Major release (August 02, 2021)

## Acknowledgments

We would like to thank all of our users who have reported problems and made suggestions for improving this release. In particular, we thank Wolfgang Britz, Ricardo Manuel Pinto de Lima, Bruce McCarl, Scott McDonald, and Kirk A. Yost.

## GAMS System

• The End User License Agreement (eula.pdf in the GAMS system directory) has been updated to version 08/2021.

### GAMS

• Improved performance of model generation for certain equations where the index order of the equations caused an out of order index reference of variables like in this example:
ejk(j,k)..  sum(i, x(i,j,k)) =e= 42;

Added new command line parameter sys19 to deactivate this performance optimization.
• Added new function platformCode and new compile time constants to be used with it.
• Added information about available CPU sockets, cores, and threads to the log.
• Improve error message for invalid values of the .scale attribute.
• Allow to read environment variables and command line parameters at execution time in put context.
• Added Put_Utility commands setEnv and dropEnv to allow environment variable modification at execution time.
• Added Python function gams.get_env to EmbeddedCode Python to access modified environment variables after Python module os has been initialized.
• Fixed a problem causing an unexpected error when beginning execution time embedded code as first statement after starting from a restart file.
• Fixed a potential warning using execution time embedded code after starting from a restart file which was created with action=c.

### Windows Installer

• Windows installer is now built with Inno Setup 6.
• Command line parameter /allUsers=yes|no has been deprecated and will be removed in a future GAMS release. Use the new parameter /installAllUsers=yes|no instead.
• New command line flags /allUsers and /currentUser can be used to explicitly control if the installation is performed in administrative or non-administrative installation mode.

### GMSPython

• The Python version has been updated to 3.8.10.

## Solvers

### Bonmin

• We plan to drop Bonmin and BonminH with one of the next major releases.

### CONVERT

• Added support for quadratic constraints in formats CplexLP, CplexMPS, and FixedMPS.
• Added option SkipNRows.
• Added option QExtractAlg.
• Fixed writing eps for zero marginals of non-basic variables or equations in format Gams.

### CPLEX

• Added the following options:
• multobjoptfiles: List of option files used for individual solves within multi-objective optimization.
• usercut: User cut activation.
• usercutpool: Indicator to use user cuts.
• qextractalg: quadratic extraction algorithm in GAMS interface.
• Fixed handling of special values (incl. missing zero values) in multimipstart.
• Fixed update of Jacobian elements within GUSS scenarios.
• Fixed setting gubcovers via cuts.

### GUROBI

• Added option qextractalg: quadratic extraction algorithm in GAMS interface.

### GUSS

• Added support of option savepoint for scenario solves.

### Ipopt and IpoptH

• New libraries 3.14.1.
• Attention
Value pardiso of option linear_solver to choose Pardiso from Intel MKL has been renamed to pardisomkl. Renamed pardiso_* options to pardisomkl_*.
• Added value pardiso for option linear_solver to choose to use Pardiso from the Pardiso Solver Project. This solver is not included in the GAMS distribution. A user needs to provide a Pardiso library. Added option pardisolib to specify name and path of Pardiso library. Added pardiso_* options.
• Added option hsllib to specify name and path of HSL library to be loaded at runtime (for users of GAMS/Ipopt or users that want to use HSL_MA77).
• Changed default of honor_original_bounds to no. In addition, Ipopt now ensures that, in addition to option bound_relax_factor, variable bounds are relaxed by at most constr_viol_tol. The Ipopt log now shows the violation of variable bounds in the solution.
• Fixed that marginals for fixed variables were not computed if fixed_variable_treatment is set to make_parameter (the default). Added value make_parameter_nodual for this option to disable calculation of marginals for fixed variables (which can cost an extra evaluation of the Jacobian).
• Added options max_wall_time, print_options_mode, print_advanced_options, and timing_statistics.
• Ipopt should now be threadsafe also when used with MUMPS as linear solver (a mutex ensures that only one thread executes MUMPS at a time).
• For more information, including bugfixes, see the Ipopt 3.14.0 release notes.
• Changed default of constr_viol_tol to 1e-6.
• GAMS ResLim now sets the default for Ipopt option max_wall_time instead of max_cpu_time.
• If GAMS ScaleOpt is set, i.e., the model has been scaled manually, then the default of option nlp_scaling_method is set to none.
• The interface has been extended to warmstart Ipopt if a modified model instance is solved, e.g., in the context of GUSS. For the warmstart, previously initialized Ipopt data structures are reused if possible and option warm_start_init_point is enabled, see also Warmstarting IPOPT.
• Enabled solvelink=6 capability for Ipopt and IpoptH.
• Update of HSL routines (IpoptH only):
• MA57 3.11.0.
• HSL_MC68 3.3.1.
• HSL_MA86 1.6.0.
• HSL_MA97 2.6.0.
• Update of MUMPS to version 5.4.0.
• Changed default of mumps_pivot_order from 5 to 7.

### JAMS

• Updated behavior and logging for models with equ.var matches in the model statement. If the trivial (aka empty or default) model transformation is specified in the EMP info file, nothing changes: the matches are used as before. In contrast, if a nontrivial or nonempty transformation is specified, the matches are ignored when creating the reformulated model and a message to this effect is sent to the log.

### KNITRO

• New libraries 12.4.
• Improved performance on mixed-integer nonlinear problems (MINLP).
• Improved performance when using the limited-memory quasi-Newton Hessian approximation.
• Added option linsolver_maxitref: Indicates the maximum allowable number of iterative refinement steps applied when a linear system is solved inside Knitro.
• Added option bfgs_scaling: Specify the initial scaling to use for the BFGS or L-BFGS Hessian approximation.
• Added option bar_linsys_storage: Indicates how to store in memory the linear systems used inside the Interior/Direct algorithm for computing primal-dual steps.
• Added option mip_cutting_plane: Specifies when to apply the cutting plane procedure.
• Added option mip_heuristic_diving: Specifies whether or not to enable the MIP diving heuristic.
• Added option mip_heuristic_feaspump: Specifies whether or not to enable the MIP feasibility pump heuristic.
• Added option mip_heuristic_mpec: Specifies whether or not to enable the MIP MPEC heuristic.
• Added option mip_heuristic_strategy: Specifies the level of effort applied for the MIP heuristic search used to try to find an initial integer feasible point.
• Deprecated option mip_heuristic: Use mip_heuristic_strategy instead.
• Added option qextractalg: quadratic extraction algorithm in GAMS interface.

### Lindo/LindoGlobal

• New libraries 13.0.291.

### LocalSolver

• New libraries 10.5 (20210624).

### ODHCPLEX

• New libraries 6.0.4.

### PATH

• New libraries 5.0.04 (maintenance release) include capability to further limit preprocessor output by specifying output_preprocess_level -1.

### SCIP

• New libraries 7.0 (d012dac064).
• Updated Ipopt to Ipopt 3.14.1, see also above.

### XPRESS

• New libraries 38.01.03.
• Xpress Optimizer Release Notes:
• Improved MIP performance.
• It is now possible to activate a special heuristic solve mode for MIPs, which emphasizes finding new solutions.
• Improved sifting algorithm when used with Barrier.
• Improved numerical stability of the Barrier algorithm.
• Xpress Nonlinear Release Notes:
• Significant MINLP performance improvements due to improved nonlinear presolver.
• Improved performance on instances with very large separable nonlinear expressions due to imroved automatic differentiation.
• Multistart now uses the nonlinear primal integral for tie breaking.
• barPerturb: In numerically challenging cases it is often advantageous to apply perturbations on the KKT system to improve its numerical properties.
• barRefIter: After terminating the barrier algorithm, further refinement steps can be performed.
• clamping: Allows for the adjustment of returned solution values such that they are always within bounds.
• clamping_dual: Adjust primal slack values to always be within constraint bounds.
• clamping_primal: Adjust primal solution to always be within primal bounds.
• clamping_rdj: Adjust reduced costs to always be within dual bounds implied by the primal solution.
• clamping_slacks: Adjust dual solution to always be within the dual bounds implied by the slacks.
• genConsAbsTransformation: Specifies the reformulation method for absolute value general constraints at the beginning of the search.
• heurEmphasis: Specifies an emphasis for the search w.r.t. primal heuristics and other procedures that affect the speed of convergence of the primal-dual gap.
• inputTol: Tolerance on input values elements.
• mipComponents: Determines whether disconnected components in a MIP should be solved as separate MIPs.
• mipConcurrentNodes: Sets the node limit for when a winning solve is selected when concurrent MIP solves are enabled.
• mipConcurrentSolves: Selects the number of concurrent solves to start for a MIP.
• mipRestartFactor: Fine tune initial conditions to trigger an in-tree restart.
• mipRestartGapThreshold: Initial gap threshold to delay in-tree restart.
• netStallLimit: Limit the number of degenerate pivots of the network simplex algorithm, before switching to either primal or dual simplex.
• nodeProbingEffort: Adjusts the overall level of node probing.
• outputControls: Toggles the printing of all control settings at the beginning of the search.
• ppFactor: Partial pricing candidate list sizing parameter.
• preFolding: Determines if a folding procedure should be used to aggregate continuous columns in an equitable partition.
• siftPasses: Determines how quickly we allow to grow the worker problems during the sifting algorithm.
• siftSwitch: Determines which algorithm to use for solving the subproblems during sifting.
• xslp_presolveOps_noLinear: Avoid performing linear reductions at the NLP level.
• xslp_presolveOps_noSimplifier: Avoid simplifying nonlinear expressions.
• Added option values:
• Changed option defaults:
• Deprecated options:
• heurStrategy. Use heurEmphasis instead.
• xslp_matrixTol. Use matrixTol instead.
• Removed options:
• treePresolve_keepBasis.
• treePresolve.
• treePresolveOps.
• xslp_analyze_autosavePool.
• xslp_analyze_recordLinearization.
• xslp_analyze_recordLinesearch.
• xslp_presolvePassLimit.
• xslp_timePrint.
• Added option algAfterNetwork: Algorithm to be used for the clean up step after the network simplex solver.
• Added option qextractalg: quadratic extraction algorithm in GAMS interface.
• Removed options that were marked deprecated in GAMS 35.

## Tools

• We will remove the tools cholesky, eigenvalue, eigenvector, invert in a future GAMS release. Similar functionality has been added via $libInclude linalg {cholesky,eigenvalue,eigenvector,invert}. See the header of the file in <sysdir>\inclib\linalg.gms for details. ### GAMS Studio • New version 1.7.2. • Dropped support for Ubuntu 16.04 LTS and openSUSE Leap 15.2 because the updated AppImage now requires glibc 2.27. Dropped support for Debian 9. • New feature: Allow specifying location of User Model Libraries in Settings dialog. • Improved visual distinction between current and other groups in Project Explorer. • Added a warning message before printing large files. • Added a list of solvers for each model type to be selected in Extended Parameter Editor and Configuration Editor. • Added shortcut Alt+I (Mac OS X: Option+I) to fold blocks of dollar control options. • Added setting to automatically collapse dollar control option blocks when opening a file (default: off). • Changed shortcuts to show/hide Extended Parameter Editor • Windows/Linux: From Ctrl-Alt-3 to Shift+Ctrl+3. • Mac OS X: From Shift-Command-3 to Control-Option-3. • Improvements for syntax highlighter and code completer, e.g.: • Added support for system attributes and compile-time constants. • Added support of quoted elements in syntax highlighter. • Disabled code completer for certain code blocks like $onEmbeddedCode or $onPut. • Improvements for remote execution support, e.g.: • Added support for GAMS Engine server with self-signed certificate (https). • Added support for GAMS Engine server with http protocol. • Added option to remember login credentials for GAMS Engine in Settings. • Renamed "MIRO" Settings page to "Remote" to better reflect new content. • Improved GAMS Engine dialog. • Added file type EFI to send additional files to a GAMS Engine server. • Stability improvements and minor bug fixes, e.g.: • Fixed duplicate file entries in the Project Explorer when having two references with different case to a single file • Fixed Studio title bar appearing outside of screen in some cases. • Fixed wrong content of "File" tab in Reference File Viewer. • Fixed missing check of some data locations for GAMS license file. • Fixed ESC key not behaving like close button in Settings dialog. • Fixed crash when reopening a closed log tab. • Fixed that MIRO menu entries were not enabled when MIRO was automatically discovered. • Fixed that theme could be broken in Settings dialog when using cancel button. ### GDXRank, GDXRename • We will remove the tools gdxrank and gdxrename in a future GAMS release. Similar functionality has been added via $libInclude gdxservice {gdxrank,gdxservice}. See the header of the file in <sysdir>\inclib\gdxservice.gms for details.
• The $libInclude rank functionality now uses $libInclude gdxservice gdxrank to sort a one dimensional parameter instead of the gdxrank tool.

### GAMS Test Library

New models:

Models trilib01, trilib02, trilib03, parlib01, cpplib00:

• Removed jinja2 from associated source archive. It is now required to have the Python package jinja2 installed to run the ql.py script.

x86 64bit
MS Windows
x86 64bit
Linux
x86 64bit
Mac OS X
ALPHAECP 2.11
ANTIGONE 1.1
BARON
BONMIN 1.8
CBC 2.10
CONOPT 3
CONOPT 4
CPLEX 20.1
DECIS
DICOPT 2
GLOMIQO 2.3
GUROBI 9.1
GUSS
IPOPT 3.14
KESTREL
KNITRO 12.4
LGO
LINDO 13.0
LINDOGLOBAL 13.0
LOCALSOLVER 10.5
MILES
MINOS
MOSEK 9
MSNLP
NLPEC
ODHCPLEX 6
PATH
SBB
SCIP 7.0
SHOT 1.1
SNOPT 7.7
SOPLEX 5.0
XA
XPRESS 38.01

# 36.2.0 Minor release (September 03, 2021)

## Acknowledgments

We would like to thank all of our users who have reported problems and made suggestions for improving this release. In particular, we thank Wolfgang Britz, Daniel Dias, Andreas Lundell, Bruce McCarl, and Tom Rutherford.

## Solvers

### GAMSCHK

• Fix default solve behavior: if no GCK file is specified, no subsolver should be called as no solution is wanted.

### GUSS

• Fixed options OptfileInit and Optfile being ignored.
• Added fallback to cold start in case of hot start failure.

### IPOPT

• New libraries 3.14.3.
• Updated MUMPS to version 5.4.1.

### MOSEK

• New libraries 9.3.4.

### SHOT

• New libraries 1.1 (9a8893e7).

## Tools

### GAMS Studio

• New version 1.7.3 with various bug fixes, stability improvements, and minor enhancements, e.g.:
• Allow to duplicate multiple lines at once.
• Added navigation and selection by word using ctrl+left/right in LOG-Viewer.
• Fixed highlighting issue when a symbol declaration ends with a space.
• Fixed horizontal scroll in LST viewer when cursor is out of view.
• Fixed that searching backwards in modified document was not working.
• Fixed "Replace" ignoring case sensitivity option.
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170


text:
# The typographic scale

The typographic scale has been used for centuries to choose harmonious font sizes. It has been likened to a harmonious musical scale. But there are flaws in those historical values.

# The egg problem

The egg problem is a classic programming challenge. However, there is a mathematical solution. You can solve this problem analytically, even in the general case with $$n$$ eggs.

# Approximate a circle with cubic Bézier curves

Bézier curves are often used to generate smooth curves because Bézier curves are computationally inexpensive and produce high-quality results. The circle can be closely approximated using a cubic Bézier curve that is constructed to minimize the radial deviation from a circle.

# Serialize a binary tree in minimal space

The natural way to serialize a binary tree requires $$2n$$ bits to store a binary tree with $$n$$ nodes. However, it’s possible to reduce this to $$2n - \frac{3}{2} \log_2 n - \frac{1}{2} \log_2 \pi$$ bits, with the help of the Catalan numbers. This is the minimal space needed to serialize an arbitrary binary tree with $$n$$ nodes.

# Symmetric senary

Symmetric senary is a tiny numeral system which is intended for people to use in their everyday life. It is especially useful for dividing things up in practical ways, and easily estimating things like tips and mileage without ever needing a calculator.


text:
• ### Science Impacts of the SPHEREx All-Sky Optical to Near-Infrared Spectral Survey: Report of a Community Workshop Examining Extragalactic, Galactic, Stellar and Planetary Science(1606.07039)

June 22, 2016 astro-ph.CO, astro-ph.GA
SPHEREx is a proposed SMEX mission selected for Phase A. SPHEREx will carry out the first all-sky spectral survey and provide for every 6.2" pixel a spectra between 0.75 and 4.18 $\mu$m [with R$\sim$41.4] and 4.18 and 5.00 $\mu$m [with R$\sim$135]. The SPHEREx team has proposed three specific science investigations to be carried out with this unique data set: cosmic inflation, interstellar and circumstellar ices, and the extra-galactic background light. It is readily apparent, however, that many other questions in astrophysics and planetary sciences could be addressed with the SPHEREx data. The SPHEREx team convened a community workshop in February 2016, with the intent of enlisting the aid of a larger group of scientists in defining these questions. This paper summarizes the rich and varied menu of investigations that was laid out. It includes studies of the composition of main belt and Trojan/Greek asteroids; mapping the zodiacal light with unprecedented spatial and spectral resolution; identifying and studying very low-metallicity stars; improving stellar parameters in order to better characterize transiting exoplanets; studying aliphatic and aromatic carbon-bearing molecules in the interstellar medium; mapping star formation rates in nearby galaxies; determining the redshift of clusters of galaxies; identifying high redshift quasars over the full sky; and providing a NIR spectrum for most eROSITA X-ray sources. All of these investigations, and others not listed here, can be carried out with the nominal all-sky spectra to be produced by SPHEREx. In addition, the workshop defined enhanced data products and user tools which would facilitate some of these scientific studies. Finally, the workshop noted the high degrees of synergy between SPHEREx and a number of other current or forthcoming programs, including JWST, WFIRST, Euclid, GAIA, K2/Kepler, TESS, eROSITA and LSST.
• ### The Debris Disk Explorer: a balloon-borne coronagraph for observing debris disks(1309.4703)

Sept. 18, 2013 astro-ph.IM
The Debris Disk Explorer (DDX) is a proposed balloon-borne investigation of debris disks around nearby stars. Debris disks are analogs of the Asteroid Belt (mainly rocky) and Kuiper Belt (mainly icy) in our Solar System. DDX will measure the size, shape, brightness, and color of tens of disks. These measurements will enable us to place the Solar System in context. By imaging debris disks around nearby stars, DDX will reveal the presence of perturbing planets via their influence on disk structure, and explore the physics and history of debris disks by characterizing the size and composition of disk dust. The DDX instrument is a 0.75-m diameter off-axis telescope and a coronagraph carried by a stratospheric balloon. DDX will take high-resolution, multi-wavelength images of the debris disks around tens of nearby stars. Two flights are planned; an overnight test flight within the United States followed by a month-long science flight launched from New Zealand. The long flight will fully explore the set of known debris disks accessible only to DDX. It will achieve a raw contrast of 10^-7, with a processed contrast of 10^-8. A technology benefit of DDX is that operation in the near-space environment will raise the Technology Readiness Level of internal coronagraphs, deformable mirrors, and wavefront sensing and control, all potentially needed for a future space-based telescope for high-contrast exoplanet imaging.
• ### Astrometric Detection of Terrestrial Planets in the Habitable Zones of Nearby Stars with SIM PlanetQuest(astro-ph/0603681)

May 4, 2006 astro-ph
SIM PlanetQuest (Space Interferometry Mission) is a space-borne Michelson interferometer for precision stellar astrometry, with a nine meter baseline, currently slated for launch in 2015. One of the principal science goals is the astrometric detection and orbit characterization of terrestrial planets in the habitable zones of nearby stars. Differential astrometry of the target star against a set of reference stars lying within a degree will allow measurement of the target star's reflex motion with astrometric accuracy of 1 micro-arcsecond in a single measurement. We assess SIM's capability for detection (as opposed to characterization by orbit determination) of terrestrial planets in the habitable zones of nearby solar-type stars. We compare SIM's performance on target lists optimized for the SIM and Terrestrial Planet Finder Coronograph (TPF-C) missions. Performance is quantified by three metrics: minimum detectable planet mass, number and mass distribution of detected planets, and completeness of detections in each mass range. Finally, we discuss the issue of confidence in detections and non-detections, and show how information from SIM's planet survey can enable TPF to increase its yield of terrestrial planets.