Marianne Gaborieau
email: m.gaborieau@uws.edu.au

Leena Nebhani
email: leena.nebhani@kit.edu

Robert Graf
email: graf@mpip-mainz.mpg.de

Leonie Barner
email: leonie.barner@ict.fraunhofer.de.

Christopher Barner-Kowollik
email: christopher.barner-kowollik@kit.edu

Accessing Quantitative Degrees of Functionalization on Solid Substrates via Solid State NMR Spectroscopy

Keywords: Surface Functionalization, Quantitative Surface Analysis, Microspheres, Solid State Nuclear Magnetic Resonance Spectroscopy

The development of a solid-state nuclear magnetic resonance (NMR) method allowing the quantification of active sites (i.e. residual vinyl groups) accessible for chemical functionalization

Introduction

Functional polymeric microspheres have a high potential in medical and biomedical applications, such as drug delivery systems, in medical diagnostics or as contrast agents for X-ray imaging, as stationary phases for chromatography or for the detection of degradation products of chemical weapons. 1,2 Polymeric microspheres can be synthesized directly by heterogeneous polymerization techniques, e.g. emulsion and dispersion polymerization. 2 In addition, highly crosslinked mono-and narrow-disperse poly(divinyl benzene) microspheres can be synthesised via precipitation polymerization. 3 Microspheres synthesized via this technique are free of surfactants or stabilizers, instead they have residual vinyl groups on their surface. These residual vinyl groups open the possibility to graft a polymeric shell from or to an existing particle thus constituting an ideal synthetic handle for the preparation of core-shell microspheres and add further chemical functionalities to the particles. So far, a wide variety of techniques have been used to functionalize these microspheres, including controlled/'living' radical polymerization, [4][5][6][7][8] anionic ring-opening polymerization, 9 and highly orthogonal 'click' chemistry. [10][11][12][13] In order to exploit the full potential of these functional microspheres, it is extremely valuable to have information about the amount of accessible active sites (e.g. vinyl groups) on the surface of the particles. 1 Being highly crosslinked, these systems are insoluble and must be characterized in the gel state or the solid state.

To the best of our knowledge, the only characterization of poly(divinyl benzene)-based microspheres in terms of residual vinyl groups was so far carried out qualitatively by infrared spectroscopy (IR). 14 IR spectroscopy detects the residual vinyl groups through resonances at 1 600 and 990 cm -1 . Crosslinked polystyrene gels were characterized by high-resolution magic-angle spinning (HR-MAS) NMR spectroscopy. [15][16][17][18] Well-resolved 1 H and 13 C NMR spectra were obtained through efficient averaging of chain orientation along the axes between crosslinking points, allowing observing the chemical functionalization. However, it is unclear if the monomer units close to the crosslinking points are contributing to the observed signals due to their slower local dynamics. 16,17,19 Residual vinyl groups in poly(divinyl benzene)-based networks were analyzed by 13 C solid-state NMR spectroscopy and a wet chemical method, e.g. bromination. Noting that 13 C cross-polarization NMR is intrinsically not quantitative and that bromination is not quantitative because of side reactions and limited reagents accessibility to highly crosslinked regions, the authors concluded that no method is available yet for accurate, quantitative analysis of the residual vinyl groups. 17 In the current study, solid-state NMR spectroscopy was applied to polymer systems exhibiting homogeneous local mobility and homogeneous 1 H density, in which all sample parts contribute to the NMR signal without bias. The investigated microspheres are formed by distillation-precipitation polymerization, a process during which the polymer chains gradually precipitate onto the particles as they are polymerized; no stabilizer or further additives are used. Furthermore, their surface is (highly) porous, and they are best described as porous particles than as bulk particles limited by a sharp surface. We thus expect these pure poly(divinyl benzene) particles with homogenous chain topology to exhibit homogeneous local mobility and 1 H density across the whole sample in the solid state. Solid-state NMR spectroscopy is a versatile technique for the characterization of local structure and dynamics in polymers. 20-25 13 C solid-state NMR spectroscopy under magic-angle spinning (MAS) exhibits significantly higher resolution than 1 H solid-state NMR spectroscopy but lower sensitivity, because only 1% of the carbon nuclei are NMR-sensitive 13 C nuclei. The sensitivity issue of the common 13 C single-pulse excitation (SPE) NMR spectroscopy can be overcome by the use of crosspolarization (CP), which consists in transferring magnetization from 1 H to 13 C nuclei before recording 13 C signals. CP takes advantage of the higher natural abundance and faster relaxation of 1 H spins compared to 13 C ones. 26,27 It generally yields higher intensities, but is usually not quantitative because of different cross-polarization efficiencies and relaxation properties of the observed groups. Alternative pulse schemes have recently been proposed to record quantitative CP-MAS spectra. [28][29][30][31] Although these allow for more uniform CP dynamics, the measurements still suffer from adverse effects of the short relaxation properties or heterogeneous local mobility 29 or need extensive complementary measurements to correct the experimental CP intensity. 31 Lowering the temperature of the measurements may help reducing the local dynamic heterogeneity, but is experimentally more challenging. 32 In the current study, we present the development of a solid-state nuclear magnetic resonance (NMR) method allowing -for the first time -the quantification of active sites (i.e. residual vinyl groups) accessible for chemical functionalization on the surface of poly(divinyl benzene) (PDVB) microspheres.

Experimental Section

Materials. Technical-grade divinyl benzene (DVB55 containing 55 wt.-% divinyl benzene isomers, Aldrich and DVB80 containing 80 wt.-% divinyl benzene isomers, Aldrich), and n-butyl acrylate (99%, Fluka) was purified by percolation through a column of activated basic alumina. 2,2'-Azoisobutyronitrile (AIBN) was purchased from Aldrich and recrystallized twice from ethanol.

Cyanopropyl dithiobenzoate (CPDB) was synthesized according to the literature and its purity was confirmed by NMR spectroscopy. 33 Acetonitrile, dichloromethane, tetrahydrofuran, toluene, ethanol, methanol and acetone were all used as received.

Synthesis of PDVB80 and PDVB55 Microspheres via Distillation-Precipitation Polymerization.

PDVB80 and PDVB55 microspheres were synthesized by distillation-precipitation polymerization. 34 AIBN (0.092 g, 0.56 mmol, 2 wt.-% relative to the total monomer) and DVB80 or DVB55 (5 mL, 4.6 g, 35.35 mmol, 2.5 vol.-% relative to the reaction medium) was dissolved in 200 mL of acetonitrile in a 500 mL round-bottom flask, attached to a distillation assembly. The reaction mixture was heated from ambient temperature to boiling state by ramping the temperature gradually, until the solvent started distilling. As the solvent started distilling the initially homogenous reaction mixture turned milky white.

The reaction was stopped after half of the initial acetonitrile used in reaction mixture was collected in the receiving flask. After the polymerization was finished, the resulting PBVB80 or PDVB55 microspheres were separated by filtration through a 0.45 µm membrane, washed and re-suspended several times in toluene, THF, acetone and diethylether. The washing of the microspheres with toluene is very critical in this case as through washing with toluene it is possible to remove the residual monomer (see below). The microspheres were dried in a vacuum oven at 40 °C before characterization.

1.36 g of PDVB80 and 1.5 g of PDVB55 were obtained in 30% and 33% yield respectively. Synthesis of Hydroxy Functionalized PDVB80 and PDVB55 Microspheres. PDVB80 or PDVB55 microspheres (1.0 g) were suspended in dry THF (10 mL) in a dry 100 mL round-bottom flask for 2 h, and 0.1 g (2.6 mmol) of sodium borohydride was added. The suspension was cooled in a cold-water bath, and 0.376 g (2.6 mmol) of boron trifluoride diethyl etherate dissolved in 1 mL of THF was added dropwise to the suspension of microspheres. The temperature of the reaction suspension was maintained at 20 °C during the addition of BF3 and further for 3 h. At the end of this period, the flask was immersed in an ice bath, and 5 mL of cold water was slowly added to destroy any residual NaBH4. Subsequently, hydrogen peroxide (0.8 mL, 30% in water, 36 mmol) was slowly added to the reaction mixture. During the addition, the pH of the solution was maintained near pH = 8 by adding 3 mol • L -1 sodium hydroxide as needed. The final solution was filtered through a 0.45 µm membrane filter and washed with water (pH = 8) followed by methanol. The resulting microspheres were dried in a vacuum oven before characterization.

Grafting of n-Butyl Acrylate from Microspheres. All RAFT polymerizations were carried out in toluene. A solution of n-butyl acrylate (19.45 g), AIBN (0.0318 g, 3.7 • 10 -3 mol • L -1 ) and CPDB (0.15 g, 1.2 • 10 -2 mol • L -1 ) in toluene (35 mL) was prepared. 5 mL of the above solution was transferred into glass sample vials, each containing 300 mg of the microspheres. The sample vials were capped with rubber septa and deoxygenated by purging with nitrogen for 15 min. The samples were stirred with a magnetic bar at 80 °C. The polymerization was stopped after 3 h. The resulting grafted microspheres were isolated by filtration through a 0.45 µm membrane, washed several times with toluene and dichloromethane and dried in a vacuum oven overnight. Polymers from the solutions were collected to determine the molecular weight by SEC (Mn = 18 000 g • mol -1 , DM = 1.2 for PDVB80 and Mn = 19 000 g • mol -1 , DM = 1.2 for PDVB55).

