The Application of Legendre Multiwavelet Functions in Image Compression

Legendre multiwavelets are introduced. These functions can be designed in such a way that the properties of orthogonality, polynomial approximation, and symmetry hold at the same time. In this way, they can be effectively deployed in image compression.

Introduction
In recent years, the wavelets theory has played a significant role in signal processing, especially in image processing. These wavelets are mainly scalar, where there is only one scaling function. However, multiwavelets are based on more than one scaling function. Such growing interests in multiwavelets mainly stem from the following facts: (i) multiwavelets can simultaneously possess orthogonality, symmetry, and a high order of approximation for a given support of the scaling functions (this is not possible for any real valued scaler wavelets); and (ii) multiwavelets have produced promising results in the areas of image compression.
A multiwavelet system can provide perfect reconstruction while preserving length (orthogonality), good performance at the boundaries (via linear-phase symmetry), and a high order of approximation (vanishing moments). Thus, multiwavelets offer the possibility of superior performance for image processing applications, compared with scalar wavelets. In this paper, we use linear Legendre multiwavelets in image compression, and show its usefulness through actual examples.

Multiwavelets
As with scalar wavelets, multiwavelets are based on the concept of multiresolution analysis (MRA). The only difference is the number of scaling functions used to generate those functions. The standard multiresolution has one scaling function ϕ(t), which satisfies the following properties (Aboufadel & Schilicker, 1999;Martin & Bell, 2001, Burrus & Gopinath, 1998Daubechies, 1992).


The translates ϕ(t -k) are linearly independent and produce a basis for the subspace ϕ 1 (t),…, ϕ N (t).
In multiwavelets, the notion of MRA is used in the same way except that the basis for V 0 is generated by the translates of N different scaling functions ϕ 1 (t -k), ϕ 2 (t -k),…, ϕ N (t -k). As in the scalar case, the vector Φ(t) = [ϕ 1 (t),…, ϕ N (t)] T , satisfies the matrix dilation equation [k] is an N by N matrix of coefficients. There are also N wavelets ψ 1 (t),…,ψ N (t) satisfying the matrix wavelet equation The scaling functions ϕ 1 (t),…, ϕ N (t) are in V 0 whose basis is

  
In the case of orthonormal multiscaling functions, {ϕ i (t): 1 ≤ i ≤ N, k ∊ Z} is not just a Riesz basis, but is orthonormal, i.e., In scalar wavelets, this means that the sum of squares of low-pass filter coefficients equals unity, and the filter is orthogonal to its even translates.

Linear Legendre Multiwavelets
A pair of linear Legendre scaling functions ϕ 1 (x) and ϕ 2 (x) on [0,1] are introduced and depicted in Figure 1. The integer translates of ϕ 1 (x) together with the ones of ϕ 2 (x) span a subspace V 0 . Furthermore, the translates of 1/2 scaled version of ϕ 1 (x) and ϕ 2 (x) that span V 1 ⊃ V 0 are given by The two-scale relations for linear Legendre scaling functions should express each of ϕ 1 (x) and ϕ 2 (x) in terms of the four scaling functions ϕ i (2x) and ϕ i (2x -1), i = 1,2 (Udea & Lodha, 1995). We propose these relations to be Let ψ 1 (x) and ψ 2 (x) be wavelets on [0,1] defined based on the linear Legendre scaling functions. By using (1), ψ 1 (x) and ψ 2 (x) can be expressed in terms of ϕ i (2x) and ϕ i (2x -1), i = 1,2. The conditions of being orthonormal and vanishing moments help reduce the two-scale relation for linear Legendre multiwavelets as follows.

Preprocessing and sampling
Preprocessing aims to convert the given scalar input signal of length N to a sequence of two-dimensional vectors ν 0,k . This is used in the analysis algorithm as shown in Figure 2. Here, N is assumed to be a multiple of a power of 2, and therefore it even. The signal {X k } is taken to be a function x(.) which is observed at integer time points. If the preprocessing produces N two-dimensional vectors, it is said to be an oversampling scheme. If it produces N / 2 two-dimensional vectors, the result is a critical sampling. After the wavelet reconstruction step (synthesis), e.g., inverse DMWT, a postfilter is applied. Evidently, prefiltering, wavelet transform, inverse transform, and postfiltering should exactly recover the input signal.

Repeated Row Preprocessing: Oversampling Scheme
The obvious way to get two input rows from a given signal is to repeat the signal. Two identical rows go into the multifilter bank. It then begins oversampling of the data by a factor of two. Although, the usefulness of oversampling has been proven, it requires more calculations than critical sampling. Furthermore, in data compression applications, one intends to remove redundancy, not to increase it. In the case of one-dimensional signals the repeated row scheme is convenient to be implemented (Strela & Walden, 1998).

Image Compression Using Legendre Wavelets
The notions stated above were applied to compress a given image. In doing so, critical sampling was deployed on a well-known photo of Barbara. Initially preprocess all the rows (see Strela & Walden, 1998), which results in the picture shown in Figure 3. Then, preprocess all columns. The amount of data remains unchanged, since we use critical sampling. At the next step, perform the 2D-wavelet cascade. For linear Legendre multiwavelets, the multiwavelet filter bank is obtained as follow. From (3), we have where 0 2 is a 2×2 zero matrix. The two-channel matrix filter bank operates on two input data streams, filters them into four output data streams, and then, downsamples each of the results by a factor of two. After one step of the 2D multiwavelet cascade algorithm for linear Legendre with approximation preprocessing, the photo of Figure 5 appears. The pattern of image subbands is shown in Figure 6 (Sudhakar & Jayaraman, 2005). By comparing Figure 5 with Figure 6, it is seen that almost all information is in the block of G 1 G 1 . This reflects the fact that, for linear Legendre, one scaling function is symmetric while the other is anti-symmetric.    The next step is to quantize the components of the Legendre multiwavelet transform. Any values of the transform that are small in modulus will be converted to 0. The modified transform is then be converted to Huffman codes and the resulting bit stream is encoded. The produced file is markedly smaller than the original one.

Conclusion
The technique of using Legendre multiwavelets in image compression, as deployed in this paper, shows great advantages compared to the wavelet-based and even other multiwavelet-based methods. This is due to the fact that in a linear Legendre multiwavelet one scaling function is symmetric while the other one is anti-symmetric. In this way, it concentrates well on the image and excludes a tiny amount of details. Linear Legendre multiwavelets were used, but, the higher order Legendre multiwavelets can be employed (Rahbar, 2004).


Wearability Factors for Skin Interfaces

As interfaces progress beyond wearables and into intrinsic human augmentation, the human body has become an increasingly important topic in the field of HCI. Wearables already act as a new layer of functionality located on the body that leads us to rethink the convergence between technology and fashion, not just in terms of the ability to wear, but also in how devices interact with us. Already, several options for wearable technology have emerged in the form of clothing and accessories. However, by applying sensors and other computing devices directly onto the body surface, wearables could also be designed as skin interfaces. In this paper, we review the wearability factors impacting wearables as clothes and accessories in order to discuss them in the context of skin interfaces. We classify these wearability factors in terms of body aspects (location, body movements and body characteristics) and device aspects (weight, attachment methods, accessibility, interaction, aesthetics, conductors, insulation, device care, connection, communication, battery life). We discuss these factors in the context of two different example skin interfaces: a rigid board embedded into special effects makeup and skin-mounted soft materials connected to devices.

