Abstract
The W3C Internationalization Tag Set 2.0 - developed by the W3C MultilingualWeb-LT Working Group enhances the foundation to integrate automated processing of human language into core Web technologies. ITS 2.0 bears many
commonalities with is predecessor ITS 1.0 but provides additional concepts that are designed to foster the automated creation and processing of multilingual Web content.
ITS 2.0 focuses on HTML, XML-based formats in general, and can leverage processing based on the XML Localization Interchange
File Format (XLIFF), as well as the Natural Language Processing Interchange Format (NIF).
The W3C MultilingualWeb-LT Working Group received funding by the European Commission (project LT-Web|) through the Seventh Framework Programme (FP7) in the area of Language Technologies (Grant Agreement No. 287815). As part
of their activities, members of the Working Group and the LT-Web project created various implementations that exemplify how
ITS 2.0 supports automated processing of human language into core Web technologies. These implementations/the corresponding
usage scenarios are sketched in this document. Each section of the document comprises the following:
- Description - An explanation of the scenario
- Data category usage - An explanation which of the ITS 2.0 data categories are involved in the automated processing; (for
details on the data categories, W3C Internationalization Tag Set 2.0 has to be consulted)
- Benefits - Reasons why the ITS 2.0 data categories enable or enhance the automated processing
- Information on Implementation Status/Issues - Links to tools and implementers (detailed information, running software, source
code etc.)
Status of this Document
This section describes the status of this document at the time of its
publication. Other documents may supersede this document. A list of current W3C
publications and the latest revision of this technical report can be found in
the W3C technical reports index at
http://www.w3.org/TR/.
This document describes usage scenarios and related implementations for Internationalization Tag Set (ITS) 2.0. ITS 2.0 enhances the foundation to integrate both automated and manual processing of human language into core Web technologies.
The work described in this document receives funding by the European Commission (project MultilingualWeb-LT (LT-Web) ) through the Seventh Framework Programme (FP7) in the area of Language Technologies (Grant Agreement No. 287815).
This document is a First Public Working Draft published by the MultilingualWeb-LT
Working Group, part of the W3C Internationalization
Activity. The Working Group expects to advance this Working Draft to Working
Group Note (see W3C
document maturity levels).
By publishing this working
draft the working group does not express any consensus about the implementation
approach, the use cases described or the proposed metadata items. The main purpose
of this publication is to gather feedback from a wider audience.
Feedback about the content of this document is encouraged.
Send your comments to<EMAIL_ADDRESS>Use "Comment on Multilingual Web metadata usage scenarios and implementations WD" in the subject line of your email. The
archives for this list are publicly available.
Publication as a Working Draft does not imply endorsement by the W3C Membership. This
is a draft document and may be updated, replaced or obsoleted by other documents at
any time. It is inappropriate to cite this document as other than work in
progress.
This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. The group does not expect this document to become a W3C Recommendation. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.
1 Introduction
The W3C Internationalization Tag Set 2.0 - developed by the W3C MultilingualWeb-LT Working Group enhances the foundation to integrate automated processing of human language into core Web technologies. ITS 2.0 bears many
commonalities with is predecessor ITS 1.0 but provides additional concepts that are designed to foster the automated creation and processing of multilingual Web content.
ITS 2.0 focuses on HTML, XML-based formats in general, and can leverage processing based on the XML Localization Interchange
File Format (XLIFF), as well as the Natural Language Processing Interchange Format (NIF).
The W3C MultilingualWeb-LT Working Group received funding by the European Commission (project MultilingualWeb-LT (LT-Web)) through the Seventh Framework Programme (FP7) in the area of Language Technologies (Grant Agreement No. 287815). As part
of their activities, project members and members of the Working Group compiled a list of usage scenarios that exemplify how
ITS 2.0 integrates automated processing of human language into core Web technologies. These usage scenarios - and implementations
realized by the Working Group - are sketched in this document. The usage scenarios comprise information such as the following:
- Description - An explanation of the scenario
- Data category usage - An explanation how the individual ITS 2.0 data categories are involved in the automated processing
(for details on the data categories, W3C Internationalization Tag Set 2.0)
- Benefits - Reasons why the ITS 2.0 data categories enable or enhance the automated processing
- Information on Implementation Status/Issues - Links to tools and implementers (detailed information, running software, source
code etc.)
2 Usage scenarios
2.1 Simple Machine Translation
2.1.1 Description
- Translate XML and HTML5 content via a Machine Translation (MT) system such as Microsoft Translator.
- The parts of the content that should be translated are first extracted based on ITS 2.0 markup. The extracted parts are send
to the MT system. After translation, the translated content is merged back with the parts that are not translation-relevant
(recreating the original XML or HTML5 format).
Benefits:
- The ITS 2.0 markup provides key information to drive the reliable extraction of translation-relevant content from both XML
and HTML5.
- Processing details such as the need to preserve white space can be passed on.
2.1.2 Data category usage
- Translate - Parts that are not translation-relevant are marked (and protected).
- Locale Filter - Only the parts that pass the locale filter are extracted. The other parts are treated as 'do not translate'
content.
- Element Within Text - Elements are either extracted as in-line codes or as sub-flows.
- Preserve Space - Extracted parts/text units can be annotated with the information that whitespace is relevant and thus needs
to be preserved.
- Domain - Domain values are placed into a property that can be used to select an MT system and/or to provide domain-related
metadata to an MT system.
2.1.3 More Information and Implementation Status/Issues
Tool: Okapi Framework (ENLASO).
Implementation status/issues:
- Only the first occurrence of the Domain value triggers the selection of the engine.
- Preserve Space is currently not respected by the engine.
2.2 Translation Package Creation
2.2.1 Description
- Create a Translation Package in OASIS XML Localization Interchange File Format (XLIFF) from XML or HTML5 content.
- Based on its ITS 2.0 metadata, the content goes through a processing pipeline (e.g. extraction of translation-relevant parts).
At the end of the pipeline, an XLIFF package is stored.
Benefits:
- The ITS 2.0 markup provides key information to drive the reliable extraction of translation-relevant content from both XML
and HTML5.
- Processing details such as the need to preserve white space can be passed on.
- Efficient version comparison and leveraging of existing translations is possible.
- Information like domain of the content, external references or localization notes, is made available in the XLIFF package.
Thus, any XLIFF-enabled tool can make use of this information to provide translation assistance.
- Terms in the source content are marked, and thus can be matched against a terminology database.
- Constraints about storage size and allowed characters help to meet physical requirements.
2.2.2 Data category usage
- Translate - Parts that are not translation-relevant are marked (and protected).
- Locale Filter - Only the parts that pass the locale filter are extracted. The other parts are treated as 'do not translate'
content.
- Element Within Text - Elements are either extracted as in-line codes or as sub-flows.
- Preserve Space - The information is mapped to xml:space
- Id Value - The value is connected to the name of the extracted text unit.
- Domain - Values are placed into a corresponding okp:itsDomain attribute.
- Storage Size - The information is placed in native ITS 2.0 markup.
- External Resource - The URI is placed in a corresponding okp:itsExternalResourceRef attribute.
- Terminology - The information about terminology is placed in a special XLIFF note element.
- Localization Note - The text is place in an XLIFF note.
- Allowed Characters - The pattern is placed in its:allowedCharacters.
2.2.3 More Information and Implementation Status/Issues
Tool: Okapi Framework (ENLASO).
Implementation status/issues:
- ITS to XLIFF and XLIFF to ITS mapping needs to be finalized
2.3 Quality Check
2.3.1 Description
- Load XML, HTML5 and XLIFF content for which ITS 2.0 meta data exists into a tool that performs different kind of quality
checks (CheckMate, a tool for checking quality).
- The XML and HTML5 content is processed based on its ITS 2.0 properties. The constraints defined with ITS 2.0 are verified
by CheckMate.
- The XLIFF content is processed based on its ITS 2.0 properties. The constraints defined with ITS 2.0 are verified by CheckMate.
Benefits:
- The ITS 2.0 markup provides key information to drive the reliable extraction of translation-relevant content from both XML
and HTML5.
- The ITS 2.0 markup provides key information to drive quality-related checks.
- The ITS 2.0 markup allows all different file formats to be handled in the same way by the quality checking tool.
2.3.2 Data category usage
- Translate - Parts that are not translation-relevant are marked (and protected).
- Locale Filter - Only the parts that pass the locale filter are extracted. The other parts are treated as 'do not translate'
content.
- Element Within Text - Elements are either extracted as in-line codes or as sub-flows.
- Preserve Space - The information is mapped to the preserveSpace field in the extracted text unit.
- Id Value - The ids are used to identify all entries with an issue.
- Storage Size - The content is verified against the storage size constraints.
- Allowed Characters - The content is verified against the pattern matching allowed characters.
2.3.3 More Information and Implementation Status/Issues
Tool: Okapi Framework (ENLASO).
Implementation status/issues:
- The Okapi's quality checker step does not map its warning levels properly to the ITS severity values.
2.4 Processing HTML5 documents with an XML tool chain
2.4.1 Description
- Turn HTML5 with "its-" attributes into XHTML with "its:" prefixes.
Benefits:
- Allows processing of HTML5 documents with XML tools.
2.4.2 Data category usage
- All data categories are covered.
2.4.3 More Information and Implementation Status/Issues
2.5 Validating HTML5 with ITS 2.0 metadata
2.5.1 Description
- W3C uses validator.nu as experimental validator for HTML5. For HTML5 with ITS 2.0 metadata, validator.nu generates errors,
since "its-" attributes are not valid HTML5.
- The software allows validation of HTML5+ITS 2.0 with validator.nu (soon to be deployed as HTML5+ITS 2.0 validator at W3C
validation service)
Benefits:
- Allows the validation of HTML5 documents which include ITS 2.0 markup.
- Detects errors in ITS 2.0 markup for HTML5.
2.5.2 Data category usage
- All data categories are covered
2.5.3 More Information and Implementation Status/Issues
2.6 Interchange between Content Management System and Translation Management System
2.6.1 Description
- Content is roundtripped between a Content Management System (CMS) and Translation Management System (TMS).
- The content originates in a CMS, and gets exposed/serialized as XHTML + ITS 2.0. This is sent to a TMS, and processed in
a workflow. Upon completion, the TMS exposes/serializes localized/translated XHTML + ITS 2.0 to the CMS.
- See ITS 2.0 for localization of content in a Web Content Management System for the description of the CMS side
Benefits:
- Facilitated coupling/interoperability between CMS and TMS.
- Cost and quality benefits for Language Service Buyer (CMS side) and Language Service Provider (TMS side).
- Language Service Buyer has more control of the localization workflow via ITS 2.0 metadata
- Automatic (e.g. via data category "Translate")
- Semiautomatic (e.g. via data category "Domain")
- Manual (e.g. via data category "Localization Note")
2.6.2 Data category usage
- Translate (global and local usage) - Parts that are not translation-relevant are marked (and protected).
- Localization Note (global and local usage) - Provide additional information for process managers, translators and reviewers
to facilitate processing.
- Domain (global usage) -
- Provide additional information for process managers, translators and reviewers to facilitate processing.
- Control workflow dimensions such as selection of dictionaries and translation memories on the TMS side.
- Language Information (local usage)- Control workflow dimensions such as selecting suitable translators and reviewers. Also
adds context information that helps to decide if a piece of content shall or shall not be translated.
- Allowed Characters (local usage) - The content is verified against the pattern matching allowed characters to ensure that
on the TMS side, no inappropriate characters become part of the content (e.g. due to work of a translator).
- Storage Size (local usage) - The content is verified against the storage size constraints to ensure that on the TMS side,
no capacity limitations related to the content are violated (e.g. due to a lengthy translation).
- Provenance (local usage) - Allows tracking of human agents or software agents that processed the content on the TMS side.
In the case of updates, provenance/tracking information will enable the TMS side to assign or propose the same human agents
(translators, or reviewers) that participated in the initial processing.
Additional data category (not part of ITS 2.0):
- Readiness (global usage) - Provides information to translation process managers (examples: When was the content was ready
to be processed? What is the deadline? What is the priority? Which service/process variant is relevant?)
2.6.3 More Information and Implementation Status/Issues
Tools (developed by Linguaserve):
Implementation status:
- Successfully tested roundtripping Drupal XHTML files utilizing supported ITS 2.0 data categories in workflow
- Used in productive translation
Implementation issues:
- Compliant implementation of ITS 2.0 global rules not finished yet
2.7 Content Internationalization and Advanced Machine Translation
2.7.1 Description
- Enable an HTML5 content reviser (language editor, translation post-editor) to add ITS 2.0 metadata to the contents of web
documents.
- Use the ITS 2.0 metadata to control the behavior of different Machine Translation (MT) Systems and Multilingual Publication
System.
- Covers post-editing of translations generated by MT.
Benefits:
- provides key information to drive the reliable extraction of translation-relevant content from HTML5;
- helps to control workflow dimensions such as selection of domain-specific vocabulary to improve the Machine Translation results;
- provides information for post-editing.
2.7.2 Data category usage
- Translate - Parts that are not translation-relevant are marked (and protected).
- Localization Note - Provides additional information for language or translation editors to facilitate translation.
- Language Information - Controls workflow dimensions such as setting the source language, and the target language (via the
lang attribute of the output), it also protects the translation of contents where the lang attribute is different from the
source language.
- Domain - Domain values are mapped to the domains used by the individual MT systems, and used to select the appropriate vocabulary.
- Provenance - Allows tracking of human agents (language or translation editors) or software agents (MT systems) that processed
the content.
- Localization Quality Issue - Can be provided for the translated content by the reviser. Can be utilized for example by MT
developers to improve the MT System.
- Locale Filter - Reveals that content is only relevant for certain locales (useful in localization).
- MT Confidence - Assesses the confidence in the quality of the translation generated by the MT system.
2.7.3 More Information and Implementation Status/Issues
Tools:
- Real Time Multilingual Publication System ATLAS PW1 (Linguaserve).
- Statistical MT System MaTrEx (DCU).
- Rule-based MT System (LucySoftware).
Implementation issues:
- Implementation of ITS 2.0 translate data category for attributes currently restricted to global rules
2.8 Using ITS 2.0 with GNU gettext utilities/PO files
2.8.1 Description
- The GNU gettext utilities assist in internationalizing and translating in the context of UNIX-like Operating Systems. The
file format of the utilities is the GNU gettext portable object (PO) file format.
- The implementation - ITS Tool - enables roundtripping between PO files and XML formats like mallard.
- ITS Tool includes default rules for various formats, and uses them for PO file generation.
- ITS Tool is aware of various ITS 2.0 data categories in the PO file generation step.
2.8.2 Data category usage
- Preserve Space
- Locale Filter
- External Resource
- Translate
- Elements Within Text
- Localization Note
- Language Information
2.8.3 More Information and Implementation Status/Issues
Implementation status/issues:
- Need to convert built-in rules to new categories, and to deprecate extensions (not a conformance blocker).
- No support for its:param (blocked by lacking support for setting XPath variables in libxml2 Python bindings; patch pending review).
- No support support for HTML. libxml2's HTML parser does not correctly handle HTML5. Need to evaluate other libraries.
2.9 Harnessing ITS 2.0 Metadata to Improve the Human Review Process
2.9.1 Description
- The implementation - the "Reviewer's Workbench" (a desktop application) - reads HTML, XML and XLIFF files annotated with
ITS 2.0 metadata.
- At each segment of the original content, the ITS metadata is made accessible to reviewers. Reviewers can adapt the access
via user-definable filter/formatting "rules". The metadata allows human reviewers to make efficient decisions.
- During the review of translations, reviewers can add Localization Quality Issue annotations (which are serialized as ITS
2.0 metadata when the file is saved). Provenance annotations are added in the background.
- The combination of captured Localization Quality Issue and Provenance data then becomes valuable data which can be used for
traditional business intelligence, or semantic web applications.
2.9.2 Data category usage
- Provenance
- Localization Quality Issue
Benefits:
- Increases review effectiveness as reviewers can be informed by metadata.
- Harvests data during review.
- Facilitates audit and quality correction.
2.9.3 More Information and Implementation Status/Issues
- Application development currently at alpha stage.
- Awaiting finalization of XLIFF mappings and underlying Okapi filter support.
- Application is closed source.
2.10 XLIFF-based Machine Translation
2.10.1 Description
- Invoke Machine Translation (MT) from a localization workflow using ITS 2.0 integrated with the XML Localization Interchange
File Format (XLIFF)
2.10.2 Data category usage
- Domain - The domain value can be used by the MT system to improve processing accuracy
- Translate - Parts that are not translation-relevant are marked (and protected).
- MT Confidence - Assesses the confidence in the quality of the translation generated by the MT system.
- Terminology - Enforce the MT system to translate specific words or phrases according to terminological information
- Provenance - Allows tracking of human agents (content editors) or software agents (MT systems) that processed the content.
Benefits:
- The use of XLIFF allows an MT system to be integrated seamlessly into automated localization workflows involving commercial
Translation Management Systems and Computer Assisted Translation (CAT) tools.
- The use of XLIFF and ITS 2.0 facilitates the integration of/switch between multiple MT systems to provide alternative translation
within a single project workflow.
- The use of the ITS 2.0 "translate" attribute ensures that content is not altered by the MT system - especially if that content
is included in a translation project as context for human agents such as translation post-editors.
- The ITS 2.0 "domain" metadata in XLIFF ensures that the most relevant MT engine can be selected by the MT system.
- Combining XLIFF and ITS 2.0 "terminology" metadata enforce the MT system to translate specific words or phrases according
to terminological information.
- Integrating ITS 2.0 MT confidence scores into XLIFF target language translation enables them to be presented to translation
post-editors.
- Recording provenance information enables localization managers to compare the performance of different MT engines or systems,
or different translation post-editors.
2.10.3 More Information and Implementation Status/Issues
2.11 XLIFF-based CMS-to-TMS Roundtripping for HTML&XML
2.11.1 Description
- SOLAS - is a service-based architecture for orchestrating localization workflows among XLIFF-aware components.
- One of SOLAS components is an OKAPI based extra Extractor/Merger service that maps ITS 2.0 categories onto XLIFF 1.2
- SOLAS is also integrated with CMS-L10N, can receive/return XLIFF jobs created by CMS-L10N.
- CMS-L10N (aka LION) is basically a middleware component based on an RDF triple store over an arbitrary CMS (tested with Alfresco,
Drupal and Wikimedia).
- Can parse the source including most of the ITS 2.0 metadata and produce XLIFF 1.2 according to a currently agreed mapping.
After the roundtrip, that is handled via SOLAS, it updates the RDF triple store accordingly.
Benefits:
- The use of ITS 2.0 and XLIFF helps to modularize and connect specialized (single-purpose) components.
- SOLAS can handle input of components aware of different ITS 2.0 categories or unaware of ITS at all and combine them. SOLAS
orchestration ensures basic ITS compliance even with ITS unaware components. E.g. If a service provider is unaware of the
translate flag, SOLAS can filter the translation request for that provider, so that the flag is actually interpreted.
2.11.2 Data category usage
- Translate
- Localization Note
- Terminology
- Directionality
- Language Information
- Elements Within Text
- Domain
- Text Analysis
- Locale Filter
- Provenance
- External Resource
- Target Pointer
- Id Value
- Preserve Space
- Localization Quality Issue
- Localization Quality Rating
- MT Confidence
- Allowed Characters
- Storage Size
2.11.3 More Information and Implementation Status/Issues
Implementer: TCD/UL, Making use of MT components by Moravia and DCU, and JSI Enrycher as Text Analysis service.
This tool is based on an ITS-XLIFF mapping:
- The mapping is currently under discussion.
- The goal is to freeze the mapping and to produce a best practice note within lifespan of the LT-Web project.
- The focus is currently on XLIFF 1.2 favoring solutions that can be structurally preserved in XLIFF 2.0. that is the main
target in the long run.
Although all ITS categories listed above, as encoded by OKAPI or TCD's CMS-LION, are covered, the demos in mid March show
consumption of mainly the following: translate, term, text analysis, domain, localization note, provenance, and MT confidence.
The demos involve:
- An XLIFF-based source quality assurance tool (LKR by UL)
- A Project Manager/Localization Engineer friendly XLIFF Viewer/Editor (LocConnect by UL)
- Integrated Machine Translation Solutions
- Moravia's implementation of M4Loc and Moses with ITS 2.0 support
- DCU MaTrEx with ITS 2.0 support
- Fallback handling of the ITS 2.0 information within SOLAS MT Service Mapper with services that are not ITS 2.0 aware, such
as Microsoft Bing
- Details (M4Loc processing of ITS2.0 enhanced XLIFF files):
- Running software: http://mlwlt.moravia.com (testing site)
- Running software (web-service): http://mlwlt.moravia.com/mlwlt-service-xliff-mt/mlwlt-service.asmx
- Source code: https://github.com/mkarasek/mlwlt-m4loc-xliff-mt
- General documentation: https://github.com/mkarasek/mlwlt-m4loc-xliff-mt/wiki
Please note that links to the running software are currently only accessible to the SOLAS system at the moment. They should
become public next week.
2.12 ITS 2.0 for localization of content in a Web Content Management System
2.12.1 Description
- Drupal is a Web Content Management System (WCMS).
- The Drupal modules, developed by Cocomore,
- add the ability to apply ITS 2.0 local metadata through Drupal's WYSIWYG editor.
- add the ability to apply global ITS 2.0 metadata at content mode level.
- Implemented jQuery plugin to optimize the GUI of the Translation Management tool (there is a published jQuery download as standalone solution, too).
Benefits:
- Support for ITS 2.0 in Drupal facilitates the localization/translation of Drupal-based content.
- The Drupal modules facilitate the roundtripping process from WCMS with systems of Localization Service Provider (including
automatic content re-integration).
- The Drupal modules enable tracking of provenance information (e.g. to identify translation post-editors).
2.12.2 Data category usage
- Translate - Mark content which should not be translated and highlight this marked content.
- Localization Note - Add a note for the translator to improve his understanding of this content and can make a better translation.
- Domain - Set the domain of a text to improve the machine and human translation process.
- Provenance - Check which translator/reviser worked on content.
- Allowed Characters/Storage Size - Make the translator aware of restrictions for specific content, like not allowed characters
or a maximum length of a translation. These constraints are automatically set by Drupal.
- Text Analysis - Annotate text with terminology metadata to improve the machine and human translation process.
2.12.3 More Information and Implementation Status/Issues
Tool: Drupal Module for editing and viewing of ITS 2.0 markup (Cocomore AG)
Tool: Drupal Module to connect to TMGMT Translator Linguaserve (Cocomore AG)
Tool: Drupal Module to interact with TMGMT Workflow (Cocomore AG)
Tool: ITS 2.0 jQuery Plugin (Cocomore AG)
2.13 Integrating ITS 2.0, Content Management Interoperability Services, and W3C Provenance
2.13.1 Description
Localization interoperability can be enhanced by using not just ITS 2.0 as standard. In particular, the following standards
provide additional opportunities:
- OASIS Content Management Information Service (CMIS) to externally associate multiple ITS 2.0 rules files with large sets
of documents, and to retrieve those documents regardless of the Content Management System in use
- W3C Provenance (PROV) to track which human agents or software agents processed the content; tracking can span multiple agents/components,
while allowing individual tracking records to be easily consolidated via linked data approaches
Benefits:
- Enables ITS 2.0 annotations to be associated with multiple documents via the CMS without editing individual files. This reduces
source content internationalization and document management costs. Furthermore, it reduces annotation errors.
- Allows fine-grained tracking and analysis of Language Technology (LT) components, human agents (language workers) and service
providers - even across multiple organizations, projects, and heterogeneous process landscapes. This reduces the overhead costs
in tracking, monitoring, analyzing and optimizing the localization workflows - especially of the critical elements within
them (e.g. MT engines, human terminologists and translators)
- Enables tracking of human linguistic judgments and their influence on the output of LT components. Tracking data can be
curated for retraining/retuning those LT components (e.g. Statistical Machine Translation or text analysis components)
- Tracking information can be mapped to the W3C PROV Ontology (PROV-O) which expresses the PROV Data Model using the OWL2 Web
Ontology Language (OWL2), and stored in Resource Description Framework (RDF) triple stores.
2.13.2 Data category usage
- Provenance - Tracks MT-based translation and translation revision through a post-editing interface. Tracking is implemented
as standoff provenance records in XLIFF files. The post-editing records detail which of the MT outputs was used if multiple
MT outputs are offered to the post-editor. The agent's ITS annotations (from translation and translation revision) are mapped
to PROV-O triples in the accompanying RDF provenance logs.
- Text analysis - Calls text analysis service (e.g. Enrycher) on source HTML file for Named Entity Recognition annotations.
These annotations are also mapped into XLIFF files. This annotation results in logging of activities performed on an 'analysed
text' entity in the PROV-O triple store.
- Terminology - Allows text annotated by Named Entity Recognition, as well as other phrases, to be identified as terms and
used to populate a multilingual glossary. If the text analysis annotation returns a DBpedia reference, a query for the label
used in the equivalent target language page can be attempted to populate the term target in the glossary. The terminology
annotation and the glossary are mapped to XLIFF as well as resulting in a 'term' entity being tracked in the PROV-O provenance
logs.
- MT Confidence - This is used to annotate - in XLIFF - the assumed quality of output of MT engines. MT Confidence is also
tracked for the translation entities generated by MT in the PROV-O logs.
- Domain - Mapped from HTML source document to XLIFF, and used to annotate PROV-O entities representing source units, i.e.
the source content of translation units.
- Translate - Mapped from HTML source document to XLIFF, and used to annotate PROV-O entities representing source units, i.e.
the source content of translation units.
Where available, and not already specified by explicit ITS provenance annotation, annotatorsRef was used to derive PROV-O
agent details for specific activities, e.g. text analysis and terminology.
2.13.3 More Information and Implementation Status/Issues
Details:
2.14 Text Analysis - Named Entity Recognition and Enrichment
2.14.1 Description
- Named entities (e.g. names of persons, places, or products) in HTML content are recognized based on the Natural Language
Processing (NLP) tool - Enrycher.
- The entities are enriched in the following ways:
- the identity is computed/disambiguated (so that for example London - England, and London - Ontario can be distinguished)
- a category (e.g. geographic name/place) is assigned
- Both the entity recognition and the enrichment generate markup which amongst others allows tracking of the software agent/NLP
tool that was used
- Enriched, disambiguated content facilitates processing for source and target languages (amongst others since it provides
context to translators)
Benefits:
- The ITS 2.0 markup provides the key information about entities, so they can be correctly processed. Example: one may employ
specific translations, transliterations, officially mandated translations, or even keep the original.
- Content management systems may use disambiguated, enriched content for providing entity-centric browsing and retrieval functionality.
2.14.2 Data category usage
- Text Analysis - Mark fragments of content which mention named entities; enrich the content by additional information such
as a URI denoting the entity's identity.
- Text Analysis - Mark fragments of content with individual word meanings; enrich the content by additional information such
as a URI denoting the word's meaning.
2.14.3 More Information and Implementation Status/Issues
Implementation issues and need for discussion:
- Implementation of NLP tools for providing the Domain data category annotations.
2.15 Automated Terminology Annotation
2.15.1 Description
- Term candidates in HTML5, XLIFF and plaintext are annotated by humans or software agents (automatic term candidate annotation).
- Automatic term candidate annotation can comprise:
- Term candidate recognition based on existing terminology resources (e.g., term banks, such as EuroTermBank or IATE)
- Term candidate identification based on unguided terminology extraction systems (e.g., ACCURAT Toolkit or TTC TermSuite)
- Content analysis and terminology mark-up are performed by a Web Service API with the following functionality:
- Support for ITS 2.0 metadata (Terminology, Language Information, Domain, Elements Within Text and Locale Filter data categories);
- Annotation of the content by the two above-mentioned methods. The API breaks down the content in Language and Domain dimensions
and uses terminology annotation services provided by the TaaS platform in order to identify terms and link them with the TaaS
platform.
- Visualization capabilities are provided for the annotated terminology allowing human users access to the annotation results.
Benefits:
The Web Service API can be integrated in automated language processing workflows, for instance, machine translation, localization,
terminology management and many other tasks that may benefit from terminology annotation.
2.15.2 Data category usage
- Domain - The domain information is used to split and analyze the content per domain separately. This allows filtering terms
in the term bank-based terminology annotation as well as identifying domain-specific content using unguided term extraction
systems. The user is asked to provide a default domain for the term bank-based terminology annotation. This user-supplied
domain will be overridden with ITS 2.0 domain metadata if present in the content.
- Element Within Text - The information is used to decide which elements are extracted as in-line codes and sub-flows.
- Language Information - The language information is used to split and analyze the content per language. The user will be asked
to provide a source (default) language, however, the default language will be overridden with ITS 2.0 Language Information
metadata if present in the content.
- Locale Filter - Whenever used only the text in the locale as specified by the user defined source language is analyzed. The
remaining content is ignored.
- Terminology - For existing terminology metadata, the mark-up is preserved (terminology mark-up overlaps are not allowed).
For new terminology metadata, terms are marked according to the Terminology data category’s rules.
2.15.3 More Information and Implementation Status/Issues
The implementation has reached Milestone 2 (Initial HTML5 term tagging with simple visualization). The implementation for
the Milestone 3 (Enhanced HTML5 term tagging with full visualization) is ongoing.
- Detailed slides: will be made available at the end of May, 2013
- Running code: http://taws.tilde.com
- Source code: will be made available at the end of May, 2013
- General documentation: will be made available at the end of May, 2013
2.16 Universal Preview of ITS 2.0 Metadata in XML, XLIFF, and HTML Files
2.16.1 Description
XML-based source content such as XLIFF files is usually provided to translators or reviewers as reduced and partially transformed
text without any information about local or global context or support for rendering/visualization of content itself or metadata
embedded in the content. In sum this has negative effects on quality of final output and productivity of human workers.
The usage scenario allows rendering of content and metadata for easy and interactive reading it as a reference material in
a browser. The rendering includes special visual cues, and interaction possibilities (such as colour-coding and pop-ups for
metadata to be displayed). It is based on auxiliary files in HTML5+ITS 2.0 (including JavaScript) that are generated from
ITS-annotated source content of any supported formats (XML, XLIFF, HTML).
2.16.2 Data category usage
- All ITS 2.0 data categories
2.16.3 More Information and Implementation Status/Issues
Implementer: Logrus
Implementation status: Prototype will display Translate, Localization Note, and Terminology data categories at the MultilingualWeb
Workshop March 2013.
2.17 ITS 2.0 in word processing software
2.17.1 Description
- The tool - ITS for Libre Office Writer Extension (ILO)- allows use of a subset of ITS 2.0 in an open source word processing
software (Libre Office).
- Capabilities include:
- Tagging phrases and terms as “not to translate” (translate)
- Tagging words as “term” (terminology)
- Tagging words for a specific locale only (locale filter)
- Providing additional information for the translator (localization note)
- The Libre Office extension and its software packages allows users to
- Load ITS 2.0 annotated XML files (ODT, XLIFF)
- Visualize ITS 2.0 metadata in the WYSIWYG editor of Libre office
- Edit text related to ITS 2.0 meta data
- Save and export the text and including ITS 2.0 markup into the original file format (ODT, XLIFF)
2.17.2 Data category usage
- Terminology - One or several words can be marked up as “term”
- Translate – Mark content as “to translate” or “not to translate”
- Localization Note – Pass a message (information, alert) to human agents (such as translators)
- Locale Filter – Limit content to specific locales
2.17.3 More Information and Implementation Status/Issues
ILO uses OKAPI capabilities for XLIFF handling and will be available in April 2013. The use of ILO will be presented at the MultilingualWeb Workshop March 2013. The results of ILO development will be given back to the public domain under the open licenses
LGPL V3 (same as Libre Office).
2.18 Training for Statistical Machine Translation
2.18.1 Description
- ITS 2.0 bilingual data is collected in a Content Management System, and passed to a Statistical Machine Translation (SMT)
system for training the system's language models.
- If domain information is supplied for the content, domain-aware modules in the SMT system are trained on the corresponding
content.
Benefits:
- The ITS 2.0 markup provides key information to drive the reliable extraction of domain-specific content.
- MT systems trained on domain-specific data allow for potentially more accurate translation.
2.18.2 Data category usage
- Translate - Parts that retain their original form are passed through the MT as-is.
- Language Information - Used to select the appropriate MT language models.
- Domain - Domain values direct the selection of/training of the appropriate MT language models.
2.18.3 More Information and Implementation Status/Issues
3 Authors and Implementation Contributors
Renat Bikmatov (Logrus),
David Filip (University of Limerick),
Leroy Finn (Trinity College Dublin),
Karl Fritsche (Cocomore AG),
Serge Gladkoff (Logrus),
Declan Groves (Centre for Next Generation Localisation (CNGL), Dublin City University),
Milan Karasek (Moravia),
Jirka Kosek (University of Economics, Prague),
Kevin Lew (Spartan Software),
Dave Lewis (Trinity College Dublin),
Fredrik Liden (ENLASO Corporation),
Shaun McCane ((public) Invited expert),
Sean Mooney (University of Limerick),
Pablo Nieto Caride (Linguaserve),
Pēteris Ņikiforovs (Tilde),
David O'Carrol (University of Limerick),
Philip O'Duffy (University of Limerick),
Mauricio del Olmo (Linguaserve),
Mārcis Pinnis (Tilde),
Phil Ritchie (VistaTEC),
Nieves Sande (German Research Center for Artificial Intelligence (DFKI) Gmbh),
Felix Sasaki (W3C Fellow),
Yves Savourel (ENLASO Corporation),
Sebastian Sklarß (]init[ Europe),
Ankit Srivastava (Centre for Next Generation Localisation (CNGL), Dublin City University),
Tadej Štajner (Jozef Stefan Institute),
Chase Tingley (Spartan Software),
Asanka Wasala (University of Limerick),
Clemens Weins (Cocomore AG).


