Over recent decades, it has been asserted that the essence of developmental learning processes is change through learning. However, capturing the essence of change in learning processes remains an open question. To study learning processes, we take up a maze problem and conduct an experiment in which a participant draws a route for the maze problem over 10 sessions. To understand how a participant learns to draw a route, we draw learning curves by plotting, for each session, the number of mazes for which a participant succeeds in drawing correct routes. To analyze the learning process, we introduce a new metric called behaviour-based entropy, which quantifies the extent of how intensively a participant is devoted to drawing a route. A crucial finding is that substantial improvement in performance is preceded by a few sessions (plateau) during which the behaviour-based entropy is quite high. We run a program that simulates drawing of routes, and thereby obtain a learning curve based on the simulation. The resultant learning curves turn out to coincide roughly with the corresponding learning curves based on the experiment, which demonstrates the plausibility of the computational model for the simulation.

Halide is a domain-specific language for image processing on CPUs and GPUs. The language is powerful for image processing with deep pipeline, e.g., guided image filtering. The guided image filtering is utilized for various applications. Some papers implement the filter on hardware; however, the implementing hardware and the purposes are different. Hardware implementation is hard; therefore, compiler supports are necessary. We utilize Halide with extended FPGA backend, called GENESIS. In our experiment, Halide code with CPU/FPGA backend is faster than the optimized C++. Also, the code length of the C++ and Halide for CPU/FPGA is 575, 141, 139 lines, respectively.

In this paper, we investigate the lower bound on the number of gates in a Boolean circuit that computes the clique function with a limited number of negation gates. To derive strong lower bounds on the size of such a circuit we develop a new approach by combining three approaches: the restriction applied to constant depth circuits due to Håstad, the approximation method applied to monotone circuits due to Razborov, and the boundary covering developed in the present paper. We prove that if a circuit C with at most $\floor{(1/6) \log \log m}$ negation gates detects cliques of size $(\log m)^{3(\log m)^{1/2}}$ in a graph with m vertices, then C contains at least $2^{(1/5)(\log m)^{(\log m)^{1/2}}}$ gates. No nontrivial lower bounds on the size of such circuits were previously known, even if we restrict the number of negation gates to be a constant. Moreover, it follows from a result of Fischer [{\it Lect. Notes Comput. Sci.,} 33 (1974), pp. 71--82] that ifone can improve the number of negation gates from $\floor{(1/6)\log\log m}$ to $\floor{2\log m}$ in the statement, then we have P $\neq$ NP. We also show that the problem of lower bounding the negation-limited circuit complexity can be reduced to the one of lower bounding the maximum of the monotone circuit complexity of the functions in a certain class of monotone functions.

Developing certain techniques for the approximation method, we establish precise versions of the following statements concerning lower bounds for circuits that detect cliques of size s in a graph with m vertices: For $5 \leq s \leq m/4$, a monotone circuit computing CLIQUE$(m,s)$ contains at least $(1/2)1.8^{\min(\sqrt{s-1}/2, m/(4s))}$ gates: If a nonmonotone circuit computes CLIQUE using a "small" amount of negation, then the circuit contains an exponential number of gates. The former is proved by using so-called bottleneck counting argument within the framework of approximation, and the latter is verified by introducing a notion of restricting negation in circuits and generalizing these arguments to nonmonotone cases.

Developing some techniques for the approximation method, we establish precise versions of the following statements concerning lower bounds for circuits that detect cliques of size s in a graph with m vertices. For 5/spl les/s/spl les/m/4, a monotone circuit computing CLIQUE(m, s) contains at least (1/2) 1.8/sup min(/spl radic/s-1/2,m/(4s))/ gates. If a non-monotone circuit computes CLIQUE using a "small" amount of negation, then the circuit contains an exponential number of gates. The former is proved very simply using so called bottleneck counting argument within the framework of approximation, whereas the latter is verified introducing a notion of restricting negation and generalizing the sunflower contraction.

A classifier with n inputs is a comparator network that classifies a set of n values into two classes with the same number of values in such a way that each value in one class is at least as large as all of those in the other. Based on the utilization of expanders, Pippenger constructed classifiers with n inputs whose size is asymptotic to $2n\log _2 n$. In the same spirit, we obtain a relatively simple method of constructing classifiers of depth $O(\log n)$. Consequently, for an arbitrary constant $C > {3 / {\log _2 3 = 1.8927}} \ldots $, we construct classifiers of depth $O(\log n)$ and of size at most $Cn\log _2 n + O(n)$.

Algorithms for learning feasibly Boolean functions from examples are explored.A class of as a hyp ot, hesis class, it, remains open whether it is properly learnable under distribution free setting. 1

Based on the uniform distribution PAC learning model, the learnability for monotone disjunctive normal form formulas with at most $O(\log n)$ terms ( $O(\log n)$ -term MDNF) is investigated.Using the technique of restriction, an algorithm that learns $O(\log n)$ -term MDNF in polynomial time is given.

