Feature selection

In machine learning, feature selection is the process of selecting a subset of relevant features (variables, predictors) for use in model construction. Feature selection techniques are used for several reasons: simplification of models to make them easier to interpret, shorter training times, to avoid the curse of dimensionality, improve the compatibility of the data with a certain learning model class, to encode inherent symmetries present in the input space. The central premise when using feature selection is that data sometimes contains features that are redundant or irrelevant, and can thus be removed without incurring much loss of information. Redundancy and irrelevance are two distinct notions, since one relevant feature may be redundant in the presence of another relevant feature with which it is strongly correlated. Feature extraction creates new features from functions of the original features, whereas feature selection finds a subset of the features. Feature selection techniques are often used in domains where there are many features and comparatively few samples (data points). == Introduction == A feature selection algorithm can be seen as the combination of a search technique for proposing new feature subsets, along with an evaluation measure which scores the different feature subsets. The simplest algorithm is to test each possible subset of features finding the one which minimizes the error rate. This is an exhaustive search of the space, and is computationally intractable for all but the smallest of feature sets. The choice of evaluation metric heavily influences the algorithm, and it is these evaluation metrics which distinguish between the three main categories of feature selection algorithms: wrappers, filters and embedded methods. Wrapper methods use a predictive model to score feature subsets. Each new subset is used to train a model, which is tested on a hold-out set. Counting the number of mistakes made on that hold-out set (the error rate of the model) gives the score for that subset. As wrapper methods train a new model for each subset, they are very computationally intensive, but usually provide the best performing feature set for that particular type of model or typical problem. Filter methods use a proxy measure instead of the error rate to score a feature subset. This measure is chosen to be fast to compute, while still capturing the usefulness of the feature set. Common measures include the mutual information, the pointwise mutual information, Pearson product-moment correlation coefficient, Relief-based algorithms, and inter/intra class distance or the scores of significance tests for each class/feature combinations. Filters are usually less computationally intensive than wrappers, but they produce a feature set which is not tuned to a specific type of predictive model. This lack of tuning means a feature set from a filter is more general than the set from a wrapper, usually giving lower prediction performance than a wrapper. However the feature set doesn't contain the assumptions of a prediction model, and so is more useful for exposing the relationships between the features. Many filters provide a feature ranking rather than an explicit best feature subset, and the cut off point in the ranking is chosen via cross-validation. Filter methods have also been used as a preprocessing step for wrapper methods, allowing a wrapper to be used on larger problems. One other popular approach is the Recursive Feature Elimination algorithm, commonly used with Support Vector Machines to repeatedly construct a model and remove features with low weights. Embedded methods are a catch-all group of techniques which perform feature selection as part of the model construction process. The exemplar of this approach is the LASSO method for constructing a linear model, which penalizes the regression coefficients with an L1 penalty, shrinking many of them to zero. Any features which have non-zero regression coefficients are 'selected' by the LASSO algorithm. Improvements to the LASSO include Bolasso which bootstraps samples; Elastic net regularization, which combines the L1 penalty of LASSO with the L2 penalty of ridge regression; and FeaLect which scores all the features based on combinatorial analysis of regression coefficients. AEFS further extends LASSO to nonlinear scenario with autoencoders. These approaches tend to be between filters and wrappers in terms of computational complexity. In traditional regression analysis, the most popular form of feature selection is stepwise regression, which is a wrapper technique. It is a greedy algorithm that adds the best feature (or deletes the worst feature) at each round. The main control issue is deciding when to stop the algorithm. In machine learning, this is typically done by cross-validation. In statistics, some criteria are optimized. This leads to the inherent problem of nesting. More robust methods have been explored, such as branch and bound and piecewise linear network. == Subset selection == Subset selection evaluates a subset of features as a group for suitability. Subset selection algorithms can be broken up into wrappers, filters, and embedded methods. Wrappers use a search algorithm to search through the space of possible features and evaluate each subset by running a model on the subset. Wrappers can be computationally expensive and have a risk of over fitting to the model. Filters are similar to wrappers in the search approach, but instead of evaluating against a model, a simpler filter is evaluated. Embedded techniques are embedded in, and specific to, a model. Many popular search approaches use greedy hill climbing, which iteratively evaluates a candidate subset of features, then modifies the subset and evaluates if the new subset is an improvement over the old. Evaluation of the subsets requires a scoring metric that grades a subset of features. Exhaustive search is generally impractical, so at some implementor (or operator) defined stopping point, the subset of features with the highest score discovered up to that point is selected as the satisfactory feature subset. The stopping criterion varies by algorithm; possible criteria include: a subset score exceeds a threshold, a program's maximum allowed run time has been surpassed, etc. Alternative search-based techniques are based on targeted projection pursuit which finds low-dimensional projections of the data that score highly: the features that have the largest projections in the lower-dimensional space are then selected. Search approaches include: Exhaustive Best first Simulated annealing Genetic algorithm Greedy forward selection Greedy backward elimination Particle swarm optimization Targeted projection pursuit Scatter search Variable neighborhood search Two popular filter metrics for classification problems are correlation and mutual information, although neither are true metrics or 'distance measures' in the mathematical sense, since they fail to obey the triangle inequality and thus do not compute any actual 'distance' – they should rather be regarded as 'scores'. These scores are computed between a candidate feature (or set of features) and the desired output category. There are, however, true metrics that are a simple function of the mutual information; see here. Other available filter metrics include: Class separability Error probability Inter-class distance Probabilistic distance Entropy Consistency-based feature selection Correlation-based feature selection == Optimality criteria == The choice of optimality criteria is difficult as there are multiple objectives in a feature selection task. Many common criteria incorporate a measure of accuracy, penalised by the number of features selected. Examples include Akaike information criterion (AIC) and Mallows's Cp, which have a penalty of 2 for each added feature. AIC is based on information theory, and is effectively derived via the maximum entropy principle. Other criteria are Bayesian information criterion (BIC), which uses a penalty of log ⁡ n {\displaystyle {\sqrt {\log {n}}}} for each added feature, minimum description length (MDL) which asymptotically uses log ⁡ n {\displaystyle {\sqrt {\log {n}}}} , Bonferroni / RIC which use 2 log ⁡ p {\displaystyle {\sqrt {2\log {p}}}} , maximum dependency feature selection, and a variety of new criteria that are motivated by false discovery rate (FDR), which use something close to 2 log ⁡ p q {\displaystyle {\sqrt {2\log {\frac {p}{q}}}}} . A maximum entropy rate criterion may also be used to select the most relevant subset of features. == Structure learning == Filter feature selection is a specific case of a more general paradigm called structure learning. Feature selection finds the relevant feature set for a specific target variable whereas structure learning finds the relationships between all the variables, usually by expressing these relationships as a graph. The most common structure learning algorithms