Routine characterization. The morphology of the microspheres was established with a Hitachi S900 scanning electron microscope (SEM). The microspheres were dispersed in ethanol; a drop of this particle suspension was cast onto an electron microscope stub covered with a double-sided carbon tape which in turn is covered with a 5 mm glass cover slip. Samples were sputter-coated with chromium.

Electron micrographs of each sample were recorded at different magnifications. The particle size analysis from SEM micrograph was done for an average of 100 microspheres. Dn, Dw and U were calculated using the following equations:

Dn = Σ ni Di /Σ ni, Dw = Σ ni Di 4 / Σ ni Di 3 , U = Dn / Dw, where,
Dn is the number average diameter, Dw is the weight average diameter, and U is the polydispersity index. The Dn, Dw and U for PDVB80 microspheres is 1.51 µm, 1.51 µm and 1.00 respectively. The Dn, Dw and U for PDVB55 microspheres is 1.59 µm, 1.62 µm and 1.01 respectively. SEC measurements were performed on a Polymer Laboratories PL-GPC 50 Plus Integrated System, comprising an auto injector, a PLgel 5 μm bead-size guard column (50 • 7.5 mm), followed by three PLgel 5 m MixedC columns (300 • 7.5 mm), and a differential refractive index detector using THF as the eluent at 35 °C with a flow rate of 1 mL • min -1 . The SEC system was calibrated using polystyrene standards ranging from 160 to 6 • 10 6 g•mol -1 and linear poly(methyl methacrylate) standards ranging from 700 to 2 • 10 6 g•mol -1 . The resulting molecular weight distribution has been corrected using the Mark-Houwink relationship with K = 12.8 • 10 -5 dL • g -1 , α = 0.69 for poly(methyl methacrylate), K = 14.1 • 10 -5 dL • g -1 , α = 0.7 for polystyrene and K = 12.2 • 10 -5 dL • g -1 , α = 0.70 for poly(n-butyl acrylate). 23,35,36 An alternative SEC data treatment taking into account the possible influence of long-chain branching 24,[37][38][39] was outside the scope of the present study. The structure of the synthesized RAFT agent (CPDB) was confirmed by 1 H and 13 C solution-state NMR spectroscopy using a Bruker AM 400 spectrometer at Larmor frequencies of 400 MHz for 1 H nuclei and 100 MHz for 13 C nuclei. All samples were dissolved in CDCl3. The chemical shift scale is internally referenced to tetramethylsilane at 0.00 ppm.

The density of the PDVB microspheres in ethanol was determined using a density meter (DMA 5000 M, Anton Paar) at 293K. The particle density was found to be 1.82 g•cm -3 and 1.12 g•cm -3 for PDVB80 and PDVB55 microspheres, respectively. Solid-state NMR spectroscopy. 1 H MAS NMR spectroscopy was carried out on a Bruker Avance spectrometer (Bruker BioSpin, Germany) operating at a 1 H Larmor frequency of 700.13 MHz using a 2.5 mm solid-state MAS NMR probehead and a MAS rotational frequency of 30 kHz. Spectra were recorded using a 2.5 s 90° pulse, 16 transients and 5 s repetition delay. 13 C SPE-MAS NMR was carried out on a Bruker Avance spectrometer (Bruker BioSpin, Germany) operating at a 13 C Larmor frequency of 175 MHz using a 4 mm solid-state MAS NMR probehead and a MAS rotational frequency of 18 kHz. Spectra were recorded using a 4 s 90° pulse, 7062 transients (8064 transients for background) and 60 s repetition delay. 13 C CP-MAS NMR spectroscopy was carried out on a Bruker Avance spectrometer (Bruker BioSpin,

Germany) operating at a 13 C Larmor frequency of 125.75 MHz using a 2.5 mm solid-state MAS NMR probehead and a MAS rotational frequency of 18 kHz. Spectra were recorded using a 2.5 s 90° pulse, 2 ms contact time, 5 632 transients (1 024 transients for sample PDVB55 with variable contact time) and 5 s repetition delay. A detailed signal assignment 17,18,[START_REF]NMR spectra database of polymers[END_REF][START_REF]Spectral database for organic compounds SDBS[END_REF] is given in the Supporting Information section. Signals C and D were integrated over the ranges from 134 to 118 ppm and from 118 to 107.5 ppm, respectively.

Results and Discussion

The highly cross-linked PDVB microspheres employed in the current work were synthesized by distillation-precipitation polymerization. This technique only requires divinyl benzene (DVB) (which is also a cross-linker), a radical initiator, 2,2'-azoisobutyronitrile (AIBN), and a near Θ-solvent for DVB (acetonitrile). DVB is available in two technical grades, DVB55 and DVB80, which are composed of isomers of DVB and 3-and 4-ethylvinyl benzene. 3-and 4-ethylvinyl benzene have only one functional vinyl group and can for this reason not act as a cross-linker. Core microspheres therefore exhibit three types of structural aromatic units in the backbone of PDVB as depicted on the upper left hand side in Scheme 1 (note that isomeric structures are not included). One structure is based on a DVB unit where both vinyl groups have reacted; forming the cross-linked network, in the other case only one of the two vinyl groups has reacted, resulting in a residual vinyl group. In addition, a further structural entity results from the incorporated 3-or 4-ethylvinyl benzene. This structural entity therefore does not include a residual vinyl group, but an ethyl group. In the subsequent modification of the microspheres only the residual vinyl groups (also termed 'active' sites) are involved in the 'grafting from' polymerization and therefore a simplified representation of the core microspheres including only these active sites is depicted on the upper right side of Scheme 1. The capital letters next to the atoms in Scheme 1 are used for the complete chemical shift assignments in the 13 C NMR spectra (refer to the Supporting Information section, Table S1).

Scheme 1. Schematic representation of the core, hydroxylated and poly(n-butyl acrylate)-graftpoly(divinyl benzene) microspheres. Capital letters relate to the 13 C chemical shift assignment in Figure 2.

Residual vinyl groups, e.g. 'active' sites, are present within and on the surface of the particle.

However, residual vinyl groups in the centre of the particle are not easily accessible for reagents (e.g. reagents cannot easily diffuse to the centre of the microspheres due to the highly crosslinked nature of the particles), therefore not all of the 'active' sites will be able to take part in the subsequent modification of the particles via 'grafting from' polymerization. Only a certain degree of the 'active' sites will be accessible for further functionalization. In order to estimate the number of 'accessible active' sites, the residual vinyl groups of the PDVB microspheres which are accessible for reagents were hydroxylated (see Scheme 1, lower right side).

In addition, core PDVB microspheres were functionalized by grafting n-butyl acrylate (BA) from the microspheres using the RAFT agent cyanopropyl dithiobenzoate (CPDB), resulting in PDVB-g-PBAmicrospheres (see Scheme 1, lower left side). Subsequently, all synthesized microspheres were characterized via 1 H and 13 C NMR spectroscopy to quantitatively access the degrees of functionalization.

1 H solid-state NMR spectra recorded at high field under fast MAS showed insufficient resolution for selectively observing signals from vinyl groups, expected in the 6 to 7 ppm range (Figure 1). The only resolved signals are indeed a massif of aliphatic signals, centered around 1 ppm, and a massif of aromatic and unsaturated signals centered around 6 ppm. Signals may be broad because of the low mobility of the samples due to their high degree of crosslinking. No significant change in the spectrum of PDVB55 was observed upon heating up to 120 °C (Figure 1). Therefore 1 H solid-state NMR spectroscopy is not appropriate for observing or quantifying active sites in PDVB microspheres, because of its limited resolution. Note that weak narrow signals were originally observed at 5.2, 6.2 and 6.7 ppm for the sample PDVB80 (see Supporting Information, Figure S1), which originate from vinyl groups. 5 These signals disappeared upon repeated washing of the sample with toluene and were thus assigned to residual monomer units rather than active sites (residual vinyl groups on the polymer chains). Care was taken to ensure that all core PDVB microspheres used for the present work had been washed appropriately to remove any residual monomer, before functionalization or NMR measurement. Careful purification is particularly important since the signal of vinyl groups from residual monomer would overlap with those from the polymer chains, inducing an error in the active sites quantified by 13 C NMR spectroscopy. Improved resolution was sought through 13 C solid-state NMR spectroscopy. 13 C SPE-MAS NMR spectroscopy allows the observation of a resolved signal at 113 ppm for the active site. It originates in the methylene carbon of the vinyl groups pending from the polymer chain (signal D on Figure 2a for PDVB80, see Scheme 1 and Supporting Information Table S1 for complete signals assignment). The signal at 128 ppm (C on Figure 2a) solely originates in the non-substituted carbons of the aromatic rings (4 per monomer units). In terms of chemical shift and shape of signal observed in 13 C SPE-MAS spectra, sample PDVB80 (Figure 2a) is representative of core and hydroxylated microspheres, while sample PDVB80-BA (Figure 2c) is representative of poly(n-butyl acrylate)-grafted microspheres.