INTRODUCTION
Although academic research has embraced wearable computing for over two decades now, they have only recently emerged as commercial products from top tech companies such as Google and Apple, as well as from fashion industry icons like Nike and Adidas. Such progress indicates that wearables will become mainstream in the forthcoming years [47]. Advances in electronics, material science and biotechnology make it possible to embed technologies into fabrics [10,35] as well as use implantable devices and biosensors [50]. Smaller and more powerful electronics and smart tags are distributed around the body and powered by new forms of energy such as thinner batteries, solar panels, thermoelectrics, and human motion [6,8,23,52]. New materials are changing the fabric industry, producing textiles-as-a-chip [9] This is the case in the partnership between Google and Levi's , which resulted in a manufacturing process for creating conductive yarns that connect to tiny circuits capturing touch interactions [21]. Moreover, inspired by biological systems, new approaches have created fabrics with embedded living organisms acting as responsive structures. An example is bioLogic, fabricated with cells that respond to humidity by opening up when skin temperature is raised during exercise [68].
Spacesuits, an early example of wearable technology [25], inspired 1960s visions like "tomorrow's man" [17] who was encased in his gadgets. These ideas evolved into reality via early experiments by the likes of Steve Mann [36], Thad Starner [51], Steve Feiner [15] and others. Wearing technological gadgets is now established in the burgeoning wearables market [38,49]. Wearable technologies, however, shouldn't be limited to clothing and accessories. Placing technology on the skin and its appendages opens new possibilities for on-body devices; e.g., direct contact to skin can significantly improve biological sensing data. Unconventional on-body interaction locations, such as eyelashes, nails, lips, etc., can be utilized; the similarity between skin interfaces with beauty products (fake nails, eyelashes and hair extensions) and tattoos allow continuous usage as a body part, instead of feeling stuck with one smart jacket everyday. Another important psychological factor is that skin interfaces usually make strong attempts to endow new abilities to the human body or overcome the limitations of human body. Different from wearables, which constantly improve external systems, skin interfaces make the wearer's own body intelligent and augmented.
Skin and its appendages (i.e. hair and nails) are regenerative organs that play a crucial role for human beings as a protective barrier, a sensory input from the environment, a heat and moisture regulator and a part of the immune system [26]. Moreover, they have been manipulated using tattoos and beauty products since the earliest days of the human race [16]. Researchers are using nanomaterials for creating epidermal electronics that act as removable tattoos for health monitoring [30] and electronic skins that, in a similar way, are used as bandages [54]. 'Beauty Technology' is another skin interface approach that hides electronics into cosmetics and applies them directly to one's skin, fingernails, and hair. Example projects include conductive Makeup, Tech Nails, FX e-makeup, and Hairware [63].
Previous work has researched the wearability of wearables [18,31,58], but there is little work in the HCI area that addresses the wearability of skin interfaces. In this paper, we map wearability factors for wearables onto wearability factors for skin interfaces. While skin-worn devices share similar functions with wearables, the modality of skin brings with it different challenges for the hardware design, such as flexibility and stretchability with stable performance. Wearables are electronic devices placed in clothes, in accessories and on the skin. For the purpose of this analysis we use the term "wearables" when we talk about electronics embedded into clothes and accessories and "skin interfaces" when we refer to electronics placed on the skin and its appendages. Section 2 identifies previous work in skin interfaces and wearability. Section 3 presents the wearability factors of wearables mapped onto the wearability factors of skin interfaces. Section 4 discusses the design of two different example skin interfaces according to the wearability factors. The conclusion and ideas for future work are presented in the last section.  Figure.1 shows an on-body taxonomy [64] that classifies each technology by its location on the body surface. Technology can be on the body (such as wearables), inside the body (such as implants) and carried next to the body (such as smartphones). The main difference between smartphones and wearables is that the former often require your full attention, are carried and not worn, and are operated using both hands [44] . Wearables can be placed in clothes and accessories. Skin interfaces, the topic of this paper, can be placed on top of the body's surface i.e. skin, nails and hair.

BACKGROUND
Wearables are massively deployed in health and wellbeing [66]. When integrated into clothing, they can be considered as noninvasive. However, when located on the skin, they are not easily attachable for extracting bio data [57] . Temporary Transfer Tattoo [5] incorporates electrodes printed directly on the epidermis by dispersing carbon fiber segments within the tattoo ink. A true integration with wearables and an attractive way of hiding sensors becomes possible when these electrodes are designed as an artistic tattoo. The company MC10 is proposing smart sensing stickers for medicine, therapy and healthcare in a bandage-like device [37]. They print an electronic mesh onto a flexible thin plastic that is malleable and adapted to the human skin as a removable tattoo, and use it to read brain waves, heart, muscle tension, body temperature, motion, and even hydration levels. At CES 2016, L'Oreal in partnership with MC10 and PCH presented My UV Patch, a temporary tattoo with photosensitive dyes that changes color according to UV exposure [41].
Another approach in skin interfaces is the use of cosmetics. While research has improved their manufacturing process, the functionality of cosmetics has changed little over time. Beauty Technology adds new features to cosmetics by integrating electronic components [61]. In the arts field there are some efforts as well, e.g., dynamically illuminating the face with wearable illumination [71], placing LEDs close to the eyes simulating larger eyes [42] and acting as glowing eye shadow when the eyes are closed [11].
Skin interfaces have also been explored as devices for daily life interaction. One example for connecting skin interfaces to smartphones is NailO, an input device in the form of a nail sticker that works as a trackpad [28]. Hairware are conductive hair extensions that are connected to a circuit for sending messages with different hair touches [60]. iSkin is a capacitive and resistive sensor that can be used to answer a call or to create music [65].
Creating wearables requires a clear understanding of the body characteristics, human movements and interactions with objects and other humans. Several researchers have studied different factors affecting the wearability of wearables. Gemperle et al. defines wearability as the interaction that exists between the body and the wearable [18]. Their guidelines include placement, form language, human movement, proxemics, sizing, attachment, containment, weight, accessibility, thermal, interaction, aesthetics and long-term use. Gepperth states that the challenges of wearables are placement and integration, interaction, energy sources and user acceptance [19]. Dunne identified that the 'wearability' in wearable technology lies at the intersection between ubiquitous computing and functional clothing design, and are thermal, moisture, mobility, flexibility, durability, sizing and fit, and garment care [12]. In the subfield of skin interfaces, there are some researches who discuss ergonomic and usability considerations, mainly related to their own design projects. Such is the case of iSkin [65] whose authors, in developing their prototype, identified skin compatibility, locations, device types and form factors, visual customization, input, output, interfacing and processing, and materials. Other more detailed studies on the design of skin interfaces identify mechanisms and design strategies to create temporary transfer tattoos [30]. Also specific techniques for creating stretchable electronics emphasize the hardsoft materials integration and its dependence on the attached surface [14]. All these studies lead us to consider appropriating guidelines already identified in the design of wearables and analyze their intersection with skin interfaces.

WEARABLITY OF SKIN INTERFACES
A major challenge that wearables are facing today is to ensure that they are unobtrusive [48]. Inappropriate design will cause the user not to be able to access the device and complete their goals. Thus, a clear understanding of wearability could lead us to envision the interplay between the body and proximate devices.
In this section, we consider the wearability factors most used in the design of wearables based on the aforementioned works. We then discuss those factors in the context of skin interfaces and add novel factors unique to skin interfaces. Table 1 shows our resulting classification of the wearability factors of skin interfaces. We classified them into body aspects (location, body mechanics and body characteristics) and device aspects (attachment methods, weight, insulation, accessibility, interaction, aesthetics, device care and connection).

Location
On-body technologies include skin interfaces, wearables, implants and carried devices. A number of studies have investigated placement of wearables on the user body, exploring the effects of weight, size, and attachment method [18,31,58]. Gemperle [18] discussed three criteria for determining on-body placement for wearables: areas that 1) are relatively the same size across adults; 2) have low movement/flexibility even when the body is in motion, and 3) are larger in surface area. Knight [31] proposed energy cost, biomechanical (musculoskeletal loading), posture, movement, and discomfort as factors to consider. On the basis that skin interfaces share all these considerations, there are several distinctions: • skin interfaces can be placed on the skin, hair and nails, also underneath clothing.
• clothing and accessories might cover and interfere with the function and interaction of skin interfaces.
• with soft and ideally stretchy electronics, skin interfaces can utilize large and curvilinear areas, such as the back, hand back, and neck.

Body Movement
Body movements can be classified into micro movements (eye movement, facial expression and the contraction\expansion of muscles) and macro movements (bipedal locomotion, arm/hand movement and gestures) [1]. Freedom of body movements can be accomplished by designing around the more active moving areas or limiting the size of devices to follow the movements [18]. Unlike wearables, micro movements and strain on skin surfaces can cause skin interfaces to fall off. Thus, areas that have relatively stiff surface, such as forehead, chest and hand back, are optimal locations compared to arm joint, neck and finger. In cases where the designs are placed on frequently moving body parts, a thin, light, flexible structure would be necessary and special attachment methods are recommended (see section 3.5).

Body Characteristics
Several studies showed that physical body characteristics must be taken into account in the design of wearables. Knight [31] suggests that individual differences such are age, sex, body size, weight, morphology and strength could interfere with a wearable. Dunne [12] points out that the body regulates its temperature below 100F. Thus, a thermal management (layering and venting) must be considered in the design of warm wearables, and a thermal energy harvester in contact with the skin may feel cold. Skin interfaces must also accommodate this constraint, mainly done by using insulation. Another physiological regulation that she addresses is moisture. Wearables and skin interfaces both need to consider sweat and oil from the skin in their designs. Moreover, direct contact to the body surface introduces extra design limitations and considerations regards to skin characteristics, such as wrinkles, skin hair, pimples, irritation, etc.
In the later discussion on attachment method and insulation, we address these issues with skin-friendly materials and lightweight device design.

Weight
Gemperle [18] proposed three guidelines on the weight of a reliable and comfortable wearable: minimizing weights; placing them on the stomach, waist and hip area; placing them as close to the body's center of gravity as possible. As to skin interfaces, the maximum weight is more restricted as heavy devices can fall off quite easily. In accordance with attachment methods, weight tolerance generally increases when using mechanically-mounted methods as opposed to gluing. Minimizing the weight of the skin interface can be achieved by placing the bigger electronics, such as the microcontroller, Bluetooth, batteries, etc. in a wearable and connecting them to the skin interface.