Data access layer

A data access layer (DAL) is a software architectural layer that provides access to data from one or more sources, such as a relational database, NoSQL database, SQL query engine, file system, or other persistent storage. It separates client code from the details of storage systems, query execution, connection handling, and data retrieval. Data access layers are commonly used to centralize data access logic, reduce coupling between applications and data sources, and provide a consistent interface for retrieving, writing, or querying data. Depending on the system, a data access layer may be implemented as application code, a shared library, an intermediary service, or part of a broader database abstraction layer. == In application architecture == In application software, a data access layer provides a boundary between business logic or application code and the systems used to store or retrieve data. For example, a data access layer may expose methods or interfaces for retrieving, writing, or querying data while hiding details such as connection management, SQL statements, storage APIs, error handling, and result conversion. Depending on the application, the layer may return objects, records, tabular results, documents, streams, or other representations of data. A common implementation is a set of classes, functions, or methods that directly reference database queries, stored procedures, storage APIs, or other data sources. For example, instead of using commands such as insert, delete, and update throughout an application to access a specific table, methods such as registerUser or loginUser may be implemented inside the data access layer. Business logic methods from an application can also be mapped to the data access layer. Instead of making several database queries directly, an application can call a single DAL method that abstracts those database calls. Applications using a data access layer may be either dependent on or independent from a particular database server. If the data access layer supports multiple database systems, the application can use any database system that the DAL can access. In either case, the data access layer provides a centralized location for calls into the underlying data store, which can make it easier to maintain, test, or port the application to other storage systems. == Implementation patterns == A data access layer can be implemented using several patterns and technologies, including data access objects, repositories, stored procedures, query builders, database drivers, or object–relational mapping tools. These mechanisms may implement part or all of a data access layer, but are not always equivalent to the layer itself. Object–relational mapping tools are commonly used in data access layers for object-oriented applications that map records in a relational database to objects in a programming language. Other data access layers may expose lower-level database interfaces, tabular results, document-oriented data, files, streams, or protocol-level interfaces. == Use with multiple underlying data systems == A data access layer may be used to abstract differences between multiple underlying data systems, allowing applications to access them through a more consistent interface. In such designs, applications call the DAL rather than interacting directly with each database or storage system. The layer may then handle connection management, query generation, result mapping, error handling, and other implementation details. A data access layer may be implemented as a shared library or as an intermediary service, such as a proxy or gateway. In this configuration, client applications or services connect to the data access layer, which then communicates with one or more underlying databases or query engines. This can provide a common location for authentication, authorization, logging, routing, and translation between different database interfaces. == Interfaces and protocols == Data access layers may expose or use standardized interfaces and protocols for database access. Examples include Open Database Connectivity (ODBC), Java Database Connectivity (JDBC), database-native wire protocols, and newer interfaces such as Apache Arrow Database Connectivity (ADBC) and Arrow Flight SQL. In systems that support multiple data stores, a data access layer may provide a consistent interface while using different drivers, protocols, or query mechanisms internally. == Distinction from related patterns == A data access layer is related to, but broader than, a data access object, which is usually an object-oriented design pattern for encapsulating access to a persistence mechanism. It is also related to a database abstraction layer, which focuses on hiding differences between database systems. In practice, the terms may overlap.

