In theoretical linguistics and computational linguistics, probabilistic context free grammars (PCFGs) extend context-free grammars, similar to how hidden Markov models extend regular grammars. Each production is assigned a probability. The probability of a derivation (parse) is the product of the probabilities of the productions used in that derivation. These probabilities can be viewed as parameters of the model, and for large problems it is convenient to learn these parameters via machine learning. A probabilistic grammar's validity is constrained by context of its training dataset. PCFGs originated from grammar theory, and have application in areas as diverse as natural language processing to the study the structure of RNA molecules and design of programming languages. Designing efficient PCFGs has to weigh factors of scalability and generality. Issues such as grammar ambiguity must be resolved. The grammar design affects results accuracy. Grammar parsing algorithms have various time and memory requirements. == Definitions == Derivation: The process of recursive generation of strings from a grammar. Parsing: Finding a valid derivation using an automaton. Parse Tree: The alignment of the grammar to a sequence. An example of a parser for PCFG grammars is the pushdown automaton. The algorithm parses grammar nonterminals from left to right in a stack-like manner. This brute-force approach is not very efficient. In RNA secondary structure prediction variants of the Cocke–Younger–Kasami (CYK) algorithm provide more efficient alternatives to grammar parsing than pushdown automata. Another example of a PCFG parser is the Stanford Statistical Parser which has been trained using Treebank. == Formal definition == Similar to a CFG, a probabilistic context-free grammar G can be defined by a quintuple: G = ( M , T , R , S , P ) {\displaystyle G=(M,T,R,S,P)} where M is the set of non-terminal symbols T is the set of terminal symbols R is the set of production rules S is the start symbol P is the set of probabilities on production rules == Relation with hidden Markov models == PCFGs models extend context-free grammars the same way as hidden Markov models extend regular grammars. The Inside-Outside algorithm is an analogue of the Forward-Backward algorithm. It computes the total probability of all derivations that are consistent with a given sequence, based on some PCFG. This is equivalent to the probability of the PCFG generating the sequence, and is intuitively a measure of how consistent the sequence is with the given grammar. The Inside-Outside algorithm is used in model parametrization to estimate prior frequencies observed from training sequences in the case of RNAs. Dynamic programming variants of the CYK algorithm find the Viterbi parse of a RNA sequence for a PCFG model. This parse is the most likely derivation of the sequence by the given PCFG. == Grammar construction == Context-free grammars are represented as a set of rules inspired from attempts to model natural languages. The rules are absolute and have a typical syntax representation known as Backus–Naur form. The production rules consist of terminal { a , b } {\displaystyle \left\{a,b\right\}} and non-terminal S symbols and a blank ϵ {\displaystyle \epsilon } may also be used as an end point. In the production rules of CFG and PCFG the left side has only one nonterminal whereas the right side can be any string of terminal or nonterminals. In PCFG nulls are excluded. An example of a grammar: S → a S , S → b S , S → ϵ {\displaystyle S\to aS,S\to bS,S\to \epsilon } This grammar can be shortened using the '|' ('or') character into: S → a S | b S | ϵ {\displaystyle S\to aS|bS|\epsilon } Terminals in a grammar are words and through the grammar rules a non-terminal symbol is transformed into a string of either terminals and/or non-terminals. The above grammar is read as "beginning from a non-terminal S the emission can generate either a or b or ϵ {\displaystyle \epsilon } ". Its derivation is: S ⇒ a S ⇒ a b S ⇒ a b b S ⇒ a b b {\displaystyle S\Rightarrow aS\Rightarrow abS\Rightarrow abbS\Rightarrow abb} Ambiguous grammar may result in ambiguous parsing if applied on homographs since the same word sequence can have more than one interpretation. Pun sentences such as the newspaper headline "Iraqi Head Seeks Arms" are an example of ambiguous parses. One strategy of dealing with ambiguous parses (originating with grammarians as early as Pāṇini) is to add yet more rules, or prioritize them so that one rule takes precedence over others. This, however, has the drawback of proliferating the rules, often to the point where they become difficult to manage. Another difficulty is overgeneration, where unlicensed structures are also generated. Probabilistic grammars circumvent these problems by ranking various productions on frequency weights, resulting in a "most likely" (winner-take-all) interpretation. As usage patterns are altered in diachronic shifts, these probabilistic rules can be re-learned, thus updating the grammar. Assigning probability to production rules makes a PCFG. These probabilities are informed by observing distributions on a training set of similar composition to the language to be modeled. On most samples of broad language, probabilistic grammars where probabilities are estimated from data typically outperform hand-crafted grammars. CFGs when contrasted with PCFGs are not applicable to RNA structure prediction because while they incorporate sequence-structure relationship they lack the scoring metrics that reveal a sequence structural potential == Weighted context-free grammar == A weighted context-free grammar (WCFG) is a more general category of context-free grammar, where each production has a numeric weight associated with it. The weight of a specific parse tree in a WCFG is the product (or sum ) of all rule weights in the tree. Each rule weight is included as often as the rule is used in the tree. A special case of WCFGs are PCFGs, where the weights are (logarithms of ) probabilities. An extended version of the CYK algorithm can be used to find the "lightest" (least-weight) derivation of a string given some WCFG. When the tree weight is the product of the rule weights, WCFGs and PCFGs can express the same set of probability distributions. == Applications == === RNA structure prediction === Since the 1990s, PCFG has been applied to model RNA structures. Energy minimization and PCFG provide ways of predicting RNA secondary structure with comparable performance. However structure prediction by PCFGs is scored probabilistically rather than by minimum free energy calculation. PCFG model parameters are directly derived from frequencies of different features observed in databases of RNA structures rather than by experimental determination as is the case with energy minimization methods. The types of various structure that can be modeled by a PCFG include long range interactions, pairwise structure and other nested structures. However, pseudoknots can not be modeled. PCFGs extend CFG by assigning probabilities to each production rule. A maximum probability parse tree from the grammar implies a maximum probability structure. Since RNAs preserve their structures over their primary sequence, RNA structure prediction can be guided by combining evolutionary information from comparative sequence analysis with biophysical knowledge about a structure plausibility based on such probabilities. Also search results for structural homologs using PCFG rules are scored according to PCFG derivations probabilities. Therefore, building grammar to model the behavior of base-pairs and single-stranded regions starts with exploring features of structural multiple sequence alignment of related RNAs. S → a S a | b S b | a a | b b {\displaystyle S\to aSa|bSb|aa|bb} The above grammar generates a string in an outside-in fashion, that is the basepair on the furthest extremes of the terminal is derived first. So a string such as a a b a a b a a {\displaystyle aabaabaa} is derived by first generating the distal a's on both sides before moving inwards: S ⇒ a S a ⇒ a a S a a ⇒ a a b S b a a ⇒ a a b a a b a a {\displaystyle S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabaabaa} A PCFG model extendibility allows constraining structure prediction by incorporating expectations about different features of an RNA . Such expectation may reflect for example the propensity for assuming a certain structure by an RNA. However incorporation of too much information may increase PCFG space and memory complexity and it is desirable that a PCFG-based model be as simple as possible. Every possible string x a grammar generates is assigned a probability weight P ( x | θ ) {\displaystyle P(x|\theta )} given the PCFG model θ {\displaystyle \theta } . It follows that the sum of all probabilities to all possible grammar productions is ∑ x P ( x | θ ) = 1 {\displaystyle \sum _{\text{x}}P(x|\theta )=1} . The scores
Vegas Pro
Vegas Pro (formerly known as Sony Vegas) is a professional video editing software package for non-linear editing (NLE), designed to run on the Microsoft Windows operating system. The first release of Vegas Beta was on June 11, 1999. Vegas was originally developed as a non-linear audio editing application. Version 2.0 would split the program into audio and video editing variants, with the former being dropped by version 4.0, making the video offering the only variant available to consumers. Vegas Pro features real-time multi-track video and audio editing on unlimited tracks, resolution-independent video sequencing, complex effects, compositing tools, 24-bit/192 kHz audio support, VST and DirectX plug-in effect support, and Dolby Digital surround sound mixing. The software was originally published by Sonic Foundry until May 2003, when Sony purchased Sonic Foundry and formed Sony Creative Software. On May 24, 2016, Sony announced that Vegas was sold to MAGIX, which formed VEGAS Creative Software, to continue support and development of the software. As of the end of March 2026, it was publicly announced that Boris FX had taken ownership of Vegas Pro. Each release of Vegas is sold standalone; however, upgrade discounts are sometimes provided. == Features == Vegas does not require any specialized hardware to run properly, allowing it to operate on any Windows computer that meets the system requirements. == History == Vegas 1.0 was released after a brief public beta by Sonic Foundry on July 23, 1999 at the NAMM Show in Nashville, Tennessee as an audio-only tool with a particular focus on re-scaling and resampling audio. It supported formats like DivX and Real Networks RealSystem G2 file formats. Martin Walker from Sound on Sound described working in Vegas 1.0 as a "very pleasurable experience, especially since so many functions are highly intuitive" though also criticizing some features as hard to figure out due to the lack of a central help file. Later, on June 12, 2000, Vegas Video and Audio 2.0 (also referred to as just Vegas 2.0) was released, with its beta releasing earlier that year on April 10. This was the first version of Vegas to include video-editing tools and was also the first to have a low-cost "LE" version alongside the regular release. The LE releases would continue through version 3.0 of Vegas but would be discontinued by the release of Vegas 4.0. Vegas 3.0 was released the next year on December 3, and added new video effects, features for ease-of-use with DV, and support for editing Windows Media files. Vegas 4.0 was released on 6 February 2003 and added application scripting, advanced color correction, 5.1 surround sound mixing, and Steinberg ASIO support. This was the last release under the Sonic Foundry name after it sold much of its software suite, including Sound Forge and Acid Pro, to Sony Pictures Digital for $18 million later in 2003. Under Sony's ownership, Vegas 5.0 was released on April 19, 2004, bringing 3D track motion, compositing, reversing, envelope automation, etc. 7.0 also added an improved video preview, enhanced layout management, improved snapping, and more customization. With the release of 8.0, Sony opted to go back to the original "Vegas Pro" branding that the first version released with. It added the ability to burn Blu-ray and DVD optical media, support for 32-bit floating point audio, support for tempo-based audio effects, and more. It also moved the timeline to the bottom of the window by default with the option of moving it back to the top if the user wished to. Sony was also experimenting with 64-bit at this time and ported Vegas Pro 8.0 to 64-bit systems under the name "Vegas Pro 8.1". Vegas Pro 9.0 added support for 4K resolution and pro camcorder formats like Red and XDCAM EX. In 2009, Sony Creative Software purchased the Velvetmatter Radiance suite of video FX plug-ins which were included in Sony Vegas Pro 9.0. As a result, they were no longer available as a separate product from Velvetmatter. Vegas Pro 10 was released in 2010 with stereoscopic 3D editing, image stabilization, OpenFX plugin support, real-time audio event effects, and a few UI changes. This was the last release to include support for Windows XP. Vegas Pro 11 was released the next year on 17 October, with GPGPU video acceleration, enhanced text tools, enhanced stereoscopic/3D features, RAW photo support, and new event synchronization mechanisms. In addition, Vegas Pro 11 comes pre-loaded with "NewBlue" Titler Pro, a 2D and 3D titling plug-in. Vegas Pro 12 would add two new configurations: Vegas Pro 12 Edit, for "Professional Video and Audio Production"; and Vegas Pro 12 Suite, for "Professional Editing, Disc Authoring, and Visual Effects Design". Vegas Pro 13 would be the last version released with Sony branding after the acquisition of much of Sony Creative Software's library by Magix. After they acquired Vegas, Magix released version 14 on September 20, 2016. It featured advanced 4K upscaling as well as many bug fixes, a higher video velocity limit, RED camera support, and a variety of other features. This was also the last version to have the light theme enabled by default. Released on August 28, 2017, Vegas Pro 15 features major UI changes that claim to bring usability improvements and customization. It was the first version of VEGAS Pro to have a dark theme; it also allows more efficient editing speeds, including adding new shortcuts to speed the video editing process. Vegas Pro 15 includes support for Intel Quick Sync Video (QSV) and other technologies, as well as various other features. It introduced a new VEGAS Pro icon as a V. Vegas Pro 16 has some new features including file backup, motion tracking, improved video stabilization, 360° editing and HDR support. Magix has continued to improve Vegas through version 21 with support for reading Matroska files, a more detailed render dialogue, live streaming, VST3 support, a VST 32-bit bridge, and a selective Paste Event Attributes menu. Magix would later release a subscription model for using Vegas named "Vegas Pro 365" on January 17, 2018, although the perpetual licence is still an option for customers. This version includes cloud-based speech synthesis among other features not included in the mainline Vegas release. == Version history == Each release of Vegas is sold standalone, however upgrade discounts are sometimes provided. === Vegas Beta === Sonic Foundry introduced a sneak preview version of Vegas Pro on June 11, 1999. It is called a "Multitrack Media Editing System". === Vegas 1.0 === Released on July 23, 1999 at the NAMM Show in Nashville, Tennessee, Vegas was an audio-only tool with a particular focus on rescaling and resampling audio. It supported formats like DivX and Real Networks RealSystem G2 file formats. Version 1.0 is the final Vegas release to include Windows 95 support. === Vegas Video beta (Vegas 2.0 beta) === Released on April 10, 2000, this was the first version of Vegas to include video-editing tools. === Vegas Video (Vegas 2.0) === Released on June 12, 2000. Version 2.0 is the final Vegas Video release to include Windows NT 4.0 support. === Vegas Video 3.0 === Released on December 3, 2001. This release added: New Video Effects – Lens Flare, Light Rays, Film FX, Color Curves, Mirror, Remap, Deform, Convolution, Linear Blur, Black Restore, Levels, Unsharp Mask, Color Grading, and Timecode Burn filter. Batch Capture with Automatic Scene Detection – Captures DV with automatic scene detection, batch capture, tape logging, still image capture and thumbnail previews. Red Book Audio CD Mastering with CD Architect (TM) Technology – Used for burning Red Book audio CD masters directly from the Vegas timeline with ISRC, UPC, and PQ list support. New Sonic Foundry DV Codec – Introduces a DV codec developed by Sonic Foundry that offers artifact-free compositing and DV chromakeying. DV Print-to-Tape from the Timeline – Prints projects to DV cameras and decks from the Vegas timeline. Windows Media (TM) File Editing – Creates and edits Windows Media (TM) files. New MPEG Encoding Tools – Used for producing MPEG-2 files for DVD productions. Dynamic RAM Previewing – Temporary RAM/render-free previews for analysis and tweaking of complex video FX without rendering. VideoCD and Data CD Burning – Burning projects directly to VideoCD for playback on most DVD players or data CDs for playback computers' CD-ROMs. === Vegas 4.0 === Released on February 6, 2003. This release added: Advanced Color Correction Tools Searchable Media Pool Bins Vectorscope, Histogram, Parade and Waveform Monitoring Application Scripting Improved Ripple Editing Motion Blur and Super-Sampling Envelopes 5.1 Surround Mixing Dolby® Digital AC-3 Encoding certified and tested by Dolby Laboratories DirectX® Audio Plug-In Effects Automation ASIO Driver Support Windows Media™ 9 Support, including Surround Encoding DVD Authoring with AC-3 File Import Capabilities Integration with DVD Architect via Chap
Random indexing
Random indexing is a dimensionality reduction method and computational framework for distributional semantics, based on the insight that very-high-dimensional vector space model implementations are impractical, that models need not grow in dimensionality when new items (e.g. new terminology) are encountered, and that a high-dimensional model can be projected into a space of lower dimensionality without compromising L2 distance metrics if the resulting dimensions are chosen appropriately. This is the original point of the random projection approach to dimension reduction first formulated as the Johnson–Lindenstrauss lemma, and locality-sensitive hashing has some of the same starting points. Random indexing, as used in representation of language, originates from the work of Pentti Kanerva on sparse distributed memory, and can be described as an incremental formulation of a random projection. It can be also verified that random indexing is a random projection technique for the construction of Euclidean spaces—i.e. L2 normed vector spaces. In Euclidean spaces, random projections are elucidated using the Johnson–Lindenstrauss lemma. The TopSig technique extends the random indexing model to produce bit vectors for comparison with the Hamming distance similarity function. It is used for improving the performance of information retrieval and document clustering. In a similar line of research, Random Manhattan Integer Indexing (RMII) is proposed for improving the performance of the methods that employ the Manhattan distance between text units. Many random indexing methods primarily generate similarity from co-occurrence of items in a corpus. Reflexive Random Indexing (RRI) generates similarity from co-occurrence and from shared occurrence with other items.
European Conference on Computer Vision
The European Conference on Computer Vision (ECCV) is a biennial research conference with the proceedings published by Springer Science+Business Media. Similar to ICCV in scope and quality, it is held those years which ICCV is not. It is considered to be one of the top conferences in computer vision, alongside CVPR and ICCV, with an 'A' rating from the Australian Ranking of ICT Conferences and an 'A1' rating from the Brazilian ministry of education. The acceptance rate for ECCV 2010 was 24.4% for posters and 3.3% for oral presentations. Like other top computer vision conferences, ECCV has tutorial talks, technical sessions, and poster sessions. The conference is usually spread over five to six days with the main technical program occupying three days in the middle, and tutorial and workshops, focused on specific topics, being held in the beginning and at the end. The ECCV presents the Koenderink Prize annually to recognize fundamental contributions in computer vision. == Location == The conference is usually held in autumn in Europe.
Evolutionary multimodal optimization
In applied mathematics, multimodal optimization deals with optimization tasks that involve finding all or most of the multiple (at least locally optimal) solutions of a problem, as opposed to a single best solution. Evolutionary multimodal optimization is a branch of evolutionary computation, which is closely related to machine learning. Wong provides a short survey, wherein the chapter of Shir and the book of Preuss cover the topic in more detail. == Motivation == Knowledge of multiple solutions to an optimization task is especially helpful in engineering, when due to physical (and/or cost) constraints, the best results may not always be realizable. In such a scenario, if multiple solutions (locally and/or globally optimal) are known, the implementation can be quickly switched to another solution and still obtain the best possible system performance. Multiple solutions could also be analyzed to discover hidden properties (or relationships) of the underlying optimization problem, which makes them important for obtaining domain knowledge. In addition, the algorithms for multimodal optimization usually not only locate multiple optima in a single run, but also preserve their population diversity, resulting in their global optimization ability on multimodal functions. Moreover, the techniques for multimodal optimization are usually borrowed as diversity maintenance techniques to other problems. == Background == Classical techniques of optimization would need multiple restart points and multiple runs in the hope that a different solution may be discovered every run, with no guarantee however. Evolutionary algorithms (EAs) due to their population based approach, provide a natural advantage over classical optimization techniques. They maintain a population of possible solutions, which are processed every generation, and if the multiple solutions can be preserved over all these generations, then at termination of the algorithm we will have multiple good solutions, rather than only the best solution. Note that this is against the natural tendency of classical optimization techniques, which will always converge to the best solution, or a sub-optimal solution (in a rugged, “badly behaving” function). Finding and maintenance of multiple solutions is wherein lies the challenge of using EAs for multi-modal optimization. Niching is a generic term referred to as the technique of finding and preserving multiple stable niches, or favorable parts of the solution space possibly around multiple solutions, so as to prevent convergence to a single solution. The field of Evolutionary algorithms encompasses genetic algorithms (GAs), evolution strategy (ES), differential evolution (DE), particle swarm optimization (PSO), and other methods. Attempts have been made to solve multi-modal optimization in all these realms and most, if not all the various methods implement niching in some form or the other. == Multimodal optimization using genetic algorithms/evolution strategies == De Jong's crowding method, Goldberg's sharing function approach, Petrowski's clearing method, restricted mating, maintaining multiple subpopulations are some of the popular approaches that have been proposed by the community. The first two methods are especially well studied, however, they do not perform explicit separation into solutions belonging to different basins of attraction. The application of multimodal optimization within ES was not explicit for many years, and has been explored only recently. A niching framework utilizing derandomized ES was introduced by Shir, proposing the CMA-ES as a niching optimizer for the first time. The underpinning of that framework was the selection of a peak individual per subpopulation in each generation, followed by its sampling to produce the consecutive dispersion of search-points. The biological analogy of this machinery is an alpha-male winning all the imposed competitions and dominating thereafter its ecological niche, which then obtains all the sexual resources therein to generate its offspring. Recently, an evolutionary multiobjective optimization (EMO) approach was proposed, in which a suitable second objective is added to the originally single objective multimodal optimization problem, so that the multiple solutions form a weak pareto-optimal front. Hence, the multimodal optimization problem can be solved for its multiple solutions using an EMO algorithm. Improving upon their work, the same authors have made their algorithm self-adaptive, thus eliminating the need for pre-specifying the parameters. An approach that does not use any radius for separating the population into subpopulations (or species) but employs the space topology instead is proposed in.
AFNLP
AFNLP (Asian Federation of Natural Language Processing Associations) is the organization for coordinating the natural language processing related activities and events in the Asia-Pacific region. == Foundation == AFNLP was founded on 4 October 2000. == Member Associations == ALTA – Australasian Language Technology Association ANLP Japan Association of Natural Language Processing ROCLING Taiwan ROC Computational Linguistics Society SIG-KLC Korea SIG-Korean Language Computing of Korea Information Science Society == Existing Asian Initiatives == NLPRS: Natural Language Processing Pacific Rim Symposium IRAL: International Workshop on Information Retrieval with Asian Languages PACLING: Pacific Association for Computational Linguistics PACLIC: Pacific Asia Conference on Language, Information and Computation PRICAI: Pacific Rim International Conference on AI ICCPOL: International Conference on Computer Processing of Oriental Languages ROCLING: Research on Computational Linguistics Conference == Conferences == IJCNLP-04: The 1st International Joint Conference on Natural Language Processing in Hainan Island, China IJCNLP-05: The 2nd International Joint Conference on Natural Language Processing in Jeju Island, Korea IJCNLP-08: The 3rd International Joint Conference on Natural Language Processing in Hyderabad, India ACL-IJCNLP-2009: Joint Conference of the 47th Annual Meeting of the Association for Computational Linguistics (ACL) and 4th International Joint Conference on Natural Language Processing (IJCNLP) in Singapore IJNCLP-11: The 5th International Joint Conference on Natural Language Processing in Chiang Mai, Thailand
Clustering illusion
The clustering illusion is the tendency to erroneously consider the inevitable "streaks" or "clusters" arising in small samples from random distributions to be non-random. The illusion is caused by a human tendency to underpredict the amount of variability likely to appear in a small sample of random or pseudorandom data. Thomas Gilovich, an early author on the subject, argued that the effect occurs for different types of random dispersions. Some might perceive patterns in stock market price fluctuations over time, or clusters in two-dimensional data such as the locations of impact of World War II V-1 flying bombs on maps of London. Although Londoners developed specific theories about the pattern of impacts within London, a statistical analysis by R. D. Clarke originally published in 1946 showed that the impacts of V-2 rockets on London were a close fit to a random distribution. == Similar biases == Using this cognitive bias in causal reasoning may result in the Texas sharpshooter fallacy, in which differences in data are ignored and similarities are overemphasized. More general forms of erroneous pattern recognition are pareidolia and apophenia. Related biases are the illusion of control which the clustering illusion could contribute to, and insensitivity to sample size in which people don't expect greater variation in smaller samples. A different cognitive bias involving misunderstanding of chance streams is the gambler's fallacy. == Possible causes == Daniel Kahneman and Amos Tversky explained this kind of misprediction as being caused by the representativeness heuristic (which itself they also first proposed).