The active sites can in principle be quantified in percents of the monomer units by 13 C NMR spectroscopy via signals D and C for all samples. However, a broad signal underlying the aromatic region was observed with an intensity comparable to that of the signals of interest. The broad underlying signal renders the quantification of the narrow C and D signals difficult. Possible causes for the observation of the broad signal were subsequently examined. Signal broadening due to paramagnetic impurities was ruled out since no paramagnetic species were present in any step of the synthesis. The broad signal may originate in highly-crosslinked samples parts, which would be locally less mobile than the rest of the sample. If this was the case, the signal should narrow with increasing local mobility upon heating. Variable-temperature experiments showed that this was not the case (see the Supporting Information section for details, Figure S2). Thus the broad underlying signal most probably originates from components other than the sample, namely the cap of the rotor containing the sample and various components of the probe. This was checked by comparing the 13 C SPE-MAS spectra of sample PDVB80 in a given rotor and of the same empty rotor under the exact same conditions (Figure 2a): the broad underlying signal observed for PDVB80 exactly overlays with the background signal. Thus the quantification of signals C and D is possible on a quantitative 13 C SPE-MAS spectrum after subtraction of the background signals. The acquisition of a quantitative spectrum however was found to require prohibitively long measuring times to be carried out on all samples (see below). S1.

Improved sensitivity was therefore sought through 13 C CP-MAS NMR spectroscopy. It overcame two problems: spectra with a resolved signal from the methylene group of the active site at 113 ppm could be recorded in shorter times without background signal (Figure 3b). 13 C CP-MAS spectra are not intrinsically quantitative. However, a range of contact times was identified, over which the relative intensities of the signals of interest did not vary, allowing quantitative comparison between samples on the same arbitrary scale (Figure 3a). The representative 13 C CP-MAS spectra of PDVB55 and PDVB55-BA are shown in Figure 3b and3c, spectra are shown for other samples in the Supporting Information in Figure S3. The active sites AS (i.e. residual vinyl groups on the polymer chains) were quantified from 13 C CP-MAS spectra, on the same arbitrary scale with respect to the monomer units, using equation ( 1):