IPUMS

IPUMS, originally the Integrated Public Use Microdata Series, is the world's largest individual-level population database. IPUMS consists of microdata samples from United States (IPUMS-USA) and international (IPUMS-International) census records, as well as data from U.S. and international surveys. The records are converted into a consistent format and made available to researchers through a web-based data dissemination and analysis system. IPUMS is housed at the Institute for Social Research and Data Innovation (ISRDI), an interdisciplinary research center at the University of Minnesota, under the direction of Professor Steven Ruggles. == Description == IPUMS includes all persons enumerated in the United States censuses from 1850 to 1950 (though, the 1890 census is missing because it was destroyed in a fire) and from the American Community Survey since 2000 and the Current Population Survey since 1962. IPUMS includes household-level data for United States Censuses from 1790 to 1840, due to the first six censuses only including the name of the head of household, with tallied household totals following. IPUMS provides consistent variable names, coding schemes, and documentation across all the samples, facilitating the analysis of long-term change. IPUMS-International includes countries from Africa, Asia, Europe, and Latin America for 1960 forward. The database currently includes more than a billion individuals enumerated in 365 censuses from 94 countries around the world. IPUMS-International converts census microdata for multiple countries into a consistent format, allowing for comparisons across countries and time periods. Special efforts are made to simplify use of the data while losing no meaningful information. Comprehensive documentation is provided in a coherent form to facilitate comparative analyses of social and economic change. Additional databases in the IPUMS family include the: North Atlantic Population Project (NAPP) IPUMS National Historical Geographic Information System (NHGIS) IPUMS Health Surveys IPUMS Global Health IPUMS Time Use The Journal of American History described the effort as "One of the great archival projects of the past two decades." Liens Socio, the French portal for the social sciences, gave IPUMS the only “best site” designation that has gone to any non-French website, writing “IPUMS est un projet absolument extraordinaire...époustouflante [mind-blowing]!” The official motto of IPUMS is "use it for good, never for evil." All public IPUMS data and documentation are available online free of charge.

Outline of databases

