A grammar checker, in computing terms, is a program, or part of a program, that attempts to verify written text for grammatical correctness. Grammar checkers are most often implemented as a feature of a larger program, such as a word processor, but are also available as a stand-alone application that can be activated from within programs that work with editable text. The implementation of a grammar checker makes use of natural language processing. == History == The earliest "grammar checkers" were programs that checked for punctuation and style inconsistencies, rather than a complete range of possible grammatical errors. The first system was called Writer's Workbench, and was a set of writing tools included with Unix systems as far back as the 1970s. The whole Writer's Workbench package included several separate tools to check for various writing problems. The "diction" tool checked for wordy, trite, clichéd or misused phrases in a text. The tool would output a list of questionable phrases and provide suggestions for improving the writing. The "style" tool analyzed the writing style of a given text. It performed a number of readability tests on the text and output the results, and gave some statistical information about the sentences of the text. Aspen Software of Albuquerque, New Mexico released the earliest version of a diction and style checker for personal computers, Grammatik, in 1981. Grammatik was first available for a Radio Shack - TRS-80, and soon had versions for CP/M and the IBM PC. Reference Software International of San Francisco, California, acquired Grammatik in 1985. Development of Grammatik continued, and it became an actual grammar checker that could detect writing errors beyond simple style checking. Other early diction and style checking programs included Punctuation & Style, Correct Grammar, RightWriter and PowerEdit. While all the earliest programs started as simple diction and style checkers, all eventually added various levels of language processing, and developed some level of true grammar checking capability. Until 1992, grammar checkers were sold as add-on programs. There were a large number of different word processing programs available at that time, with WordPerfect and Microsoft Word the top two in market share. In 1992, Microsoft decided to add grammar checking as a feature of Word, and licensed CorrecText, a grammar checker from Houghton Mifflin that had not yet been marketed as a standalone product. WordPerfect answered Microsoft's move by acquiring Reference Software, and the direct descendant of Grammatik is still included with WordPerfect. As of 2019, grammar checkers are built into systems like Google Docs, browser extensions like Grammarly and Qordoba, desktop applications like Ginger, free and open-source software like LanguageTool, and text editor plugins like those available from WebSpellChecker Software. == Technical issues == The earliest writing style programs checked for wordy, trite, clichéd, or misused phrases in a text. This process was based on simple pattern matching. The heart of the program was a list of many hundreds or thousands of phrases that are considered poor writing by many experts. The list of questionable phrases included alternative wording for each phrase. The checking program would simply break text into sentences, check for any matches in the phrase dictionary, flag suspect phrases and show an alternative. These programs could also perform some mechanical checks. For example, they would typically flag doubled words, doubled punctuation, some capitalization errors, and other simple mechanical mistakes. True grammar checking is more complex. While a programming language has a very specific syntax and grammar, this is not so for natural languages. One can write a somewhat complete formal grammar for a natural language, but there are usually so many exceptions in real usage that a formal grammar is of minimal help in writing a grammar checker. One of the most important parts of a natural language grammar checker is a dictionary of all the words in the language, along with the part of speech of each word. The fact that a natural word may be used as any one of several parts of speech (such as "free" being used as an adjective, adverb, noun, or verb) greatly increases the complexity of any grammar checker. A grammar checker will find each sentence in a text, look up each word in the dictionary, and then attempt to parse the sentence into a form that matches a grammar. Using various rules, the program can then detect various errors, such as agreement in tense, number, word order, and so on. It is also possible to detect some stylistic problems with the text. For example, some popular style guides such as The Elements of Style deprecate excessive use of the passive voice. Grammar checkers may attempt to identify passive sentences and suggest an active-voice alternative. The software elements required for grammar checking are closely related to some of the development issues that need to be addressed for speech recognition software. In voice recognition, parsing can be used to help predict which word is most likely intended, based on part of speech and position in the sentence. In grammar checking, the parsing is used to detect words that fail to follow accepted grammar usage. Recently, research has focused on developing algorithms which can recognize grammar errors based on the context of the surrounding words. == Criticism == Grammar checkers are considered a type of foreign language writing aid which non-native speakers can use to proofread their writings as such programs endeavor to identify syntactical errors. However, as with other computerized writing aids such as spell checkers, popular grammar checkers are often criticized when they fail to spot errors and incorrectly flag correct text as erroneous. The linguist Geoffrey K. Pullum argued in 2007 that they were generally so inaccurate as to do more harm than good: "for the most part, accepting the advice of a computer grammar checker on your prose will make it much worse, sometimes hilariously incoherent."
Cyclodisparity
In vision science, cyclodisparity is the difference in the rotation angle of an object or scene viewed by the left and right eyes. Cyclodisparity can result from the eyes' torsional rotation (cyclorotation) or can be created artificially by presenting to the eyes two images that need to be rotated relative to each other for binocular fusion to take place. == Human and animal vision == The eyes and visual system can compensate for cyclodisparity up to a certain point; if the cyclodisparity is larger than a threshold, the images cannot be fused, resulting stereoblindness, and in double vision in subjects who otherwise have full stereo vision. When a human subject is presented with images that have artificial cyclodisparity, cyclovergence is evoked, that is, a motor response of the eye muscles that rotates the two eyes in opposite directions, thereby reducing cyclodisparity. Visually-induced cyclovergence of up to 8 degrees has been observed in normal subjects. Furthermore, up to about 8 degrees can usually be compensated by purely sensory means, that is, without physical eye rotation. This means that the normal human observer can achieve binocular image fusion in presence of cyclodisparity of up to approximately 16 degrees. Cyclodisparity due to images having been rotated inward can be compensated better when the gaze is directed downwards, and cyclodisparity due to an outward rotation can be compensated better when the gaze is directed upwards. A proposed explanation for this phenomenon is that the motor system is coordinated in such a way that the eyes perform a torsional movement to reduce the size of the search zones and thus the computational load required for solving the correspondence problem. The resulting cyclovergence at near gaze is smaller than the cyclovergence predicted by Listing's law. == Video processing and computer vision == Active camera torsion can be used in machine and computer vision for several purposes. For instance, camera torsion can be used to make improved use of the search range over which matching detectors or stereo matching algorithms operate, or to make a 3D slanted surface appear frontoparallel for further stereo processing. For image compression purposes, images with cyclodisparity are advantageously encoded using global motion compensation using a rotational motion model.
VMDS
VMDS abbreviates the relational database technology called Version Managed Data Store provided by GE Energy as part of its Smallworld technology platform and was designed from the outset to store and analyse the highly complex spatial and topological networks typically used by enterprise utilities such as power distribution and telecommunications. VMDS was originally introduced in 1990 as has been improved and updated over the years. Its current version is 6.0. VMDS has been designed as a spatial database. This gives VMDS a number of distinctive characteristics when compared to conventional attribute only relational databases. == Distributed server processing == VMDS is composed of two parts: a simple, highly scalable data block server called SWMFS (Smallworld Master File Server) and an intelligent client API written in C and Magik. Spatial and attribute data are stored in data blocks that reside in special files called data store files on the server. When the client application requests data it has sufficient intelligence to work out the optimum set of data blocks that are required. This request is then made to SWMFS which returns the data to the client via the network for processing. This approach is particularly efficient and scalable when dealing with spatial and topological data which tends to flow in larger volumes and require more processing then plain attribute data (for example during a map redraw operation). This approach makes VMDS well suited to enterprise deployment that might involve hundreds or even thousands of concurrent clients. == Support for long transactions == Relational databases support short transactions in which changes to data are relatively small and are brief in terms in duration (the maximum period between the start and the end of a transaction is typically a few seconds or less). VMDS supports long transactions in which the volume of data involved in the transaction can be substantial and the duration of the transaction can be significant (days, weeks or even months). These types of transaction are common in advanced network applications used by, for example, power distribution utilities. Due to the time span of a long transaction in this context the amount of change can be significant (not only within the scope of the transaction, but also within the context of the database as a whole). Accordingly, it is likely that the same record might be changed more than once. To cope with this scenario VMDS has inbuilt support for automatically managing such conflicts and allows applications to review changes and accept only those edits that are correct. == Spatial and topological capabilities == As well as conventional relational database features such as attribute querying, join fields, triggers and calculated fields, VMDS has numerous spatial and topological capabilities. This allows spatial data such as points, texts, polylines, polygons and raster data to be stored and analysed. Spatial functions include: find all features within a polygon, calculate the Voronoi polygons of a set of sites and perform a cluster analysis on a set of points. Vector spatial data such as points, polylines and polygons can be given topological attributes that allow complex networks to be modelled. Network analysis engines are provided to answer questions such as find the shortest path between two nodes or how to optimize a delivery route (the travelling salesman problem). A topology engine can be configured with a set of rules that define how topological entities interact with each other when new data is added or existing data edited. == Data abstraction == In VMDS all data is presented to the application as objects. This is different from many relational databases that present the data as rows from a table or query result using say JDBC. VMDS provides a data modelling tool and underlying infrastructure as part of the Smallworld technology platform that allows administrators to associate a table in the database with a Magik exemplar (or class). Magik get and set methods for the Magik exemplar can be automatically generated that expose a table's field (or column). Each VMDS row manifests itself to the application as an instance of a Magik object and is known as an RWO (or real world object). Tables are known as collections in Smallworld parlance. # all_rwos hold all the rwos in the database and is heterogeneous all_rwos << my_application.rwo_set() # valve_collection holds the valve collection valves << all_rwos.select(:collection, {:valve}) number_of_valves << valves.size Queries are built up using predicate objects: # find 'open' valves. open_valves << valves.select(predicate.eq(:operating_status, "open")) number_of_open_valves << open_valves.size _for valve _over open_valves.elements() _loop write(valve.id) _endloop Joins are implemented as methods on the parent RWO. For example, a manager might have several employees who report to him: # get the employee collection. employees << my_application.database.collection(:gis, :employees) # find a manager called 'Steve' and get the first matching element steve << employees.select(predicate.eq(:name, "Steve").and(predicate.eq(:role, "manager")).an_element() # display the names of his direct reports. name is a field (or column) # on the employee collection (or table) _for employee _over steve.direct_reports.elements() _loop write(employee.name) _endloop Performing a transaction: # each key in the hash table corresponds to the name of the field (or column) in # the collection (or table) valve_data << hash_table.new_with( :asset_id, 57648576, :material, "Iron") # get the valve collection directly valve_collection << my_application.database.collection(:gis, :valve) # create an insert transaction to insert a new valve record into the collection a # comment can be provide that describes the transaction transaction << record_transaction.new_insert(valve_collection, valve_data, "Inserted a new valve") transaction.run()
Documentation science
Documentation science is the study of the recording and retrieval of information. It includes methods for storing, retrieving, and sharing of information captured on physical as well as digital documents. This field is closely linked to the fields of library science and information science but has its own theories and practices. The term documentation science was coined by Belgian lawyer and peace activist Paul Otlet. He is considered to be the forefather of information science. He along with Henri La Fontaine laid the foundations of documentation science as a field of study. Professionals in this field are called documentalists. Over the years, documentation science has grown to become a large and important field of study. Evolving from traditional practices like archiving and retrieval to modern theories about the nature of documents, novel methods for organizing digital information, and applications in libraries, research, healthcare, business, and technology and more. This field continues to evolve in the digital age. == Developments in documentation science == 1895: The International Institute of Bibliography (originally Institut International de Bibliographie, IIB) was established on 12 September 1895, in Brussels, Belgium by Paul Otlet and Henri La Fontaine. It aimed to catalog all recorded knowledge using a universal classification system now known as the Universal Decimal Classification (UDC). 1931: International Institute of Bibliography (originally Institut International de Bibliographie, IIB) was renamed The International Institute for Documentation, (Institut International de Documentation, IID). 1934: Paul Otlet envisioned a “radiated library,” a global network of interconnected documents accessible from anywhere via telecommunication. This early idea is now seen as a forerunner of the internet. 1937: American Documentation Institute was founded (1968 nameshift to American Society for Information Science). 1951: Suzanne Briet published Qu'est-ce que la documentation? where she proposed that “a document is evidence in support of a fact,” expanding the definition to include objects such as animals in zoos when they are part of a scientific study. This was a significant theoretical shift in defining documents. 1965-1990: Documentation departments were established, for example, large research libraries, online computer retrieval systems and more. The persons doing the searches were called documentalists. But with the appearance of first CD-ROM databases in the mid-1980s and later the internet in 1990s, these intermediary searches decreased and most such departments closed or merged with other departments. 1996: "Dokvit", Documentation Studies, was established in 1996 at the University of Tromsø in Norway. 2001: The Document Academy was established. It is an international network that celebrates documentation. It was conducted by The Program of Documentation Studies, University of Tromsø, Norway and The School of Information Management and Systems, UC Berkeley. 2003: The first Document Research Conference (DOCAM), a series of conferences made by the Document Academy. DOCAM '03 (2003) was held 13–15 August 2003 at The School of Information Management and Systems (SIMS) at the University of California, Berkeley. 2007: Michael Buckland, Ronald Day, and Birger Hjørland expanded the theoretical foundations of documentation science. They researched and explored documents to be social artifacts, the role of ideology in classification, and how documents influenced knowledge systems. 2010s: The concept of post-documentation or “documentality” began in the 2010s, which focused on how digital traces (e.g., tweets, logs) function as documents without traditional physical form. This led to new thinking in document theory. 2016–present: The Document Academy's DOCAM conferences have continued, offering ongoing developments in the theory and practice of documentation. Themes include affect, memory, activism, and born-digital records. 2017: The journal Information Research published special issues addressing “document theory,” including views on documentation in virtual environments and digital archives. 2020–present: The growth of research data management (RDM) and open science has made documentation practices central to data sharing, metadata standards, and reproducibility in scientific work. == Theoretical foundations == Documentation science has some deep theories that explain what a document is, how people use documents, and how they are organized. These concepts were introduced by scholars who have not only studied libraries, but also philosophy, language, and social sciences. Suzanne Briet described a document as “any material form of evidence” that is made to be used as proof or to share information. An antelope in a zoo, for example, can be a document because it is being studied, classified, and described. Documents are not just things or materials but are also shaped by society. Michael Buckland noted that documents have meaning only when people agree they are useful or valid as information. He explained a document becomes a document when someone decides to use it as evidence. Ronald Day wrote about how documentation is not neutral, it can be influenced by power, ideology, and politics. He claimed that classification systems, like how libraries organize books, are not just technical tools. They also show what kinds of knowledge are seen as more important than others. In recent years, new theories have been introduced, like “documentality” by Maurizio Ferraris. He proposed that a document does not have to be a paper or file, it can also be something digital like a tweet, a database entry, or a log file, as long as it leaves a trace that can be looked at later. This theory helps explain modern digital documents. == Methodologies and practice == Documentation science includes many methods that help people collect, organize, store, and find information. These practices are used in libraries, archives, research labs, companies, and now also in online systems. === Collecting and creating documents === In the past, documentation work included gathering books, articles, reports, and other printed materials. People created records of these materials manually, using catalog cards, indexes, or bibliographies. Paul Otlet’s work with the Universal Bibliographic Repertory is one example. He created millions of card entries to organize knowledge from around the world. Today, documents are not only created by humans. Computers and machines also generate documents, like log files, metadata, and sensor data. These need new tools and methods for collection and management. === Organizing information === Organizing documents has always been a foundational element of documentation science. Methods like classification (dividing things into groups) and indexing (making lists of topics or keywords) help individuals find what they need. A widely used system is the Universal Decimal Classification (UDC) developed by Otlet and La Fontaine. Another is the Library of Congress Classification (LCC) used in the majority of U.S. libraries. Indexing can be performed by humans or by software programs that read the text and add tags to documents. Metadata is also used to describe documents. Metadata is “data about data” like the title, author, date, and subject of a document. Standards like Dublin Core are used in digital libraries to keep metadata consistent. === Retrieval and access === One of the main objectives of documentation is helping users find the right document. This is called information retrieval. In the past, this meant using catalog drawers or printed indexes. Today, people use search engines, databases, and digital libraries. Modern retrieval tools use Boolean logic, ranking algorithms, and sometimes machine learning to show the most useful results first. This is part of what is studied in both documentation science and information retrieval. === Preservation and archiving === Documents require long-term storage. This is called preservation of documents. Printed documents can be damaged by light, pests, or even time on the other hand digital documents can be deemed worthless if formats become outdated or storage facilities fail. Archivists use methods like migration, which includes moving files to new formats, and emulation, which replicates obsolete systems, to preserve materials. These methods and tools are ever changing as new technologies develop. But the main objective of documentation has remained the same, which is to keep information safe, organized, and easy to find. == Documentation in the digital age == With the expansion of the internet, computers, and cloud storage, documents are no longer just books, papers, or reports. They can now be emails, tweets, videos, websites, databases, or even log files created by machines. === Born-digital documents === Many documents today are created directly in digital form. These are called born-digit
External memory algorithm
In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (auxiliary memory) such as hard drives or tape drives, or when memory is on a computer network. External memory algorithms are analyzed in the external memory model. == Model == External memory algorithms are analyzed in an idealized model of computation called the external memory model (or I/O model, or disk access model). The external memory model is an abstract machine similar to the RAM machine model, but with a cache in addition to main memory. The model captures the fact that read and write operations are much faster in a cache than in main memory, and that reading long contiguous blocks is faster than reading randomly using a disk read-and-write head. The running time of an algorithm in the external memory model is defined by the number of reads and writes to memory required. The model was introduced by Alok Aggarwal and Jeffrey Vitter in 1988. The external memory model is related to the cache-oblivious model, but algorithms in the external memory model may know both the block size and the cache size. For this reason, the model is sometimes referred to as the cache-aware model. The model consists of a processor with an internal memory or cache of size M, connected to an unbounded external memory. Both the internal and external memory are divided into blocks of size B. One input/output or memory transfer operation consists of moving a block of B contiguous elements from external to internal memory, and the running time of an algorithm is determined by the number of these input/output operations. == Algorithms == Algorithms in the external memory model take advantage of the fact that retrieving one object from external memory retrieves an entire block of size B. This property is sometimes referred to as locality. Searching for an element among N objects is possible in the external memory model using a B-tree with branching factor B. Using a B-tree, searching, insertion, and deletion can be achieved in O ( log B N ) {\displaystyle O(\log _{B}N)} time (in Big O notation). Information theoretically, this is the minimum running time possible for these operations, so using a B-tree is asymptotically optimal. External sorting is sorting in an external memory setting. External sorting can be done via distribution sort, which is similar to quicksort, or via a M B {\displaystyle {\tfrac {M}{B}}} -way merge sort. Both variants achieve the asymptotically optimal runtime of O ( N B log M B N B ) {\displaystyle O\left({\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)} to sort N objects. This bound also applies to the fast Fourier transform in the external memory model. The permutation problem is to rearrange N elements into a specific permutation. This can either be done either by sorting, which requires the above sorting runtime, or inserting each element in order and ignoring the benefit of locality. Thus, permutation can be done in O ( min ( N , N B log M B N B ) ) {\displaystyle O\left(\min \left(N,{\frac {N}{B}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)\right)} time. == Applications == The external memory model captures the memory hierarchy, which is not modeled in other common models used in analyzing data structures, such as the random-access machine, and is useful for proving lower bounds for data structures. The model is also useful for analyzing algorithms that work on datasets too big to fit in internal memory. A typical example is geographic information systems, especially digital elevation models, where the full data set easily exceeds several gigabytes or even terabytes of data. This methodology extends beyond general purpose CPUs and also includes GPU computing as well as classical digital signal processing. In general-purpose computing on graphics processing units (GPGPU), powerful graphics cards (GPUs) with little memory (compared with the more familiar system memory, which is most often referred to simply as RAM) are utilized with relatively slow CPU-to-GPU memory transfer (when compared with computation bandwidth). == History == An early use of the term "out-of-core" as an adjective is in 1962 in reference to devices that are other than the core memory of an IBM 360. An early use of the term "out-of-core" with respect to algorithms appears in 1971.
Random feature
Random features (RF) are a technique used in machine learning to approximate kernel methods, introduced by Ali Rahimi and Ben Recht in their 2007 paper "Random Features for Large-Scale Kernel Machines", and extended by. RF uses a Monte Carlo approximation to kernel functions by randomly sampled feature maps. It is used for datasets that are too large for traditional kernel methods like support vector machine, kernel ridge regression, and gaussian process. == Mathematics == === Kernel method === Given a feature map ϕ : R d → V {\textstyle \phi :\mathbb {R} ^{d}\to V} , where V {\textstyle V} is a Hilbert space (more specifically, a reproducing kernel Hilbert space), the kernel trick replaces inner products in feature space ⟨ ϕ ( x i ) , ϕ ( x j ) ⟩ V {\displaystyle \langle \phi (x_{i}),\phi (x_{j})\rangle _{V}} by a kernel function k ( x i , x j ) : R d × R d → R {\displaystyle k(x_{i},x_{j}):\mathbb {R} ^{d}\times \mathbb {R} ^{d}\to \mathbb {R} } Kernel methods replaces linear operations in high-dimensional space by operations on the kernel matrix: K X := [ k ( x i , x j ) ] i , j ∈ 1 : N {\displaystyle K_{X}:=[k(x_{i},x_{j})]_{i,j\in 1:N}} where N {\textstyle N} is the number of data points. === Random kernel method === The problem with kernel methods is that the kernel matrix K X {\textstyle K_{X}} has size N × N {\textstyle N\times N} . This becomes computationally infeasible when N {\textstyle N} reaches the order of a million. The random kernel method replaces the kernel function k {\textstyle k} by an inner product in low-dimensional feature space R D {\textstyle \mathbb {R} ^{D}} : k ( x , y ) ≈ ⟨ z ( x ) , z ( y ) ⟩ {\displaystyle k(x,y)\approx \langle z(x),z(y)\rangle } where z {\textstyle z} is a randomly sampled feature map z : R d → R D {\textstyle z:\mathbb {R} ^{d}\to \mathbb {R} ^{D}} . This converts kernel linear regression into linear regression in feature space, kernel SVM into SVM in feature space, etc. Since we have K X ≈ Z X T Z X {\displaystyle K_{X}\approx Z_{X}^{T}Z_{X}} where Z X = [ z ( x 1 ) , … , z ( x N ) ] {\displaystyle Z_{X}=[z(x_{1}),\dots ,z(x_{N})]} , these methods no longer involve matrices of size O ( N 2 ) {\textstyle O(N^{2})} , but only random feature matrices of size O ( D N ) {\textstyle O(DN)} . == Random Fourier feature == === Radial basis function kernel === The radial basis function (RBF) kernel on two samples x i , x j ∈ R d {\displaystyle x_{i},x_{j}\in \mathbb {R} ^{d}} is defined as k ( x i , x j ) = exp ( − ‖ x i − x j ‖ 2 2 σ 2 ) {\displaystyle k(x_{i},x_{j})=\exp \left(-{\frac {\|x_{i}-x_{j}\|^{2}}{2\sigma ^{2}}}\right)} where ‖ x i − x j ‖ 2 {\displaystyle \|x_{i}-x_{j}\|^{2}} is the squared Euclidean distance and σ {\displaystyle \sigma } is a free parameter defining the shape of the kernel. It can be approximated by a random Fourier feature map z : R d → R 2 D {\displaystyle z:\mathbb {R} ^{d}\to \mathbb {R} ^{2D}} : z ( x ) := 1 D [ cos ⟨ ω 1 , x ⟩ , sin ⟨ ω 1 , x ⟩ , … , cos ⟨ ω D , x ⟩ , sin ⟨ ω D , x ⟩ ] T {\displaystyle z(x):={\frac {1}{\sqrt {D}}}[\cos \langle \omega _{1},x\rangle ,\sin \langle \omega _{1},x\rangle ,\ldots ,\cos \langle \omega _{D},x\rangle ,\sin \langle \omega _{D},x\rangle ]^{T}} where ω 1 , . . . , ω D {\displaystyle \omega _{1},...,\omega _{D}} are IID samples from the multidimensional normal distribution N ( 0 , σ − 2 I ) {\displaystyle N(0,\sigma ^{-2}I)} . Since cos , sin {\displaystyle \cos ,\sin } are bounded, there is a stronger convergence guarantee by Hoeffding's inequality. === Random Fourier features === By Bochner's theorem, the above construction can be generalized to arbitrary positive definite shift-invariant kernel k ( x , y ) = k ( x − y ) {\displaystyle k(x,y)=k(x-y)} . Define its Fourier transform p ( ω ) = 1 2 π ∫ R d e − j ⟨ ω , Δ ⟩ k ( Δ ) d Δ {\displaystyle p(\omega )={\frac {1}{2\pi }}\int _{\mathbb {R} ^{d}}e^{-j\langle \omega ,\Delta \rangle }k(\Delta )d\Delta } then ω 1 , . . . , ω D {\displaystyle \omega _{1},...,\omega _{D}} are sampled IID from the probability distribution with probability density p {\displaystyle p} . This applies for other kernels like the Laplace kernel and the Cauchy kernel. === Neural network interpretation === Given a random Fourier feature map z {\displaystyle z} , training the feature on a dataset by featurized linear regression is equivalent to fitting complex parameters θ 1 , … , θ D ∈ C {\displaystyle \theta _{1},\dots ,\theta _{D}\in \mathbb {C} } such that f θ ( x ) = R e ( ∑ k θ k e i ⟨ ω k , x ⟩ ) {\displaystyle f_{\theta }(x)=\mathrm {Re} \left(\sum _{k}\theta _{k}e^{i\langle \omega _{k},x\rangle }\right)} which is a neural network with a single hidden layer, with activation function t ↦ e i t {\displaystyle t\mapsto e^{it}} , zero bias, and the parameters in the first layer frozen. In the overparameterized case, when 2 D ≥ N {\displaystyle 2D\geq N} , the network linearly interpolates the dataset { ( x i , y i ) } i ∈ 1 : N {\displaystyle \{(x_{i},y_{i})\}_{i\in 1:N}} , and the network parameters is the least-norm solution: θ ^ = arg min θ ∈ C D , f θ ( x k ) = y k ∀ k ∈ 1 : N ‖ θ ‖ {\displaystyle {\hat {\theta }}=\arg \min _{\theta \in \mathbb {C} ^{D},f_{\theta }(x_{k})=y_{k}\forall k\in 1:N}\|\theta \|} At the limit of D → ∞ {\displaystyle D\to \infty } , the L2 norm ‖ θ ^ ‖ → ‖ f K ‖ H {\displaystyle \|{\hat {\theta }}\|\to \|f_{K}\|_{H}} where f K {\displaystyle f_{K}} is the interpolating function obtained by the kernel regression with the original kernel, and ‖ ⋅ ‖ H {\displaystyle \|\cdot \|_{H}} is the norm in the reproducing kernel Hilbert space for the kernel. == Other examples == === Random binning features === A random binning features map partitions the input space using randomly shifted grids at randomly chosen resolutions and assigns to an input point a binary bit string that corresponds to the bins in which it falls. The grids are constructed so that the probability that two points x i , x j ∈ R d {\displaystyle x_{i},x_{j}\in \mathbb {R} ^{d}} are assigned to the same bin is proportional to K ( x i , x j ) {\displaystyle K(x_{i},x_{j})} . The inner product between a pair of transformed points is proportional to the number of times the two points are binned together, and is therefore an unbiased estimate of K ( x i , x j ) {\displaystyle K(x_{i},x_{j})} . Since this mapping is not smooth and uses the proximity between input points, Random Binning Features works well for approximating kernels that depend only on the L 1 {\displaystyle L_{1}} distance between datapoints. === Orthogonal random features === Orthogonal random features uses a random orthogonal matrix instead of a random Fourier matrix. == Historical context == In NIPS 2006, deep learning had just become competitive with linear models like PCA and linear SVMs for large datasets, and people speculated about whether it could compete with kernel SVMs. However, there was no way to train kernel SVM on large datasets. The two authors developed the random feature method to train those. It was then found that the O ( 1 / D ) {\displaystyle O(1/D)} variance bound did not match practice: the variance bound predicts that approximation to within 0.01 {\displaystyle 0.01} requires D ∼ 10 4 {\displaystyle D\sim 10^{4}} , but in practice required only ∼ 10 2 {\displaystyle \sim 10^{2}} . Attempting to discover what caused this led to the subsequent two papers.
Zassenhaus algorithm
In mathematics, the Zassenhaus algorithm is a method to calculate a basis for the intersection and sum of two subspaces of a vector space. It is named after Hans Zassenhaus, but no publication of this algorithm by him is known. It is used in computer algebra systems. == Algorithm == === Input === Let V be a vector space and U, W two finite-dimensional subspaces of V with the following spanning sets: U = ⟨ u 1 , … , u n ⟩ {\displaystyle U=\langle u_{1},\ldots ,u_{n}\rangle } and W = ⟨ w 1 , … , w k ⟩ . {\displaystyle W=\langle w_{1},\ldots ,w_{k}\rangle .} Finally, let B 1 , … , B m {\displaystyle B_{1},\ldots ,B_{m}} be linearly independent vectors so that u i {\displaystyle u_{i}} and w i {\displaystyle w_{i}} can be written as u i = ∑ j = 1 m a i , j B j {\displaystyle u_{i}=\sum _{j=1}^{m}a_{i,j}B_{j}} and w i = ∑ j = 1 m b i , j B j . {\displaystyle w_{i}=\sum _{j=1}^{m}b_{i,j}B_{j}.} === Output === The algorithm computes the base of the sum U + W {\displaystyle U+W} and a base of the intersection U ∩ W {\displaystyle U\cap W} . === Algorithm === The algorithm creates the following block matrix of size ( ( n + k ) × ( 2 m ) ) {\displaystyle ((n+k)\times (2m))} : ( a 1 , 1 a 1 , 2 ⋯ a 1 , m a 1 , 1 a 1 , 2 ⋯ a 1 , m ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ a n , 1 a n , 2 ⋯ a n , m a n , 1 a n , 2 ⋯ a n , m b 1 , 1 b 1 , 2 ⋯ b 1 , m 0 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ b k , 1 b k , 2 ⋯ b k , m 0 0 ⋯ 0 ) {\displaystyle {\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots &a_{1,m}&a_{1,1}&a_{1,2}&\cdots &a_{1,m}\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\a_{n,1}&a_{n,2}&\cdots &a_{n,m}&a_{n,1}&a_{n,2}&\cdots &a_{n,m}\\b_{1,1}&b_{1,2}&\cdots &b_{1,m}&0&0&\cdots &0\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\b_{k,1}&b_{k,2}&\cdots &b_{k,m}&0&0&\cdots &0\end{pmatrix}}} Using elementary row operations, this matrix is transformed to the row echelon form. Then, it has the following shape: ( c 1 , 1 c 1 , 2 ⋯ c 1 , m ∙ ∙ ⋯ ∙ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ c q , 1 c q , 2 ⋯ c q , m ∙ ∙ ⋯ ∙ 0 0 ⋯ 0 d 1 , 1 d 1 , 2 ⋯ d 1 , m ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 0 d ℓ , 1 d ℓ , 2 ⋯ d ℓ , m 0 0 ⋯ 0 0 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 0 0 0 ⋯ 0 ) {\displaystyle {\begin{pmatrix}c_{1,1}&c_{1,2}&\cdots &c_{1,m}&\bullet &\bullet &\cdots &\bullet \\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\c_{q,1}&c_{q,2}&\cdots &c_{q,m}&\bullet &\bullet &\cdots &\bullet \\0&0&\cdots &0&d_{1,1}&d_{1,2}&\cdots &d_{1,m}\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\0&0&\cdots &0&d_{\ell ,1}&d_{\ell ,2}&\cdots &d_{\ell ,m}\\0&0&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &&\vdots &\vdots &\vdots &&\vdots \\0&0&\cdots &0&0&0&\cdots &0\end{pmatrix}}} Here, ∙ {\displaystyle \bullet } stands for arbitrary numbers, and the vectors ( c p , 1 , c p , 2 , … , c p , m ) {\displaystyle (c_{p,1},c_{p,2},\ldots ,c_{p,m})} for every p ∈ { 1 , … , q } {\displaystyle p\in \{1,\ldots ,q\}} and ( d p , 1 , … , d p , m ) {\displaystyle (d_{p,1},\ldots ,d_{p,m})} for every p ∈ { 1 , … , ℓ } {\displaystyle p\in \{1,\ldots ,\ell \}} are nonzero. Then ( y 1 , … , y q ) {\displaystyle (y_{1},\ldots ,y_{q})} with y i := ∑ j = 1 m c i , j B j {\displaystyle y_{i}:=\sum _{j=1}^{m}c_{i,j}B_{j}} is a basis of U + W {\displaystyle U+W} and ( z 1 , … , z ℓ ) {\displaystyle (z_{1},\ldots ,z_{\ell })} with z i := ∑ j = 1 m d i , j B j {\displaystyle z_{i}:=\sum _{j=1}^{m}d_{i,j}B_{j}} is a basis of U ∩ W {\displaystyle U\cap W} . === Proof of correctness === First, we define π 1 : V × V → V , ( a , b ) ↦ a {\displaystyle \pi _{1}:V\times V\to V,(a,b)\mapsto a} to be the projection to the first component. Let H := { ( u , u ) ∣ u ∈ U } + { ( w , 0 ) ∣ w ∈ W } ⊆ V × V . {\displaystyle H:=\{(u,u)\mid u\in U\}+\{(w,0)\mid w\in W\}\subseteq V\times V.} Then π 1 ( H ) = U + W {\displaystyle \pi _{1}(H)=U+W} and H ∩ ( 0 × V ) = 0 × ( U ∩ W ) {\displaystyle H\cap (0\times V)=0\times (U\cap W)} . Also, H ∩ ( 0 × V ) {\displaystyle H\cap (0\times V)} is the kernel of π 1 | H {\displaystyle {\pi _{1}|}_{H}} , the projection restricted to H. Therefore, dim ( H ) = dim ( U + W ) + dim ( U ∩ W ) {\displaystyle \dim(H)=\dim(U+W)+\dim(U\cap W)} . The Zassenhaus algorithm calculates a basis of H. In the first m columns of this matrix, there is a basis y i {\displaystyle y_{i}} of U + W {\displaystyle U+W} . The rows of the form ( 0 , z i ) {\displaystyle (0,z_{i})} (with z i ≠ 0 {\displaystyle z_{i}\neq 0} ) are obviously in H ∩ ( 0 × V ) {\displaystyle H\cap (0\times V)} . Because the matrix is in row echelon form, they are also linearly independent. All rows which are different from zero ( ( y i , ∙ ) {\displaystyle (y_{i},\bullet )} and ( 0 , z i ) {\displaystyle (0,z_{i})} ) are a basis of H, so there are dim ( U ∩ W ) {\displaystyle \dim(U\cap W)} such z i {\displaystyle z_{i}} s. Therefore, the z i {\displaystyle z_{i}} s form a basis of U ∩ W {\displaystyle U\cap W} . == Example == Consider the two subspaces U = ⟨ ( 1 − 1 0 1 ) , ( 0 0 1 − 1 ) ⟩ {\displaystyle U=\left\langle \left({\begin{array}{r}1\\-1\\0\\1\end{array}}\right),\left({\begin{array}{r}0\\0\\1\\-1\end{array}}\right)\right\rangle } and W = ⟨ ( 5 0 − 3 3 ) , ( 0 5 − 3 − 2 ) ⟩ {\displaystyle W=\left\langle \left({\begin{array}{r}5\\0\\-3\\3\end{array}}\right),\left({\begin{array}{r}0\\5\\-3\\-2\end{array}}\right)\right\rangle } of the vector space R 4 {\displaystyle \mathbb {R} ^{4}} . Using the standard basis, we create the following matrix of dimension ( 2 + 2 ) × ( 2 ⋅ 4 ) {\displaystyle (2+2)\times (2\cdot 4)} : ( 1 − 1 0 1 1 − 1 0 1 0 0 1 − 1 0 0 1 − 1 5 0 − 3 3 0 0 0 0 0 5 − 3 − 2 0 0 0 0 ) . {\displaystyle \left({\begin{array}{rrrrrrrr}1&-1&0&1&&1&-1&0&1\\0&0&1&-1&&0&0&1&-1\\\\5&0&-3&3&&0&0&0&0\\0&5&-3&-2&&0&0&0&0\end{array}}\right).} Using elementary row operations, we transform this matrix into the following matrix: ( 1 0 0 0 ∙ ∙ ∙ ∙ 0 1 0 − 1 ∙ ∙ ∙ ∙ 0 0 1 − 1 ∙ ∙ ∙ ∙ 0 0 0 0 1 − 1 0 1 ) {\displaystyle \left({\begin{array}{rrrrrrrrr}1&0&0&0&&\bullet &\bullet &\bullet &\bullet \\0&1&0&-1&&\bullet &\bullet &\bullet &\bullet \\0&0&1&-1&&\bullet &\bullet &\bullet &\bullet \\\\0&0&0&0&&1&-1&0&1\end{array}}\right)} (Some entries have been replaced by " ∙ {\displaystyle \bullet } " because they are irrelevant to the result.) Therefore ( ( 1 0 0 0 ) , ( 0 1 0 − 1 ) , ( 0 0 1 − 1 ) ) {\displaystyle \left(\left({\begin{array}{r}1\\0\\0\\0\end{array}}\right),\left({\begin{array}{r}0\\1\\0\\-1\end{array}}\right),\left({\begin{array}{r}0\\0\\1\\-1\end{array}}\right)\right)} is a basis of U + W {\displaystyle U+W} , and ( ( 1 − 1 0 1 ) ) {\displaystyle \left(\left({\begin{array}{r}1\\-1\\0\\1\end{array}}\right)\right)} is a basis of U ∩ W {\displaystyle U\cap W} .