Fighting hunger and food waste by facilitating the redistribution of surplus food.
The Problem
40% of the food produced in Canada is wasted each year.
The average Canadian wastes approximately 183kg of solid food per year.
Food waste costs Canada's economy more than $31 billion each year.
What We Do
TrashTALK is a social platform where relationships are built between food businesses and charities, communication is quick and simple and food reaches those in need, safely and conveniently.
When a business has surplus food to donate, they upload their information online. Nearby charities scroll through our Trashboard and can claim the food online.


Free and hackable accounting
Loading JS..
Failed contacting the server, please check if:
Sorry to bother you, but I got an error that needs to be corrected:


Background Transparency
Band Transparency
Band Thickness
Band 1 Position
Band 2 Position
Band 3 Position
Gradient


--- layout: post title: Funny highway circumstances published: 1 category: - Humor ---
Seen this morning in the slow crawl down the freeway to get to work this morning: a shiny white BMW 5-series number, creeping along like the rest of us, with a vanity plate that read "ZIP N BY".


Choose where you log in
Log In
Cancel
Login with custom provider ...
Solid Community
Inrupt Pod Spaces
OpenLink WebID-OIDC
OpenLink Solid Server ver:5.x
OpenLink Solid Server ver:5.6
OpenLink Solid Community
OpenLink Data Spaces (QA server)
OpenLink URIBurner Service
OpenLink Identity Provider
ID MyOpenLink.NET
Logged In as:
Logout