The following is provided as an overview of and topical guide to databases: Database – organized collection of data, today typically in digital form. The data are typically organized to model relevant aspects of reality (for example, the availability of rooms in hotels), in a way that supports processes requiring this information (for example, finding a hotel with vacancies). == What type of things are databases? == Databases can be described as all of the following: Information – sequence of symbols that can be interpreted as a message. Information can be recorded as signs, or transmitted as signals. Data – values of qualitative or quantitative variables, belonging to a set of items. Data in computing (or data processing) are often represented by a combination of items organized in rows and multiple variables organized in columns. Data are typically the results of measurements and can be visualised using graphs or images. Computer data – information in a form suitable for use with a computer. Data is often distinguished from programs. A program is a sequence of instructions that detail a task for the computer to perform. In this sense, data is everything in software that is not program code. == Types of databases == Active database – Database with event driven features Animation database – Database for storing and reusing animation fragments or motion capture data Back-end database – Organized collection of data in computingPages displaying short descriptions of redirect targets Bibliographic database – database of bibliographic records, an organized digital collection of references to published literature, including journal and newspaper articles, conference proceedings, reports, government and legal publications, patents, books, etc. Centralized database – database located and maintained in one location, unlike a distributed database. Cloud database – Database running on a cloud computing platform Collection database – collection catalog of a museum or archive implemented using a computerized database, in which the institution's objects or material are catalogued. Collective Optimization Database – open repository to enable sharing of benchmarks, data sets and optimization cases from the community, provide web services and Plug-in (computing)|plugins to analyze optimization data and predict program transformations or better hardware designs for multi-objective optimizations based on statistical and machine learning techniques provided there is enough information collected in the repository from multiple users. Configuration management database – Database used to store info on hardware and software assets Cooperative database – holds information on customers and their transactions. Current database – conventional database that stores data that is valid now. Directory – repository or database of information which is optimized for reading, under the assumption that data updates are very rare compared to data reads. Commonly, a directory supports search and browsing in addition to simple lookups. Distributed database – database in which storage devices are not all attached to a common CPU. Document-oriented database – computer program designed for storing, retrieving, and managing document-oriented, or Semi-structured model|semi structured data, information. EDA database – database specialized for the purpose of electronic design automation. Endgame tablebase – computerized database that contains precalculated exhaustive analysis of a chess endgame position. Food composition database (FCDB) – provides detailed information on the nutritional composition of foods. Full-text database – database that contains the complete text of books, dissertations, journals, magazines, newspapers or other kinds of textual documents. Also called a "complete-text database". Government database – collects personal information for various reasons (mass surveillance, Schengen Information System in the European Union, social security, statistics, etc.). Graph database – uses graph structures with nodes, edges, and properties to represent and store data. Knowledge base – special kind of database for knowledge management. A knowledge base provides a means for information to be collected, organised, shared, searched and utilised. Mobile database – can be connected to by a mobile computing device over a mobile network. Navigational database – database in which objects (or records) in it are found primarily by following references from other objects. Non-native speech database – speech database of non-native pronunciations of English. Online database – database accessible from a network, including from the Internet. Operational database – accessed by an Operational System to carry out regular operations of an organization. Parallel database – improves performance through parallelization of various operations, such as loading data, building indexes and evaluating queries. Probabilistic database – uncertain database in which the possible worlds have associated probabilities. Real-time database – processing system designed to handle workloads whose state is constantly changing (Buchmann). Relational database – collection of data items organized as a set of formally described tables from which data can be accessed easily. Spatial database – database that is optimized to store and query data that is related to objects in space, including points, lines and polygons. Temporal database – database with built-in time aspects, for example a temporal data model and a temporal version of Structured Query Language (SQL). Time series database – a time series is an associative array of numbers indexed by a datetime or a datetime range. These time series are often called profiles or curves, depending upon the market. A time series of stock prices might be called a price curve, or a time series of energy consumption might be called a load profile. Despite the disparate naming, the operations performed on them are sufficiently common as to demand special database treatment. Triplestore – purpose-built database for the storage and retrieval of triples, a triple being a data entity composed of subject-predicate-object, like "Bob is 35" or "Bob knows Fred". Very large database (VLDB) – contains an extremely high number of tuples (database rows), or occupies an extremely large physical filesystem storage space. Vulnerability database – platform aimed at collecting, maintaining, and disseminating information about discovered vulnerabilities targeting real computer systems. XLDB – Stands for "eXtremely Large Data Base". XML database – data stored in XML format, where it can be queried, exported and serialized into the desired format. == History of databases == History of databases – History of database management systems –: == Database use == Database usage requirements – Database theory – encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems. Database machine – or is a computer or special hardware that stores and retrieves data from a database. Also called a "back end processor" Database server – computer program that provides database services to other computer programs or computers, as defined by the client-server model. Database application – computer program whose primary purpose is entering and retrieving information from a computer-managed database. Database management system (DBMS) – software package with computer programs that control the creation, maintenance, and use of a database. Database connection – facility in computer science that allows client software to communicate with database server software, whether on the same machine or not. Datasource – name given to the connection set up to a database from a server. The name is commonly used when creating a query to the database. The Database Source Name (DSN) does not have to be the same as the filename for the database. For example, a database file named "friends.mdb" could be set up with a DSN of "school". Then DSN "school" would then be used to refer to the database when performing a query. Data Source Name (DSN) – are data structures used to describe a connection to a data source. Sometimes known as a database source name though data sources are not limited to databases. Database administrator (DBA) – is a person responsible for the installation, configuration, upgrade, administration, monitoring and maintenance of physical databases. Lock – Comparison of database tools – (provides tables for comparing general and technical information for a number of available database administrator tools.) Database-centric architecture – software architectures in which databases play a crucial role. Also called "data-centric architecture". Intelligent database – was put forward as a system that manages information (rather than data) in a way that appears natural to users and which goes beyond simple record keeping. Two-phase locking (2PL) – is a

