Reconstructing Negative Survey with Least Squares Criterion

Inspired by artificial immune system, negative survey is a cost-effective privacy protection method for multiple choice question-answering with the advantage of decentralization. Present reconstruction methods for negative surveys can obtain positive survey without negative values and achieve high efficiency, but one important assumption is each negative category owns an equal chance of being selected. However, there are many situations where each negative category is selected with predefined probability. In this case, the current methods are difficult to reconstruct positive surveys. In this paper, we propose to extend current reconstruction methods to estimate positive surveys from negative surveys, in which each negative category is selected with any given probability. Our new method is to construct a system of contradictory equations and find the nonnegative least square solutions. We show that in many cases, can not only obtain positive survey without negative values, but also suitable for single choice negative survey in which each negative category is selected with any given probability. Experimental results show that this effective method can return non-negative values and have a smaller squared error.