#include <container_p.h>
Public Types | |
| using | const_iterator = container_type::const_iterator |
| using | container_type = StagePrivate::container_type |
| using | iterator = container_type::iterator |
| using | NonConstStageCallback = std::function< bool(Stage &, int)> |
| Public Types inherited from moveit::task_constructor::StagePrivate | |
| typedef std::list< Stage::pointer > | container_type |
| container type used to store children More... | |
Public Member Functions | |
| bool | canCompute () const override |
| const_iterator | childByIndex (int index, bool for_insert=false) const |
| const container_type & | children () const |
| void | compute () override |
| InterfacePtr | pendingBackward () const |
| InterfacePtr | pendingForward () const |
| bool | remove (ContainerBasePrivate::const_iterator pos) |
| remove child at given iterator position, returns fals if pos is invalid More... | |
| InterfaceFlags | requiredInterface () const override |
| Retrieve interface required by this stage, UNKNOWN if auto-detected from context. More... | |
| bool | traverseStages (const ContainerBase::StageCallback &processor, unsigned int cur_depth, unsigned int max_depth) const |
| traversing all stages up to max_depth More... | |
| bool | traverseStages (const NonConstStageCallback &processor, unsigned int cur_depth, unsigned int max_depth) |
| non-const version More... | |
| void | validateConnectivity () const override |
| validate connectivity of children (after init() was done) More... | |
| Public Member Functions inherited from moveit::task_constructor::StagePrivate | |
| void | composePropertyErrorMsg (const std::string &name, std::ostream &os) |
| void | connect (const InterfaceState &from, const InterfaceState &to, const SolutionBasePtr &solution) |
| InterfacePtr & | ends () |
| InterfaceConstPtr | ends () const |
| InterfaceFlags | interfaceFlags () const |
| actually configured interface of this stage (only valid after init()) More... | |
| container_type::const_iterator | it () const |
| const Stage * | me () const |
| Stage * | me () |
| const std::string & | name () const |
| void | newSolution (const SolutionBasePtr &solution) |
| InterfacePtr | nextStarts () |
| InterfaceConstPtr | nextStarts () const |
| const ContainerBase * | parent () const |
| ContainerBase * | parent () |
| InterfacePtr | prevEnds () |
| InterfaceConstPtr | prevEnds () const |
| InterfacePtr & | pullInterface (Interface::Direction dir) |
| templated access to pull/push interfaces More... | |
| InterfaceConstPtr | pullInterface (Interface::Direction dir) const |
| InterfacePtr | pushInterface (Interface::Direction dir) |
| InterfaceConstPtr | pushInterface (Interface::Direction dir) const |
| virtual void | resolveInterface (InterfaceFlags) |
| Resolve interface/propagation direction to comply with the given external interface. More... | |
| void | runCompute () |
| void | sendBackward (InterfaceState &&from, const InterfaceState &to, const SolutionBasePtr &solution) |
| void | sendForward (const InterfaceState &from, InterfaceState &&to, const SolutionBasePtr &solution) |
| void | setIntrospection (Introspection *introspection) |
| void | setNextStarts (const InterfacePtr &next_starts) |
| bool | setParent (ContainerBase *parent) |
| void | setParentPosition (container_type::iterator it) |
| void | setPrevEnds (const InterfacePtr &prev_ends) |
| void | spawn (InterfaceState &&state, const SolutionBasePtr &solution) |
| StagePrivate (Stage *me, const std::string &name) | |
| InterfacePtr & | starts () |
| InterfaceConstPtr | starts () const |
| bool | storeFailures () const |
| bool | storeSolution (const SolutionBasePtr &solution) |
| void | unparent () |
| explicitly orphan stage More... | |
| virtual | ~StagePrivate ()=default |
Protected Member Functions | |
| ContainerBasePrivate (ContainerBase *me, const std::string &name) | |
| void | copyState (Interface::iterator external, const InterfacePtr &target, bool updated) |
| copy external_state to a child's interface and remember the link in internal_to map More... | |
| auto & | internalToExternalMap () |
| const auto & | internalToExternalMap () const |
| void | liftSolution (const SolutionBasePtr &solution, const InterfaceState *internal_from, const InterfaceState *internal_to) |
| lift solution from internal to external level More... | |
| void | setChildsPushBackwardInterface (StagePrivate *child) |
| void | setChildsPushForwardInterface (StagePrivate *child) |
Protected Attributes | |
| InterfaceFlags | required_interface_ |
| Protected Attributes inherited from moveit::task_constructor::StagePrivate | |
| InterfacePtr | ends_ |
| std::list< SolutionBaseConstPtr > | failures_ |
| Stage * | me_ |
| std::string | name_ |
| size_t | num_failures_ = 0 |
| PropertyMap | properties_ |
| std::list< Stage::SolutionCallback > | solution_cbs_ |
| ordered< SolutionBaseConstPtr > | solutions_ |
| InterfacePtr | starts_ |
| std::list< InterfaceState > | states_ |
| std::chrono::duration< double > | total_compute_time_ |
Private Attributes | |
| container_type | children_ |
| std::map< const InterfaceState *, InterfaceState * > | internal_to_external_ |
| InterfacePtr | pending_backward_ |
| InterfacePtr | pending_forward_ |
Friends | |
| class | ContainerBase |
| void | swap (StagePrivate *&lhs, StagePrivate *&rhs) |
Definition at line 72 of file container_p.h.
| using moveit::task_constructor::ContainerBasePrivate::const_iterator = container_type::const_iterator |
Definition at line 80 of file container_p.h.
Definition at line 78 of file container_p.h.
| using moveit::task_constructor::ContainerBasePrivate::iterator = container_type::iterator |
Definition at line 79 of file container_p.h.
| using moveit::task_constructor::ContainerBasePrivate::NonConstStageCallback = std::function<bool(Stage&, int)> |
Definition at line 81 of file container_p.h.
|
protected |
Definition at line 56 of file container.cpp.
|
overridevirtual |
Implements moveit::task_constructor::StagePrivate.
Definition at line 99 of file container.cpp.
| ContainerBasePrivate::const_iterator moveit::task_constructor::ContainerBasePrivate::childByIndex | ( | int | index, |
| bool | for_insert = false |
||
| ) | const |
Retrieve iterator into children_ pointing to indexed element. Negative index counts from end, i.e. -1 is last, -2 is second last, etc. (if !for_insert) If for_insert == true, negative indexes are shifted by one: -1 is end(), -2 is –end(), etc. Contrary to std::advance(), iterator limits are considered.
Definition at line 62 of file container.cpp.
|
inline |
Definition at line 83 of file container_p.h.
|
overridevirtual |
Implements moveit::task_constructor::StagePrivate.
Definition at line 104 of file container.cpp.
|
protected |
copy external_state to a child's interface and remember the link in internal_to map
Definition at line 109 of file container.cpp.
|
inlineprotected |
Definition at line 140 of file container_p.h.
|
inlineprotected |
Definition at line 141 of file container_p.h.
|
protected |
lift solution from internal to external level
Definition at line 121 of file container.cpp.
|
inline |
Definition at line 116 of file container_p.h.
|
inline |
Definition at line 117 of file container_p.h.
| bool moveit::task_constructor::ContainerBasePrivate::remove | ( | ContainerBasePrivate::const_iterator | pos | ) |
remove child at given iterator position, returns fals if pos is invalid
Definition at line 203 of file container.cpp.
|
inlineoverridevirtual |
Retrieve interface required by this stage, UNKNOWN if auto-detected from context.
Implements moveit::task_constructor::StagePrivate.
Definition at line 110 of file container_p.h.
|
inlineprotected |
Definition at line 123 of file container_p.h.
|
inlineprotected |
Definition at line 128 of file container_p.h.
| bool moveit::task_constructor::ContainerBasePrivate::traverseStages | ( | const ContainerBase::StageCallback & | processor, |
| unsigned int | cur_depth, | ||
| unsigned int | max_depth | ||
| ) | const |
traversing all stages up to max_depth
Definition at line 78 of file container.cpp.
|
inline |
non-const version
Definition at line 99 of file container_p.h.
|
overridevirtual |
validate connectivity of children (after init() was done)
Reimplemented from moveit::task_constructor::StagePrivate.
Reimplemented in moveit::task_constructor::ParallelContainerBasePrivate, and moveit::task_constructor::SerialContainerPrivate.
Definition at line 93 of file container.cpp.
|
friend |
Definition at line 74 of file container_p.h.
|
friend |
|
private |
Definition at line 147 of file container_p.h.
|
private |
Definition at line 150 of file container_p.h.
|
private |
Definition at line 155 of file container_p.h.
|
private |
Definition at line 157 of file container_p.h.
|
protected |
Definition at line 144 of file container_p.h.