Kinematic chain

In mechanical engineering, a kinematic chain is an assembly of rigid bodies connected by joints to provide constrained motion that is the mathematical model for a mechanical system. As the word chain suggests, the rigid bodies, or links, are constrained by their connections to other links. An example is the simple open chain formed by links connected in series, like the usual chain, which is the kinematic model for a typical robot manipulator. Mathematical models of the connections, or joints, between two links are termed kinematic pairs. Kinematic pairs model the hinged and sliding joints fundamental to robotics, often called lower pairs and the surface contact joints critical to cams and gearing, called higher pairs. These joints are generally modeled as holonomic constraints. A kinematic diagram is a schematic of the mechanical system that shows the kinematic chain. The modern use of kinematic chains includes analysis of Linkages (mechanical), compliance that arises from flexure joints in precision mechanisms, link compliance in compliant mechanisms and micro-electro-mechanical systems, and cable compliance in cable robotic and tensegrity systems. == Mobility formula == The degrees of freedom, or mobility, of a kinematic chain is the number of parameters that define the configuration of the chain. A system of n rigid bodies moving in space has 6n degrees of freedom measured relative to a fixed frame. This frame is included in the count of bodies, so that mobility does not depend on link that forms the fixed frame. This means the degree-of-freedom of this system is M = 6(N − 1), where N = n + 1 is the number of moving bodies plus the fixed body. Joints that connect bodies impose constraints. Specifically, hinges and sliders each impose five constraints and therefore remove five degrees of freedom. It is convenient to define the number of constraints c that a joint imposes in terms of the joint's freedom f, where c = 6 − f. In the case of a hinge or slider, which are one-degree-of-freedom joints, have f = 1 and therefore c = 6 − 1 = 5. The result in general where d {\displaystyle d} is the degrees of freedom for the mobility of a kinematic chain formed from n moving links and j joints each with freedom fi, i = 1, 2, …, j, is given by M = d n − ∑ i = 1 j ( d − f i ) = d ( N − 1 − j ) + ∑ i = 1 j f i {\displaystyle M=dn-\sum _{i=1}^{j}(d-f_{i})=d(N-1-j)+\sum _{i=1}^{j}f_{i}} Where N is the total number of links and includes the fixed link. Spacial linkages used d = 6 {\displaystyle d=6} and planar linkages use d = 3 {\displaystyle d=3} . This result is known as the Chebychev–Grübler–Kutzbach criterion. == Analysis of kinematic chains == The constraint equations of a kinematic chain couple the range of movement allowed at each joint to the dimensions of the links in the chain, and form algebraic equations that are solved to determine the configuration of the chain associated with specific values of input parameters, called degrees of freedom. The constraint equations for a kinematic chain are obtained using rigid transformations [Z] to characterize the relative movement allowed at each joint and separate rigid transformations [X] to define the dimensions of each link. In the case of a serial open chain, the result is a sequence of rigid transformations alternating joint and link transformations from the base of the chain to its end link, which is equated to the specified position for the end link. A chain of n links connected in series has the kinematic equations, [ T ] = [ Z 1 ] [ X 1 ] [ Z 2 ] [ X 2 ] ⋯ [ X n − 1 ] [ Z n ] , {\displaystyle [T]=[Z_{1}][X_{1}][Z_{2}][X_{2}]\cdots [X_{n-1}][Z_{n}],\!} where [T] is the transformation locating the end-link—notice that the chain includes a "zeroth" link consisting of the ground frame to which it is attached. These equations are called the forward kinematics equations of the serial chain. Kinematic chains of a wide range of complexity are analyzed by equating the kinematics equations of serial chains that form loops within the kinematic chain. These equations are often called loop equations. The complexity (in terms of calculating the forward and inverse kinematics) of the chain is determined by the following factors: Its topology: a serial chain, a parallel manipulator, a tree structure, or a graph. Its geometrical form: how are neighbouring joints spatially connected to each other? Explanation Two or more rigid bodies in space are collectively called a rigid body system. We can hinder the motion of these independent rigid bodies with kinematic constraints. Kinematic constraints are constraints between rigid bodies that result in the decrease of the degrees of freedom of rigid body system. == Synthesis of kinematic chains == The constraint equations of a kinematic chain can be used in reverse to determine the dimensions of the links from a specification of the desired movement of the system. This is termed kinematic synthesis. Perhaps the most developed formulation of kinematic synthesis is for four-bar linkages, which is known as Burmester theory. Ferdinand Freudenstein is often called the father of modern kinematics for his contributions to the kinematic synthesis of linkages beginning in the 1950s. His use of the newly developed computer to solve Freudenstein's equation became the prototype of computer-aided design systems. This work has been generalized to the synthesis of spherical and spatial mechanisms.