Attachment Method
Skin is a soft, stretchy surface that secretes oil and sweat: "Globally, detachment can occur in either tension or compression because of interfacial cracks that initiate at the edges or the central regions of the devices" [30]. A thin, light, soft skin interface is preferred for stable contact when structures need to be glued onto skin. For larger devices, solutions for makeup prosthetics and external cosmetics (fake nails, hair extension) are useful references. Skin-friendly adhesives, latex and silicone products are well explored in FX makeup areas already. However, wearers should still need to consult with physicians before applying devices onto allergic skins, sensitive skins of children, elder people and wounded areas (although smart bandages may evolve into a variety of skin interface [54]).

Accessibility
Accessibility is necessary to consider in proper design of wearable devices. Visual, tactile, auditory and kinesthetic accesses on the body allow the wearer to interact with their wearables [4]. Depending on application, skin interfaces can also be placed underneath clothing and accessories to work as sensing and monitoring devices, although interaction may be compromised.

Interaction
Interactions with wearables and skin interfaces are usually achieved by the use of sensors and actuators. The interface acts as an actuator when it emits sounds, lights up, changes temperature, vibrates, etc. For example, LED Eyelashes [39] used two strings of LEDs on the lower eyelids to simulate bigger eyes. Skin interfaces could also be a sensor: Kramer developed a keypad that senses touch via stretchable electronics [31]. Moreover, skin interfaces are always functioning as both input and output devices at the same time. The LEDs on Kinisi [55] are an example of actuators, where light patterns are activated on the skin and hair.
In the same project, the sensors on the skin detect blinking, smiling, raising an eyebrow and closing lips.

Aesthetics
Aesthetics and cultural/social acceptance are crucial factors in designing on-body devices, since wearable technology provides potentially off-putting technical functions as well as novel aesthetic elements in personal appearance. This formed the wellknown reaction to Google Glass [20]. More specifically, Toney [58] made an e-suit to explore wearable technology in business scenarios. Profita [46] explored on-body interaction in public and evaluated the societal perceptions from a third-party perspective. Skin interfaces, especially those exposed to other people, have to be considered similarly to cosmetics products. Kao [28] uses stickers to cover the devices on her nails while Vega [63] proposed and explored the concept of Beauty Technology.

Conductors
To support robust circuitry on the skin surface, conductors are required to be soft and stretchable, while maintaining their conductive property. The materials and fabrication processes used for on-skin electronics fall into the following categories:

Miniature rigid electronics
Typically, in the realm of wearable computing and interfaces, many researchers have attached miniature electronics directly on body surfaces to study on-body interactions. NailO [28], Twinkle Nails [62] and NailDisplay [53] both employed miniature electronics on the fingernails, which serve as a hard surface for attachment; Commercial devices such as Myo [56] and Ring [34] utilize on-body accessories as wearable platforms for gesture recognition; LED Eyelashes [42] attaches SMD LEDs to thin wires for digital makeup effects. Even though these wearable devices have many important capabilities and managed to function as computing systems on body surfaces, their stiff, inorganic structures mismatch with the soft, curvilinear properties of our skin. It is hard to establish long-term use and robust electrical contact without irritating the skin or causing discomfort during body movements.

Conductive ink, glue
Conductive ink & glue have been widely used to explore creating thin, flexible electronic circuitry on skin in design and research. They normally contain powdered or flaked conductive components, such as carbon, silver and silver chloride. Typical characteristics of conductive glues and inks to consider in soft circuits are: resistance, applicable substrates, and application methods. Carbon based inks and glues have much higher resistance compared with Ag\Ag-AgCl based materials with the same concentration. Conductive materials are applied directly on the skin surface or on an interlayer. Bare Conductive [3] introduced their carbon-based electronic paint as a non-toxic material for direct on-skin attachment: Humanthesizer [24] transform a dancer's body into a music controller by applying conductive ink; INKO [13] is an iPad sensing keyboard and cover with conductive ink tattooed onto leather. Silver-based conductive inks and glues cannot be applied on the skin directly, so a layer of thin, soft, flexible substrate is often required for skin attachment, such as silicone and PDMS.

Conductive soft materials
Another approach for flexibility and stretchability on skin is utilizing conductive soft materials, such as stretchy fabrics and elastic polymers. In Cheng's work [7], a pressure-based textile sensor is attached to the user's cheek to detect tongue movements; Plex [69] used conductive textiles for flexible finger sensors. The use of conductive elastic polymers, especially cPDMS and AgPDMS, also provided a compelling potential solution for onskin soft electronics configuration. iSkin [65] presented an onskin touch sensor using conductive cPDMS as the electrodes for capacitive and resistive sensing. The underlying technology has been long in development [39,40], and progresses rapidly.

Conductive cosmetics
Since cosmetics are already an additional layer on the skin, researchers can integrate cosmetics with conductive materials and have them perform as part of the electronics. Vega [63] uses chemically metalized eyelashes that maintain their natural black color while being conductive. In another work, she also customizes conductive stickers that look like eyeliner make up.

Metal (Epidermal Electronics System)
Material scientists and device engineers from University of Illinois have developed epidermal electronics with metal traces that are ultra-thin and can be applied on skin directly. To achieve stretchy moduli and conformal contact, the metal traces are designed in the form of filamentary serpentine nanoribbons. The fabrication of EES devices is normally executed at nano-scale, including photolithography, to match the stiffness and thickness of epidermis [14,30].

Liquid-embedded elastomer electronics
Another novel technology to construct soft electronics is using a thin elastomer film embedded with microchannels of conductive liquid. This method essentially replaced solid circuit traces with conductive liquid for deformable material properties. R.J Wood's group in Harvard has developed functional skin interfaces for curvature sensing [32], a stretchable keypad [33] based on conductive liquid (eGaIn), and elastomers that are extremely soft and stretchable. Yong-Lae Park [43] described the design and fabrication of elastomer electronics with multiple layers.

Insulation
Since our body's conductivity varies on a daily bases and across each individual, a layer of insulation between skin and electronic components is crucial for reliable performance. Also, avoiding electronics directly in contact with skin could be important for safety, in case of allergy or oxidization. Another benefit of insulation is preventing the skin from being burnt by electronically-generated heat. Skin-friendly materials are highly preferred among the choices of insulation materials, such as silicone used in prosthetics makeups (Smooth-On, Dragon Skin), skin-safe fabrics (LessEMF), cosmetics products (nail gel for device mounting [54,62]), etc.

Device Care
Unlike implanted devices, skin interfaces are required to be able to be taken down and reapplied. Even though we have insulation and attachment methods for each design, soft materials are not as easy to apply onto skin as wearing a watch. Some of the devices are temporary and can only be applied once, like digital temporary tattoos [22,30]; Cosmetic-based devices take longer to apply each time due to the glue and covering layers. Additionally, their designs vary among individuals, due to different skin color, nail lengths, facial structure, etc. [42,55,59,62]. Each wearing duration depends on the attachment and insulation methods: embedding inside nail gel could last for weeks, while functional on-skin tattoos only survive for 3 to 5 days. Body sweat, shower/bath, scratches, and body movements are major causes of devices falling off or even breaking.

Connection
Due to the unconventional electrodes (such as conductive fabric and ink) and soft substrate used in on-skin circuity, its electronic connections cannot adopt common Tin based solders (melting temperature at 180~190℃) or rigid mechanical assembly connectors. Several approaches to this problem are presented: lower-temperature solders (138℃) [67], conductive adhesives [27,45], and direct contact with physical pressure [65]. Most of the connection breaks happen at the interconnection between soft (on-skin components) and rigid (external components, wearables) parts, since the rigid parts are not adapted to flexible structures. Advanced fabrication technologies for flex circuits can avoid hard chip packages and use thinned bare-die silicon chips (which become flexible), wire-bonding or flip-chip-bonding them to a flexible circuit board before covering all electronics in soft encapsulant [2]. Printed electronics, which are steadily improving, also promise to be a good match for flexible circuitry [29].

Communication
Although there are examples of fully integrated skin interfaces that contain a battery and wireless communication developed through nanotechnology [30], in the area of HCI, we still have to balance between device size and functionality. Passive wireless systems like RFID/NFC could be embedded into on-skin electronics easily [22,55,62], depending on antenna constraints and attainable Q. Kao [28] managed to shrink her device down to the size of a fingernail with battery and BLE communication, however NailO is still thick and bulky for daily use. Most researchers choose to connect skin interfaces to a wearable, which can contain more computing capacity and less constrained communication systems, either wireless or wired [65,70].

Battery Life
Even though most wearable devices use ultra-low power components, they still need to be charged frequently. Rechargeable Li-Po batteries are widely used and can be fabricated into a variety of sizes and shapes. Thin-film batteries are developed in a flat form, thus are suitable for skin interfaces. However, the smaller the battery is, the lower its capacity tends to be. Alternatively to frequent charging, we can also consider disposable solutions (like temporary tattoos), which on the other hand might introduce environmental issues. Energy harvesting takes energy from external sources including kinetic (locomotion, vibration, rotation, etc. converted usually magnetically, electrostatically, or piezelectrically), light (solar cells), heat (thermoelectrics), and even radio waves (rectannas or resonators). The drawback to energy harvesting is that it needs sufficient excitation from the environment and often yields little power or requires large deployment area, volume, or mass.