Before Change
self.log.debug("Read %d bytes" % total_bytes)
// Check the size.
if total_bytes != expected_size:
raise self.CacheError("Read only %d bytes from %d expected" % (total_bytes,
expected_size))
// Extract the tarfile.
with open_tar(outfile.name, "r") as tarfile:
tarfile.extractall(self.artifact_root)
return True
except Exception as e:
After Change
// Extract the tarfile.
artifact = TarballArtifact(self.artifact_root, outfile.name, self.compress)
artifact.extract()
return artifact
except Exception as e:
self.log.warn("Error while reading from remote artifact cache: %s" % e)
return None


Main Page
Related Pages
Data Structures
Files
Related Pages
Here is a list of all related documentation pages:
Tommy Benchmarks
Tommy Multi Indexing
Tommy Design
Tommy License


@Documented @PodamAnnotation @Target(value={FIELD,PARAMETER}) @Retention(value=RUNTIME) public @interface PodamCollection
Please note that this annotation can be used with all types of container elements, including arrays.
The minimum number of elements is
PodamConstants.DEFAULT_NBR_COLLECTION_ELEMENTS
| Modifier and Type | Optional Element and Description |
|---|---|
Class<? extends AttributeStrategy<?>> |
collectionElementStrategy
The strategy that will populate the annotated attribute.
|
String |
comment
It allows clients to specify a comment on this annotation
|
Class<? extends AttributeStrategy<?>> |
mapElementStrategy
The strategy that will populate a map element on an attribute of type
Map.
|
Class<? extends AttributeStrategy<?>> |
mapKeyStrategy
The strategy that will populate a map key on an attribute of type Map.
|
int |
nbrElements
The number of elements to create for the collection
|
public abstract int nbrElements
public abstract Class<? extends AttributeStrategy<?>> collectionElementStrategy
The default, in order to make the strategy actually optional is
type Object. At runtime, only if both the value of this annotation and
the collection element type are Objects, then the collection will be set
with type Object
, otherwise the collection element type will win.
public abstract Class<? extends AttributeStrategy<?>> mapKeyStrategy
The default, in order to make the strategy actually optional is
type Object. At runtime, only if both the value of this annotation and
the collection element type are Objects, then the collection will be set
with type Object
, otherwise the collection element type will win.
public abstract Class<? extends AttributeStrategy<?>> mapElementStrategy
The default, in order to make the strategy actually optional is
type Object. At runtime, only if both the value of this annotation and
the collection element type are Objects, then the collection will be set
with type Object
, otherwise the collection element type will win.
public abstract String comment
Copyright © 2017. All rights reserved.