Knowledge graph embedding

In representation learning, knowledge graph embedding (KGE), also called knowledge representation learning (KRL), or multi-relation learning, is a machine learning task of learning a low-dimensional representation of a knowledge graph's entities and relations while preserving their semantic meaning. Leveraging their embedded representation, knowledge graphs can be used for various applications such as link prediction, triple classification, entity recognition, clustering, and relation extraction. == Definition == A knowledge graph G = { E , R , F } {\displaystyle {\mathcal {G}}=\{E,R,F\}} is a collection of entities E {\displaystyle E} , relations R {\displaystyle R} , and facts F {\displaystyle F} . A fact is a triple ( h , r , t ) ∈ F {\displaystyle (h,r,t)\in F} that denotes a link r ∈ R {\displaystyle r\in R} between the head h ∈ E {\displaystyle h\in E} and the tail t ∈ E {\displaystyle t\in E} of the triple. Another notation that is often used in the literature to represent a triple (or fact) is ⟨ head , relation , tail ⟩ {\displaystyle \langle {\text{head}},{\text{relation}},{\text{tail}}\rangle } . This notation is called the Resource Description Framework (RDF). A knowledge graph represents the knowledge related to a specific domain; leveraging this structured representation, it is possible to infer a piece of new knowledge from it after some refinement steps. However, nowadays, people have to deal with the sparsity of data and the computational inefficiency to use them in a real-world application. The embedding of a knowledge graph is a function that translates each entity and each relation into a vector of a given dimension d {\displaystyle d} , called embedding dimension. It is even possible to embed the entities and relations with different dimensions. The embedding vectors can then be used for other tasks. A knowledge graph embedding is characterized by four aspects: Representation space: The low-dimensional space in which the entities and relations are represented. Scoring function: A measure of the goodness of a triple-embedded representation. Encoding models: The modality in which the embedded representation of the entities and relations interact with each other. Additional information: Any additional information coming from the knowledge graph that can enrich the embedded representation. Usually, an ad hoc scoring function is integrated into the general scoring function for each additional piece of information. == Embedding procedure == All algorithms for creating a knowledge graph embedding follow the same approach. First, the embedding vectors are initialized to random values. Then, they are iteratively optimized using a training set of triples. In each iteration, a batch of size b {\displaystyle b} triples is sampled from the training set, and a triple from it is sampled and corrupted—i.e., a triple that does not represent a true fact in the knowledge graph. The corruption of a triple involves substituting the head or the tail (or both) of the triple with another entity that makes the fact false. The original triple and the corrupted triple are added in the training batch, and then the embeddings are updated, optimizing a scoring function. Iteration stops when a stop condition is reached. Usually, the stop condition depends on the overfitting of the training set. At the end, the learned embeddings should have extracted semantic meaning from the training triples and should correctly predict unseen true facts in the knowledge graph. === Pseudocode === The following is the pseudocode for the general embedding procedure. algorithm Compute entity and relation embeddings input: The training set S = { ( h , r , t ) } {\displaystyle S=\{(h,r,t)\}} , entity set E {\displaystyle E} , relation set R {\displaystyle R} , embedding dimension k {\displaystyle k} output: Entity and relation embeddings initialization: the entities e {\displaystyle e} and relations r {\displaystyle r} embeddings (vectors) are randomly initialized while stop condition do S b a t c h ← s a m p l e ( S , b ) {\displaystyle S_{batch}\leftarrow sample(S,b)} // Sample a batch from the training set for each ( h , r , t ) {\displaystyle (h,r,t)} in S b a t c h {\displaystyle S_{batch}} do ( h ′ , r , t ′ ) ← s a m p l e ( S ′ ) {\displaystyle (h',r,t')\leftarrow sample(S')} // Sample a corrupted fact T b a t c h ← T b a t c h ∪ { ( ( h , r , t ) , ( h ′ , r , t ′ ) ) } {\displaystyle T_{batch}\leftarrow T_{batch}\cup \{((h,r,t),(h',r,t'))\}} end for Update embeddings by minimizing the loss function end while == Performance indicators == These indexes are often used to measure the embedding quality of a model. The simplicity of the indexes makes them very suitable for evaluating the performance of an embedding algorithm even on a large scale. Given Q {\displaystyle {\ce {Q}}} as the set of all ranked predictions of a model, it is possible to define three different performance indexes: Hits@K, MR, and MRR. === Hits@K === Hits@K or in short, H@K, is a performance index that measures the probability to find the correct prediction in the first top K model predictions. Usually, it is used k = 10 {\displaystyle k=10} . Hits@K reflects the accuracy of an embedding model to predict the relation between two given triples correctly. Hits@K = | { q ∈ Q : q < k } | | Q | ∈ [ 0 , 1 ] {\displaystyle ={\frac {|\{q\in Q:q