SkinSense
SkinSense turns skin into an input/output skin interface using capacitive sensing (Microchip, MTCH6102) that lights up a tattoo via surface mounted LEDs wired with flexible, conductive ink sealed in silicone packages. SkinSense communicates via Bluetooth to a computer whenever the device is touched. Figure 2 shows SkinSense with its components.
Its sensing interface has three layers: the electrode layer is realized by conductive ink (Bare Conductive), and is encapsulated by two layers of thin silicone (SmoothOn Ecoflex 0030). The bottom layer of silicone functions as an insulation substrate while the top layer seals the electrodes for stable performance. SkinSense can be located directly on the hand using without interfering with natural gestures and body movements, while also making the LEDs visible. The sensing interface is connected to a rigid PCB embedded inside a bracelet through 40 AWG magnet wires. The tattoo interface weighs around five grams. The attachment method used was latex-free eyelash glue.

Carnival Mask
Carnival Mask is an input/output skin interface developed for creating interactive face painting. During a Halloween event, we combined face painting and electronics embedded into FX makeup to create 300 masks with LEDs that reacted to music beats. Makeup artists attached them to the skin, and different designs on the face were applied. The location selected for this was the forehead, as it is a large, flat and somewhat rigid area for gluing the device and making it visible. Depending on the particular design and time needed to install the mask, we use two different attachment methods: eyelash glue that dries faster and attaches the device firmly to the skin and silicone glue that dries slower but smoothes the edges of the device touching the skin. We used free-latex and special effects makeup tested for skin in order to make sure our devices were attached safely. The silicone (Dragon Skin Silicone Rubber) hemispherical container has a hollow pocket inside for insulating the electronics, which comprised a miniature rigid PCB (from Pixmob) with a RGB LED and IR receiver. The LED was controlled with preprogrammed lighting effects based on a transmitted IR signal. A 3V coin battery can be mounted on the backside of our PCB and runs the device for around 5 hours with active intervals of 10-15 seconds, lighting for 2 seconds each time. During the Halloween event, we designed and cast Carnival Mask silicone balls with glitter, neon pigments and snow stickers. Combined with face painting, our makeup artist achieved a variety of designs with different aesthetics. Figure 3 shows one Carnival Mask with the LEDs activated.

DISCUSSION
We developed two prototypes to apply our wearability factors in different design goals. Carnival Masks are face decorations that generate interactive lighting patterns. The devices are big (3cm diameter) and self-contained with all the electronics inside. SkinSense is an digital tattoo with capacitive touch sensing and embedded LEDs . The on-skin part of SkinSense is soft and thin, because its rigid electronic parts, including microcontroller board and battery, are carried inside the bracelet wearable. Carnival Masks are designed for creative face painting, thus we decorated the silicone container with glitter, face paint, stickers, and silicone pigments, which also helped to hide the electronics. SkinSense, on the other hand, attempts to look like a real temporary tattoo and its fabrication focuses on a thin and flexible structure. We located the Carnival Masks device on the forehead to best exhibit the visual effects, and the forehead is more stiff than other parts of the face. SkinSense was located on the back of the hand so it can be easily touched. In both cases, we used platinum-cured silicone rubbers mixed in 1A:1B parts for insulating the electronics, and latex-free eyelash glue and silicone glue for attachment.

CONCLUSION
This paper has identified the most common factors reported on wearability of wearables and analyzed them also in terms of skin interfaces. We classified the wearability factors in body aspects and device aspects. This work aims to provide a set of broad guidelines for skin interface designers. Future projects will also explore nanotechnology-based electronics on skin and study design guidelines to be followed in the development of skin interfaces at scale. We also will develop usability tests to discover new challenges in user acceptance of these devices in daily life routines.
Skin interfaces present new challenges for developing technology on the body surface. This involves the miniaturization of electronics and the development of novel materials; creating seamless devices that integrate with the body by embedding technology into beauty products such as skin prosthetics, makeup, hair extensions and fake nails; and understanding the skin properties, structure and functionality for interfacing it with different devices. This offers possibilities for creating novel interactions. New, more accurate data could be sensed due to the devices' contact with the body. Micro movements could be amplified and unconscious behaviors such as a hair stroke or touching the face could trigger different devices. In the same way that the wearables industry is integrating fashion practices in their development, we envision new partnerships between the technology industry and skin professionals such as prosthesis experts, tattooists and makeup artists.


Transforming Dependency Structures to Logical Forms for Semantic Parsing

The strongly typed syntax of grammar formalisms such as CCG, TAG, LFG and HPSG offers a synchronous framework for deriving syntactic structures and semantic logical forms. In contrast—partly due to the lack of a strong type system—dependency structures are easy to annotate and have become a widely used form of syntactic analysis for many languages. However, the lack of a type system makes a formal mechanism for deriving logical forms from dependency structures challenging. We address this by introducing a robust system based on the lambda calculus for deriving neo-Davidsonian logical forms from dependency trees. These logical forms are then used for semantic parsing of natural language to Freebase. Experiments on the Free917 and Web-Questions datasets show that our representation is superior to the original dependency trees and that it outperforms a CCG-based representation on this task. Compared to prior work, we obtain the strongest result to date on Free917 and competitive results on WebQuestions.

Introduction
Semantic parsers map sentences onto logical forms that can be used to query databases (Zettlemoyer and Collins, 2005;Wong and Mooney, 2006), instruct robots (Chen and Mooney, 2011), extract information (Krishnamurthy and Mitchell, 2012), or describe visual scenes (Matuszek et al., 2012). Current systems accomplish this by learning task-specific grammars (Berant et al., 2013), by using strongly-typed CCG grammars (Reddy et al., 2014), or by eschewing the use of a grammar entirely (Yih et al., 2015).  In recent years, there have been significant advances in developing fast and accurate dependency parsers for many languages (McDonald et al., 2005;Nivre et al., 2007;Martins et al., 2013, inter alia). Motivated by the desire to carry these advances over to semantic parsing tasks, we present a robust method for mapping dependency trees to logical forms that represent underlying predicate-argument structures. 1 We empirically validate the utility of these logical forms for question answering from databases. Since our approach uses dependency trees as input, we hypothesize that it will generalize better to domains that are well covered by dependency parsers than methods that induce semantic grammars from scratch.
The system that maps a dependency tree to its logical form (henceforth DEPLAMBDA) is illustrated in Figure 1. First, the dependency tree is binarized via an obliqueness hierarchy to give an s-expression that describes the application of functions to pairs of arguments. Each node in this s-expression is then substituted for a lambda-calculus expression and the relabeled s-expression is beta-reduced to give the logical form in Figure 1(c). Since dependency syntax does not have an associated type theory, we introduce a type system that assigns a single type to all constituents, thus avoiding the need for type checking (Section 2). DEPLAMBDA uses this system to generate robust logical forms, even when the dependency structure does not mirror predicate-argument relationships in constructions such as conjunctions, prepositional phrases, relative clauses, and wh-questions (Section 3).
These ungrounded logical forms (Kwiatkowski et al., 2013;Reddy et al., 2014;Krishnamurthy and Mitchell, 2015) are used for question answering against Freebase, by passing them as input to GRAPHPARSER (Reddy et al., 2014), a system that learns to map logical predicates to Freebase, resulting in grounded Freebase queries (Section 4). We show that our approach achieves state-of-the-art performance on the Free917 dataset and competitive performance on the WebQuestions dataset, whereas building the Freebase queries directly from dependency trees gives significantly lower performance. Finally, we show that our approach outperforms a directly comparable method that generates ungrounded logical forms using CCG. Details of our experimental setup and results are presented in Section 5 and Section 6, respectively.

