Seam carving (or liquid rescaling) is an algorithm for content-aware image resizing, developed by Shai Avidan, of Mitsubishi Electric Research Laboratories (MERL), and Ariel Shamir, of the Interdisciplinary Center and MERL. It functions by establishing a number of seams (paths of least importance) in an image and automatically removes seams to reduce image size or inserts seams to extend it. Seam carving also allows manually defining areas in which pixels may not be modified, and features the ability to remove whole objects from photographs. The purpose of the algorithm is image retargeting, which is the problem of displaying images without distortion on media of various sizes (cell phones, projection screens) using document standards, like HTML, that already support dynamic changes in page layout and text but not images. Image Retargeting was invented by Vidya Setlur, Saeko Takage, Ramesh Raskar, Michael Gleicher and Bruce Gooch in 2005. The work by Setlur et al. won the 10-year impact award in 2015. == Seams == Seams can be either vertical or horizontal. A vertical seam is a path of pixels connected from top to bottom in an image with one pixel in each row. A horizontal seam is similar with the exception of the connection being from left to right. The importance/energy function values a pixel by measuring its contrast with its neighbor pixels. == Process == The below example describes the process of seam carving: The seams to remove depends only on the dimension (height or width) one wants to shrink. It is also possible to invert step 4 so the algorithm enlarges in one dimension by copying a low energy seam and averaging its pixels with its neighbors. === Computing seams === Computing a seam consists of finding a path of minimum energy cost from one end of the image to another. This can be done via Dijkstra's algorithm, dynamic programming, greedy algorithm or graph cuts among others. ==== Dynamic programming ==== Dynamic programming is a programming method that stores the results of sub-calculations in order to simplify calculating a more complex result. Dynamic programming can be used to compute seams. If attempting to compute a vertical seam (path) of lowest energy, for each pixel in a row we compute the energy of the current pixel plus the energy of one of the three possible pixels above it. The images below depict a DP process to compute one optimal seam. Each square represents a pixel, with the top-left value in red representing the energy value of that pixel. The value in black represents the cumulative sum of energies leading up to and including that pixel. The energy calculation is trivially parallelized for simple functions. The calculation of the DP array can also be parallelized with some interprocess communication. However, the problem of making multiple seams at the same time is harder for two reasons: the energy needs to be regenerated for each removal for correctness and simply tracing back multiple seams can form overlaps. Avidan 2007 computes all seams by removing each seam iteratively and storing an "index map" to record all the seams generated. The map holds a "nth seam" number for each pixel on the image, and can be used later for size adjustment. If one ignores both issues however, a greedy approximation for parallel seam carving is possible. To do so, one starts with the minimum-energy pixel at one end, and keep choosing the minimum energy path to the other end. The used pixels are marked so that they are not picked again. Local seams can also be computed for smaller parts of the image in parallel for a good approximation. == Issues == The algorithm may need user-provided information to reduce errors. This can consist of painting the regions which are to be preserved. With human faces it is possible to use face detection. Sometimes the algorithm, by removing a low energy seam, may end up inadvertently creating a seam of higher energy. The solution to this is to simulate a removal of a seam, and then check the energy delta to see if the energy increases (forward energy). If it does, prefer other seams instead. == Implementations == Adobe Systems acquired a non-exclusive license to seam carving technology from MERL, and implemented it as a feature in Photoshop CS4, where it is called Content Aware Scaling. As the license is non-exclusive, other popular computer graphics applications (e. g. GIMP, digiKam, and ImageMagick) as well as some stand-alone programs (e. g. iResizer) also have implementations of this technique, some of which are released as free and open source software. There also exists an implementation for webpages. == Improvements and extensions == Better energy function and application to video by introducing 2D (time+1D) seams. Faster implementation on GPU. Application of this forward energy function to static images. Multi-operator: Combine with cropping and scaling. Much faster removal of multiple seams. Removing seams through neural deformation fields to extend to continuous domains like 3D scenes. A 2010 review of eight image retargeting methods found that seam carving produced output that was ranked among the worst of the tested algorithms. It was, however, a part of one of the highest-ranking algorithms: the multi-operator extension mentioned above (combined with cropping and scaling).
ASR-complete
ASR-complete is, by analogy to "NP-completeness" in complexity theory, a term to indicate that the difficulty of a computational problem is equivalent to solving the central automatic speech recognition problem, i.e. recognize and understanding spoken language. Unlike "NP-completeness", this term is typically used informally. Such problems are hypothesised to include: Spoken natural language understanding Understanding speech from far-field microphones, i.e. handling the reverbation and background noise These problems are easy for humans to do (in fact, they are described directly in terms of imitating humans). Some systems can solve very simple restricted versions of these problems, but none can solve them in their full generality.
Polythematic Structured Subject Heading System
Polythematic Structured Subject Heading System (abbreviated as PSH from the Czech Polytematický Strukturovaný Heslář) is a bilingual Czech–English controlled vocabulary of subject headings developed and maintained by the National Technical Library (the former State Technical Library) in Prague. It was designed for describing and searching information resources according to their subject. PSH contains more than 13,900 terms, which cover the main fields of human knowledge. Because of its release in SKOS, PSH can be used not only for describing documents in a library, but also for indexing web pages. Everyone can use PSH for free. PSH is a part of the Linked Open Data cloud diagram (LOD cloud diagram). The image of the LOD cloud diagram shows datasets that have been published in Linked Data format, by contributors to the Linked Open Data community project and other individuals and organisations. == History and development == The PSH preparation project started in 1993, supported by several grants from the Czech Ministry of Culture and Czech Ministry of Education, Youth and Sport. Since 1995, PSH has been used for indexing the State Technical Library's documents. Starting 1997, PSH has been distributed to other libraries and companies, originally as a commercial, paid product; since 2009 for free. In 2000, the State Technical Library received a grant from the Ministry of Culture to translate PSH into English. The next milestone in its development was its releasing in the SKOS format, in 2009. The vast majority of new subject headings is suggested and approved by the indexing experts from the National Technical Library. However, the users and public can also make suggestions, using an online form, which are then assessed by the experts. The main decisions about the development and the future of PSH are done by the Committee for Coordination of Polythematic Structured Subject Heading System. The Committee consists of specialists from the National Technical Library and cooperating institutions, and representatives from the libraries and companies which use PSH. The Committee meets once a year in the National Technical Library; in the meantime, the members communicate using an electronic mailing list. == Browsing PSH == PSH Browser was released in June 2009. It serves for browsing the PSH system and its distribution in SKOS format. This tool navigates users through PSH from general to specific terms. Users can also use the Search field. PSH manager tool was released in 2012. It serves as an indexing tool especially to catalogers. Catalogers can easy orient in its clear structure. All the terms in PSH manager contain link to the catalogue of NTK. There can be also viewed the record in MARC21 format. == Autoindexing == In 2012 was released beta version of autoindexing application. It is accessible on Autoindexing. Users enter chosen text into indexing field and activate indexing. In few seconds the terms describing content are displayed. == PSH structure == PSH is a tree structure with 44 thematic sections. Subject headings are included in a hierarchy of six (or seven) levels according to their semantic content and specificity. There are hierarchical, associative ("see also") and equivalence ("see") relations in PSH. Hierarchical relations are represented by broader and narrower terms (e.g. physical diagnostic methods is broader term to electrocardiography, and on the other hand, electrocardiography is narrower term to physical diagnostic methods). Equivalence relations link subject headings with their nonpreferred versions (e.g. electrocardiography and ECG). Moreover, associative relations are used to link related subject headings from different parts of PSH, regardless their affiliation to a section, (e.g. electrocardiography: see also cardiology). Every subject heading belongs to just one section, which has its own two-character abbreviation, assigned to every subject heading of the section. This enables users to recognize affiliation of subject headings from lower levels to the thematic sections. The 44 thematic sections have following root nodes: == PSH formats == The main format for storage, maintenance and sharing PSH is the MARC 21 Format for Authority Data, which is implemented in library automated systems. PSH is also available in SKOS, using RDF/XML syntax, which is a version suitable for web distribution. Single headings can be accessed on the PSH website through URI links. Alternatively, the whole vocabulary can be downloaded in one file. It is possible to display tags from PSH (metadata snippets – Dublin Core and CommonTag), which can be embedded in an HTML document to provide its semantic description in a machine-readable way. == New subject headings == New subject headings are primarily obtained through the log analysis in the National Technical Library's on-line catalogue of documents, which are the terms used by end-users when searching various documents. Google Analytics service is now used for gaining search queries used by users. Within the data analysis, users queries are divided into seven categories that contain the title of the document, person, subject, action, institution, geographical terms and others. Then the candidates for new preferred terms and non-preferred terms are identified in the subject category. Users can suggest preferred or non-preferred terms through the web form or via e-mail psh(@)techlib.cz. == PSH and Creative Commons == PSH/SKOS has been available under the Creative Commons License CC BY 3.0 CZ (Attribution-ShareAlike 3.0 Czech Republic)since 2011. Users are free to copy, distribute, display and perform the work and make derivative works, but they must give the original author credit and if they alter, transform, or build upon this work, they have to distribute the resulting work only under a licence identical to this one. Users can download all data in one zip file, which is continuously updated.
Mike Vernal
Mike Vernal (born September 7, 1980) is an American business executive who is a venture capitalist at Conviction. He was previously an investor at Sequoia Capital in Silicon Valley and was one of the top executives at Facebook between 2008 and 2016. Prior to joining Sequoia Capital, he was Vice President of Search, Local, and Developer products at Facebook. == Career == Vernal joined Facebook in 2008. From 2009 to 2013, Vernal managed the Facebook Platform team and is credited with managing the Facebook Platform transition from desktop to mobile. During his time at Facebook, he served as vice president and was considered among the “top executives” who ran the company. In 2016, after eight years at Facebook, Vernal announced his plans to leave the company. In May 2016, he joined Sequoia Capital, a venture-capital firm specializing in technology startups. He is an early investor in Rippling, Clay, Notion and Statsig. In July 2023, The Information reported that Vernal was departing Sequoia. At Conviction, he has led investments in Listen Labs, OpenEvidence and Thinking Machines Lab.
Horovod (machine learning)
Horovod is a free and open-source distributed deep learning training framework for TensorFlow, Keras, PyTorch and Apache MXNet. It is designed to scale existing single-GPU training scripts to efficiently run on multiple GPUs and computer nodes with minimal code changes, using synchronous data-parallel training based on the ring-allreduce communication pattern. Horovod was initially developed at Uber and released as an open-source project in 2017, and is now hosted by the LF AI & Data Foundation, a project of the Linux Foundation. == History == Horovod was created at Uber as part of the company's internal machine learning platform Michelangelo to simplify scaling TensorFlow models across many GPUs. The first public release of the library, version 0.9.0, was tagged on GitHub in August 2017 under the Apache 2.0 licence. In October 2017, Uber Engineering publicly introduced Horovod as an open-source component of its deep learning toolkit. In February 2018 Alexander Sergeev and Mike Del Balso published a technical paper describing Horovod's design and benchmarking its performance on up to 512 GPUs, showing near-linear scaling for several image-classification models when compared with single-GPU baselines. In December 2018 Uber contributed Horovod to the LF Deep Learning Foundation (later LF AI & Data), making it a Linux Foundation project. Horovod entered incubation under LF AI & Data and graduated as a full foundation project in 2020. Since its initial release the project has expanded beyond TensorFlow to provide APIs for PyTorch, Keras and Apache MXNet, as well as integrations with frameworks such as Apache Spark and Ray, support for elastic training, and tooling for automated performance tuning and profiling. == Design and features == Horovod core principles are based on the MPI concepts size, rank, local rank, allreduce, allgather, broadcast, and alltoall. Horovod implements synchronous data-parallel training, in which each worker process maintains a replica of the model and computes gradients on different mini-batches of data. The gradients are aggregated across workers using the ring-allreduce communication pattern rather than a central parameter server, which reduces communication bottlenecks and can improve scaling on multi-GPU clusters. Communication is built on top of collective-communication libraries such as MPI, NCCL, Gloo and Intel oneCCL, and supports both GPU and CPU training. In the benchmark experiments reported in the original paper, Horovod achieved around 90% scaling efficiency on 512 GPUs for the ResNet-101 and Inception v3 convolutional neural networks, and around 68% scaling efficiency for the VGG-16 model. Horovod can be deployed on-premises or in cloud environments and is distributed as a Python package with optional GPU support via CUDA. The official documentation provides guides for running Horovod with Docker, Kubernetes (including via Kubeflow and the MPI Operator), commercial platforms such as Databricks, and cluster schedulers such as LSF. == Adoption and use cases == Within Uber, Horovod has been used for applications including autonomous driving research, fraud detection and trip forecasting. Major cloud providers have integrated Horovod into their managed machine learning offerings. Amazon Web Services supports distributed training with Horovod in services such as Amazon SageMaker and AWS Deep Learning Containers, while Microsoft Azure documents Horovod-based training workflows for Azure Synapse Analytics. Technical guides from academic and research computing centres, including Purdue University and the NASA Advanced Supercomputing programme, describe Horovod-based workflows for multi-GPU training on supercomputers and clusters. Horovod is also used in conjunction with Apache Spark and dedicated storage systems as part of end-to-end data processing and model-training pipelines. Industry blogs and technical tutorials describe deployments of Horovod on Kubernetes, on-premises clusters and cloud-managed Kubernetes services such as Amazon EKS.
Intrinsic dimension
In mathematics, the intrinsic dimension of a subset can be thought of as the minimal number of variables needed to represent the subset. The concept has widespread applications in geometry, dynamical systems, signal processing, statistics, and other fields. Due to its widespread applications and vague conceptualization, there are many different ways to define it rigorously. Consequently, the same set might have different intrinsic dimensions according to different definitions. The intrinsic dimension can be used as a lower bound of what dimension it is possible to compress a data set into through dimension reduction, but it can also be used as a measure of the complexity of the data set or signal. For a data set or signal of N variables, its intrinsic dimension M satisfies 0 ≤ M ≤ N, although estimators may yield higher values. == Exact dimension == === Differential === In differential geometry, given a differentiable manifold N and a submanifold M, the intrinsic dimension of M is its dimension. Suppose N has n dimensions and M has m dimensions, then that means around any point in M, there exists a local coordinate system ( x 1 , … , x m , x m + 1 , … , x n ) {\displaystyle (x_{1},\dots ,x_{m},x_{m+1},\dots ,x_{n})} of N, such that the manifold M is simply the subset of N defined by x m + 1 = 0 , … , x n = 0 {\displaystyle x_{m+1}=0,\dots ,x_{n}=0} . === Metric === Given a mere metric space, we can still define its intrinsic dimension. The most general case is the Hausdorff dimension, though for metric spaces occurring in practice, the box-counting dimension and the packing dimension often are identical to the Hausdorff dimension. Let X , d {\textstyle X,d} be a metric space and A ⊂ X {\textstyle A\subset X} be totally bounded. Define the covering number N ( A , ε ) = min { k : A ⊂ ⋃ i = 1 k B ( x i , ε ) } . {\displaystyle N(A,\varepsilon )=\min \left\{k:A\subset \bigcup _{i=1}^{k}B\left(x_{i},\varepsilon \right)\right\}.} The metric entropy is H ( A , ε ) = log N ( A , ε ) {\textstyle H(A,\varepsilon )=\log N(A,\varepsilon )} (any log base). The upper and lower metric entropy dimensions are dim ¯ E A = lim sup ε ↓ 0 H ( A , ε ) log ( 1 / ε ) , dim _ E A = lim inf ε ↓ 0 H ( A , ε ) log ( 1 / ε ) . {\displaystyle {\overline {\dim }}_{E}A=\limsup _{\varepsilon \downarrow 0}{\frac {H(A,\varepsilon )}{\log(1/\varepsilon )}},\quad {\underline {\dim }}_{E}A=\liminf _{\varepsilon \downarrow 0}{\frac {H(A,\varepsilon )}{\log(1/\varepsilon )}}.} If they are equal, then dim E A {\textstyle \operatorname {dim} _{E}A} is that common value, called the metric entropy dimension. The entropy dimensions are usually used in information theory, and especially coding theory, since entropy is involved in its definition. === Topological === If X {\displaystyle X} is merely a topological space, then we can still define its intrinsic dimension, using the topological dimension or Lebesgue covering dimension. An open cover of a topological space X is a family of open sets Uα such that their union is the whole space, ∪ α {\displaystyle \cup _{\alpha }} Uα = X. The order or ply of an open cover A {\displaystyle {\mathfrak {A}}} = {Uα} is the smallest number m (if it exists) for which each point of the space belongs to at most m open sets in the cover: in other words Uα1 ∩ ⋅⋅⋅ ∩ Uαm+1 = ∅ {\displaystyle \emptyset } for α1, ..., αm+1 distinct. A refinement of an open cover A {\displaystyle {\mathfrak {A}}} = {Uα} is another open cover B {\displaystyle {\mathfrak {B}}} = {Vβ}, such that each Vβ is contained in some Uα. The covering dimension of a topological space X is defined to be the minimum value of n such that every finite open cover A {\displaystyle {\mathfrak {A}}} of X has an open refinement B {\displaystyle {\mathfrak {B}}} with order n + 1. The refinement B {\displaystyle {\mathfrak {B}}} can always be chosen to be finite. Thus, if n is finite, Vβ1 ∩ ⋅⋅⋅ ∩ Vβn+2 = ∅ {\displaystyle \emptyset } for β1, ..., βn+2 distinct. If no such minimal n exists, the space is said to have infinite covering dimension. == Introductory example == Let f ( x 1 , x 2 ) {\textstyle f(x_{1},x_{2})} be a two-variable function (or signal) which is of the form f ( x 1 , x 2 ) = g ( x 1 ) {\textstyle f(x_{1},x_{2})=g(x_{1})} for some one-variable function g which is not constant. This means that f varies, in accordance to g, with the first variable or along the first coordinate. On the other hand, f is constant with respect to the second variable or along the second coordinate. It is only necessary to know the value of one, namely the first, variable in order to determine the value of f. Hence, it is a two-variable function but its intrinsic dimension is one. A slightly more complicated example is f ( x 1 , x 2 ) = g ( x 1 + x 2 ) {\textstyle f(x_{1},x_{2})=g(x_{1}+x_{2})} . f is still intrinsic one-dimensional, which can be seen by making a variable transformation y 1 = x 1 + x 2 {\textstyle y_{1}=x_{1}+x_{2}} and y 2 = x 1 − x 2 {\textstyle y_{2}=x_{1}-x_{2}} which gives f ( y 1 + y 2 2 , y 1 − y 2 2 ) = g ( y 1 ) {\textstyle f\left({\frac {y_{1}+y_{2}}{2}},{\frac {y_{1}-y_{2}}{2}}\right)=g\left(y_{1}\right)} . Since the variation in f can be described by the single variable y1 its intrinsic dimension is one. For the case that f is constant, its intrinsic dimension is zero since no variable is needed to describe variation. For the general case, when the intrinsic dimension of the two-variable function f is neither zero or one, it is two. In the literature, functions which are of intrinsic dimension zero, one, or two are sometimes referred to as i0D, i1D or i2D, respectively. == Signal processing == In signal processing of multidimensional signals, the intrinsic dimension of the signal describes how many variables are needed to generate a good approximation of the signal. For an N-variable function f, the set of variables can be represented as an N-dimensional vector x: f = f ( x ) where x = ( x 1 , … , x N ) {\textstyle f=f\left(\mathbf {x} \right){\text{ where }}\mathbf {x} =\left(x_{1},\dots ,x_{N}\right)} . If for some M-variable function g and M × N matrix A it is the case that for all x; f ( x ) = g ( A x ) , {\textstyle f(\mathbf {x} )=g(\mathbf {Ax} ),} M is the smallest number for which the above relation between f and g can be found, then the intrinsic dimension of f is M. The intrinsic dimension is a characterization of f, it is not an unambiguous characterization of g nor of A. That is, if the above relation is satisfied for some f, g, and A, it must also be satisfied for the same f and g′ and A′ given by g ′ ( y ) = g ( B y ) {\textstyle g'\left(\mathbf {y} \right)=g\left(\mathbf {By} \right)} and A ′ = B − 1 A {\textstyle \mathbf {A'} =\mathbf {B} ^{-1}\mathbf {A} } where B is a non-singular M × M matrix, since f ( x ) = g ′ ( A ′ x ) = g ( B A ′ x ) = g ( A x ) {\textstyle f\left(\mathbf {x} \right)=g'\left(\mathbf {A'x} \right)=g\left(\mathbf {BA'x} \right)=g\left(\mathbf {Ax} \right)} . == The Fourier transform of signals of low intrinsic dimension == An N variable function which has intrinsic dimension M < N has a characteristic Fourier transform. Intuitively, since this type of function is constant along one or several dimensions its Fourier transform must appear like an impulse (the Fourier transform of a constant) along the same dimension in the frequency domain. === A simple example === Let f be a two-variable function which is i1D. This means that there exists a normalized vector n ∈ R 2 {\textstyle \mathbf {n} \in \mathbb {R} ^{2}} and a one-variable function g such that f ( x ) = g ( n T x ) {\textstyle f(\mathbf {x} )=g(\mathbf {n} ^{\operatorname {T} }\mathbf {x} )} for all x ∈ R 2 {\textstyle \mathbf {x} \in \mathbb {R} ^{2}} . If F is the Fourier transform of f (both are two-variable functions) it must be the case that F ( u ) = G ( n T u ) ⋅ δ ( m T u ) {\textstyle F\left(\mathbf {u} \right)=G\left(\mathbf {n} ^{\mathrm {T} }\mathbf {u} \right)\cdot \delta \left(\mathbf {m} ^{\mathrm {T} }\mathbf {u} \right)} . Here G is the Fourier transform of g (both are one-variable functions), δ is the Dirac impulse function and m is a normalized vector in R 2 {\textstyle \mathbb {R} ^{2}} perpendicular to n. This means that F vanishes everywhere except on a line which passes through the origin of the frequency domain and is parallel to m. Along this line F varies according to G. === The general case === Let f be an N-variable function which has intrinsic dimension M, that is, there exists an M-variable function g and M × N matrix A such that f ( x ) = g ( A x ) ∀ x {\textstyle f(\mathbf {x} )=g(\mathbf {Ax} )\quad \forall \mathbf {x} } . Its Fourier transform F can then be described as follows: F vanishes everywhere except for a subspace of dimension M The subspace M is spanned by the rows of the matrix A In the subspace, F varies according to G the Fourier transform of g == Generalizations == The type of intrinsic dimension described above assume
HiLog
HiLog is a programming logic with higher-order syntax, which allows arbitrary terms to appear in predicate and function positions. However, the model theory of HiLog is first-order. Although syntactically HiLog strictly extends first order logic, HiLog can be embedded into this logic. HiLog was first described in 1989. It was later extended in the direction of many-sorted logic. The XSB system parses HiLog syntax, but the integration of HiLog into XSB is only partial. In particular, HiLog is not integrated with the XSB module system. A full implementation of HiLog is available in the Flora-2 system. It has been shown that HiLog can be embedded into first-order logic through a fairly simple transformation. For instance, p(X)(Y,Z(V)(W)) gets embedded as the following first-order term: apply(p(X),Y,apply(apply(Z,V),W)). The Framework for Logic-Based Dialects (RIF-FLD) of the Rule Interchange Format (RIF) is largely based on the ideas underlying HiLog and F-logic. == Examples == In all the examples below, capitalized symbols denote variables and the comma denotes logical conjunction, as in most logic programming languages. The first and the second examples show that variables can appear in predicate positions. Predicates can even be complex terms, such as closure(P) or maplist(F) below. The third example shows that variables can also appear in place of atomic formulas, while the fourth example illustrates the use of variables in place of function symbols. The first example defines a generic transitive closure operator, which can be applied to an arbitrary binary predicate. The second example is similar. It defines a LISP-like mapping operator, which applies to an arbitrary binary predicate. The third example shows that the Prolog meta-predicate call/1 can be expressed in HiLog in a natural way and without the use of extra-logical features. The last example defines a predicate that traverses arbitrary binary trees represented as first-order terms.