Image tracing

In computer graphics, image tracing, raster-to-vector conversion or raster vectorization is the conversion of raster graphics into vector graphics. == Background == An image does not have any structure: it is just a collection of marks on paper, grains in film, or pixels in a bitmap. While such an image is useful, it has some limits. If the image is magnified enough, its artifacts appear. The halftone dots, film grains, and pixels become apparent. Images of sharp edges become fuzzy or jagged. See, for example, pixelation. Ideally, a vector image does not have the same problem. Edges and filled areas are represented as mathematical curves or gradients, and they can be magnified arbitrarily (though of course the final image must also be rasterized in to be rendered, and its quality depends on the quality of the rasterization algorithm for the given inputs). The task in vectorization is to convert a two-dimensional image into a two-dimensional vector representation of the image. It is not examining the image and attempting to recognize or extract a three-dimensional model that may be depicted; i.e. it is not a vision system. For most applications, vectorization also does not involve optical character recognition; characters are treated as lines, curves, or filled objects without attaching any significance to them. In vectorization, the shape of the character is preserved, so artistic embellishments remain. Vectorization is the inverse operation corresponding to rasterization, as integration is to differentiation. And, just as with these other operations, while rasterization is fairly straightforward and algorithmic, vectorization involves the reconstruction of lost information and therefore requires heuristic methods. Synthetic images such as maps, cartoons, logos, clip art, and technical drawings are suitable for vectorization. Those images could have been originally made as vector images because they are based on geometric shapes or drawn with simple curves. Continuous tone photographs (such as live portraits) are not good candidates for vectorization. The input to vectorization is an image, but an image may come in many forms such as a photograph, a drawing on paper, or one of several raster file formats. Programs that do raster-to-vector conversion may accept bitmap formats such as TIFF, BMP and PNG. The output is a vector file format. Common vector formats are SVG, DXF, EPS, EMF and AI. Vectorization can be used to update images or recover work. Personal computers often come with a simple paint program that produces a bitmap output file. These programs allow users to make simple illustrations by adding text, drawing outlines, and filling outlines with a specific color. Only the results of these operations (the pixels) are saved in the resulting bitmap; the drawing and filling operations are discarded. Vectorization can be used to recapture some of the information that was lost. Vectorization is also used to recover information that was originally in a vector format but has been lost or has become unavailable. A company may have commissioned a logo from a graphic arts firm. Although the graphics firm used a vector format, the client company may not have received a copy of that format. The company may then acquire a vector format by scanning and vectorizing a paper copy of the logo. == Process == Vectorization starts with an image. === Manual === The image can be vectorized manually. A person could look at the image, make some measurements, and then write the output file by hand. That was the case for the vectorization of a technical illustration about neutrinos. The illustration has a few geometric shapes and a lot of text; it was relatively easy to convert the shapes, and the SVG vector format allows the text (even subscripts and superscripts) to be entered easily. The original image did not have any curves (except for the text), so the conversion is straightforward. Curves make the conversion more complicated. Manual vectorization of complicated shapes can be facilitated by the tracing function built into some vector graphics editing programs. If the image is not yet in machine readable form, then it has to be scanned into a usable file format. Once there is a machine-readable bitmap, the image can be imported into a graphics editing program (such as Adobe Illustrator, CorelDRAW, or Inkscape). Then a person can manually trace the elements of the image using the program's editing features. Curves in the original image can be approximated with lines, arcs, and Bézier curves. An illustration program allows spline knots to be adjusted for a close fit. Manual vectorization is possible, but it can be tedious. Although graphics drawing programs have been around for a long time, artists may find the freehand drawing facilities awkward even when a drawing tablet is used. Instead of using a program, Pepper recommends making an initial sketch on paper. Instead of scanning the sketch and tracing it freehand in the computer, Pepper states: "Those proficient with a graphic tablet and stylus could make the following changes directly in CorelDRAW by using a scan of the sketch as an underlay and drawing over it. I prefer to use pen and ink, and a light table"; most of the final image was traced by hand in ink. Later the line-drawing image was scanned at 600 dpi, cleaned up in a paint program, and then automatically traced with a program. Once the black and white image was in the graphics program, some other elements were added and the figure was colored. Similarly, Ploch recreated a design from a digital photograph. The JPEG was imported and some "basic shapes" were traced by hand and colored in the graphics drawing program; more complex shapes were handled differently. Ploch used a bitmap editor to remove the background and crop the more complex image components. He then printed the image and traced it by hand onto tracing paper to get a clean black and white line drawing. That drawing was scanned and then vectorized with a program. === Automatic === Some programs automate the vectorization process. Example programs are Adobe Illustrator, Inkscape, Corel's PowerTRACE, and Potrace. Some of these programs have a command line interface while others are interactive that allow the user to adjust the conversion settings and view the result. Adobe Streamline is not only an interactive program, but it also allows a user to manually edit the input bitmap and the output curves. Corel's PowerTRACE is accessed through CorelDRAW; CorelDRAW can be used to modify the input bitmap and edit the output curves. Adobe Illustrator has a facility to trace individual curves. Automated programs can have mixed results. A program (PowerTRACE) was used to convert a PNG map to SVG. The program did a good job on the map boundaries (the most tedious task in the tracing) and the settings dropped out all the text (small objects). The text was manually re-inserted. Other conversions may not go as well. The results depend on having high-quality scans, reasonable settings, and good algorithms. Scanned images often have a lot of noise, which can require additional work to clean up. == Options == There are many different image styles and possibilities, and no single vectorization method works well on all images. Consequently, vectorization programs have many options that influence the result. One issue is what the predominant shapes are. If the image is of a fill-in form, then it will probably have just vertical and horizontal lines of a constant width. The program's vectorization should take that into account. On the other hand, a CAD drawing may have lines at any angle, there may be curved lines, and there may be several line weights (thick for objects and thin for dimension lines). Instead of (or in addition to) curves, the image may contain outlines filled with the same color. Adobe Streamline allows users to select a combination of line recognition (horizontal and vertical lines), centerline recognition, or outline recognition. Streamline also allows small outline shapes to be thrown out; the notion is such small shapes are noise. The user may set the noise level between 0 and 1000; an outline that has fewer pixels than that setting is discarded. Another issue is the number of colors in the image. Even images that were created as black on white drawings may end up with many shades of gray. Some line-drawing routines employ anti-aliasing; a pixel completely covered by the line will be black, but a pixel that is only partially covered will be gray. If the original image is on paper and is scanned, there is a similar result: edge pixels will be gray. Sometimes images are compressed (e.g., JPEG images), and the compression will introduce gray levels. Many of the vectorization programs will group same-color pixels into lines, curves, or outlined shapes. If each possible color is grouped into its object, there can be an enormous number of objects. Instead, the user is asked to s