Logical Forms
We use a version of the lambda calculus with three base types: individuals (Ind), events (Event), and truth values (Bool). Roughly speaking individuals are introduced by nouns, events are introduced by verbs, and whole sentences are functions onto truth values. For types A and B, we use A × B to denote the product type, while A → B denotes the type of functions mapping elements of A to elements of B. We will make extensive use of variables of type Ind × Event. For any variable x of type Ind × Event, we use x = (x a , x e ) to denote the pair of variables x a (of type Ind) and x e (of type Event). Here, the subscript denotes the projections · a : Ind× Event → Ind and · e : Ind × Event → Event.
An important constraint on the lambda calculus system is as follows: All natural language con-stituents have a lambda-calculus expression of type Ind × Event → Bool.
A "constituent" in this definition is either a single word, or an s-expression.
S-expressions are defined formally in the next section; examples are (dobj acquired Pixar) and (nsubj (dobj acquired Pixar) Disney).
Essentially, s-expressions are binarized dependency trees, which include an ordering over the different dependencies to a head (in the above the dobj modifier is combined before the nsubj modifier).
Some examples of lambda-calculus expressions for single words (lexical entries) are as follows: acquired ⇒ λx. acquired(x e ) Disney ⇒ λy. Disney(y a ) Pixar ⇒ λz. Pixar(z a ) An example for a full sentence is as follows: Disney acquired Pixar ⇒ λx. ∃yz. acquired(x e ) ∧ Disney(y a ) ∧ Pixar(z a ) ∧ arg 1 (x e , y a ) ∧ arg 2 (x e , z a ) This is a neo-Davidsonian style of analysis. Verbs such as acquired make use of event variables such as x e , whereas nouns such as Disney make use of individual variables such as y a .
The restriction that all expressions are of type Ind × Event → Bool simplifies the type system considerably. While it leads to difficulty with some linguistic constructions-see Section 3.3 for some examples-we believe the simplicity and robustness of the resulting system outweighs these concerns. It also leads to some spurious variables that are bound by lambdas or existentials, but which do not appear as arguments of any predicate: for example in the above analysis for Disney acquired Pixar, the variables x a , y e and z e are unused. However these "spurious" variables are easily identified and discarded.
An important motivation for having variables of type Ind × Event is that a single lexical item sometimes makes use of both types of variables. For example, the noun phrase president in 2009 has semantics λx. ∃y. president(x a ) ∧ president event(x e ) ∧ arg 1 (x e , x a ) ∧ 2009(y a ) ∧ prep.in(x e , y a ) In this example president introduces the predicates president, corresponding to an individual, and president event, corresponding to an event; essentially a presidency event that may have various properties. This follows the structure of Freebase closely: Freebase contains an individual corresponding to Barack Obama, with a president property, as well as an event corresponding to the Obama presidency, with various properties such as a start and end date, a location, and so on. The entry for president is then Note that proper nouns do not introduce an event predicate, as can be seen from the entries for Disney and Pixar above.

Dependency Structures to Logical Forms
We now describe the system used to map dependency structures to logical forms. We first give an overview of the approach, then go into detail about various linguistic constructions.

An Overview of the Approach
The transformation of a dependency tree to its logical form is accomplished through a series of three steps: binarization, substitution, and composition. Below, we outline these steps, with some additional remarks.

Binarization.
A dependency tree is mapped to an s-expression (borrowing terminology from Lisp). For example, Disney acquired Pixar has the s-expression (nsubj (dobj acquired Pixar) Disney) Formally, an s-expression has the form (exp1 exp2 exp3), where exp1 is a dependency label, and both exp2 and exp3 are either (1) a word such as acquired ; or (2) an s-expression such as (dobj acquired Pixar).
We refer to the process of mapping a dependency tree to an s-expression as binarization, as it involves an ordering of modifiers to a particular head, similar to binarization of a context-free parse tree.
Substitution. Each symbol (word or label) in the s-expression is assigned a lambda expression. In our running example we have the following assignments: Composition. Beta-reduction is used to compose the lambda-expression terms to compute the final semantics for the input sentence. In this step expressions of the form (exp1 exp2 exp3) are interpreted as function exp1 being applied to arguments exp2 and exp3. For example, (dobj acquired Pixar) receives the following expression after composition: Obliqueness Hierarchy. The binarization stage requires a strict ordering on the different modifiers to each head in a dependency parse. For example, in (nsubj (dobj acquired Pixar) Disney), the dobj is attached before the nsubj. The ordering is very similar to the obliqueness hierarchy in syntactic formalisms such as HPSG (Pollard and Sag, 1994).
Type for Dependency Labels. Recall from Section 2 that every s-expression subtree receive a logical form of type η = Ind × Event → Bool. It follows that in any s-expression (exp1 exp2 exp3), exp1 has type η → (η → η), exp2 and exp3 both have type η, and the full expression has type η. Since each labeled dependency relation (e.g., nsubj, dobj, partmod) is associated with exp1 in connecting two s-expression subtrees, dependency labels always receive expressions of type η → (η → η).
Mirroring Dependency Structure. Whenever a dependency label receives an expression of the form where rel is a logical relation, the composition operation builds a structure that essentially mirrors the original dependency structure. For example nsubj and dobj receive expressions of this form, with rel = arg 1 and rel = arg 2 , respectively; the final lambda expression for Disney acquired Pixar is This structure is isomorphic to the original dependency structure: there are variables x e , y a and z a corresponding to acquired, Disney and Pixar, respectively; and the sub-expressions arg 1 (x e , y a ) and arg 2 (x e , z a ) correspond to the dependencies acquired → Disney and acquired → Pixar. By default we assume that the predicate argument structure is isomorphic to the dependency structure 129 and many dependency labels receive a semantics of the form shown in (1). However, there are a number of important exceptions. As one example, the dependency label partmod receives semantics with arg 1 (x e , z a ) in place of the arg 1 (z e , x a ) in (1). This reverses the dependency direction to capture the predicate-argument structure of reduced relative constructions such as a company acquired by Disney.
Post-processing. We apply three post-processing steps-simple inferences over lambda-calculus expressions-to the derived logical forms. These relate to the handling of prepositions, coordination and control and are described and motivated in more detail under the respective headings below.

Analysis of Some Linguistic Constructions
In this section we describe in detail how various linguistic constructions not covered by the rule in (1)prepositional phrases, conjunction, relative clauses, and Wh questions-are handled in the formalism. 2 Prepositional Phrases. Prepositional phrase modifiers to nouns and verbs have similar s-expressions: (prep president (pobj in 2009)) (prep acquired (pobj in 2009)) The following entries are used in these examples: where the entries for prep and pobj simply mirror the original dependency structure with prep modifying the event variable z e .
The semantics for acquired in 2009 is as follows: The system contains 32 binarization rules (e.g., rules for obliqueness hierarchy and identifying traces) and 46 substitution rules (i.e., rules for dependency labels and parts of speech). The rules can be found at http://github.com/ sivareddyg/deplambda. We replace in(p e ) ∧ prep(x e , p e ) ∧ pobj(p e , y a ) by prep.in(x e , y a ) as a post-processing step, effectively collapsing out the p variable while replacing the prep and pobj dependencies by a single dependency, prep.in. The final semantics are then as follows: In practice this step is easily achieved by identifying variables (in this case p e ) participating in prep and pobj relations. It would be tempting to achieve this step within the lambda calculus expressions themselves, but we have found the post-processing step to be more robust to parsing errors and corner cases in the usage of the prep and pobj dependency labels.
Conjunctions. First consider a simple case of NPconjunction, Bill and Dave founded HP, whose s-expression is as follows: (nsubj (dobj founded HP) (conj-np (cc Bill and) Dave)) We make use of the following entries: The sentence Bill and Dave founded HP then receives the following semantics: Note how the x variable occurs in two subexpressions: coord(x, y, z), and arg 1 (e e , x a ). It can be interpreted as a variable that conjoins variables y and z together. In particular, we introduce a post-processing step where the subexpression coord(x, y, z) ∧ arg 1 (e e , x a ) is replaced with arg 1 (e e , y a ) ∧ arg 1 (e e , z a ), and the x variable is removed. The resulting expression is as follows: VP-coordination is treated in a very similar way. Consider the sentence Eminem signed to Interscope and discovered 50 Cent. This has the following s-expression: (nsubj (conj-vp (cc s-to-I and) d-50) Eminem) where s-to-I refers to the VP signed to Interscope, and d-50 refers to the VP discovered 50 Cent. The lambda-calculus expression for conj-vp is identical to the expression for conj-np: The logical form for the full sentence is then where we use s to I(y) and d 50(z) as shorthand for the lambda-calculus expressions for the two VPs.
After post-processing this is simplified to Other types of coordination, such as sentencelevel coordination and PP coordination, are handled with the same mechanism. All coordination dependency labels have the same semantics as conj-np and conj-vp. The only reason for having distinct dependency labels for different types of coordination is that different labels appear in different positions in the obliqueness hierarchy. This is important for getting the correct scope for different forms of conjunction. For instance, the following s-expression for the Eminem example would lead to an incorrect semantics:

(conj-vp (nsubj (cc s-to-I and) Eminem) d-50)
This s-expression is not possible under the obliqueness hierarchy, which places nsubj modifiers to a verb after conj-vp modifiers.
We realize that this treatment of conjunction is quite naive in comparison to that on offer in CCG. However, given the crude analysis of conjunction in dependency syntax, a more refined treatment is beyond the scope of the current approach.
Relative Clauses. Our treatment of relative clauses is closely related to the mechanism for traces described by Moortgat (1988;1991); see also Carpenter (1998) and Pereira (1990). Consider the NP Apple which Jobs founded with s-expression: Note that the s-expression has been augmented to include a variable f in dobj position, with (BIND f ...) binding this variable at the clause level. These annotations are added using a set of heuristic rules over the original dependency parse tree.
The BIND operation is interpreted in the following way. If we have an expression of the form where f is a variable and g is an expression that includes f , this is converted to with the expression EQ(z) substituted for f . EQ(z)(z ) is true iff z and z are equal (refer to the same entity). In addition we assume the following entries: ∧ arg 1 (x e , y a ) ∧ arg 2 (x e , z a ) and Apple which Jobs founded has semantics Note that this latter expression can be simplified, by elimination of the z variable, to Wh Questions. Wh questions are handled using the BIND-mechanism described in the previous section. As one example, the s-expression for Who did Jim marry is as follows: (wh-dobj (BIND f (nsubj (aux (dobj marry f ) did) Jim)) who) We assume the following lambda expressions: It can be verified that this gives the final logical form ∧ arg 1 (y e , z a ) ∧ arg 2 (y e , x a ) Note that the predicate TARGET is applied to the variable that is the focus of the question. A similar treatment is used for cases with the wh-element in subject position (e.g., who married Jim) or where the wh-element is extracted from a prepositional phrase (e.g., who was Jim married to).

Comparison to CCG
In this section we discuss some differences between our approach and CCG-based approaches for mapping sentences to logical forms. Although our focus is on CCG, the arguments are similar for other formalisms that use the lambda calculus in conjunction with a generative grammar, such as HPSG and LFG, or approaches based on context-free grammars.
Our approach differs in two important (and related) respects from CCG: (1) all constituents in our approach have the same semantic type (Ind × Event → Bool); (2) our formalism does not make the argument/adjunct distinction, instead essentially treating all modifiers to a given head as adjuncts.
As an example, consider the analysis of Disney acquired Pixar within CCG. In this case acquired would be assigned the following CCG lexical entry: Note the explicit arguments corresponding to the subject and object of this transitive verb (f 1 and f 2 , respectively). An intransitive verb such as sleeps would be assigned an entry with a single functional argument corresponding to the subject (f 1 ): In contrast, the entries in our system for these two verbs are simply λx. acquired(x e ) and λx. sleeps(x e ). The two forms are similar, have the same semantic type, and do not include variables such as f 1 and f 2 for the subject and object.
The advantage of our approach is that it is robust, and relatively simple, in that a strict grammar that enforces type checking is not required. However, there are challenges in handling some linguistic constructions. A simple example is passive verbs. In our formalism, the passive form of acquired has the form λx. acquired.pass(x e ), distinct from its active form λx. acquired(x e ). The sentence Pixar was acquired is then assigned the logical form λx. ∃y. acquired.pass(x e ) ∧ Pixar(y a ) ∧ arg 1 (x e , y a ). Modifying our approach to give the same logical forms for active and passive forms would require a significant extension of our approach. In contrast, in CCG the lexical entry for the passive form of acquired can directly specify the mapping between subject position and the arg 2 : S\NP ⇒ λf 2 x. ∃z. acquired(x) ∧ f 2 (z) ∧ arg 2 (x, z) As another example, correct handling of object and subject control verbs is challenging in the singletype system: for example, in the analysis for John persuaded Jim to acquire Apple, the CCG analysis would have an entry for persuaded that explicitly takes three arguments (in this case John, Jim, and to acquire Apple) and assigns Jim as both the direct object of persuaded and as the subject of acquire. In our approach the subject relationship to acquire is instead recovered in a post-processing step, based on the lexical identity of persuaded.

Semantic Parsing as Graph Matching
We next describe how the ungrounded logical forms from the previous section are mapped to a fully grounded semantic representation that can be used for question answering against Freebase. Following Reddy et al. (2014), we treat this mapping as a graph matching problem, but instead of deriving ungrounded graphs from CCG-based logical forms, we use the dependency-based logical forms from the previous sections. To learn the mapping to Freebase, we rely on manually assembled question-answer pairs. For each training question, we first find the set of oracle grounded graphs-Freebase subgraphs which when executed yield the correct answer-derivable from the question logical form. These oracle graphs are then used to train a structured perceptron model.

Ungrounded Graphs
We follow Reddy et al. (2014) and first convert logical forms to their corresponding ungrounded graphs. Figure 2(a) shows an example for What is the name of the company which Disney acquired in 2006?. Predicates corresponding to resolved entities (Disney(y a ) and 2006(v a )) become entity nodes (rectangles), whereas remaining entity predicates (name(w a ) and company(x a )) become entity nodes (w a and x a ), connected to entity type nodes (name and company; rounded rectangles). The TARGET(w a ) node (diamond) connects to the entity node whose denotation corresponds to the answer to the question.

Grounded Graphs
The ungrounded graphs are grounded to Freebase subgraphs by mapping entity nodes, entity-entity  edges and entity type nodes in the ungrounded graph to Freebase entities, relations and types, respectively. While Reddy et al. (2014) assume that the ungrounded graphs are isomorphic to their corresponding Freebase subgraph, at least 15% of the examples in our development set do not satisfy this property. For example, the ungrounded graph in Figure 2(a) is not isomorphic to the Freebase subgraph in Figure 2(b), making it impossible to derive the correct grounded graph from the ungrounded one by a direct mapping. To account for such structural mismatch, we introduce two simple transformation operations.
CONTRACT. The CONTRACT operation takes a pair of entity nodes connected by an edge and merges them into a single node. For example, in Figure 2(a) the entity nodes w a and x a are connected by an edge via the event w e . After applying the CONTRACT operation to nodes w a and x a , they are merged. Note how in Figure 2(b) all the nodes attached to w a attach to the node x a after this operation. The contracted graph is now isomorphic to its Freebase subgraph.
EXPAND. Parse errors may lead to ungrounded graphs with disconnected components. For example, the ungrammatical question What to do Washington DC December? results in the lambda expression λz. ∃xyw. TARGET(x a ) ∧ do(z e ) ∧ arg 1 (z e , x a ) ∧ Washington DC(y a ) ∧ December(w a ). The corre-sponding ungrounded graph has three disconnected components (December and Washington DC, and the component with entity node x a linked to event z e ). In such cases, the graph is expanded by linking disconnected entity nodes to the event node with the largest edge degree. In the example above, this would add edges corresponding to the predicates dep(z e , y a ) ∧ dep(z e , w a ), where dep is the predicate introduced by the EXPAND operation when linking y a and w a to z e . When there is no existing event node in the graph, a dummy event node is introduced.

Learning
We use a linear model to map ungrounded to grounded graphs. The parameters of the model are learned from question-answer pairs. For example, the question What is the name of the company which Disney acquired in 2006? is paired with its answer {Pixar}. In line with most work on question answering against Freebase, we do not rely on annotated logical forms associated with the question for training, instead treating grounded graphs as latent variables.
Let q be a question, let u be an ungrounded graph for q and let g be a grounded graph formed by grounding the nodes and edges of u to the knowledge base K (throughout we use Freebase as the knowledge base). Following Reddy et al. (2014), we use beam search to find the highest scoring pair of ungrounded and grounded graphs (û,ĝ) under the model θ ∈ n : (û,ĝ) = arg max (u,g) θ · Φ(u, g, q, K) , where Φ(u, g, q, K) ∈ n denotes the features for the pair of ungrounded and grounded graphs. Note that for a given query there may be multiple ungrounded graphs, primarily due to the optional use of the CON-TRACT operation. 3 The feature function has access to the ungrounded and grounded graphs, to the question, as well as to the content of the knowledge base and the denotation |g| K (the denotation of a grounded graph is defined as the set of entities or attributes reachable at its TARGET node). See Section 5.3 for the features employed.
The model parameters are estimated with the averaged structured perceptron (Collins, 2002;Fre-und and Schapire, 1999). Given a training questionanswer pair (q, A), the update is: where (u + , g + ) denotes the pair of gold ungrounded and grounded graphs for q. Since we do not have direct access to these gold graphs, we instead rely on the set of oracle graphs, O K,A (q), as a proxy: where O K,A (q) is defined as the set of pairs (u, g) derivable from the question q, whose denotation |g| K has minimal F 1 -loss against the gold answer A. We find the oracle graphs for each question a priori by performing beam-search with a beam size of 10k and only use examples with oracle F 1 > 0.0 for training.

Experimental Setup
We next verify empirically that our proposed approach derives a useful logical compositional semantic representation from dependency syntax. Below, we give details on the evaluation datasets and baselines used for comparison. We also describe the model features and provide implementation details.

Training and Evaluation Datasets
We evaluated our approach on the Free917 (Cai and Yates, 2013) and WebQuestions (Berant et al., 2013) datasets. Free917 consists of 917 questions manually annotated with their Freebase query. We retrieved the answer to each question by executing its query on Freebase and ignore the query for all subsequent experiments. WebQuestions consists of 5810 questionanswer pairs. The standard train/test splits were used for both datasets, with Free917 containing 641 train and 276 test questions and WebQuestions containing 3030 train and 2780 test questions. For all our development experiments we tuned the models on held-out data consisting of 30% of the training questions, while for final testing we used the complete training data.