Tutorial Attendance Dashboard
What's this?
{{ tutorialAttendance.title}}
Tutorial Attenadnce
×
This dashboard showcases the number of tutorial sessions attended by students.


Responsibilities:
Work as Project Manager or Project Leader in Web-based development projects with main duties:
• Contact with onshore Project Manager (Europe) or development Partner or Customer (in English);
• Project Requirement: analysis, development and management (change tracking);
• Estimate project’s development cost (in association with Technical Team if necessary);
• Plan project’s schedule, organize team, lead, build/manage project documents, manage the development process;
• Manage: Cost, budget, qualities & customer satisfaction;
• Follow company process, contribute on process improvement;
• Discuss and troubleshoot the requirements or problems with onshore (European) managers or customers (via email, messenger, PMS tool);
• Report to the Program Manager & PMO Head;
• Ready to work overtime up on request (for problems or urgent issues).
We offer:
• Young, dynamic, creative and friendly environment
• Knowledge sharing
• Learning from colleagues
• Fast growing career path
• Project Bonus
• The best overtime policy
• Health care program
• Competitive salary package
Requirements:
• Nationality: Vietnamese or Overseas Vietnamese
• Education: Bachelor (software related)
• Language: Very good at all skills of English
• 4 years professional experience in Web/Internet or software development, with more than 1 year experience in PROJECT MANAGER position in Enterprise environment.
• Strong knowledge about Web/Online development. Broad knowledge of contemporary web systems, sites and concepts such as Social Networks, Social Community, Online Marketing, E-commerce, CRM, SaaS, Cloud, etc...
• Good knowledge in project management, development process, tools (such as Ms Project, Open Workbench,…)
• Good knowledge in Installation & Configuration with Windows Web/DB servers, and/or Apache..
• Good communication skills: group discussion leading, team working..
• Good project management skills: estimating, planning, organizing, leading.
• Have knowledge and experience in Web development and some technologies (.NET or PHP or JAVA).
• Personality: highly responsible, well-organized, communicative, pro-active, dare-to-lead, result oriented, flexibility & adaptabilities
Location: Ho Chi Minh City
Company information:
Pyramid Consulting is an International Web Agency offering Web-based, Multimedia and Wireless/SMS development services for Europe, North America and APAC clients who are the top International Interactive Marketing Agencies or Enterprise clients, founded since 1999 in Brussels, Belgium (Europe).
Pyramid Consulting Vietnam is the offshore Development Center of Pyramid Consulting Group, started since 2001, providing Online & Mobile development outsourcing services to world-wide customers. Pyramid Consulting Vietnam is currently one of top 3 largest Web development firms in Vietnam and is the only one serving online interactive marketing & e-business industry.
With 10 years of evolution and around more than 250 members, Pyramid Consulting is partner of the top International Interactive Marketing Communication Agencies in Europe (Belgium, France, Holland, UK), North America (Canada, United States) and APAC (Singapre, Hongkong, Australia, Vietnam), such as Publicis Moderm, MRM Worldwide, BBDO proximity, Ogilvy Interactive, McCann, FullSix, YellowPepper, etc.
The company is invested by IDG.
We offer a friendly, creative and cooperative workplace. Salary is kept competitive in the market.
Join and enrich your values at Pyramid Consulting Vietnam!


SDEDownloadManager
is a download management library, which is written with Swift and is compatible with Objective-C.
The same name class SDEDownloadManager provides download management features. And, a UITableViewController subclass, DownloadListController, coordinates with SDEDownloadManager to display and manage download tasks, and track download activity.
API Reference: Quick help in Xcode maybe doesn’t work well out of framework, you will need this. It’s generated by jazzy.
Requirements
- iOS 8.0/Swift 4.0
Library Components
SDEDownloadManager [Document]
- Basic download management: download/pause/resume/stop/restart/delete.
- Sort download list with predefine types and powerful predicate.
- Control download count: it’s good as you think.
- Track download activity: download progress and speed.
- Cache thumbnails for files.
- Handle part authentication: Basic, Digest, and server trust.
- Handle app force quit in downloading and you have to do nothing.
The features it doesn’t support:
- Don’t support specifying file store location. It’s meaningless on iOS devices.
- Don’t support playing and caching online media file. It just download file.
- Don’t support limiting download speed.
- Don’t support multithreading download for a single file.
DownloadListController [Document] [Cheat Sheet]
- Custom content to display:
- Custom cell content. All elements in the cell are customizable, some examples:
Except textLabel, other elements could be hidden.
You also could use custom UITableViewCell. There is only one cell available for now.
- Custom manage features in cell swipe and multiple selection, these features are disabled by default;
- Adjust max download count by
adjustButtonItem
; - Sort list by
sortButtonItem
.
SliderAlertController [Document]
A UIViewController subclass like UIAlertController to display a slider, allows to display custom symbol for special vaule, like ∞
for 0 above.
URLPickerController [Document]
A UITableViewController subclass to pick URL strings. In demo, I use it to pick files for DownloadListController
to download.
What you need to know before using the library
SDEDownloadManager
maintains a downloadList
for all tasks, which is a [[String]]
and is designed for UITableView/UICollectionView.
Here is the only method to create a SDEDownloadManager object:
static func manager(identifier: String, manualMode: Bool = false) -> SDEDownloadManager
If a download manager with specified identifier exists in the memory already, this method returns it directly, so you don’t have to keep a reference to use it in other places.
let libraryLink = "https://codeload.github.com/seedante/SDEDownloadManager/zip/master"
SDEDownloadManager.manager(identifier: "Link").download([libraryLink])
SDEDownloadManager has two sort modes: manual and predefined mode(include: .addTime
, .fileName
, .fileSize
, .fileType
). The two sort modes can switch to each other freely in sortListBy(type:order:)
. Except for obvious sort difference, what’s difference between with two modes?
Download new file. In predefined mode, you just need to offer download URL, but in manual mode, you must also offer its insert location in
downloadList
.A section in UITableView with
.plain
style can’t be distinguished from last section if it doesn’t have a title, so in manual mode, when you insert a new section, it must have a title.
Although you can switch between with two sort modes freely, switching from manual mode to predefined mode will lose all section titles, and switching from predefined mode to manual mode will integrate all tasks into one section with a placeholder title, so choose sort mode based on your usage scenario discreetly.
In addition, in predefined mode, when downloading a new file, its name and type maybe change, and its file size is known after its meta info is fetched, so SDEDownloadManager change its sort type to .addTime
automatically if it’s not.
Installation
CocoaPods: pod 'SDEDownloadManager'
Carthage: github "seedante/SDEDownloadManager"
If you are not familiar with CocoaPods or Carthage, or you want to install it manually, reference to Installation Guide.
After installation, import SDEDownloadManager into your project:
// In Swift file
import SDEDownloadManager
// In Objective-C file
@import SDEDownloadManager;
Localization for UIViewController in the Library
Supported localizable languages for now: English, Simplified Chinese.
License
SDEDownloadManager is released under the MIT LICENSE.