( ) ( ) C 4 D 100 .) a.u ( I I AS   = (1)
where I(D) is the area of the signal centered around 113 ppm, originating solely in one (methylene) carbon of residual vinyl groups, and I(C) is the area of the signal centered around 128 ppm, originating solely in four carbons per phenyl group of the monomer unit (unsubstituted carbons). Active sites quantified on the same arbitrary scale are given for all samples in Table 1. The peak at 128 ppm is not fully resolved from the signals centered around 138 and 145 ppm; however, considering the similar signal areas present on both sides of the minimum at 134 ppm, the error introduced is small compared to the experimental error, and systematic for all samples. Note that for the samples grafted with poly(nbutyl acrylate), the signal centered around 128 ppm also contains the signal of the 5 non-substituted aromatic carbons of the RAFT group, which is assumed to be negligible compared to the experimental error made during the measurements. Such an assumption is supported by the fact that the C=S signal of the same RAFT group at approximately 225 ppm is below the detection limit for both PDVB55-BA and PDVB80-BA microspheres (see Supporting Information, Figure S4). Solid-state NMR spectroscopy measures the whole sample volume and not only its surface; therefore the active sites are quantified throughout the sample. Actives sites inside the microspheres, however, will not be accessible for functionalization because reagents will not be able to penetrate the microspheres to react with them.

Active sites accessible for functionalization (ASAF) may however be quantified via comparison of actives sites remaining after hydroxylation AShydroxylated with the active sites present in the corresponding core microspheres AScore, using equation ( 2):

( )

core ed hydroxylat core 100 (%) AS AS AS ASAF -  = (2)
Similarly, an absolute quantification of the active sites actually functionalized during PBA-grafting, in percent of the active sites originally present on the core microspheres, may be calculated by replacing AShydroxylated by ASPBA-grafted in Equation ( 2). ASAF values are shown for all hydroxylated and PBAgrafted samples in Table 1.

Residual vinyl groups are quantified with Equation (1) on the same arbitrary scale. This scale can be calibrated with the measurement of AS in percents of the monomer unit of one sample in a quantitative way. A quantitative 13 C SPE-MAS spectrum can be recorded using a sufficiently long relaxation delay between scans to ensure full sample relaxation. Comparison of the spectra of PDVB80 recorded with relaxation delays ranging from 2 to 20 s indicated that a relaxation delay of 10 s is not sufficient to ensure full relaxation (see Supporting Information, Figure S5). Therefore a very long relaxation delay of 60 s was chosen. To increase the sensitivity, a larger sample volume was measured (filling a 4 mm rotor rather than a 2.5 mm rotor). A quantitative 13 C SPE-MAS spectrum of PDVB80 was recorded, using a sufficiently long relaxation delay between scans to ensure full sample relaxation (Figure 2a). A 13 C SPE-MAS spectrum of the empty rotor was subsequently recorded under the exact same experimental conditions to yield the background signal (Figure 2a). The subtraction of the background from the 13 C SPE-MAS spectrum of sample PDVB80 yields the quantitative 13 C SPE-MAS spectrum of sample PDVB80 (Figure 2b). a AS (a.u.) are the active sites quantified with respect to the monomer units on the same arbitrary scale for all samples, via 13 C-CP MAS NMR spectroscopy. b ASAF (%) are the active sites accessible for functionalization, quantified on an absolute scale by comparison of AS (a.u.) of the functionalized microspheres and of the corresponding core ones. c AS (%) are the active sites quantified with respect to the monomer units on an absolute scale, obtained from AS (a.u.) via the same correction factor for all samples. d CL (%) is the degree of crosslinking calculated on the corresponding core microsphere. e Fmon (%) is the degree of functionalization quantified in percents of the monomer units. f Fpart (groups particle -1 ) is the number of active groups per particle.

g Fsurf (groups nm -1 ) is the number of active groups per nm 2 . h LC (loading capacity) is the moles of active groups per gram of particle.

Equation ( 1) was used to determine the absolute percentages of residual vinyl groups in PDVB80: it was found that 30% of the monomer units contain residual vinyl groups. The percentage of active sites of PDVB80 on the arbitrary scale was found to be 39%. Thus, a correcting factor of 30/39=0.77 must be applied to percentages of vinyl groups determined from 13 C CP-MAS to convert them into actual percentages of vinyl groups, using equation (3):

77 . 0 ) a.u. ( .) . ( (%) ) a.u. ( ) % ( PDVB80 PDVB80  =  = AS u a AS AS AS AS (3)
The corrected values are given in Table 1 for all samples. Note that the active sites concentration measured by 13 C CP-MAS is overestimated. This observed overestimation of the signal intensity for the vinyl methylene carbons with respect to that of the non-substituted aromatic carbons is attributed to the higher number of directly bound 1 H nuclei (two versus one) leading to a more efficient polarization transfer, whereas the relaxation of the bound 1 H nuclear spins under the applied radio-frequency field (T1) can be expected to be identical (see Supporting Information for detailed discussion).

Several conclusions can be drawn from the comparison of the samples in terms of active sites quantified with respect to the monomer units on the same arbitrary scale via 13 C-CP MAS NMR spectroscopy (Table 1, first and second columns). Firstly, PDVB80 samples have a higher degree of active sites AS (e.g. 41 a.u.) than PDVB55 ones (e.g. 32 a.u.). However, PDVB80 samples have proportionally less active sites accessible for functionalization ASAF (%) than PDVB55 ones. Both findings can be rationalized as follows. PDVB80 microspheres are synthesized from a monomer mixture with a higher proportion of difunctional monomer than PDVB55 ones, therefore they are expected to be more crosslinked, and consequently less swellable. This results in a higher number of active sites (vinyl groups) being trapped inside the microspheres, which are therefore not accessible for functionalization.

Secondly, for both PDVB80 and PDVB55 systems, more active sites are accessible for functionalization (ASAF (%)) in the case of hydroxylation than in the case of grafting with n-butyl acrylate, BA. Such an observation is in agreement with the larger reagent size in the case of BA. Note that during the hydroxylation of sample PDVB80-OH, a side reaction leading to the hydrogenation of the vinyl group [START_REF] Westcott | [END_REF] leads to a signal increase in the pending ethyl groups observed at 16 and 30 ppm. Both hydroxylation and hydrogenation of the vinyl group lead to the disappearance of this signal, thus in both cases the active site is quantified as being functionalized.

The quantification of active sites with respect to the monomer units on an absolute scale provides additional information (Table 1, third column). First, the core PDVB55 and PDVB80 microspheres have approximately 25 and 32% residual vinyl groups per monomer unit, while the initial monomer mixture contained 55 and 80% of difunctional monomer, respectively. Thus a significant fraction of the difunctional monomers have reacted only once (assuming there is no bias towards mono-or difunctional monomer the first time its reacts). This observation is consistent with an earlier report of significant amounts of residual vinyl groups in poly(styrene-co-divinyl benzene) networks, as soon as more than 10% divinyl benzene was used for the synthesis. 17 The resulting microspheres are highly crosslinked.

The degree of crosslinking, defined as the proportion of monomer units which have reacted twice in the final polymer, may be calculated as follows:

( ) ( ) % % ) % ( AS DM CL - = (4)
where DM (%) is the proportion of difunctional monomer in the initial monomer mixture (55% for PDVB55 and 80% for PDVB80, respectively). Note that this formula holds only for the core microspheres before functionalization, and assumes that there is no bias towards mono-or difunctional monomer the first time a monomer unit reacts. The degree of crosslinking of the microspheres is high:

approximately 30% for PDVB55 and approximately 50% for PDVB80 (Table 1, fourth column), which is much higher than the usual 2 to 10% observed in the more common poly(styrene-co-divinyl benzene)

systems (e.g. Merrifield resins). The higher degree of crosslinking results in a lower swellability of PDVB80 compared to PDVB55 microspheres.

The extent of the functionalization may be quantified in different ways: with respect to the monomer units, to the number of groups per particle, to the nominal particle surface area and even as the loading capacity of the particles. The number of functional groups is easily calculated in percents of the monomer units as follows:

( )

(%) (%) (%) ed hydroxylat core mon AS AS F - = (5) 20
Hydroxylated microspheres have a higher number of functional groups per monomer unit, Fmon, than PBA-grafted ones, as was expected from the smaller reagent size. Interestingly, PDVB55 and PDVB80 microspheres exhibit a slightly different number of hydroxyl groups per monomer unit, but the same number of PBA grafts per monomer unit within experimental error.

The number of functional groups per particle may be calculated according to Equation 6:

( ) M d AS AS n F F      - =  = 6 N 100 (%) (%) 100 (%) 3 ed hydroxylat core mon part   (6)
where n is the number of monomer units per particle, d is the particle diameter, ρ is the density of the PDVB microspheres (1.82 g•cm -3 and 1.12 g•cm -3 for PDVB80 and PDVB55 microspheres respectively), N is the Avogadro's number and M is the molar mass of the divinyl benzene monomer unit (130.19 g•mol -1 ). PDVB55 microspheres contain 8.70•10 8 and PDVB80 microspheres contain 1.28•10 9 active groups (e.g. vinyl groups) per particle that are accessible for grafting with BA.

The number of functional groups can also be expressed as number of functional groups per nominal surface area (groups per nm -2 ). The calculation of the number of functional groups per surface area in the current study is based on the nominal surface area of a single microsphere, which does not take into account that the microsphere has a porous surface and the available surface area is clearly significantly larger than that nominally calculated. However, it is very difficult to obtain a suitable value for the accessible surface area, as this area is dependent on the type of molecule that is grafted as discussed earlier. The number of functional groups per nominal surface area (groups per nm -2 ) may be calculated according to Equation 7:

( ) M d AS AS SA n F F     - =   = 6 N 100 (%) (%) 100 (%) ed hydroxylat core mon surf  (7)
where SA is the nominal surface area of one microsphere. Derived from Equation 7, PDVB55 microspheres contain 110 and PDVB80 microspheres contain 179 active groups (e.g. vinyl groups) per nominal surface area, i.e. nm 2 , that are accessible for grafting with BA. Inspection of the ratio of the degree of crosslinking of the two types of particles (30/50 = 0.6) and comparison with the ratio of the number of functional groups per nominal surface area of the two types of particles (110/179 = 0.61) demonstrates that the number of accessible active groups is directly linked with the degree of crosslinking.

In addition, the loading capacity LC (in mmol•g -1 ) of the microspheres may be calculated according to Equation 8:

3 part N 6000 d F LC     =   (8)
The PDVB55-BA and PDVB80-BA microspheres have a loading capacity of 0.61 and 0.65 mmol•g - 1 , respectively. These loading capacities are similar to the loading capacities found for Merrifield resins, 43 e.g. Merrifield resins of mesh size 100-200 (which corresponds to a particle diameter of 74 to 149 m) have loading capacities from 1.5 to 4.5 mmol•g -1 .

Conclusions

The potential of solid-state NMR spectroscopy to characterize surface functionalization in highly crosslinked microspheres is demonstrated. For the first time, residual vinyl groups were quantified in poly(divinyl benzene) microspheres in percents of the monomer units through solid-state NMR spectroscopy. 13 C CP-MAS NMR spectroscopy allows the comparison of samples on the same arbitrary scale in a short measuring time. This scale was calibrated by one longer, absolute quantification of vinyl groups using 13 C SPE-MAS NMR spectroscopy. Solid-state NMR spectroscopy detects all vinyl groups present in the sample, not distinguishing if they are located inside or at the surface of the particle. A comparison of core microspheres with the corresponding hydroxylated ones yields the proportion of the vinyl groups available for chemical functionalization. The proportion of the reacted vinyl groups is quantified by comparison of poly(n-butyl acrylate)-grafted microspheres with the corresponding core ones. It was found that not all vinyl groups available for functionalization were actually functionalized via grafting of BA. The degree of crosslinking was calculated to be 30% and 50% for PDVB55 and PDVB80 microspheres, respectively. The number of active groups per nominal surface area was 110 22 and 179 groups per nm -2 for PDVB55 and PDVB80 microspheres, respectively. The loading capacities of the microspheres are similar to ones found in Merrifield resins of comparable sizes. m.gaborieau@uws.edu.au, graf@mpip-mainz.mpg.de 2 Preparative Macromolecular Chemistry, Institut für Technische Chemie und Polymerchemie, Karlsruhe Institute of Technologie (KIT), Engesserstrasse 18, 76128 Karlsruhe, Germany, leena.nebhani@kit.edu, christopher.barner-kowollik@kit.edu 3 Fraunhofer Institut für Chemische Technologie, Joseph-von-Fraunhofer-Strasse 7, 76327 Pfinztal (Berghausen), Germany, leonie.barner@ict.fraunhofer.de.

Acknowledgements. Funding from the

Figure S1: 1 H MAS spectrum of sample PDVB80 with residual monomer

The weak narrow signals were originally observed at 5.2, 6.2 and 6.7 ppm for sample PDVB80 originate in vinyl groups. They disappeared upon repeated washing of the sample with toluene. They were thus assigned to residual monomers rather than active sites (residual vinyl groups on the polymer chains). Care was taken to ensure that all core PDVB microspheres used for the present work had been washed appropriately to remove any residual monomer, before functionalization or NMR measurement. This is particularly important since the signal of vinyl groups from residual monomer would overlap with those from the polymer chains, inducing an error in the active sites quantified by 13 C NMR. However, after the background signal was recorded on another day, the background subtraction was done, yielding the spectra below.

It is now obvious that there is a big difference in the signal C at ca 128 ppm between 10 and 20 s.

Discussion of the overestimation of AS by 13 C CP-MAS measurements

The active sites concentration measured by 13 C CP-MAS is overestimated, meaning that the signal intensity for the vinyl methylene carbons is overestimated with respect to that of the nonsubstituted aromatic carbons.

Figure 1 .

 1 Figure 1. 1 H solid-state NMR spectra at high field and fast MAS of PDVB55 microspheres at

Figure 2 .

 2 Figure 2. 13 C solid-state SPE-MAS NMR spectra of (a, top) PDVB80 microspheres, (a, bottom)

Figure 3 .

 3 Figure 3. 13 C solid-state CP-MAS NMR spectra of (a) PDVB55 microspheres with short measuring

  Experimental conditions: Bruker Avance 500, 4 mm MAS probe, ZrO2 rotor with BN cap, 10 kHz MAS, 13 C SPE-MAS, 4 s 90° pulse, 10 s repetition delay, no temperature calibration thus approximate temperatures; at 150 °C with NS = 1 360 in 3 h 50; at 200 °C with NS = 4 038 in 11 h 20; at 100 °C with NS = 1 024 in 2 h 50.

Figure S3 :

 S3 Figure S3: Influence of contact time on signal intensities in 13 C CP-MAS spectra

Figure S4 :Figure S5 :

 S4S5 Figure S4: Semi-quantitative 13 C CP-MAS spectra Experimental conditions: 13 C CP-MAS, semi-quantitative: Avance 500, 2.5 mm MAS probe,

Thus 10 s

 10 relaxation delay is not sufficient to record a quantitative13 C SPE-MAS spectrum of PDVB80. As it would be too time-consuming to test various longer relaxation delays, it was decided to directly use a very log relaxation delay (60 s) and record the13 C SPE-MAS spectra of PDVB80 and the background.

The 13 C 13 C

 1313 CP-MAS experiment is divided in three parts: first the flip of the hydrogen magnetization to the xy-plane, then the transfer of the magnetization between 1 H and13 C nuclei in the xy-plane via cross-polarization during a time TCP, followed by the recording of the FID. During TCP, polarization transfer is possible via heteronuclear dipole-dipole interactions since the 1 H spins are locked with an rf field B1 1H , while the13 C spins are irradiated with a different magnetic field B1 13C = 4B1 1H , so that they finally have the same precession frequency  C = C . B1 C = H . B1 H =  H in the locking fields (so-called Hartmann-Hahn conditions). During TCP, both 1 H and13 C loose magnetization (in the xy-plane) through T1 relaxation phenomena (corresponding to the relaxation under an applied radio-frequency field). Efficient magnetization transfer is possible only if the relaxation time constants T1 are higher than the time constant TCH of the magnetization transfer. As the cross-polarization and the T1 relaxation of the 1 H nuclei are the fastest phenomena, the intensity MC(t) of the13 C nuclei magnetization over time approximately follows the equation: the initial 1 H magnetization, T1 the longitudinal relaxation time of 1 H nuclei under Hartmann-Hahn conditions, and 1/TCH the magnetization transfer rate from 1 H to13 C nuclei under Hartmann-Hahn conditions (ref Grimmer, A. R.; Bluemich, B.; Introduction to Solid-State NMR, In NMR Basic Principles and Progress, 1994; vol. 30, pp 1-62). The intensity of the magnetization of a nucleus as a function of the contact time TCP is sketched on the figure below (typical time constants are indicated): time constants, TCH and T1, we expect TCH to contribute predominantly to the observed overestimation of the signal intensity for the vinyl methylene carbons with respect to that of the non-substituted aromatic carbons. First, T1 can be expected to be very similar for the vinyl proton sites and the aromatic protons, since the vinyl group is directly bound to the aromatic ring leading to a conjugation of the vinyl double bond and the aromatic ring, which excludes molecular motions with correlation times differing on a logarithmic scale needed to cause different T1 relaxation times. The shorter TCH of the vinyl group can be attributed to the fact that the vinyl methylene carbons are bound to two 1 H nuclei each, while the non-substituted aromatic ones are bound to only one each. Moreover the shorter TCH of the vinyl methylene group is supported by the experimental finding that the CP-MAS signal of this group build up fastest with short CP contact times, as shown in figure 3, whereas all other signals need longer CP contact times to achieve contact time independent relative intensities.

Table 1 .

 1 Overview of the quantitative degrees of functionalization for various microspheres as described in Scheme 1.

	Sample	AS	ASAF	AS	CL	Fmon	Fpart	Fsurf	LC
		(a.u.) a	(%) b	(%) c	(%) d	(%) e	(groups	(groups	(mmol
							particle -1 ) f	nm -2 ) g	g -1 ) h
	PDVB55-1	29		22	33
	PDVB55-OH	11	62	8		14	1.50•10 9	188	1.05
	PDVB55-2	35		27	28
	PDVB55-BA	24	30	19		8	8.70•10 8	110	0.61
	PDVB80-1	39		30	50
	PDVB80-OH	26	34	20		10	1.53•10 9	213	0.77
	PDVB80-2	43		33	47
	PDVB80-BA	32	26	25		9	1.28•10 9	179	0.65

Table of Contents use only

  Max Planck Society as well as the Karlsruhe Institute of Technology (KIT) is gratefully acknowledged. L.N., L.B. and C.B.-K. thank Dr. James Hook (NMR Facility, Analytical Centre, The University of New South Wales, Sydney, Australia) for fruitful discussions. In addition, M.G. and R.G. thank Prof. H. W. Spiess for continued support and his interest in the current work.Supporting information available: full13 C chemical shift assignment, 1 H and13 C solid-state NMR spectra. This information is available free of charge via the Internet at http://pubs.acs.org/.Accessing Quantitative Degrees of Functionalization on Solid Substrates via Solid State NMR Spectroscopy Marianne Gaborieau, Leena Nebhani, Robert Graf, Leonie Barner, ChristopherBarner-

	Supporting Information for Accessing Quantitative Degrees of Functionalization For Kowollik on Solid Substrates via Solid State NMR
	Spectroscopy
	Marianne Gaborieau,* Leena Nebhani, Robert Graf, Leonie Barner*,
	Christopher Barner-Kowollik*
	1 Max Planck Institute for Polymer Research, Ackermannweg 10, 55128 Mainz, Germany,

Table S -1: Full 13 C chemical shifts assignment

 S Complete13 C chemical shifts assignment for13 C NMR spectra of core, hydroxylated and PBAgrafted poly(divinyl benzene) microspheres (chemical formulae given in Scheme 1). Letters refer to

	Figure S2:
	Scheme 1.
	Group Chemical shift / ppm	Assignment
	L	13	CH3 of side chain of PBA
	G	16	CH3 of ethyl on aromatic ring
	K	20	CH2 of side chain of PBA in  of CH3
	J	29, 31	CH2 of side chain of PBA adjacent to O-CH2-
	F	30	CH2 from ethyl on aromatic ring
	E	41-50	CH backbone PDVB and PBA
			CH2 backbone PDVB and PBA
			CH2 of ethyl-OH in  of aromatic ring (if OH in  of ring)
	I	64	O-CH2 of side chain of PBA
	D	113	C=C (C not adjacent to aromatic ring)
	C	128	benzene ring (not substituted) of PDVB or RAFT group
	B	138	C=C (C adjacent to aromatic ring)
			aromatic ring (adjacent to C=C, or to ethyl-OH if OH in  of ring)
	A	146	aromatic ring (adjacent to ethyl or backbone, or to ethyl-OH if
			OH in  of ring, or to C=S in RAFT group)
	H	166	C=O of PBA
	It was checked that the presence of 2 substituents in meta or para on the aromatic ring did not
	change the chemical shift of aromatic C to the point that they would some out in another massif
	observed by solid-state NMR.
	Note: the following signals were below the detection limit:
	-CH3 of ethyl-OH (if OH in  of ring), expected at ca. 25 ppm
	-CH2 of ethyl-OH in  of aromatic ring (if OH in  of ring), expected at ca. 63 ppm
	-CH from ethyl-OH (if OH in  of ring), expected at ca .70 ppm
	-C=S of RAFT group, expected at ca. 225 ppm

No influence of temperature on broad underlying signal

  Variable-temperature experiments revealed that the broad underlying signal in the aromatic region does not originate in highly-crosslinked samples parts, but is actually a background signal from the rotor caps and the probes.


Christian Bessiere
email: bessiere@lirmm.fr

Remi Coletta
email: coletta@l-rd.fr

Barry O'

Sullivan 4c
email: b.osullivan@4c.ucc.ie

Mathias Paulin
email: paulin@lirmm.fr

Query-driven Constraint Acquisition

The modelling and reformulation of constraint networks are recognised as important problems. The task of automatically acquiring a constraint network formulation of a problem from a subset of its solutions and non-solutions has been presented in the literature. However, the choice of such a subset was assumed to be made independently of the acquisition process. We present an approach in which an interactive acquisition system actively selects a good set of examples. We show that the number of examples required to acquire a constraint network is significantly reduced using our approach.

Introduction

Constraint Programming (CP) provides a powerful paradigm for solving combinatorial problems. However, the specification of constraint networks still remains limited to specialists in the field. An approach to automatically acquiring constraint networks from examples of their solutions and nonsolutions has been proposed by [Bessiere et al., 2005]. Constraint acquisition was formulated as a concept learning task. The classical version space learning paradigm [Mitchell, 1982] was extended so that constraint networks could be learned efficiently. Constraint networks are much more complex to acquire than simple conjunctive concepts represented in propositional logic. While in conjunctive concepts the atomic variables are pairwise independent, in constraint satisfaction there are dependencies amongst them.

In [Bessiere et al., 2005] the choice of the subset of solutions and non-solutions to use for learning was assumed to be made before and independently of the acquisition process. In this paper we present an approach in which the acquisition system actively assists in the selection of the set of examples used to acquire the constraint network through the use of learner-generated queries. A query is essentially a complete instantiation of values to the variables in the constraint network that the user must classify as either a solution or nonsolution of her 'target' network. We show that the number of examples required to acquire a constraint network is significantly reduced if queries are selected carefully.

When acquiring constraint networks computing good queries is a hard problem. The classic query generation strat-egy is one in which, regardless of the classification of the query, the size of the version space is reduced by half. Therefore, convergence of the version space can be achieved using a logarithmic number of queries. Furthermore, in the classic setting, a query can be generated in time polynomial in the size of the version space. When acquiring constraint networks, query generation becomes NP-hard. This is further aggravated by the fact that in constraint acquisition, while the ordering over the hypothesis space is most naturally defined in terms of the solution space of constraint networks, we usually learn at the constraint level, i.e. a compact representation of the set of solutions of a hypothesis. Our main contribution is a number of algorithms for identifying good queries for acquiring constraint networks. Our empirical studies show that using our techniques the number of examples required to acquire a constraint network is significantly reduced. This work is relevant to interactive scenarios where users are actively involved in the acquisition process.

Constraint Acquisition using CONACQ

A constraint network is defined on a (finite) set of variables X and a (finite) set of domain values D. This common knowledge shared between the learner and the user is called the vocabulary. Furthermore, the learner has at its disposal a constraint library from which it can build and compose constraints. The problem is to find an appropriate combination of constraints that is consistent with the examples provided by the user. For the sake of notation, we shall assume that every constraint defined from the library is binary. However, the results presented here can be easily extended to constraints of higher arity, and this is demonstrated in our experiments.

A binary constraint c ij is a binary relation defined on D that specifies which pairs of values are allowed for variables x i , x j . The pair of variables (x i , x j ) is called the scope of c ij . For instance, ≤ 12 denotes the constraint specified on (x 1 , x 2 ) with relation "less than or equal to". A binary constraint network is a set C of binary constraints. A constraint bias is a collection B of binary constraints built from the constraint library on the given vocabulary. A constraint network C is said to be admissible for a bias B if for each constraint c ij in C there exists a set of constraints

{b 1 ij , • • • , b k ij } in B such that c ij = b 1 ij ∩ • • • ∩ b k ij .
An instance e is a map that assigns to each variable x i in IJCAI-07 X a domain value e(x i ) in D. Equivalently, an instance e can be regarded as a tuple in D n . An instance e satisfies a binary constraint c ij if the pair (e(x i ), e(x j )) is an element of c ij ; otherwise we say that c ij rejects e. If an instance e satisfies every constraint in C, then e is called a solution of C; otherwise, e is called a non-solution of C.

Finally, a training set E f consists of a set E of instances and a classification function f : E → {0, 1}. An element e in E such that f (e) = 1 is called positive example (often denoted by e + ) and an element e such that f (e) = 0 is called negative example (often denoted by e -). A constraint network C is said to be consistent with a training set E f if every positive example e + in E f is a solution of C and every negative example e -in E f is a non-solution of C. We also say that C correctly classifies E f . Given a constraint bias B and a training set E f , the Constraint Acquisition Problem is to find a constraint network C admissible for the bias B and consistent with the training set E f .

A SAT-based algorithm, called CONACQ, was presented in [Bessiere et al., 2005] for acquiring constraint networks based on version spaces. Informally, the version space of a constraint acquisition problem is the set of all constraint networks that are admissible for the given vocabulary and bias, and that are consistent with the given training set. We denote as V B (E f ) the version space corresponding to the bias B and the training set E f . In the SAT-based framework this version space is encoded in a clausal theory K. Each model of the theory K is a constraint network of V B (E f ).

More formally, if B is the constraint bias, a literal is either an atom b ij in B, or its negation ¬b ij . Notice that ¬b ij is not a constraint: it merely captures the absence of b ij in the acquired network. A clause is a disjunction of literals (also represented as a set of literals), and the clausal theory K is a conjunction of clauses (also represented as a set of clauses). An interpretation over B is a map I that assigns to each constraint atom b ij in B a value I(b ij ) in {0, 1}. A transformation is a map φ that assigns to each interpretation I over B the corresponding constraint network φ(I) defined according to the following condition:

c ij ∈ φ(I) iff c ij = {b p ij ∈ B : I(b p ij ) = 1}.
An interpretation I is a model of K if K is true in I according to the standard propositional semantics. The set of all models of K is denoted Models(K). For each instance e, κ(e) denotes the set of all constraints b ij in B rejecting e.

For each example e in the training set E f , the CONACQ algorithm iteratively adds to K a set of clauses so that for any I ∈ M odels(K), the network φ(I) correctly classifies all already processed examples plus e. When an example e is positive, unit clauses {¬b ij } are added to K for all b ij ∈ κ(e).

When an example e is negative, the clause { bij ∈κ(e) b ij } is added to K. The resulting theory K encodes all candidate networks for the constraint acquisition problem. That is,

V B (E f ) = {φ(m) | m ∈ M odels(K)}.
Example 1 (CONACQ's Clausal Representation) We wish to acquire a constraint network involving 4 variables, x 1 , . . . , x 4 , with domains D(x 1 ) = . . . = D(x 4 ) = {1, 2, 3, 4}. We use a complete and uniform bias, with L = {≤, =, ≥} as a library. That is, for all 1 ≤ i < j ≤ 4, B contains ≤ ij , = ij and ≥ ij . Assume that the network we wish to Table 1: An example of the clausal representation built by CONACQ, where each example e ? i = (x 1 , x 2 , x 3 , x 4 ).

E f example clauses added to K {e + 1 } (1,2,3,4) ¬ ≥12 ∧¬ ≥13 ∧¬ ≥14 ∧¬ ≥23 ∧¬ ≥24 ∧¬ ≥34 {e + 2 } (4,3,2,1) ¬ ≤12 ∧¬ ≤13 ∧¬ ≤14 ∧¬ ≤23 ∧¬ ≤24 ∧¬ ≤34 {e - 3 } (1,1,1,1) ( =12 ∨ =13 ∨ =14 ∨ =23 ∨ =24 ∨ =34)
acquire contains only one constraint, namely x 1 = x 4 ; there is no constraint between any other pair of variables. For each example e (first column), Table 1 shows the clausal encoding constructed by CONACQ after e is processed, using the set κ(e) of constraints in the bias B that can reject e.

The learning capability of CONACQ can be improved by exploiting domain-specific knowledge [Bessiere et al., 2005]. In constraint programming, constraints are often interdependent, e.g. two constraints such as ≥ 12 and ≥ 23 impose a restriction on the relation of any constraint defined on the scope (x 1 , x 3 ). This is a crucial difference with conjunctive concepts where atomic variables are pairwise independent. Because of such interdependency, some constraints in a network can be redundant. c ij is redundant in a network C if the constraint network obtained by deleting c ij from C has the same solutions as C. The constraint ≥ 13 is redundant each time ≥ 12 and ≥ 23 are present.

Redundancy must be carefully handled if we want to have a more accurate idea of which parts of the target network are not precisely learned. One of the methods to handle redundancy proposed in [Bessiere et al., 2005], was to add redundancy rules to K based on the library of constraints used to build the bias B. For instance, if the library contains the constraint type ≤, for which we know that ∀x, y, z, (x ≤ y) ∧ (y ≤ z) → (x ≤ z), then for any pair of constraints ≤ ij , ≤ jk in B, we add the Horn clause ≤ ij ∧ ≤ jk →≤ ik in K. This form of background knowledge can help the learner in the acquisition process.

The Interactive Acquisition Problem

In reality, there is a cost associated with classifying instances to form a training set (usually because it requires an answer from a human user) and, therefore, we should seek to minimise the size of training set required to acquire our target constraint network. The target network is the constraint network C T expressing the problem the user has in mind. That is, given a vocabulary X, D, C T is the constraint network such that an instance on X is a positive example if and only if it is a solution of C T .

During the learning process the acquisition system has knowledge that can help characterise what next training example would be ideal from the acquisition system's point of view. Thus, the acquisition system can carefully select 'good' training examples (which we will discuss in Section 4 in more depth), that is, instances which, depending on how the user classifies them, can help reduce the expected size of the version space as much as possible. We define a query and the classification assigned to it by the user as follows.

Definition 1 (Queries and Query Classification) A query q is an instance on X that is built by the learner. The user

IJCAI-07 51

classifies a query q using a function f such that f (q) = 1 if q is a solution of C T and f (q) = 0 otherwise.

Angluin [Angluin, 2004] defines several classes of queries, among which the membership query is exactly the kind used here. The user is presented with an unlabelled instance, and is asked to classify it. We can now formally define the interactive constraint acquisition problem. Definition 2 (Interactive Constraint Acquisition Problem) Given a constraint bias B and an unknown user classification function f , the Interactive Constraint Acquisition Problem is to find a converging sequence Q = q 1 , . . . , q m of queries, that is, a sequence such that: q i+1 is a query relative to B and V B (E f i ) where E i = {q 1 , . . . , q i }, and |V B (E f m )| = 1. Note that the sequence of queries is built incrementally, that is, each query q i+1 is built according to the classification of q 1 , . . . , q i . In practice, minimising the length of Q is impossible because we do not know in advance the answers from the user. However, in the remainder of the paper we propose techniques that are suitable for interactive learning.

Query Generation Strategies

Polynomial-time Query Generation

In practice, it can be the case that an example e from the training set does not bring any more information than that which has already been provided by the other examples that have been considered so far. If we allow for queries to be generated whose classification is already known based on the current representation of the version space, K, then we will ask the user to classify an excessive number of examples for no improvement in the quality of our representation of the version space of the target network. We exemplify this problem with a short example. Example 2 (A Redundant Query) Consider an acquisition problem over the three variables x 1 , x 2 , x 3 , with the domains D(x 1 ) = D(x 2 ) = D(x 3 ) = {1, 2, 3, 4} using the same constraint library as in Example 1. Given the positive example e + 1 = (x 1 , 1), (x 2 , 2), (x 3 , 3) , K = ¬ ≥ 12 ∧¬ ≥ 13 ∧¬ ≥ 23 . Asking the user to classify e 2 = (x 1 , 1), (x 2 , 2), (x 3 , 4) is redundant, since all constraints rejecting it are already forbidden by K. Then any constraint network in the version space accepts e 2 .

We propose a simple (poly-time) technique that avoids proposing such redundant queries to the user. This irredundant queries technique seeks a classification only for an example e that cannot be classified, given the current representation K of the version space. An example e can be classified by ] of κ(e), obtained by removing from κ(e) all constraints that appear as negated literals in K, is empty. Alternatively, e is a nonsolution in all networks in V B (E f ), if κ(e) [K] is a superset of an existing clause of K. Example 3 (An Irredundant Query) Consider again Example 2 in which the positive example e + 1 has been considered. The query e = (x 1 , 1), (x 2 , 2), (x 3 , 2) is irredundant.

V B (E f ) if it is either a solution in all networks in V B (E f ) or a non-solution in all networks in V B (E f ). e is a solution in all networks in V B (E f ) iff the subset κ(e) [K
This can be seen by considering the literals that would be added to K by this query. If the query is classified as positive, the clauses (¬ ≥ 12 ), (¬ ≥ 13 ) and (¬ = 23 ) will be added to K, otherwise the clause (≥ 12 ∨ ≥ 13 ∨ = 23 ) will be added. Since we know from example e + 1 that both ≥ 12 and ≥ 13 must be set to false, the only extra literal this new example adds is either (¬ = 23 ) or ( = 23 ) (indeed κ(e) [K] = { = 23 }). Regardless of the classification of e, something new is learned, so this is an irredundant query.

Towards Optimal Query Generation

The technique presented in Section 4.1 guarantees that each newly classified query e adds something new to K. However, different irredundant examples give us different gains in knowledge. In fact, the gain for a query q is directly related to the size k of κ(q) [K] and its classification f (q). If f (q) = 1, k unary negative clauses will be added to K, then k literals will be fixed to 0. In terms of CONACQ, we do not have direct access to the size of the version space, unless we wish to perform very expensive computation through the clausal representation K. But assuming that the models of K are uniformly distributed, fixing k literals divides the number of models by 2 k . If f (q) = 0, a positive clause of size k is added to K, thus removing 1/2 k models. We can distinguish between queries that can be regarded as optimistic, or as optimal-in-expectation.

An optimistic query is one that gives us a large gain in knowledge when it is classified "in our favour", but which tells us very little when it is classified otherwise. More specifically, in CONACQ the larger the κ(q) [K] of a query q, the more optimistic it is. When classified as positive, such a query allows us to set |κ(q) [K] | literals to 0. If the query is classified as negative we just add a clause of size |κ(q) [K] |. Therefore, an optimistic query is maximally informativesets all literals it introduces to 0 -if it is classified as positive, but is minimally informative if it is classified as negative.

The optimal query strategy is one that involves proposing a query that will reduce the size of the version space in half regardless of how the user classifies it. We define a query as being optimal-in-expectation if we are guaranteed that one literal will be fixed to either a 0 or a 1 regardless of the classification provided by the user. Formally, such a query will have a κ(q) [K] of size 1, therefore, if it is classified as positive, we can set the literal in κ(q) [K] to 0, otherwise it is set to a 1.

We illustrate a sequence of queries that are sufficient for the version space of the problem presented as Example 1 to converge using queries that are optimal-in-expectation. Example 4 (Optimal-in-Expectation Queries) We want to converge on the target network from Example 1 (i.e., the only constraint x 1 = x 4 in a network with four variables and the complete bias of constraints {≤, =, ≥}). Recall that having processed the set of examples E = {e + 1 , e + 2 , e - 3 }, the unique positive clause in K is Cl = ( = 12 ∨ = 13 ∨ = 14 ∨ = 23 ∨ = 24 ∨ = 34 ). All other atoms in K are fixed to 0 because of e + 1 and e + 2 . In the following

K {e + 1 ,e + 2 } refers to (¬ ≥ 12 ) ∧ . . . (¬ ≥ 34 ) ∧ (¬ ≤ 12 ) ∧ . . . ∧ (¬ ≤ 34 ). Accord- ing to this notation, the clausal theory K built by CONACQ having processed E is K = K {e + 1 ,e + 2 } ∧ Cl.
f (e) K e4 = (1, 1, 2, 3) { =12} + K {e + 1 ,e + 2 } ∧ (¬ =12) ∧ ( =13 ∨ =14 ∨ =23 ∨ =24 ∨ =34) e5 = (2, 1, 1, 3) { =23} + K {e + 1 ,e + 2 } ∧ (¬ =12) ∧ (¬ =23) ∧ ( =13 ∨ =14 ∨ =24 ∨ =34) e6 = (2, 3, 1, 1) { =34} + K {e + 1 ,e + 2 } ∧ (¬ =12) ∧ (¬ =23) ∧ (¬ =34) ∧ ( =13 ∨ =14 ∨ =24) e7 = (1, 3, 1, 2) { =13} + K {e + 1 ,e + 2 } ∧ (¬ =12) ∧ (¬ =23) ∧ (¬ =34) ∧ (¬ =13) ∧ ( =14 ∨ =24) e8 = (2, 1, 3, 1) { =24} + K {e + 1 ,e + 2 } ∧ (¬ =12) ∧ (¬ =23) ∧ (¬ =34) ∧ (¬ =13) ∧ (¬ =24)∧( =14)
a sequence of queries that are optimal-in-expectation on the version space obtained after the three first examples are processed. The goal is to reduce V B (E) to contain a single hypothesis. The first column is a query e generated according to the optimal-in-expectation strategy. The second column gives the set κ(e) [K] of constraints still possible in a network of the version space that could reject e. The third column is the classification of e by the user, and the fourth column is the update of K. The query e 4 is such that = 12 is the only constraint still possible in the version space that can reject it. Because it is classified as positive, we are sure = 12 cannot belong to a network in the version space. CONACQ adds (¬ = 12 ) to K and the literal = 12 is removed from Cl by unit propagation.

The process repeats with e 5 , e 6 and e 7 , decreasing the size of Cl by one literal at a time, and thus reducing the version space by half. Finally, e 8 is the last example required to ensure that the version space converges on the target network, which contains the single constraint x 1 = x 4 . Note that at the beginning of this example, the version space V B (E) contained 2 6 possible constraint networks, and we could converge using O(log 2 |V B (E)|) queries, which is an optimal worst-case [Mitchell, 1982].

In Example 4, we always found an example e with |κ(e) [K] | = 1, as the optimal-in-expectation strategy requires. However, redundancy can prevent us from being able to generate an example e with a given size for its κ(e) [K] . For instance, consider the acquisition problem, using a complete and uniform bias, with L = {≤, =, ≥} as a library, and with x 1 = x 2 = x 3 as a target network. After processing an initial positive example (for instance e + 1 = (2, 2, 2)), the possible constraints in the version space are ≤ 12 , ≤ 13 , ≤ 23 , ≥ 12 , ≥ 13 , ≥ 23 . Hence, every further negative example e has either a κ(e) [K] of size 3 (if no variables equal) or a κ(e) [K] of size 2 (if two variables equal). Therefore, no example with a κ(e) [K] of size 1 can be generated. Redundancy prevents us from generating such examples.

Implementing our Strategies

In Section 4.2, we presented two strategies for generating queries: optimal-in-expectation and optimistic. These two strategies are characterised by the target number t of constraints still possible in the version space that reject the instances q they try to produce. However, it may be the case that, due to redundancy between constraints, there does not exist any network in the version space that has a solution s with |κ(s) [K] | = t. (And it is useless to ask classification of an instance if it is not a solution of some network in the version space -see Section 4.1). We then must allow for some uncertainty in the number of constraints rejecting an instance.

We implement the query generation problem as a two step process. First, Algorithm 1 tries to find an interpretation I on B such that any solution s of φ(I) is such that t -≤ |κ(s) [K] | ≤ t + , where is the variation accepted on the size of the κ(q) [K] of the query q we want to generate. This algorithm takes another input parameter which is the set L of constraints in which κ(q) [K] must be included. We will explain later that this is a way to monitor the 'direction' in which we want to improve our knowledge of the target network of the user. Second, once I has been found, we take a solution of φ(I) as a query. We first present the algorithm, then we will discuss its complexity and describe how we can use it to implement our strategies (by choosing the values t and ).

Algorithm 1: QUERY GENERATION PROBLEM input : B the bias, K the clausal theory, L a set of literals, t a target size and the variation output:

An interpretation I F ← K 1 foreach b ij ∈ B \ {b ij | (¬b ij ) ∈ K} do 2 if b ij ∈ L then F ← F ∧ (b ij ) 3 else F ← F ∧ (b ij ∨ b ij ) lower ← max(|L| -t -, 1) 4 upper ← min(|L| -t + , |L|) 5 F ← F ∧ atLeast(lower, L) ∧ atM ost(upper, L) 6 if M odels(F) = ∅ then return a model of F 7 else return "inconsistency" 8
Algorithm 1 works as follows. It takes as input the target size t, the allowed variation and the set L of literals on which to concentrate. The idea is to build a formula F for which every model I will satisfy the requirements listed above. F is initialised to K to guarantee that any model will correspond to a network in the version space (line 1). For each literal b ij not already negated in K (line 2), if b ij does not belong to L, we add the clause (b ij ) to F to enforce the constraint b ij to belong to the network φ(I) for all models I of F ('then' instruction of line 3). Hence, any solution s of φ(I) will be rejected either by a constraint in L or a constraint b ij already negated in K (so no longer in the version space). Thus, κ(s) [K] ⊆ L. We now have to force the size of κ(s) [K] to be in the right interval. If b ij belongs to L ('else' instruction of line 3), we add the clause (b ij ∨ b ij ) to F to ensure that either b ij or its complementary constraint b ij is in the re-IJCAI-07 sulting network. 1 b ij is required because ¬b ij only expresses the absence of the constraint b ij . ¬b ij is not sufficient to enforce b ij to be violated. We now just add two pseudo-Boolean constraints that enforce the number of constraints from L violated by solutions of φ(I) to be in the interval [t -.. t + ]. This is done by forcing at most |L|t + constraints and at least |L|tconstraints to be satisfied (lines 4-6). The 'min' and 'max' ensure we avoid trivial cases (no constraint from L is violated) and to remain under the size of L. Line 7 searches for a model of F and returns it. But remember that redundancy may prevent us from computing a query q with a given κ(q) [K] size (Section 4.2). So, if is too small, F can be unsatisfiable and an inconsistency is returned (line 8).

The following property tells us when the output of Algorithm 1 is guaranteed to lead to a query.

Property 1 (Satisfiability) Given a bias B, a clausal theory K, and a model I of K. If K contains all existing redundancy rules over B, then φ(I) has solutions.

If not all redundancy rules belong to K, Algorithm 1 can return I such that φ(I) is inconsistent. In such a case, we extract a conflict set of constraints S from φ(I) and add the clause bij ∈S ¬b ij to K to avoid repeatedly generating models I with this hidden inconsistency in φ(I ).

The next property tells us that generating a given type of query can be hard.

Property 2 Given a bias B, a theory K, a set L of constraints, a target size t and a variation , generating a query q such that:

κ(q) [K] ⊂ L and t -≤ |κ(q) [K] | ≤ t + is N P -hard.
The experimental section will show that despite its complexity, this problem is handled very efficiently by the technique presented in Algorithm 1. The algorithm can be used to check if there exists a query rejected by a set of constraints from the version space of size t ± included in a given set L. The optimal-in-expectation strategy requires t = 1 and optimistic requires a larger t. In the following, we chose to be "half-way" optimistic and to fix t to |L|/2. There still remains the issue of which set L to use and which values of to try. is always initialised to 0. Concerning L, we take the smallest non-unary positive clause of K. A positive clause represents the set of constraints that reject a negative example already processed by CONACQ. So, we are sure that at least one of the constraints in such a set L rejects an instance. Choosing the smallest one increases the chances to quickly converge on a unary clause. If K does not contain any such non-unary clauses we take the set containing all non-fixed literals in K.

Since Algorithm 1 can return an inconsistency when called for a query, we have to find another set of input parameters on which to call the algorithm. t is fixed by the strategy, so we can change L or . If there are several non-unary clauses in K, we set L to the next positive clause in K (ordered by size).

1 Not all libraries of constraints contain the complement of each constraint. However, the complements may be expressed by a conjunction of other constraints. For instance, in library ≤, =, ≥, ≤ does not exist but it can be expressed by (≥ ∧ =). If no conjunction can express the complement of a constraint, we can post an approximation of the negation (or nothing). We just lose the guarantee on the number of constraints in L that will reject the generated query.

If we have tried all the clauses without success, we have to increase . We have two options. The first one, called closest, will look for a query generated with a set L instantiated to the clause that permits the smallest . The second one, called approximate, increases by fixed steps. It first tries to find a set L where a query exists with = 0.25 • |L|. If not found, it looks (repeatedly) with 0.50 • |L|, 0.75 • |L| and then |L|.

We thus have four policies to generate queries: optimistic and optimal-in-expectation combined with closest and approximate: optimistic means t = L/2 whereas optimal-inexpectation means t = 1; closest finds the smallest whereas approximate increases by steps of 25%.

Experimental Results

We implemented CONACQ using SAT4J2 and Choco3 . In our implementation we exploit redundancy to the largest extent possible, using both redundancy rules and backbone detection [Bessiere et al., 2005].

Problem Classes. We used a mix of binary and non-binary problem classes in our experiments. We studied random binary problems, with and without structure, as well as acquiring a CSP defining the rules of the logic puzzle Sudoku. CONACQ used a learning bias defined as the set of all edges in each problem using the library {≤, ≥, =}. The random binary problems comprised 14 variables, with a uniform domain of size 20. We generated target constraint networks by randomly selecting a specified number of constraints from {<, ≤, =, ≥, >, =}, retaining only those that were soluble. We also considered instances in which we forced some constraint patterns in the constraint graph to assess the effect of structure [Bessiere et al., 2005]. We did this by selecting the same constraint relation to form a path in the target network. Finally, we used a 4 × 4 Sudoku as the target network. The acquisition problem in this case was to learn the rules of Sudoku from (counter)examples of grid configurations.

As an example of a non-binary problem, we considered the Schur's lemma, which is Problem 15 from the CSPLIB4 . In this case, CONACQ used the library of ternary constraints {ALLDIFF, ALLEQUAL, NOTALLDIFF, NOTALLEQUAL}.

Results. In Table 3 we report averaged results for 100 experiments of each query generation approach on each of the problem classes we studied. In each case the initial training set contained a single positive example. In the table the first column contains a description of the target networks in terms of number of variables and constraints. We report results for each of the query generation approaches we studied. Random is a baseline approach, generating queries entirely at random, which may produce queries that are redundant with respect to each other. The Irredundant approach generates queries at random, but only uses those that can provide new information to refine the version space. Finally, Optimistic and Optimalin-expectation refer to approaches described in Section 5 and for both we consider the approximate and the closest variants. Each column is divided in two parts. The left part is the number of queries needed to converge on the target network; a limit was set 1000 queries. The right part measures the average time needed to compute a query. With the exception of very sparse random problems and Schur's Lemma, generating queries with Random is never able to converge on the target hypothesis, even with a large number of queries. The Irredundant approach is strictly better than Random and successfully converged in a number of cases. However, when the density of the target network increases, Irredundant begins to struggle to converge.

Optimistic and Optimal-in-expectation are more accurate, since they always enable us to converge, regardless of the target network used. Their closest variants require an average computation time between 2 and 5 times longer than the approximate ones, as to be expected. However, the closest strategies have the advantage of being able to converge on the target network by asking up to 40% fewer queries than the approximate strategies. Optimistic is the best approach on very sparse networks, but as the number of constraints in the target network grows, Optimal-in-expectation becomes the best strategy, since it requires both fewer queries to converge and less computation time. The number of queries for Optimal-inexpectation decreases when density increases because redundancy rules apply more frequently, deriving more constraints. Despite this, Optimistic performance decays when density increases because the probability that a query is classified negative (unlucky case) grows with density.

Related Work

Recently, researchers have become interested in techniques that can be used to acquire constraint networks in situations where a precise statement of the constraints of the problem is not available [START_REF] Freuder | [END_REF][START_REF] Rossi | [END_REF]. The use of version space learning [Mitchell, 1982] as a basis for constraint acquisition has received most attention from the constraints community [O'Connell et al., 2003], but the problem of query generation for acquiring constraint networks has not been studied.

Conclusion

In this paper we have tackled the question of how a constraint acquisition system, based on CONACQ, can help improve the interactive acquisition process by seeking fewer, but better selected, examples to be proposed as queries for classification by a user. We have provided a theoretical and empirical evaluation of query generation strategies for interactive constraint acquisition, with very positive results.

Table 2

 2

	shows

Table 2 :

 2 Optimal-in-expectation query generation strategy on Example 4.

	e	κ(e) [K]

Table 3 :

 3 Comparison of the various queries generation approaches on different classes of problems. Time is measured in milliseconds on a Pentium IV 1.8 GHz processor. We highlight the smallest number of queries for each problem class in bold.

			Random		Irredundant		Optimistic			Optimal-in-expectation
	Target Network					approximate	closest	approximate	closest
	|X|	| C|	#q	time	#q	time	#q	time	#q	time	#q	time	#q	time
							Random Binary Problem
	14	1	48	1	36	1	24	19	24	46	106	12	99	57
	14	2	118	1	71	1	55	87	50	204	102	13	97	58
	14	4	> 1000	1	729	1	101	237	94	573	81	19	75	63
	14	14	> 1000	1	> 1000	1	235	412	219	918	72	23	58	67
	14	40	> 1000	1	> 1000	1	298	1314	273	3048	71	27	44	66
							Pattern Binary Problem
	14	14	> 1000	1	> 1000	1	220	17	197	34	42	45	32	76
								Sudoku 4 × 4
	16	72	> 1000	1	> 1000	1	178	154	168	186	69	31	57	82
								Schur's lemma
	6	6	88	1	27	1	21	167	19	382	24	198	23	432
	8	1 2	298	1	66	1	56	274	51	772	46	218	44	563

Available from: http://www.sat4j.org.

Available from: http://choco.sourceforge.net.

Available from: http://www.csplib.org.IJCAI-07

Acknowledgments

The authors would like to thank Frederic Koriche for very useful discussions and comments. This work has received support from Science Foundation Ireland under Grant 00/PI.1/C075.