Baseline Models and Representations
In addition to the dependency-based semantic representation DEPLAMBDA (Section 3) and previous work on these datasets, we compare to three additional baseline representations outlined below. We use GRAPHPARSER 4 to map these representations to Freebase.
DEPTREE. In this baseline, an ungrounded graph is created directly from the original dependency tree. An event is created for each parent and its dependents in the tree. Each dependent is linked to this event with an edge labeled with its dependency relation, while the parent is linked to the event with an edge labeled arg 0 . If a word is a question word, an additional TARGET predicate is attached to its entity node.
SIMPLEGRAPH. This representation has a single event to which all entities in the question are connected by the predicate arg 1 . An additional TARGET node is connected to the event by the predicate arg 0 . This is similar to the template representation of Yao (2015) and Bast and Haussmann (2015). Note that this cannot represent any compositional structure.
CCGGRAPH. Finally, we compare to the CCGbased semantic representation of Reddy et al. (2014), adding the CONTRACT and EXPAND operations to increase its expressivity.

Implementation Details
Below are more details of our entity resolution model, the syntactic parser used, features in the grounding model and the beam search procedure.
Entity Resolution. For Free917, we follow prior work and resolve entities by string match against the entity lexicon provided with the dataset. For Web-Questions, we use eight handcrafted part-of-speech patterns to identify entity span candidates. We use the Stanford CoreNLP caseless tagger for part-of-speech tagging (Manning et al., 2014). For each candidate mention span, we retrieve the top 10 entities according to the Freebase API. 5 We then create a lattice in which the nodes correspond to mention-entity pairs, scored by their Freebase API scores, and the edges encode the fact that no joint assignment of entities to mentions can contain overlapping spans. Finally, we generate ungrounded graphs for the top 10 paths through the lattice and treat the final entity disambiguation as part of the semantic parsing problem. Syntactic Parsing. We recase the resolved entity mentions and run a case-sensitive second-order conditional random field part-of-speech tagger (Lafferty et al., 2001). The hypergraph parser of Zhang and McDonald (2014) is used for dependency parsing. The tagger and parser are both trained on the OntoNotes 5.0 corpus (Weischedel et al., 2011), with constituency trees converted to Stanford-style dependencies (De Marneffe and Manning, 2008). To derive the CCG-based representation, we use the output of the EasyCCG parser (Lewis and Steedman, 2014). Features. We use the features from Reddy et al. (2014), which include edge alignment and stem overlap between ungrounded and grounded graphs, and contextual features such as word and grounded relation pairs. In addition, we introduce a feature indicating the use of the CONTRACT operation: (Merged-SubEdge, HeadSubEdge, MergedIsEntity, HeadIsEntity). For example, in Figure 2 the edge between w a and x a is contracted to x a , resulting in the feature (name.arg 1 , name.prep.of, False, False). The EX-PAND operation is treated as a pre-processing step and no features are used to encode its use. Finally, the entity-lattice score is used as a real valued feature. Beam Search. We use beam search to infer the highest scoring graph pair for a question. The search operates over entity-entity edges and entity type nodes of each ungrounded graph. For an entity-entity  edge, we can ground the edge to a Freebase relation, contract the edge in either direction, or skip the edge.
For an entity type node, we can ground the node to a Freebase type, or skip the node. The order of traversal is based on the number of named entities connected to an edge. After an edge is grounded, the entity type nodes connected to it are grounded in turn, before the next edge is processed. To restrict the search, if two beam items correspond to the same grounded graph, the one with the lower score is discarded. A beam size of 100 was used in all experiments.

Experimental Results
We examine the different representations for question answering along two axes. First, we compare their expressiveness in terms of answer reachability assuming a perfect model. Second, we compare their performance with a learned model. Finally, we conduct a detailed error analysis of DEPLAMBDA, with a comparison to the errors made by CCGGRAPH. For WebQuestions evaluation is in terms of the average F 1 -score across questions, while for Free917, evaluation is in terms of exact answer accuracy. 6 6.1 Expressiveness of the Representations CCGGRAPH and DEPLAMBDA align much more closely to Freebase and achieve similar oracle F 1 scores with far less spurious ambiguity. SIMPLE-GRAPH, which cannot represent any compositional semantics, is competitive with these syntax-based representations. This might come as a surprise, but it simply reflects the fact that the dataset does not contain questions that require compositional reasoning.

Results on WebQuestions and Free917
We use the best settings on the development set in subsequent experiments, i.e., with CONTRACT and EXPAND enabled. Table 3 shows the results on the WebQuestions and Free917 test sets with additional entries for recent prior work on these datasets. The trend from the development set carries over and DE-PLAMBDA outperforms the other graph-based representations, while performing slightly below the stateof-the-art model of Yih et al. (2015) ("Y&C"), which uses a separately trained entity resolution system (Yang and Chang, 2015). When using the standard Freebase API ("FB API") for entity resolution, the performance of their model drops to 48.4% F 1 . On Free917, DEPLAMBDA outperforms all other representations by a wide margin and obtains the best result to date. Interestingly, DEPTREE outperforms SIMPLEGRAPH in this case. We attribute this to the small training set and larger lexical variation of Free917. The structural features of the graph-based representations seem highly beneficial in this case.

Error Analysis
We categorized 100 errors made by DEPLAMBDA (+C +E) on the WebQuestions development set. In 43 cases the correct answer is present in the beam,  but ranked below an incorrect answer (e.g., for where does volga river start, the annotated gold answer is Valdai Hills, which is ranked second, with Russia, Europe ranked first). In 35 cases, only a subset of the answer is predicted correctly (e.g, for what countries in the world speak german, the system predicts Germany from the human language.main country Freebase relation, whereas the gold relation human language.countries spoken in gives multiple countries). Together, these two categories correspond to roughly 80% of the errors. In 10 cases, the Freebase API fails to add the gold entity to the lattice (e.g., for who is blackwell, the correct blackwell entity was missing). Due to the way WebQuestions was crowdsourced, 9 questions have incorrect or incomplete gold annotations (e.g., what does each fold of us flag means is answered with USA). The remaining 3 cases are due to structural mismatch (e.g., in who is the new governor of florida 2011, the graph failed to connect the target node with both 2011 and Florida).
Due to the ungrammatical nature of WebQuestions, CCGGRAPH fails to produce ungrounded graphs for 4.5% of the complete development set, while DE-PLAMBDA is more robust with only 0.9% such errors. The CCG parser is restricted to produce a sentence tag as the final category in the syntactic derivation, which penalizes ungrammatical analyses (e.g., what victoria beckham kids names and what nestle owns). Examples where DEPLAMBDA fails due to parse errors, but CCGGRAPH succeed include when was blessed kateri born and where did anne frank live before the war. Note that the EXPAND operation mitigates some of these problems. While CCG is known for handling comparatives elegantly (e.g., who was sworn into office when john f kennedy was assassinated ), we do not have a special treatment for them in the semantic representation. Differences in syntactic parsing performance and the somewhat limited expressivity of the semantic representation are likely the reasons for CCGGRAPH's lower performance.

Related Work
There are two relevant strands of prior work: general purpose ungrounded semantics and grounded semantic parsing. The former have been studied on their own and as a component in tasks such as semantic parsing to knowledge bases (Kwiatkowski et al., 2013;Reddy et al., 2014;Choi et al., 2015;Krishnamurthy and Mitchell, 2015), sentence simplification (Narayan and Gardent, 2014), summarization (Liu et al., 2015), paraphrasing (Pavlick et al., 2015) and relation extraction (Rocktäschel et al., 2015). There are two ways of generating these representations: either relying on syntactic structure and producing the semantics post hoc, or generating it directly from text. We adopt the former approach, which was pioneered by Montague (1973) and is becoming increasingly attractive with the advent of accurate syntactic parsers.
There have been extensive studies on extracting semantics from syntactic representations such as LFG (Dalrymple et al., 1995), HPSG (Copestake et al., 2001;Copestake et al., 2005), TAG (Gardent and Kallmeyer, 2003;Joshi et al., 2007) and CCG (Baldridge and Kruijff, 2002;Bos et al., 2004;Steedman, 2012;Artzi et al., 2015). However, few have used dependency structures for this purpose. Debusmann et al. (2004) and Cimiano (2009) describe grammar-based conversions of dependencies to semantic representations, but do not validate them empirically. Stanovsky et al. (2016) use heuristics based on linguistic grounds to convert dependencies to proposition structures. Bédaride and Gardent (2011) propose a graph-rewriting technique to convert a graph built from dependency trees and semantic role structures to a first-order logical form, and present results on textual entailment. Our work, in contrast, assumes access only to dependency trees and offers an alternative method based on the lambda calculus, mimicking the structure of knowledge bases such as Freebase; we further present extensive empirical results on recent question-answering corpora.
Structural mismatch between the source semantic representation and the target application's representation is an inherent problem with approaches using general-purpose representations. Kwiatkowski et al. (2013) propose lambda-calculus operations to generate multiple type-equivalent expressions to handle this mismatch. In contrast, we use graph-transduction operations which are relatively easier to interpret. There is also growing work on converting syntactic structures to the target application's structure without going through an intermediate semantic representation, e.g., answer-sentence selection (Punyakanok et al., 2004;Heilman and Smith, 2010;Yao et al., 2013) and semantic parsing (Ge and Mooney, 2009;Poon, 2013;Parikh et al., 2015;Wang et al., 2015;Andreas and Klein, 2015).
A different paradigm is to directly parse the text into a grounded semantic representation. Typically, an over-generating grammar is used whose accepted parses are ranked (Zelle and Mooney, 1996;Zettlemoyer and Collins, 2005;Wong and Mooney, 2007;Kwiatkowksi et al., 2010;Liang et al., 2011;Berant et al., 2013;Flanigan et al., 2014;Groschwitz et al., 2015). In contrast, Bordes et al. (2014) and Dong et al. (2015) discard the notion of a target representation altogether and instead learn to rank potential answers to a given question by embedding questions and answers into the same vector space.