Docker is a set of platform as a service products that uses OS-level virtualization to deliver software in packages called containers.
Images
is a file, comprised of multiple layers, that is used to execute code in a Docker container. Images are created from a Dockerfile with the docker build command.
Containers
are isolated units of software that packages up code and all its dependencies so the application runs quickly and reliably from one computing environment to another. A runnable instance of an image
Virutal Machines
a virtual machine is an emulation of a computer system. A virtual machine is sandboxed from the rest of the system, meaning that the software inside a virtual machine can’t escape or tamper with the computer itself.
Containers and virtual machines have similar resource isolation and allocation benefits, but function differently because containers virtualize the operating system instead of hardware. Containers are more portable and efficient.
What does Microservices have to do with container orchestration? Please watch the video below in your own time. The video provides an overview of microservices and how containers are orchestrated.
Simple Environment Configuration
Simple configuration is the primary use case of Docker
App Isolation & Testing
Cautious of erraneous code can be ran in a contained environment. Testing and previewing new applications. Using Docker Hub to pull down preconfigured applications.
Rapid Deployment and Scaling
Easier to deploy an application that runs within a container that contains all of the application processes
Code Pipeline Management
Docker eases the code development and deployment pipeline and offers a consistent environment for the application from dev through production.
Please watch the video below in your own time. The video highlights the difference between virtual machines and containers.
The best choice for running a microservices application architecture is application containers. Containers encapsulate a lightweight runtime environment for your application, presenting a consistent software environment that can follow the application from the developer's desktop to testing to final production deployment, and you can run containers on physical or virtual machines.
Installing Docker on Windows
1) Navigate to docker.com/get-started to download for windows.
2) Click on the download button for Windows
3) Run the executable file to install docker on machine.
Using Docker Plugin in VS Code
1) Within Visual Studio Code, navigate to the extensions tab on the left
2) Search for Docker from Microsoft and install
# Lets us know the version of docker
docker --version
# Pulling the hello-world image from Docker Hub and runs the container
docker run hello-world
# Command to display on the images
docker image ls
# Stops container and removes container
docker container stop hello-world
docker container rm hello-world
Step 1
Open Visual Studio code and click on the extensions tab/icon.
Step 2
Open terminal and run the various commands above.
Step 3
Stop container and remove container
DockerHub - the world's easiest way to create, manage, and deliver your teams' container applications.
Step 1
Navigate to hub.docker.com and make sure you create an account and complete initial walkthrough that has you create and push up a container.
Step 2
Navigate to the Explore tab and search for ghost image. Click on ghost image and copy command docker run -d --name some-ghost -e url=http://localhost:3001 -p 3001:2368 ghost
. Open in browser and explore ghost blog platform. The -p 3001:2368
is mapping my machines port to the containers port.
Step 3
Stop container by running command [docker container stop some-ghost] and remove container by running command [docker container rm some-ghost]
What is a dockerfile - a text file that contains all commands, in order, needed to build a given image
# Define from what image we want to build from
FROM node:14.18.1
# Provides metadata regarding the Dockerfile
LABEL version="1.0"
LABEL description="Docker image for class example "
LABEL maintainer =<EMAIL_ADDRESS># Sets the working directory for application in container
WORKDIR /app
# Which files would we like to copy into the construction of the image
COPY . /app
# What commands we would like to run once
CMD ["node", "app/docker.js"]
FROM
Defines the image we will use as the basis for our container.
LABEL
Defines the metadata for our Dockerfile, including information about the version, description, and maintainers.
WORKDIR
Sets the working directory for the application. If the working directory does not already exist, it is created by Docker.
COPY
Copy a file or files into the Docker container.
RUN
Specifies a command that should be run by Docker. You typically use this command to install dependencies, debug, and execute commands in the container.
EXPOSE
Tells Docker which ports the container should listen on during runtime.
CMD
Specifies the command that should be executed when the docker container starts.
1. Create a file called dockerfile
Create a folder and run the touch command to create a Dockerfile. No file extension is needed.
2. Add Instructions in Dockerfile
Dockerfile reference can be found at this link
3. Build Dockerfile to create image
Run the docker build -t newimagename:1.0
to construct image that is now named "newimagename" version "1.0"
4. Run Image to create container
Run the command docker container run --name to run the container.
5. Stop and remove container
Run the command docker container stop [NAME_OF_CONTAINER]
and run the command docker container rm [NAME_OF_CONTAINER]
# Step 1 - Defines and invokes function
dockerSucessOutput();
function dockerSucessOutput(){
console.log("Dockerfile correctly constructed and image and ran program");
}
# Step 2 - Including directives into Dockerfile
FROM node:14.18.1
COPY . /app
CMD ["node", "app/docker.js"]
# Step 3 - Stop container
docker container stop sample_walkthrough .
Step 1
Create a project folder and add a file called docker.js. Within the docker.js file copy the code under step 1 and save.
Step 2
Create a Dockerfile by running command [touch Dockerfile]. Within the docker file, copy the statements under step 2.
Step 3
Build the image by running command [docker build -t sample_walkthrough .]. Observe the output in console and stop container by running the command above under step 3.
Compose is a tool for defining and running multi-container Docker applications. With Compose, you use a YAML file to configure your application’s services.
YAML File Examples below:
Containers: front-end + back-end
version: '1'
services:
front:
build: ./front
ports:
- '3000:3000'
depends_on:
- back
back:
build: ./back
ports:
- '8080:8080'
Containers: MySQL DB + Wordpress CMS
version: '2'
services:
db:
image: mysql:5.7
volumes:
- db_data:/var/lib/mysql
restart: always
environment:
MYSQL_ROOT_PASSWORD: rootpasswordchangeme
MYSQL_DATABASE: wordpress
MYSQL_USER: usernamechangeme
MYSQL_PASSWORD: passwordchangeme
wordpress:
depends_on:
- db
image: wordpress:latest
ports:
- "8000:80"
restart: always
environment:
WORDPRESS_DB_HOST: db:3306
WORDPRESS_DB_USER: usernamechangeme
WORDPRESS_DB_PASSWORD: passwordchangeme
volumes:
db_data:
1. Build individual images or pull them from a registry.
Make sure each service has it's own Dockerfile that builds an image.
2. Define all services in a docker-compose.yml file.
Once each service has a dockerfile, consider the placement of the .yaml file
3. Run command
Run all of them together using the docker-compose CLI. docker-compose up -d
Kubernetes is able to load balance and distribute the network traffic so that the deployment is stable.
Kubernetes allows you to automatically mount a storage system of your choice, such as local storages, public cloud providers, and more.
Kubernetes can create new containers for your deployment, remove existing containers and adopt all their resources to the new container.
You tell Kubernetes how much CPU and memory (RAM) each container needs. Kubernetes can fit containers onto your nodes to make the best use of your resources.
Kubernetes restarts containers that fail, replaces containers, kills containers that don't respond to your user-defined health check, and doesn't advertise them to clients until they are ready to serve.
Kubernetes lets you store and manage sensitive information, such as passwords, OAuth tokens, and SSH keys
source: https://kubernetes.io/docs/concepts/overview/what-is-kubernetes/
Kubernetes runs your workload by placing containers into Pods to run on Nodes
Master Node [3 Components]
A master node is a node which controls and manages a set of worker nodes (workloads runtime) and resembles a cluster in Kubernetes.
Worker Nodes
A Node is a worker machine in Kubernetes and may be either a virtual or a physical machine, depending on the cluster. Each Node is managed by the control plane. A Node can have multiple pods, and the Kubernetes control plane automatically handles scheduling the pods across the Nodes in the cluster.
Pods
Pods are the smallest, most basic deployable objects in Kubernetes. A Pod represents a single instance of a running process in your cluster. Pods contain one or more containers, such as Docker containers.
How would you best describe Kubernetes?
What does kubernetes do?
How does kubernetes group containers together?
Which feature in kubernetes assigns pods to a node at runtime?
Documentation on getting started with Kubernetes using docker desktop. Link found here.
# Your workflow name.
name: Deploy to heroku.
# Run workflow on every push to master branch.
on:
push:
branches: [main]
# Your workflows jobs.
jobs:
build:
runs-on: ubuntu-latest
steps:
# Check-out your repository.
- name: Checkout
uses: actions/checkout@v2
### ⬇ IMPORTANT PART ⬇ ###
- name: Build, Push and Release a Docker container to Heroku. # Your custom step name
uses<EMAIL_ADDRESS># GitHub action name (leave it as it is).
with:
# Below you must provide variables for your Heroku app.
# The email address associated with your Heroku account.
# If you don't want to use repository secrets (which is recommended) you can do:
# email<EMAIL_ADDRESS>email: ${{ secrets.HEROKU_EMAIL }}
# Heroku API key associated with provided user's email.
# Api Key is available under your Heroku account settings.
heroku_api_key: ${{ secrets.HEROKU_API_KEY }}
# Name of the heroku application to which the build is to be sent.
heroku_app_name: ${{ secrets.HEROKU_APP_NAME }}
# (Optional, default: "./")
# Dockerfile directory.
# For example, if you have a Dockerfile in the root of your project, leave it as follows:
dockerfile_directory: ./
# (Optional, default: "Dockerfile")
# Dockerfile name.
dockerfile_name: Dockerfile
# (Optional, default: "")
# Additional options of docker build command.
docker_options: "--no-cache"
# (Optional, default: "web")
# Select the process type for which you want the docker container to be uploaded.
# By default, this argument is set to "web".
# For more information look at https://devcenter.heroku.com/articles/process-model
process_type: web
### ⬆ IMPORTANT PART ⬆ ###