In the framework of PAC-learning model, relationships between learning processes and information compressing processes are investigated.Information compressing processes are formulated as weak Occam algorithms.A weak Occarn algorithm is a deterministic polynomial time aJgorit hm that, when given m examples of unknown function, outputs, with high probability, a representation of a function that is consistent with the examples and belongs to a function class with complexity o(m).It has been shown that a weak Occam algorithm is also a consistent PAC-learning algorithm.In this extended abstract, it is shown that the converse does not hold by giving a PAClearning algorithm that is not a weak Occarn algorithm.and also some natural properties, caUed cowervativene.w and monotonicity, for learning algorithms that might help the converse hold are given.In particular, the conditions that make a conservative PAC-learning algorithm a weak Occam algorithm are given, and it is shown that, under some natural conditions, a monotone PAC-learning algorithm for a hypothesis class can be transformed to a weak Occam algorithm without changing the hypothesis class.

Valiant introduced a new computational model of concept learning by examples, gave the definition of learnability of classes of Boolean functions, and derived algorithms for learning specific classes of Boolean functions. Using his model as a base, the authors show that the class of Boolean functions expressed by monotone disjunctive normal form formulae with at most a fixed number of monomials and the class of Boolean threshold functions are polynomial time learnable when the examples are generated according to the uniform distribution.

Let f be a Boolean function from $\{0,1\}^n$ to $\{0,1\}$. The amplification function $A_f $ of f from $[0,1]$ to $[0,1]$ is defined as $A_f (p) = \Pr [f({\bf X}_1 , \cdots ,{\bf X}_n ) = 1]$, where ${\bf X}_1 , \cdots ,{\bf X}_n $ are independent random variables with $\Pr [X_i = 1] = p$ for $1 \leqq i \leqq n$. f is said to amplify $(p,q)$ to $(p',q')$ if and only if $A_f (p) \leqq p'$ and $A_f (q) \geqq q'$. Let $\Sigma _d \cup \Pi _d $ be a family of monotone Boolean formulae with alternating d levels of AND gates and OR gates each having the same number of fan-ins. A Boolean formula is said to be read once when each variable in the formula occurs at most once. In this paper it is proven that the size of monotone read-once formulae in $\Sigma _d \cup \Pi _d $ that amplify $(p,p + 1 / m)$ to $(p',p' + 1 / c)$ is $\exp (\theta ((d - m)(m / c)^{1 / (d - 1)} ))$ under certain conditions.

We present a new complexity measure for Boolean functions based on partitions of combinatorial circuits into subcircuits, and give upper and lower bounds on the complexity for Boolean functions. Roughly speaking, for a function g whose range is the set of positive integers, g(n)-partition of a circuit is a partition of a circuit into subcircuits such that. 1) each subcircuit has at most g(n) output gates, through which gates in the subcircuit are connected to gates in another succeeding subcircuits and 2) each subcircuit has at most two preceding subcircuits where subcircuit N1 (N2) is said to precede (succeed) subcircuit N2 (N1) when there is a line directed from a gate in N1 to a gate in N2. Our main result, which is stated in terms of a lower bound theorem and an upper bound theorem, is a precise version of the following statement: For "almost all" n-argument Boolean functions fn, the minimum nu mber of subcircuits over g n)-partition of a circuit to compute fn is given as (2n/g(n)22g(n)) unless g(n) grows much more slowly than n as n increases. To prove the theorems, we regard a Boolean circuit, together with g(n)-partition of it, as the multivalued circuit composed of multivalued gates corresponding to the subcircuits obtained from the g(n)-partition.

A bipartite graph Gn = (U, V, E) is said an (n, k, d) expander if |U| = |V| = n, |E| ≤ kn, and for any X s U, |GGn(X)| ≥ (1+d(1-|X|/n)) |X|, where GGn(X) is the set of nodes in V connected to nodes in X with edges in E. In this paper we show that the problem of estimating the coefficient d of a bipartite graph is reduced to that of estimating the eigenvalue of a matrix related to the graph. As a result we give an explicit construction of (n, 5, 1 - 5/8 √2) expanders. By applying Gabber and Galil's construction to these expanders we obtain n-superconcentrators with 248n edges.

The flexible network is a network composed of flexible logical multivalued cells which can be adjusted at will to perform any functions. The network is assumed to have a fixed interconnection pattern and to have a fixed-input variable assignment. We have already investigated the necessary and sufficient range of flexibility of the cell's function to obtain all the output functions the network could realize. Let the network be composed of p cells and let the necesary and sufficient flexibility range of the 1th cell be denoted by φζ for ζ = 1,...,p It is shown that although the range of flexibility of the whole network φ1X ... X φpis sufficient for the network, as a whole, to produce all the output functions the network could realize, the above range is not necessary in general. Finally we derive a sufficient condition for the proposition that the range of logical flexibility of the network, φ1X ...φp, is critical. This gives a relationship between the range of logical flexibility obtained by considering a cell in the network and the one obtained by considering the whole network.

The flexible network is a network composed of flexible logical multivalued cells that can be adjusted at will to perform any functions. The network is assumed to have a fixed-interconnection pattern and to have a fixed-input variable assignment. The following question is answered. What is the necessary and sufficient range of the flexibility of the cells' functions to obtain all the output functions the circuit could realize? Furthermore, the relation between the cells functions that realize the same output functions is derived and the number of different realizable output functions is counted.