Conclusion
We have introduced a method for converting dependency structures to logical forms using the lambda calculus. A key idea of this work is the use of a single semantic type for every constituent of the dependency tree, which provides us with a robust way of compositionally deriving logical forms. The resulting representation is subsequently grounded to Freebase by learning from question-answer pairs. Empirically, the proposed representation was shown to be superior to the original dependency trees and more robust than logical forms derived from a CCG parser. 137


Blending Entropy: A Term for Addressing Information Density in Mediated Reality

The virtuality continuum describes the degrees of positive virtuality under the umbrella term mixed reality. Besides adding virtual information within a mixed environment, diminished reality aims at reducing real world information. Mann defined the term mediated reality (MR), which also considered diminished reality, but without the possibility to describe different degrees of fusion between a mixed and a diminished reality. That is why this work defines the new term blending entropy that captures the relations between a mixed and a diminished reality. The blending entropy is based on the information density of the mediated reality and the actual area the user has to comprehend, which is named perceptual frustum. We describe the blending entropy's twodimensional dependencies and detail important points in the blending entropy's space.

Definition of the Blending Entropy
In information theory, entropy is the average information within a message. In a MR, entropy can be viewed as the total of any information perceived by the user. The blending entropy is characterized by the entropy density and the perceptual frustum as illustrated in Figure 1.

Entropy Density
The information density or entropy density of an environment depends on the number and kind of physical objects and other visible information such as text, speech and haptic. The blending of the realities as defined in the virtuality continuum [4] fuses these entropy densities. Mann [2] called it MR if this mixture can lead to a diminished reality. There is no clear concept yet that defines the stages between diminished and mixed reality. That is why the new term blending entropy is introduced.
The lower limit of entropy density is a reality with an entropy density of zero. The user that interacts in such a void reality would receive no information or knowledge. This void reality could be an environment that just consists of emptiness. Decreasing the entropy density in relation to the equilibrated reality leads to the diminished reality (DR), which aims at removing real-world objects unnoticeably, i.e, reducing the entropy density of the real world.
The mixed reality comprises a larger entropy density than the equilibrated reality, since its goal is usually to add valuable information to the real-or virtual environment. The upper limit of the entropy density raises the uncertainty to a maximum, i.e., the environment only comprises independent and dense information. Such an environment can be accomplished by combining the real with (multiple) virtual realities into a multiversed reality. This definition of a multiversed reality motivates the importance of the term blending entropy. A multiversed reality would overwhelm the user's mind, i.e., the user would not be able to interact and reasonably process the information regardless of the size of the perceptual frustum. This is also called information overload and describes the overmuch processing of information [5]. This issue can be addressed via the blending entropy. For instance, minimizing the blending entropy circumvents an information overload, which can be achieved by reducing the entropy density or the perceptual frustum.

Perceptual Frustum
The perceptual frustum is similar to the field of regard, but the perceptual frustum is dynamic. It depends on the situation and the spatial distribution of the necessary information. If the user has to be aware of information distributed in a vast environment for a certain task or purpose, the perceptual frustum is large. When compressing the required information into a small space, the perceptual frustum is tiny.
The largest perceptual frustum is dubbed "god-like". It expresses a (theoretical) perceptual frustum that requires the user to concurrently access the total information of the world. In the work of Stafford et al. [6], a "god-like" user tagged navigation clues on a tabletop for a user that received them in the real world via augmented reality (AR). This work is close to but still different from a "god-like" perceptual frustum, since the "god-like" user just focused on a single person and it was not necessary to conceive the whole reality.
A perceptual frustum smaller than the "god-like" one is an omnidirectional perceptual frustum. The difference to "god-like" is that only the immediate environment of the virtual avatar or the person has to be comprehended and it is not necessary to consider multiple places of the world. Reducing the size of the perceptual frustum even further results in a tunnel-like perceptual frustum, which presents the necessary information right in front of the user. The ParaFrustum proposed by Sukan et al. [7] is a practicable example of a tunnel-like perceptual frustum. The ParaFrustum did not add further expert knowledge but it guided the user's view to the important parts of the current manual step.
The smallest (theoretical) perceptual frustum is a point-like spot. A scenario of a user that has to press a lone button depending on the augmentation would comply to a point-like perceptual frustum. A study by Marner et al. [3] is close to such a perceptual frustum. Here, the users pressed buttons sequentially according to spatial AR cues.

Blending Entropy
Finally, the blending entropy is the integration of the entropy density along the perceptual frustum. It holds the information of the joint realities that have to be perceived by the user. An increased or decreased blending entropy states that more or less information has to be processed by the user, respectively. The dotted line in Figure 1 illustrates the direction of raising blending entropy. In consequence, the largest blending entropy exists for a multiversed reality with a "god-like" perceptual frustum.

Equilibrated Reality
It is important to note that the origin of the blending entropy is defined by the entropies of the extrema of the virtuality continuum, i.e., the real or virtual environments. A blending entropy of zero is called equilibrated reality. Here, the entropy density and the perceptual frustum of either the purely real or the purely virtual environments is identical to the density and the frustum of the equilibrated reality. Therefore, the equilibrated reality shares the same perceptual frustum and information density than the unmixed environments but it still consists of a modulated environment. Thus, the equilibrated reality can simply be described as a modulated reality that shares the identical information complexity as the purely virtual or real environments.

Examples
One of the goals of this work is to link mixed and diminished reality within a single representation. Mixed reality typically describes techniques and applications that advance the reality. The extension of the realities occurs for both extrema of the virtuality continuum. On the one hand, physical objects enhance the virtual reality, which is known as augmented virtuality [4]. On the other hand, virtual objects are integrated into the real world, i.e., AR. In every case, additional knowledge or material complements the environment, which introduces a higher entropy density according to the new terms of this work.
Then reducing the entropy density connects the DR with the MR. An example for a DR application is the work of Korkalo et al. [1]. They concealed AR markers via DR from the real environment, i.e., the goal was to lower the entropy density. Diminishing contents in the environment, while keeping the same perceptual frustum realizes a lower blending entropy. A term that describes all degrees of blending entropy already exists and is named mediated reality [2]. The mediated reality consists of positive (MR) and negative (DR) entropy densities. The shortcoming of the original definition of the mediated reality is that there are no levels between mixed and diminished reality that describes the underlying relation. The definition of the entropy density allows such a classification.
The size of the blending entropy depends on the user as well as on the task. For example, the real environment of an industrial worker may already comprise a lot of information such as a console with different gauges, buttons and switches, i.e., the entropy density of the non-modulated environment is rather large. The worker, however, is accustomed to this environment and the specific tasks therein. This knowledge of the worker about the scene may produce a tunnel view, since the worker exactly knows where to look at, which minimizes complexity and creates an acceptable entropy for the worker. Consequently, the goal of a mediated reality can be the increase of the blending entropy and certain expert knowledge can be presented to the worker.
On the other hand, an untrained user that has not worked in such an environment before may be near an information overload. Because of the definition of the blending entropy, also a variety of options are available for this user. The mediated reality application could aim at reducing the blending entropy or, at least, produce a balanced blending entropy, i.e., stay at the equilibrated state. This can be achieved via an AR-guided reduction of the perceptual frustum [7], which narrows the user's perception (tunnel vision). Moreover, the entropy density can be minimized via DR, i.e., the application identifies the actual relevant parts and diminishes the unimportant parts. Diminishing parts that are close to the border of the perceptual frustum may also decrease the perceptual frustum, which would generate an even smaller blending entropy.

Conclusion
Most MR applications aim at modifying the blending entropy. For instance, some MR applications guide the user (lowering perceptual frustum) or present special information (higher entropy density), which can now be expressed via the blending entropy. Furthermore, the introduction of entropy density allowed to define a relationship between diminished and mixed reality.