Reference: Barak’s notes. Barak and Steurer’s survey.
“Sum-of-squares” is an algorithm that attempts to find feasible solutions to systems of polynomial inequalities, or a proof that there is no solution. It is widely applicable because many computational problems can naturally be put into the form of polynomial inequalities (ex. \(k\)-SAT can be encoded with degree \(k\)). The degree \(d\) of sum-of-squares is a tunable parameter; the algorithm runs in \(n^d\) time. We can look at
Why is SoS a natural notion?
There are many equivalent notions of sum-of-squares; we give 4. The first definition introduces an algorithm that searches for a pseudo-expectation operator; on the boolean cube this is essentially equivalent to a pseudo-distribution. We also give equivalences to a sum-of-squares proof and sum-of-squares representation.
In the next section we will motivate these definitions and show equivalences.
Let \(x=(x_1,\ldots, x_n)\) and \(\R[x]_{\le d}\) denote polynomials in \(x_1,\ldots, x_n\) of degree \(\le d\).
1$$2: See exercise 1.7.
2$$3: This is the SOS Theorem. It encompasses the Positivstellensatz, which says that every unsatisfiable system of equalities has a finite degre proof of unsatisfiability. (See exercise 1.14, 15 for part of the theorem.)
3$$4: See exercise 1.11.
The most common use of sum-of-squares is in SDP relaxations of combinatorial problems, as follows. Let \(f\) be a convex function. The goal is to find \[ \min_{x\in \{-1,1\}^n}f(x). \] One way to relax this is to write \(f(x)=g(x^Tx/n)\), and find \[ \min_{M\succeq 0, M_{ii}=1} g(M). \] This is a relaxation because if \(x\) is the optimal solution to the first problem, \(x^Tx/n\) is a feasible point for the second problem achieving the same value.2
Think of \(M_{ii}=1\) as degree-2 constraints that shrink the space we’re minizing over to be closer to just the set \(\set{x^Tx/n}{x\in \{-1,1\}^n}\).
Note this is the degree-2 SoS relaxation of this problem!3 The degree-\(l\) SoS relaxation is the optimization problem \[\min_{M\text{ pseudo-expectation satisfying }x_i^2=1} h(M)\] (note we showed that the set of pseudo-expectations is convex; it is defined by \(M\succeq 0\) and some linear equations). (\(x_i^2=1\) corresponds to \(M_{ii}=1\).) In the equation above we thought of \(M\) as a bilinear form on \(\R^n\times \R^n = \R[x]_{=1}\times \R[x]_{=1}\); here we’re just adding 1 to the vector space to get \(\R[x]_{\le 1}\times \R[x]_{\le 1}\) and stipulating \(M(1,1)=1\), which doesn’t change anything.
(If \(f\) is a linear function \(f(x_1,\ldots, x_n,x_1^2,x_1x_2,\ldots, x_1^3,\ldots)\), then \(g(M)\) is the function \(f(M(x_1,1),\ldots, M(x_n,1), M(x_1,x_1),\ldots)\).)
For example, the degree-4 SoS relaxation would correspond to optimizing over \((\R^2,\R^1,\R)^{\ot 2}\), where the solutions corresponding to solutions of the original problem are in the form \((x^{\ot 2},x,1)^{\ot 2},x\in \{-1,1\}^n\). For $M\((\R^2,\R^1,\R)^{\ot 2}\), the solutions satisfy equations like \(M_{ii,jk}=1, M_{i,ij}=1\), etc.—corresponding to multiples of polynomials \(x_i^2-1\).
Define
We can express this in terms of the characteristic function \(x\) of \(S\) defined as \(x_i=(i\in S)-(i\nin S)\) by \[ \an{x,Lx} = \rc{2d}\sum_{i\sim j} (x_i-x_j)^2 =\fc{4E(S,\ol S)}{d} = 2n\text{cut}(S). \]
Lemma: Let \(\wt{\E}\) be a degree-2 pseudo-expectation operator. Then there is a Gaussian distribution \(N\) such that \[\wt{\E_{x\sim\mu}} p(x) = \E_{y\sim N} p(y).\] The pseudo-expectation operator is a bilinear form on \(\R[x]_{\le 1}\times \R[x]_{\le 1}\) is associated with a matrix \(A=B^2\). Then \(y=Bx\) where \(x\sim N(0,1)\), i.e., \(y\) is the Gaussian with covariance matrix \(B\).
A lemma about Gaussians.
Lemma: If \((x,y)\) are \(1-\ep\)-correlated Gaussians, then \((x,y)^T =Av\) where \(A=\rc2 \smatt{\sqrt\ep+\sqrt{2-\ep}}{\sqrt{\ep}-\sqrt{2-\ep}}{\sqrt{\ep}-\sqrt{2-\ep}}{\sqrt{\ep}+\sqrt{2-\ep}}\), \(v\sim N(0,I)\). In other words, if \((x,y)\) are \(\cos(\te)\)-correlated Gaussians, then \(A=\smatt{\sin(\fc\pi4-\fc\te2)}{\sin(\fc\pi4+\fc\te2)}{\cos(\fc\pi4-\fc\te2)}{\cos(\fc\pi4+\fc\te2)}\) (I might have gotten cos/sin switched).
(Sanity check: when \(\te=0\) they point in \(\pi/4\), when \(\te=\fc \pi2\) they point in \(0,\fc\pi2\).)
Lemma: Let \(y,y'\) be Gaussians with variance 1 such that \[\E(y-y')^2 \ge 4(1-\de) = 2+2\cos(\te).\] Then \[\Pj(\sgn(y) = \sgn(y')) = \fc{\te}{\pi} = O(\sqrt{\de}).\]
Theorem: There is a polynomial-time algorithm which given a \(n\)-vertex \(d\)-regular graph \(G=(V,E)\) and a degree 2 pseudo-distribution with \(\wt E_{x\sim \mu} x_i^2=1\), \(\wt E\an{x,Lx} \ge 2n(1-\ep)\), outputs \(z\in \{\pm1\}^n\) such that \(\an{z,Lz} \ge (1-f_{GW}(\ep))=O(\sqrt \ep)\). (Add the precise form of \(f\).)
Proof: Let \(z_i=\sgn(y_i)\) and use Lemma on Gaussian variables on each term.
This is optimal. To see optimality in order of magnitude, take the odd cycle on \(n=\rc{\sqrt{\ep}}\) vertices, or a union of these. To see optimality in an additive sense, use the Feige-Schectman graph (random points on sphere connected in \(\an{v_i,v_j}\le -1+\ep\)).
Show that the FS graph can be solved by a degree 4 SoS. This is the same as saying there is no degree-4 distribution over \(\R^n\) consistent with \(\{x_i^2=1\}\) such that \[\wt E\sum (x_i-x_{i+1})^2>4(n-1).\] (We had a degree-2 distribution with \(\wt E>4n\pa{1-O\prc{n^2}}\), which gave the gap.)
Proof: The squared triangle inequality holds for degree-4 pseudodistributions. Sum up inequalities \(\wt E(x_i-x_{i+1})^2 \le \sum_{j\ne i} \wt E(x_j+x_{j+1})^2\).
Applications
Sum-of-squares is a powerful meta-algorithm.
Other meta-algorithms:
Gradient descent, integer linear programming: for a given problem there are many ways of formulating it. It depends crucially on how you set it up. SoS doesn’t suffer this. There is a mechanical way to apply it.
The vanilla version is impractical, but there are efforts to extract practical algorithms. They resemble heuristic algorithms used in practice.
Given \(p\in \R[x_1,\ldots, x_n]\), \(p\ge 0\) over \(\R^n\),
Krivine characterized systems of polynomial inequalities without solutions over \(\R^n\). (Positivstellensatz, cf. Farkas lemma)
Given \(f:\{0,1\}^n\to \R\) (given as coefficients in monomial basis up to degree \(\deg f\)), is \(f\ge 0\) or \(\exists x\in \{0,1}^n, f(x)<0\)? The number of coefficients is \(\le n^{\deg f}\). (Every monomial is actually a subset.) This is NP-hard for degree 2.
Max-cut: \[ \max cut(G) \le c \iff c - \sum_{\{i,j\}\in E(G)} (x_i-x_j)^2 \ge 0. \]
Given \(f\), the algorithm outputs either a short proof for \(f>0\) or an object ptends to be a collection of \(x\in \{0,1\}^n\).
Degree \(d\) SoS certificate for \(f\): \(\deg g_i\le \fc d2\), \[\forall x\in \{0,1\}^n, f(x) = \sumo iv g_i(x)^2.\] It can be the case that \(\deg g_i>\deg f\)! That would be true over \(\R\), but we are working over \(\{0,1\}^n\).
For degree 2, we can do this efficiently over \(\R\); this question is hard because we restrict to the hypercube.
If \(f\) has a degree \(d\) sos certificate, we can find degree-\(d\) certificate for \(f+2^{-n^d}\) in time \(n^{O(d)}\). (Can’t solve general convex problems exactly.)
Theorem. For all \(G\), there exists a degree-2 sos certificate, \(\max(f_G) - 0.878 f_G\). This estimates MAX-CUT up to \(0.878\).
Open question: if we replace 2 by 4, can we replace \(0.878\) by a larger constant? This would disprove unique games.
Theorem 5. \(f\) has degree-\(d\) sos certificate iff there exists positive semidefinite \(A\) such that \[\forall x\in \{0,1\}^n, f(x) = \an{(1,x)^{\ot d2}, A (1,x)^{\ot \fc d2}}.\] (Proof. \(A\) has a square root.)
Theorem. If \(f\ge 0\), then it has a degree \(2n\) sos certificate.
Proof. \(f=g^2, g=\sqrt f\), \(\deg g\le n\), or \(f(x) = \sum_{y\in \{0,1\}^n} (\sqrt{f(y)}\one_y(x))^2\).
Proof (finding sos certificates). \(f(x) = \an{(1,x)^{\ot d/2}, F(1,x)^{\ot d/2}}\). Find \(A\), \[ A-T\in W = \set{Q}{\an{(1,x)^{\ot d/2}, Q(1,x)^{\ot d/2}}\equiv 0\text{ over }\{0,1\}^n}. \] Look at \(F+W\cap\)cone.
We just need an efficient separation oracle.
Cheeger: Let \(G\) be a \(d\)-regular graph and \(L_G=I-\rc dA\) be its Laplacian, and \(\la\) be the second smallest eigenvalue. Then \[\la \ge \Om(\ph(G)^2).\]
The second smallest eigenvalue of \(L_{C_n}\) is \(O\prc{n^2}\). (Proof: compute.) This shows Cheeger is tight, as we have \[ \la = \Te\prc{n^2}, \quad \ph(G) = \Te\prc{n}. \]
Maxcut: We showed that \[maxcut (G)\le 1-\ep \implies (\forall \deg \mu=2, \wt{\EE_{\mu}} f_G(x) \le 1-\Om(\ep^2)).\]
To show tightness up to constant, show that for \(G=C_n\) there is \(\mu\): \[\begin{align} maxcut(C_n) &\le 1-\rc n =:1- \ep\\ \wt{\EE_\mu} f_G(x) &= 1-\Te\prc{n^2}. \end{align}\] Proof. Let \(n=2k+1\). Define \(u, v, w, X, \mu\) as follows. \[\begin{align} u=(\om^{jk})_{j=0}^{n-1} &= u+iw\\ X&=vv^T+ww^T\\ \wt{\EE_\mu} x &= \rc2 \one\\ \wt{\EE_{\mu}} xx^T &= \rc 4 \one \one^T + \rc 4 X \end{align}\](We can find a degree-2 pseudodistibution whenever \(\wt{\EE_\mu} xx^T - (\wt{\EE_\mu} x)(\wt{\EE_{\mu}}x)^T\) is psd and the diagonal of \(\wt{\EE_\mu} xx^T\) equals \(\wt{\EE_\mu}x\). (Do we want it to be in \([0,1]\)?)) Calculation: \[ \wt{\EE_{\mu}} f_G(x) = \rc 4 \sum |u_i-u_j|^2 = n\pa{1-\Te\prc{n^2}}. \] (Working backwards, setting \(X=vv^T+ww^T\) and then finding what the values of \(v,w\) should be, we want \(\sum_{(i,j)\in E}|u_i-u_j|^2\) to be large. This motivates hops of \(\om^k\). Calculations: \(\E(x_i-x_j)^2 = \E[1-\fc{2v_iv_j+2w_iw_j}4]\).)
\[\begin{align} \al_{GW} &= \min_{0\le x\le 1} \fc{\cos^{-1}(1-2x)}{\pi x}\\ &=\min_{-1\le \rh\le 1} \fc{2\cos^{-1}\rh}{(1-\rh)\pi}\\ \rh_{GW} &= \amin_{-1\le \rh\le 1} \fc{2\cos^{-1}\rh}{(1-\rh)\pi} \end{align}\] Theorem (Tightness of GW): For every \(\ep>0\) there is \(G\) and \(\mu\) such that \[\begin{align} maxcut(G) &\le \al_{GW} x_{GW} + \ep\\ \wt{\EE_{\mu}} f_G(x) &\ge x_{GW}. \end{align}\]Proof. Feige-Schechtman graph: Connect up points on the sphere if \(\an{v,w}\le \rh_{GW}+\ep\). (Later reduce to a discrete graph by sampling.) We have variables \(\{X_v\}_{v\in \R^d}\), \(X_v = \rc 2 + \fc{\an{v,g}}2\), \(\Cov(X_u,X_v) = \E \an{u,g}\an{v,g} = \an{u,v} \le -\rh_{GW} + \ep\) if \(\an{u,v}\le \rh\).
Theorem. It is NP-hard to solve \(\text{Max-3XOR}_{\rc 2+\de, 1-\ep}\).
There are reductions \(3\SAT\stackrel{\wt O(n)}{\le}\text{LabelCover} \stackrel{O(n)}\le \text{3XOR}\).
The fraction of constraints satisfied by 3XOR problem \(x_i+x_j+x_k = a_{ijk}\) is \[ f_\psi = \rc 2 + \rc{2|\psi|}\sum_{\{i,j,k\}\in \psi} (1-a_{ijk})(1-2x_i)(1-2x_j)(1-2x_k). \]
Theorem (Grigoriev). For every \(\ep>0\), for large enough \(n\), there is an instance \(\psi\) of Max-3XOR such that
Intuition: Unlike Gaussian elimintion, the sos algorithm cannot distinguish between a perfectly and \(1-o(1)\) satisfiable system.
Proof. Take a random \((m,n)\) bipartite graph with left-degree 3. Left is constraints, right is variables.
Completeness: (cf. expander codes.) Let \(\chi_S = \prod_{i\in S}(1-2x_i)\). Idea: make pseudistribution “uniform” subject to constraints.
We define \(\wt{\EE_{\mu}}\chi_S\) for \(|S|\le \ep n\). If \(\wt \E \chi_S\), \(\wt \E \chi_T\) have been defined and \(|S\triangle T|\le d=\ep n\), set \(\wt \E \chi_{S\triangle T} = (\wt \E \chi_S)(\wt \E \chi_T)\). Set remaining \(\wt \E \chi_S=0\).
A degree \(d\) derivation is a set that is reached after some number of steps, each set on the way being \(\le d\).
WHP the graph is an expander. If we have degree \(d\) derivations for \(\sum_{i\in S} x_i\equiv 0\) and \(\sum_{i\in S} x_i\equiv 1\), then we get a degree \(2d\) derivtion of \(\sum_{i\in \phi} x_i=1\). Impossible—similar to proof of expander codes: In order for \(T_t\) to be \(\bigopl_{l\in T_t}\Ga(l) = \phi\), \(T_t\) is large; take the first large \(T_i\) in the derivation, it will have large neighbor set.
Show \(\deg p\le \fc d2\implies \wt \E p^2\ge 0\) by Fourier expansion. Break \(|S|\le \fc d2\) into equivalence classes based on \(\E[\chi_{S\triangle T}]\ne 0\). For \(p_i=\sum_{S\in C_i} p_S\chi_S\), \[ \wt \E p_i^2 = \sum_i (\sum_S p_S\wt{\E} x_{S\triangle S_i})^2\ge 0.\]
Exercise 11. DO this!
To reduce from Max 3SAT \((\fc 78+\ep, 1)\), convert \(a_{\ell_i}x_i \vee a_{\ell_j}x_j \vee a_{\ell_k}x_k=1\) to \(x_i+x_j+x_k \equiv a_{\ell_i}+a_{\ell_j} + a_{\ell_k}\).
A nice \(V\in \F_2^L\) is one such that every \(u\in V^{\perp}\bs \{0\}\) has \(\ve{u}_0\ge 3\). A nice subspace predicate is one such that there exists nice \(V\), \(P(x)=1\iff x\in V\).
Theorem (SoS hardness for nice-subspace CSP, SoS PCP). Let \(k,\ep>0\) be given. There exist \(\be = 2^k\prc{\ep^2}\), \(c=\poly\prc{\be}\) such that there is an instance \(\psi\) of Max-P for [\(k\)-variate predicate \(P\) with \(\le 2k\) satisfying assignments] on \(n\gg \rc c\) variables and \(m=\be n\) constraints such that
Read the rest (15-21)
Theorem. Let \(G\) be a \(d\)-regular graph with vertex set \([n]\) and \(\mu:B^n\to \R\) be a degree-4 pseudo-distribution. Then \[ \ph(G) = \min_{x\in B^n} \fc{f_G}{\fc dn |x|(n-|x|)} \le O(\sqrt{\ln n}) \ph_\mu(G). \] There is a polynomial time algorithm that given \(G\) and \(\mu\), finds \(x\) such that \(\ph(G)\le O(\sqrt{\ln n})\ph_\mu(G,x)\).
Proof.
Let \(d(i,j)=\wt{\EE_{\mu}} (x_i-x_j)^2\). For degree 4, we have \(d(i,j) + d(j,k) \ge d(i,k)\).
This gives a lower bound on \(\E \max_{i,j\in [n]} X_j-X_i\ge \fc{\Phi(k)}n\).
Lemma (chaining). \[\Phi(k+1) \ge \Phi(k) + \E |M| - O(n) \max_{i\in [n], j\in H^{k+1}(i)} \pa{\E(X_i-X_j)^2}^{\rc 2}.\]We want \(\min_{x\in B^n}f\); degree \(d\) SoS finds \(\min_{\deg \mu = d} \wt{\EE_{\mu}} f\).
Often the global minimum is at a single point, but pseudodistribution pretends to be high entropy over nonexistent elements, “supported on unicorns”.
Replace \(B^n\) with \(\Om\subeq \R^n\) defined by polynomial inequalities \(A=\{f_1\ge 0,\ldots, f_m\ge 0\}\). Questions:
A degree \(l\) SoS proof is \(g=\sum_{S\subeq [n]} p_S \prod_{i\in S} f_i\), where \(p_S\) is SoS, each \(\deg(p_S \prod_{i\in S} f_i)\le l\). Write \(A\vdash_l \{g\ge 0\}\). (There is a SoS proof of degree \(d\) of \(g\ge 0\) from \(A\).)
Theorem (Positivstellensatz). Every \(A\) is either feasible, or \(A\vdash_l\{-1\ge 0\}\) for some \(l\in \N\).
SoS has inference rules for addition, multiplication (add degrees), transitivity (multiply degrees), and substitution (multiply with degree of substituted \(H\)).
Lemma. Let \(\mu\) have finite support, \(\wt{\EE_{\mu}} 1=1\). \(\mu\) is degree \(d\) pd iff \(\wt{\EE_{\mu}} ((1,x)^{\ot d/2})((1,x)^{\ot d/2})^T\) is psd.
Proof. Writing \(p = \an{v,(1,x)^{\ot d/2}}\), \(\wt{\EE_{\mu}} p^2 = \wt{\EE_{\mu}} \an{v,(1,x)^{\ot d/2}}^2\).
Write \(\mu\vDash_l A\) (satisfy \(A=\{f_i\}\) at degree \(l\)) if for all \(S\subeq [m]\), every SoS with \(\deg h + \sum_{i\in S} \max(\deg f_i,l)\le d\) satisfies \(\wt \E_\mu h \prod_{i\in S}f_i\ge 0\) for all SoS’s \(h\). (Ex. for \(A=\{f\ge 0\}\), take \(S=\{f\}\).)
Question: how does this mesh with \(B^n\) definition?
Theorem (Duality). Suppose \(\ve{x}^2\le M\) is in \(A\). For all \(d\in \N\), \(f\in \R[x]_{\le d}\), either
Proof. Consider 2 cases.
Think of \(\vdash\) as a proof, and \(\mu \vDash\) as saying \(\mu\) is a model.
Lemma
Theorem (SoS algorithm).
Planted clique: Take \(G(n,\rc 2)\), add a random \(\om\)-clique.
Whp the max clique of \(G(n,\rc 2)\) is of size \(c\ln(n)\), so for \(\Om(\ln n)\) size cliques there is quasipoly algorithm.
Theorem (SoS hardness). Let \(d(n)\) be a function. There is \(c\) such that for \(\om = n^{\rc 2 - c\pf{d}{\ln n}^{\rc 2}}\) and large enough \(n\), wp \(1-\rc n\) over \(G\sim G(n,\rc 2)\), there is a degree \(d\) pseudodistribution \(\mu\) over \(B^n\) that is consistent with \(x_ix_j=0\) for every \(i\nsim j\) in \(G\) and such that \(\wt{\EE_{\mu}} \sumo in x_i\ge \om\).
In contrast with Max-3XOR, in planted clique, each variable has a weak but GLOBAL effect on all other variables.
Definition. A degree \(d\) pseudoexpectation map is \(G\mapsto \mu_G, \deg (\mu_G)=d\). It is pseudocalibrated with respect to \(f\) if \[\sum_{G\sim G(n,\rc 2)} \wt{\EE_{G}} f_G = \EE_{(G,x)\sim G(n,\rc 2,\om)}f_G(x).\] (\(x\) is the characteristic vector of the planted clique.)
(Q: Why is the LHS \(G(n,\rc2)\) rather than \(G(n,\rc 2,\om)\)?)
Example: If \(f_G(x)=x_{17}\), then a first estimate could be \(\wt E x_{17}=\fc{\om}n\). But if we want to get higher degree functions, ex. covariance with degree, right, then we should not each \(\wt E x_i\) to \(\fc{\om}n\).
Proof (Sketch). Let \(\mu(G,x) = \mu_{planted}(G,x)_{\deg_x\le d, \deg_G\le \tau}\). Show it still satisfies normalization, etc. Hrd part is psd-ness.
Finish
Tensor decomposition with and without SoS
Plan
Problem
Application
Algorithm (high-level)
Estimate \(\sum a_i^{\ot 3}\) from samples
Random contraction algorithm (Jeinrich)
Consider the orthogonal case first. Note that the most difficult case is if all the norms are the same (if they are all different, we can use SVD).
… (see notebook)
Decompose random gaussian along 2 directions. If correlation large ,more likely to recover \(e_1\).
Claim. \(\E_g \ve{(I^{\ot 2}\ot g^T)X} \le \sqrt{\ln d} \si\) where \(\si = \max\{\ve{X}_{13,2},\ve{X}_{1,23}\}\).
This is a linear function of \(g\), we can write it as in the concentration inequality.
\[\begin{align} (I^{\ot 2} \ot g^T)X &=\sum g_i \ub{(I^{\ot 2} \ot e_i^T)X}{A_i}\\ \ve{X} &=\ve{X^TX}^{\rc 2} = \ve{XX^T}^{\rc 2}\\ \sum A_iA_i^T &= X_{3,12}^T X_{3,12}\\ \sum A_i^TA_i &= X_{1,23}^T X_{1,23} \end{align}\](check the indices).
Davis-Kahan: \(\ve{A-aa^T}\le o(1) \ve{a}^2\) implies that the top eigenvector of \(A\) is \(o(1)\) close to \(a\). So top eigenvector of \((I\ot I\ot a^T)X\) is close to \(a\).
Theorem. Let \(a_1,\ldots, a_n\in R^d\), \(\ve{a_i}=1\). Suppose \(\sum a_i a_i^T \preceq \si I\) (\(\si\) is overcompleteness), \(\max_{i\ne j} |\an{a_i,a_j}|\le \rh\). Then, given \(\sumo ih a_i^{\ot3}\), can recover vectors close to \(a_1,\ldots, a_n\) in polytime whenever \(\rh \si^2=o(1)\).
E.g., \(\si=d^{0.1}\), \(\rh = d^{0.3}\). This is satisfied by \(d^{1.1}\) random unit vectors, or \(n=d^{1.24}, (d^{.24},d^{-.5})\).
This algorithm can be poly in \(d\) and \(n\).
Open question: Is this true for \(\rh\si <o(1)\)? This would imply for \(d^{1.5}\) random vectors. (Though there is another argument that can give up to \(d^{1.5}\).) (Maybe a \(-\ep\) in exponent.)
Algorithm: given \(M_3\),
Use SoS to find tensor which we can run random contraction on, living in higher-dimensional space.
Under conditions of theorem, let \(b_i=a_i^{\ot 2}\), can show that random contraction works for \(X=\sum b_i^{\ot 3}\). (Show \(\ve{X}_{12,3}\le O(1)\) if \(\rh\si^2\ll 1\).) Recover the \(b_i\)’s, then recover \(a_i\)’s. But we don’t get \(b_i^{\ot 3}\), we just get \(a_i^{\ot 3}\). SoS: given \(a_i^{\ot 3}\) it’s computing \(b_i^{\ot 3}\). Find pseudodistribution matching 3rd moment and outputs 6th moments.
The intended \(\mu\) is uniform over \(a_1,\ldots, a_n\). \(\wt \EE_{\mu} x^{\ot 3} = \rc n \sum a_i^{\ot 3}\) and \(\E x^{\ot 6} = \rc n \sum a_i^{\ot 6} = \rc X\).
Philosophy: first prove statement for distributions, then verify that the steps fall in SoS proof system.8
When are 3rd moments enough for overcomplete tensors, \(n\gg d\)? Robustness against noise in input tensor?
We use lower-degree moments, have better error robustness, and develop new improved analyses of classical tensor decomposition algorithms.
SoS a priori not practical but we can extract practical algorithms
Dream up higher-degree moments and apply classical algorithms.
Algorithm: Magic box lifts 3rd moments to 6th moment, \(M_3=\sum_i a_i^{\ot 3}\) to \(M_6=\sum_i a_i^{\ot 6}\). Then apply Jennrich to get \(a_i^{\ot 2}\).
It’s not even clear this is information theoretically possible!
Ideal implementation: find \(D\) over unit sphere subject to \(\EE_D x^{\ot 3} = \rc n M_3\), then use \(\EE_D x^{\ot 6}\). Claim is that this is \(\approx \rc n M_6\).
Key inequality: by niceness of vectors, \(a_1,\ldots, a_n\) are approximate global maximizers. For all \(x\in \bS^{d-1}\), \[\begin{align} P(x) &\le \max_{i\in [n]} \an{a_i,x} + O(\rh si^2).\\ 1 &\approx \EE_D \sumo in \an{a_i,x}^3\\ \EE_{D} P(x) &\ge 1-o(1). \end{align}\]Also close to uniform over \(a_i\).
Remaining questions:
SoS is slow. Instead find direct algorithm to fool Jennrich, \[ \sum_{ijk} \an{a_i,a_k}\an{a_j,a_k} (a_i\ot a_j) \ot (a_i\ot a_j) \ot a_k\approx \sumo in a_i^{\ot 5} = M_5. \]
Tensor structure to implement Jennrich in time \(O(d^{1+\om})\).
Open: 3 tensors with \(d^{1+\ep}\) generic components, \(d^{1.5+\ep}\) random components?
Tensor power: fewer guarantees. Does better in amount of time needed to reduce error.
There is another way to relax this kind of problem, by changing the values \(x_i\) could take from \(\pm1\) to vectors, like in Goemans-Williamson. We don’t consider this kind of relaxation here. (Though we can do GW here too…?)↩
There is another way to relax this kind of problem, by changing the values \(x_i\) could take from \(\pm1\) to vectors, like in Goemans-Williamson. We don’t consider this kind of relaxation here. (Though we can do GW here too…?)↩
Not really. I’m confused here: why don’t we factor through \((\R[x]/I)_{\le l}\) instead of \((\R[x]/I)_{\le l/2}\times (\R[x]/I)_{\le l/2}\)?↩


This is a sample shiny app illustrating a solution of the following problem.
Consider a graph with millions of nodes. These may be of two types U and P.
U nodes only connect to P nodes, if at all
P nodes only connect to U nodes
The weighing of all single connections is the same,
What is the distance between two U nodes where distance is defined as:
If the shortest path between two U nodes is via a single P node (i.e. they are both connected to the same P node) the distance is 1
If there is no path between two U nodes, the distance is 0
If the nodes to be checked are the same node the distance is defined as -1
The distance between two U nodes is always calculated based on the shortest path, meaning if U1 and U2 join directly to P1, they have a distance of one, moreover, if U2 and U3 join directly to P2, then the distance between U1 and U3 is 2, unless U1 and U3 both join directly to P3 (then it’s 1 at that is the shortest path). U4 might join directly to P4 and P5, and therefore the distance between U1 and U4 is 0 as they are not connected.
You can either enter your own graph data in the input box, or use the generator to create sample data.
There are five types of sample data graphs that can be calculated either a chain of u nodes, each connected to the next by one p node, or on of four random sample data sets where you can vary the level of connectivity.
The visualisation tab will show the network if there are fewer than 1000 nodes


Go is a wonderful language. But Go has gotchas.
Read the snippets, try to guess the output, and then click [Run] and [Discussion].


The Content team can approve or reject pending EventFeedback from this page. The feedback will not be visible to the Event owner before it is approved. The Event owner will not be able to see the username of the feedback authors. The feedback author can see when the feedback has been approved or rejected by returning to the feedback page.
{% if event_feedback_list %}
{% else %}
There is no feedback awaiting approval.
Cancel
{% endif %}